= Solution
Write the input <word over an alphabet> as $w=a_1\cdots a_n$. Starting with $z_0=\gamma$, obtain $z_i$ from $z_{i-1}$ by <linear-time multiplication in an automatic structure> with $a_i$. <Mathematical induction> gives
$$
z_i\in L,\qquad \overline{z_i}=a_1\cdots a_i,
\qquad |z_i|\leq|\gamma|+iN.
$$
The <time complexity> of step $i$ is at most a constant times $|\gamma|+(i-1)N+1$. Summing the costs gives
$$
T(w)\leq C\sum_{i=1}^n\bigl(|\gamma|+(i-1)N+1\bigr)
=C\left(n(|\gamma|+1)+\frac{Nn(n-1)}2\right).
$$
The <automatic structure for a group>, $N$ and $\gamma$ are fixed, so \b[the required representative is]
$$
\boxed{z=z_n,\qquad \overline z=\overline w,\qquad
|z|\leq |\gamma|+nN,\qquad T(w)=O(n^2)\ (n\geq1).}
$$
For the <empty word>, return $\gamma$ in constant time.
Back to article page
