Automatic group

Remarks

Equivalently, $G$ is automatic if there is a regular language $L$ over $A$ mapping onto $G$ with the fellow traveller property. This means there is a constant $k$ such that whenever $u, v \in L$ and $\bar u^{-1} \bar v \in A \cup \set{e}$, the prefixes $u(t)$ and $v(t)$ of length $t$ satisfy $d_A(\overline{u(t)}, \overline{v(t)}) \le k$ for all $t$, in the word metric.

Example: $G = \Z^2 = \langle a, b \rangle$ with $A = \set{a, a^{-1}, b, b^{-1}}$ and $L$ the set of words $a^m b^n$, $m, n \in \Z$, which is regular. Two such words naming elements that differ by one generator differ by one in the exponent of $a$ or of $b$. Their prefixes stay at distance at most $2$, so $L$ has the fellow traveller property.

Non-example: the integer Heisenberg group is not automatic. It is finitely presented, but its Dehn function grows like $n^3$, while every automatic group satisfies a quadratic isoperimetric inequality.

Being automatic does not depend on the choice of the finite generating set.