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.^[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 word-acceptor, which accepts for every element of G at least one word in ${\displaystyle A^{\ast }}$ representing it;
• multipliers, one for each ${\displaystyle a\in A\cup \{1\}}$, which accept a pair (w₁, w₂), for words w_i accepted by the word-acceptor, precisely when ${\displaystyle w_{1}a=w_{2}}$ in G.

The property of being automatic does not depend on the set of generators.^[3]