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 whether a given word representation of a group element is in a "canonical form" and can tell whether two elements given in canonical words differ by a generator.^[1]

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:^[2]

the word-acceptor, which accepts for every element of G at least one word in $A^{\ast }$ 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.^[3]

^ Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. (1992), Word Processing in Groups, Boston, MA: Jones and Bartlett Publishers, ISBN 0-86720-244-0.
^ Epstein et al. (1992), Section 2.3, "Automatic Groups: Definition", pp. 45–51.
^ Epstein et al. (1992), Section 2.4, "Invariance under Change of Generators", pp. 52–55.

[1] Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. (1992), Word Processing in Groups, Boston, MA: Jones and Bartlett Publishers, ISBN 0-86720-244-0.

[2] Epstein et al. (1992), Section 2.3, "Automatic Groups: Definition", pp. 45–51.

[3] Epstein et al. (1992), Section 2.4, "Invariance under Change of Generators", pp. 52–55.

[1]

[2]

[3]