Modifying the definition of iso/automorphism of a formal language string found in Eugene Luk's and Laszlo Babai's works...

Question

Reference article: https://jeremykun.com/tag/automorphism-groups/

In Eugene Luk's and Laszlo Babai's work on the graph isomorphism problem, they rely fundamentally on isomorphisms of strings. But they merely define an isomorphism of two equal-length strings $x,y$ to be a permutation $\sigma \in S_{|x|}$ such that $x_{\sigma (i)} = y_i$, where $x = x_1 \cdots x_n$ sim $y$.

I would like a definition that also incorperates alphabetical changes (permutations?). So for instance $x = abcdefabc$ has the automorphism sending $a \mapsto d$ and at the same time maps the index where $a$ resides to the index where $d$ resides. So that $(a,d)$ "together with" $(1,4)$ forms a basic example of an automorphism of $x$.

So what construction of group theory would accomplish this in terms of strings?

The point is that $abc$ and $def$ are isomorphic as strings, but $abc$ and $dee$ are not. I'm not sure how this works group theoretically.

Answer 1

Note that in the string automorphism problem, we're allowed to specify any group $G$ acting on our strings, not just the symmetric group, and ask: is there an element of $G$ that takes one string to the other?

To take advantage of this, if our alphabet has $n$ letters, replace the $i^{\text{th}}$ letter by a block $00\dots 1 \dots 00$ of length $n$, where the $i^{\text{th}}$ symbol is $1$ and the rest are $0$. For example, if the alphabet is $(a,b,c)$ and $n=3$, the string $abacab$ would be represented as $100\,010\,100\,001\,100\,010$.

Now let $G$ be the permutation group generated by the following permutations:

1. Swap the $i^{\text{th}}$ and $j^{\text{th}}$ block entirely, for some $i$ and $j$.
2. In every block, swap the $i^{\text{th}}$ and $j^{\text{th}}$ symbol.

For example, we can swap the $3^{\text{rd}}$ and $6^{\text{th}}$ blocks in $100\,010\,100\,001\,100\,010$ to get $100\,010\,010\,001\,100\,100$, which corresponds to $abbcaa$; this is the ordinary permutation of strings we were already allowed. (If we wanted only some permutations of our strings, then we can limit the type-1 permutations to only the ones we like.)

We can also swap the $2^{\text{nd}}$ and $3^{\text{rd}}$ symbol in every block, turning $100\,010\,100\,001\,100\,010$ into $100\,001\,100\,010\,100\,001$; back in Letterland, this corresponds to turning $abacab$ into $acabac$, or swapping $b$ with $c$. In general, swapping the $i^{\text{th}}$ and $j^{\text{th}}$ symbol in every block is equivalent to swapping the $i^{\text{th}}$ and $j^{\text{th}}$ letter in our alphabet.