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, i. e. 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.[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 property of being automatic does not depend on the set of generators.[3]

The concept of automatic groups generalizes naturally to automatic semigroups.[4]

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 are equal.[5]

Examples of automatic groups

The automatic groups include:

Examples of non-automatic groups

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.[7]

Examples include:

Automatic structures

The idea of describing algebraic structures with finite-automata can be generalized from groups to other structures.[9]

References

  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.
  4. Epstein et al. (1992), Section 6.1, "Semigroups and Specialized Axioms", pp. 114–116.
  5. Epstein et al. (1992), Theorem 2.3.10, p. 50.
  6. Brink and Howlett (1993), "A finiteness property and an automatic structure for Coxeter groups", Mathematische Annalen (Springer Berlin / Heidelberg), doi:10.1007/bf01445101, ISSN 0025-5831.
  7. Birget, Jean-Camille (2000), Algorithmic problems in groups and semigroups, Trends in mathematics, Birkhäuser, p. 82, ISBN 0-8176-4130-0
  8. 1 2 Charney, Ruth (1992), "Artin groups of finite type are biautomatic", Mathematische Annalen 292: 671–683, doi:10.1007/BF01444642
  9. Khoussainov, Bakhadyr; Rubin, Sasha (2002), Some Thoughts On Automatic Structures, CiteSeerX: 10.1.1.7.3913

Additional reading

This article is issued from Wikipedia - version of the Saturday, October 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.