↑ arvau

Wikipedia / 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.

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 representing it;

  • multipliers, which accept a pair (w1,w2), for words wi in G.

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

Properties

Automatic groups have word problem).

Automatic groups are characterized by the fellow traveler property.. Then, G is automatic with respect to a word acceptor L which differ by at most one generator, the distance between the respective prefixes of u and v is bounded by C). This means that when reading the words synchronously, it is possible to keep track of the difference between both elements with a finite number of states (the neighborhood of the identity with diameter C in the Cayley graph).

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.

Examples include:

Automatic structures

The idea of describing algebraic structures with finite-automata can be generalized from groups to other structures. For instance, it generalizes naturally to automatic semigroups.

References

Further reading

  • .