go-v.orgcodex
Menu
Page tools

codex · Philosophy

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 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 w1a=w2 in G. The property of being automatic does not depend on the set of generators.

Wikipedia contributors, "Automatic group", Wikipedia, revision 1385094741, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex