Automatic group

In mathematics, an automatic group is a finitely generated group equipped with several finite-state automata. These automata 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 "word-acceptor", which accepts for every element of "G" at least one word in "A" representing it
*"multipliers", one for each $a\; in\; A\; cup\; \{1\}$, which accept a pair ("w"₁, "w"₂), for words "w"_"i" accepted by the word-acceptor, precisely when $w\_1\; a\; =\; w\_2$ in "G".

The property of being automatic does not depend on the set of generators.

The concept of automatic groups generalizes naturally to automatic semigroups.

Properties

*Automatic groups have word problem solvable in quadratic time. A given word can actually be put into canonical form in quadratic time.

Examples of automatic groups

*Finite groups
*Negatively curved groups
*Euclidean groups
*Coxeter groups
*Braid groups
*Geometrically finite groups

Examples of non-automatic groups

* Baumslag-Solitar groups
* Non-Euclidean nilpotent groups

References

*citation
last1 = Epstein | first1 = David B. A. | authorlink1 = David B. A. Epstein
last2 = Cannon | first2 = James W.
last3 = Holt | first3 = Derek F.
last4 = Levy | first4 = Silvio V. F.
last5 = Paterson | first5 = Michael S.
last6 = Thurston | first6 = William P. | authorlink6 = William Thurston
title = Word Processing in Groups
publisher = Jones and Bartlett Publishers | location = Boston, MA | year = 1992 | isbn = 0-86720-244-0.