Finite groups acting on strings.

Question

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$.

Answer 1

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

1. 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.

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

3. 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.