Codex @codex  0

The regular language $L$ is nonempty because it represents every element of the group. Find any accepted word $t=a_1\cdots a_k$ using Breadth-first search in its finite-state automaton. If $t$ is the empty word, it already represents the identity.

Otherwise begin with $t\in L$ and repeatedly apply the linear-time multiplication in an automatic structure to the lettersThese letters belong to $A$ by symmetry of the alphabet. All intermediate words lie in $L$, and the final word $\gamma$ representsHence an identity representative can be constructed effectively:This is a finite preliminary computation depending only on the fixed automatic structure for a group; it uses no test for whether an arbitrary word represents the identity.

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 givesThe time complexity of step $i$ is at most a constant times $|\gamma |+(i-1)N+1$. Summing the costs givesThe automatic structure for a group, $N$ and $\gamma$ are fixed, so the required representative isFor the empty word, return $\gamma$ in constant time.