Automatic group

From Wikipedia, the free encyclopedia

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 , which accept a pair (w₁, w₂), for words w_i accepted by the word-acceptor, precisely when w₁a = w₂ 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.

[edit] Properties

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

[edit] Examples of automatic groups

• Finite groups, to see this take the regular language to be the set of all words in the finite group.
• Negatively curved groups
• Euclidean groups
• All finitely generated Coxeter groups ^[1]
• Braid groups
• Geometrically finite groups

[edit] Examples of non-automatic groups

• Baumslag-Solitar groups
• Non-Euclidean nilpotent groups

[edit] References

1. ^ Brink and Howlett (1993). "A finiteness property and an automatic structure for Coxeter groups". Mathematische Annalen (Springer Berlin / Heidelberg). ISSN 0025-5831. 

• 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 .
• Chiswell, Ian (2008), A Course in Formal Languages, Automata and Groups, Springer, ISBN 978-1-84800-939-4 .