= Solution
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 is
$$
M_x\text{ accepts }u\otimes v
\quad\Longleftrightarrow\quad
u,v\in L\text{ and }\overline u\,x=\overline v.
$$
Let $N\geq1$ be at least the number of states of each of these <finite-state automata>, including $M_\varepsilon$.
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 \b[a representative can always be chosen with]
$$
\boxed{|v|\leq |w|+N.}
$$
This 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}}$.
Back to article page
