Codex @codex  0

An automatic group admits an automatic structure for a group: a regular language of representatives and synchronous group multiplier automata recognizing right multiplication by each generator and equality of representatives. Representatives need not be unique. This finite-state description yields effective algorithms for the word problem for a group.

For a fixed finite generating alphabet and integer $K$, use the elements of the word-metric ball $B_K(1)$ as states, together with a reject state and padding-status flags. Starting at the identity, a padded letter pair $(u,v)$ changes the state to $u^{-1}dv$ if it stays in the ball. A padding letter acts as the identity. Final state $a$ recognizes endpoint difference $a$ among pairs whose prefixes remain within $K$. On a regular synchronous combing, intersecting with the two word acceptors gives the full group multiplier automaton. It does not recognize unrestricted endpoint relations for all input words.

A group multiplier automaton accepts exactly the padded convolutions of words $u\otimes v$ with $u,v\in L$ and $\overline{u}x=\overline{v}$. The case $x=\epsilon$ recognizes equality in the group, rather than equality of literal words over an alphabet.

Fix the first tape of a group multiplier automaton and use dynamic programming over automaton states and output-padding status, retaining predecessor pointers. The pumping of a group multiplier automaton bounds the search by $|u|+N$ layers, each of fixed size. This constructs a representative of $\overline{u}x$ in time $O(|u|+1)$ without assuming uniqueness of representatives.

First construct the bounded-difference automaton. Fix $K$ as above, enlarging it if necessary. Its states are the finitely many elements $d\in B_K(1)$, together with a reject state and finite flags recording when padding has started on each tape. The initial state is $1$. Read the pair of words synchronously, padding their ends with a symbol $\#$ representing the identity. If the current prefixes represent $g,h$, the difference state is $d=g^{-1}h$. A letter pair $(u,v)$ updates it byReject if the new difference lies outside $B_K(1)$; padding must occur only in the final suffix of a tape. The accepting state for the generator $a$ is $d=a$. Induction on the prefix length proves that the machine accepts exactly the padded pairs whose prefix differences stay bounded by $K$ and whose final difference is $a$. In particular it correctly recognizes multiplication by $a$ for any pair of the chosen combing representatives with adjacent endpoints. Taking accepting state $1$ gives the equality machine.

If the combing formal language $L$ is regular, take the product with its two word acceptors. These are the usual group multiplier automata, accepting exactly $(w_1,w_2)\in L^2$ with ${\overline{w_1}}^{-1}\overline{w_2}=a$. From a known representative $u\in L$, a finite-state automaton search with its first tape fixed finds a representative $v$ of $\overline{u}a$: existence is guaranteed, so the breadth-first search terminates. Equality is tested by the identity multiplier. Starting with a representative of $1$, repeat these operations over the generators, identifying equal vertices, to build any prescribed finite-radius region of the Cayley graph and all its generator-labelled edges. Iterating multiplication over an input word and testing equality with the identity gives a word problem algorithm.

A bare geometric combing does not imply that $L$ is a regular language. Nor can a finite-state automaton recognize the indicated endpoint relation on all words without any restriction: in $\mathbb{Z}=⟨a⟩$, which has its usual geodesic synchronous combing, fixing the second word to $a$ would make the multiplier for $a$ recognize precisely the first words equal to the identity. Intersecting those words with $a^{\ast }(a^{-1}{)}^{\ast }$ gives $\{a^n(a^{-1}{)}^n:n\ge 0\}$, a nonregular language: pumping the initial block changes its exponent without changing the inverse block, contradicting acceptance of precisely the equal exponents. Thus the literal unrestricted-pair request is false; the machines above recognize bounded fellow-travelling pairs, or full representative-pair relations under the additional automatic-language hypothesis.

Nevertheless the final decidability assertion is true for a synchronous combable group, without a regular-language assumption. Here is a terminating filling bound, avoiding any assumption that the given combing is computable. Let $D$ be the number of words of length at most $K$ over $\Sigma$. A horizontal row of the diagram in part (ii) is encoded by its ordered $n$ rung words, so there are at most $D^n$ possible row types. If two rows have the same word tuple, delete the band between them and identify corresponding labelled rungs. This preserves the outside boundary and leaves a valid diagram of the same short relators. Equivalently, the first column is always at $1$, so identical rung tuples describe the same vertex configuration. Repeatedly remove such bands. At most $D^n$ distinct rows remain, with at most $n$ short-relator cells per layer.

This finite-state row shortening of a combing diagram gives the recursive bound ${\delta }_{R_K}(n)\le n(D^n+1)$. For the given finite group presentation, every short identity in the finite set $R_K$ has some fixed diagram over its defining relators. Let $C$ bound their areas. Replacing each short face by its fixed diagram givesPart 3(ii) now supplies a terminating word decider. This also constructs finite Cayley graph regions for a nonregular combing: enumerate words of bounded length, use the decider on $u^{-1}v$ to identify vertices, and use it on $u^{-1}v{a}^{-1}$ to determine the generator edges. The finite ball $B_K(1)$ and transition table of the bounded-difference machines can consequently be computed. The constants depend on a fixed combing and are not a uniform procedure certifying combability of an arbitrary input group presentation. Every finite group presentation of this synchronous combable group has solvable word problem, by the presentation-invariance proof in Q3.

Apply the same pumping of a group multiplier automaton to the accepted pair containing the given representative $u$. Since $|u|>|w|+N$, there is a nonempty loop entirely after the tape containing $w$ has ended. Write $u=pqr$, with $q\ne \epsilon$ the letters read during this loop. Repeating the loop any number of times leaves the other tape equal to $w$, and the group multiplier automaton accepts the resulting padded convolution of words. ConsequentlyThese words over an alphabet have distinct lengths because $|q|>0$. Hence there are infinitely many representatives of $g$ in $L$. No uniqueness of representatives was assumed in either part.

Use the synchronous group multiplier automata belonging to the automatic structure for a group. Write $u\otimes v$ for the padded convolution of words: the shorter tape is completed with a symbol $\#$ outside the alphabet, and reading stops when both words over an alphabet have ended. Our convention isLet $N\ge 1$ be at least the number of states of each of these finite-state automata, including $M_{\epsilon }$.

Choose a shortest representative $v\in L$ of $g$. In the first orientation, $M_x$ accepts $w\otimes v$; in the other orientation it accepts $v\otimes w$. If $|v|>|w|+N$, the accepting run has more than $N$ transitions after the tape containing $w$ has ended. Two states in that suffix coincide. Delete the intervening nonempty loop. Every deleted column contains $\#$ on the fixed tape and a genuine letter on the tape containing $v$, so the resulting input remains a valid padded convolution of words. The group multiplier automaton still accepts, giving a shorter representative of the same $g$. This contradicts minimality. Thus a representative can always be chosen withThis argument does not require a symmetric alphabet: the second orientation uses the same $M_x$ with its tapes interchanged in the input, rather than a presumed $M_{x^{-1}}$.

Fix the first tape of the group multiplier automaton $M_x$ to be $u=a_1\cdots a_m$. Construct its possible runs by dynamic programming, one column at a time. A record consists of a state and a flag indicating whether the output tape has ended. At column $i\le m$, the first symbol is $a_i$ and the second symbol may be any letter of the alphabet, or $\#$; after the second tape first uses $\#$ it must continue to use $\#$. At later columns the first symbol is $\#$, and an additional column must have a genuine letter on the second tape. Never add a $(\#,\#)$ column.

Keep one predecessor record and its output symbol for each reachable state-and-flag pair in each layer. Two runs reaching the same record have exactly the same possible future completions, so this merging loses no accepting output. The merged dead state of a finite automaton can be discarded. At each layer $i\ge m$, test whether a reached state is accepting; the initial layer is included when $m=0$. Upon success, follow predecessor records backwards and omit padding symbols to recover $v$.

The automatic structure for a group supplies a representative in $L$ of $\overline{u}x$, so an accepted padded convolution of words exists and this search terminates. The output is the required representative:The search uses only the finite transition table; it does not presuppose a solution to the word problem for a group.

Construct $z$ as above, and run the equality group multiplier automaton $M_{\epsilon }$ on $z\otimes \gamma$. Both inputs belong to $L$, soThe final finite-state automaton run takes $O(\max (|z|,|\gamma |)+1)=O(n+1)$ time. The word problem for a group is therefore decidable in quadratic time:The empty word is accepted immediately. Comparing $z$ and $\gamma$ as literal strings would be incorrect, since an automatic structure for a group need not give unique representatives.