Automatic groups have
word problem solvable in quadratic time. More strongly, a given word can actually be put into canonical form in quadratic time, based on which the word problem may be solved by testing whether the canonical forms of two words represent the same element (using the multiplier for a = 1). Automatic groups are characterized by the
fellow traveler property. Let d(x,y) denote the distance between x, y \in G in the Cayley graph of G. Then,
G is automatic with respect to a word acceptor
L if and only if there is a constant C \in \mathbb{N} such that for all words u, v \in L which differ by at most one generator, the distance between the respective prefixes of
u and
v is bounded by
C. In other words, \forall u, v \in L, d(u,v) \leq 1 \Rightarrow \forall k \in \mathbb{N}, d(u_{|k},v_{|k}) \leq C where w_{|k} for the k-th prefix of w (or w itself if k > |w|). This means that when reading the words synchronously, it is possible to keep track of the difference between both elements with a finite number of states (the neighborhood of the identity with diameter
C in the Cayley graph). == Examples of automatic groups ==