Group multiplier automaton ($M_x$)

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.

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.

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.