Kalpana Kalpana (Editor)

Automatic group

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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 ∈ A ∪ { 1 } , which accept a pair (w1, w2), for words wi 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. 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.

    Examples of automatic groups

    The automatic groups include:

  • Finite groups. To see this take the regular language to be the set of all words in the finite group.
  • Euclidean groups
  • All finitely generated Coxeter groups
  • Geometrically finite groups

    • Examples of non-automatic groups

  • Baumslag-Solitar groups
  • Non-Euclidean nilpotent 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.

    Examples include:

  • Hyperbolic groups.
  • Any Artin group of finite type including braid groups.

    • Automatic structures

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

    Additional reading

  • Chiswell, Ian (2008), A Course in Formal Languages, Automata and Groups, Springer, ISBN 978-1-84800-939-4 .

    • References

    Automatic group Wikipedia
    (Text) CC BY-SA