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.

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.