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

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]

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