Finite groups acting on strings. Let $s = abcdandsoon.. \ \in \Sigma^*$.  Let $|s| = n$ be the length of $s$.  Consider all permutations of the positioned symbols that make up $s$, such that $s$ is fixed under the permutation.  So if $s = abcdabc$.  Then the symmetry group of $s$ is generated by $\{\text{id}, (1,5), (2,6), (3,7)\}$ where the numbers indicate position in the string starting on the left at $1$.  Now let $g$ be the obvious smallest grammar for $s$, $g = \{ g_0 \to g_1 d g_1, \ \ g_1 \to abc \}$.  Its symmetry group is $\{\text{id}, (1,3)\}$ if the rhs symbols are listed in order $g_1dg_1, abc, g_2 \dots$ 
Define a set of transpositions to be a repeated substring if it looks like $(x,y), (x+1, y+1), \dots, (x+(n-1), y+(n-1))$ for some $x,y = 1\dots n$.  Now for all such $(x,y)$ in the group create a node in a graph and label it $(x,y,n)$ where $n$ is clearly the length of the repeated substring.
Clearly this approach is dead ending.  I'm trying to relate the smallest grammar problem with these symmetry groups, but failing.
Please help!
Let $g = $
$$
A \to B^6 \\
B \to bb
$$
$B$'s symmetry group is $\{1, (1,2)\}$ and $A$'s is $S_6$.
 A: This is the color automorphism problem.  In general, it appears to be difficult.  It is at least graph isomorphism hard since the problem of computing the automorphism group of a graph reduces to it.  Color automorphism is also one of the two main ingredients in the best algorithm known for graph isomorphism.  Algorithms are available for special cases.
Let $n$ be the length of the string.  We call a permutation an automorphism if it respects the string and let $\mathrm{Aut}_G(s)$ be the group of automorphisms of the string $s$ that are contained in a specified subgroup $G \leq S_n$.  Define the composition width $d$ of $G$ to be the smallest value such that every composition factor of $G$ is a subgroup of $S_d$.  There are a series of works that give progressively faster algorithms:


*

*If $d$ is constant, then $\mathrm{Aut}_G(s)$ can be computed in time $\mathrm{poly}(n)$ [1]

*$\mathrm{Aut}_G(s)$ can be computed in $n^{O(d)}$ time [2]

*$\mathrm{Aut}_G(s)$ can be computed in $n^{O(d / \log d)}$ time (uses the classification of finite simple groups) [3]


There is also a version of this problem that computes a canonical form instead of the automoprhism group.  This is NP-hard for canonical forms defined according to arbitrary orderings.  If you don't care which ordering is used then the same bounds hold (see [2]).
References


*

*Luks, Eugene M. "Isomorphism of graphs of bounded valence can be tested in polynomial time." Foundations of Computer Science, 1980., 21st Annual Symposium on. IEEE, 1980.

*Babai, László, and Eugene M. Luks. "Canonical labeling of graphs." Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983.

*Babai, László, William M. Kantor, and Eugene M. Luks. "Computational complexity and the classification of finite simple groups." Foundations of Computer Science, 1983., 24th Annual Symposium on. IEEE, 1983.
