Automatic group

In mathematics, an automatic group is a finitely generated group equipped with several finite-state automata. These automata represent the Cayley graph of the group. That is, they can tell if a given word representation of a group element is in a "canonical form" and can tell if two elements given in canonical words differ by a generator.
More precisely, let "G" be a group and "A" be a finite set of generators. Then an "automatic structure" of "G" with respect to "A" is a set of finite-state automata:
The property of being automatic does not depend on the set of generators.
Properties.
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 formula_4).
Automatic groups are characterized by the "fellow traveler property". Let formula_5 denote the distance between formula_6 in the Cayley graph of formula_7. Then, "G" is automatic with respect to a word acceptor "L" if and only if there is a constant formula_8 such that for all words formula_9 which differ by at most one generator, the distance between the respective prefixes of "u" and "v" is bounded by "C". In other words, formula_10 where formula_11 for the k-th prefix of formula_12 (or formula_12 itself if formula_14). 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.
The automatic groups include:
Biautomatic groups.
A group is biautomatic if it has two multiplier automata, for left and right multiplication by elements of the generating set, respectively. A biautomatic group is clearly automatic. 
Examples include:
Automatic structures.
The idea of describing algebraic structures with finite-automata can be generalized from groups to other structures. For instance, it generalizes naturally to automatic semigroups.