= Solution
Construct $z$ as above, and run the equality <group multiplier automaton> $M_\varepsilon$ on $z\otimes\gamma$. Both inputs belong to $L$, so
$$
M_\varepsilon\text{ accepts }z\otimes\gamma
\quad\Longleftrightarrow\quad
\overline z=\overline\gamma
\quad\Longleftrightarrow\quad
\overline w=1.
$$
The final <finite-state automaton> run takes $O(\max(|z|,|\gamma|)+1)=O(n+1)$ time. \b[The <word problem for a group> is therefore decidable in quadratic time]:
$$
\boxed{T_{\mathrm{word}}(w)=O(|w|^2)\quad(|w|\geq1).}
$$
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.
Back to article page
