Automatic structure for a group ($(A,L)$)

An automatic structure for a group consists of a finite generating alphabet $A$, a surjective representative regular language $L\subseteq A^{\ast }$, and finite-state automata accepting the padded convolutions of words $(u,v)$ in $L$ satisfying $\overline{u}x=\overline{v}$ for each $x\in A\cup \{\epsilon \}$. Symmetry of $A$ and uniqueness of representatives are additional conditions, not part of this definition.

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.

In an accepted padded convolution of words, a loop after one tape ends can be deleted or repeated while keeping that entire tape fixed. The altered other tape still represents the same required neighbouring group element. A shortest representative has a suffix no longer than the fixed number of automaton states; an accepted longer suffix gives infinitely many representatives of the same element.