Automatic Group

A finitely generated group with a regular covering language of representative words and synchronous finite-state recognition of multiplication by generators.

Version

v1 · 2026-10-03 · History

Domain-specific #

12997

Aliases

Automatic group in geometric group theory

Core Idea

An automatic group is a finitely generated group that admits a regular language of words representing every element, together with finite-state machines recognizing which accepted word pairs differ by right multiplication by a generator. The pair recognizers read the words synchronously, padding the shorter at its end. Equivalently, paths for such neighboring elements in the Cayley graph stay uniformly close at corresponding positions. The group is the object classified; a particular language and machines are its witness.

Scope of Application

Free groups and free abelian groups provide concrete witnesses, using respectively reduced words and ordered-exponent words. Automaticity does not depend on which finite generating set is chosen, although the witness can change. An automatic group is finitely presented and has a soluble word problem and a quadratic upper bound on its Dehn function; these are consequences rather than defining requirements.

Clarity

The representative language must cover all group elements but need not choose exactly one word for each in the displayed witness. Regularity alone is insufficient: the synchronous multiplier relations must also be finite-state. Decidability of word equality alone does not establish automaticity. Biautomaticity adds a left-multiplication condition; asynchronous automaticity allows paths to advance at different rates.

Manages Complexity

The infinite group can be represented using a finite word recognizer plus finite machines for local generator steps. A uniform fellow-traveller bound explains why adjacent representative paths can be compared through bounded finite-state information. This enables calculation after a witness is known; it does not guarantee that a witness can be found automatically from any presentation.

Abstract Reasoning

Choose a finite generating alphabet and regular language covering the group. For each generator and identity, test whether a finite-state machine accepts precisely the end-padded word pairs representing elements one right-multiplication step apart. In the free-group example a move appends or cancels a final generator; in the free-abelian example it shifts one lattice coordinate. Either synchronous recognizers or the equivalent uniform same-time Cayley-path bound establish the key condition.

Knowledge Transfer

For another proposed finite-state algebraic system, separate the classified object from its encoding. Ask whether the language covers all objects, whether basic operations are synchronized finite-state relations, and whether the relation is independent of one presentation choice. The proposed DAG parent is live Group; Automaton and Formal Language are witness components, not the mathematical genus.

Relationships to Other Abstractions

Current abstraction Automatic Group Domain-specific

Parents (1) — more general patterns this builds on

• Automatic Group is a kind of Group Prime

  An automatic group is a group that additionally admits a regular covering language and synchronous finite-state multipliers.

Hierarchy paths (5) — routes to 5 parentless roots

• Automatic Group → Group → Monoid → Semigroup → Set and Membership

Show alternative paths (4)

Neighborhood in Abstraction Space

Automatic Group sits in a sparse region of the domain-specific corpus (60^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Formal Sequences & Language Structure (16 abstractions)

Nearest neighbors

• Square-free word — 0.85
• Field (Algebraic) — 0.85
• Hamming Scheme — 0.85
• Cayley Graph — 0.85
• Unavoidable Pattern — 0.85

Computed from structural-signature embeddings · 2026-10-08