Automatic group#Biautomatic groups

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.

{{citation

| last1 = Epstein | first1 = David B. A. | authorlink1 = David B. A. Epstein

| last2 = Cannon | first2 = James W. | authorlink2 = James W. Cannon

| last3 = Holt | first3 = Derek F.

| last4 = Levy | first4 = Silvio V. F.

| last5 = Paterson | first5 = Michael S. | authorlink5 = Mike Paterson

| last6 = Thurston | first6 = William P. | authorlink6 = William Thurston

| title = Word Processing in Groups | title-link = Word Processing in Groups

| publisher = Jones and Bartlett Publishers | location = Boston, MA | year = 1992 | isbn = 0-86720-244-0}}.

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:{{harvtxt|Epstein|Cannon|Holt|Levy|1992}}, Section 2.3, "Automatic Groups: Definition", pp. 45–51.

the word-acceptor, which accepts for every element of G at least one word in $A^\ast$ representing it;
multipliers, one for each $a \in A \cup \{1\}$ , which accept a pair (w₁, w₂), for words w_i accepted by the word-acceptor, precisely when $w_1 a = w_2$ in G.

The property of being automatic does not depend on the set of generators.{{harvtxt|Epstein|Cannon|Holt|Levy|1992}}, Section 2.4, "Invariance under Change of Generators", pp. 52–55.

Properties

Automatic groups have word problem solvable in quadratic time. More strongly, a given word can actually be put into canonical form in quadratic time, based on which the word problem may be solved by testing whether the canonical forms of two words represent the same element (using the multiplier for $a = 1$ ).{{harvtxt|Epstein|Cannon|Holt|Levy|1992}}, Theorem 2.3.10, p. 50.

Automatic groups are characterized by the fellow traveler property.

{{citation

| last1 = Campbell | first1 = Colin M.

| last2 = Robertson | first2 = Edmund F.

| last3 = Ruskuc | first3 = Nik

| last4 = Thomas | first4 = Richard M.

| title = Automatic semigroups

| journal = Theoretical Computer Science

| volume = 250 | year = 2001 | issue = 1–2 | pages = 365–391

| url = https://core.ac.uk/download/pdf/82399070.pdf

| doi = 10.1016/S0304-3975(99)00151-6| doi-access = free

}} Let $d(x,y)$ denote the distance between $x, y \in G$ in the Cayley graph of $G$ . Then, G is automatic with respect to a word acceptor L if and only if there is a constant $C \in \mathbb{N}$ such that for all words $u, v \in L$ which differ by at most one generator, the distance between the respective prefixes of u and v is bounded by C. In other words, $\forall u, v \in L, d(u,v) \leq 1 \Rightarrow \forall k \in \mathbb{N}, d(u_{|k},v_{|k}) \leq C$ where $w_{|k}$ for the k-th prefix of $w$ (or $w$ itself if $k > |w|$ ). 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:

Finite groups. To see this take the regular language to be the set of all words in the finite group.
Euclidean groups
All finitely generated Coxeter groups{{Citation | last = Brink and Howlett | title = A finiteness property and an automatic structure for Coxeter groups | year = 1993 | journal = Mathematische Annalen | volume = 296 | pages = 179–190 | publisher = Springer Berlin / Heidelberg | issn= 0025-5831 | postscript = .| doi = 10.1007/bf01445101 | s2cid = 122177473 }}
Geometrically finite groups

Examples of non-automatic groups

Baumslag–Solitar groups
Non-Euclidean nilpotent groups
Not every CAT(0) group is biautomatic{{cite journal |last1=Leary |first1=I. J. |last2=Minasyan |first2=Ashot |title=Commensurating HNN extensions: nonpositive curvature and biautomaticity |journal=Geom. Topol. |date=2021 |volume=25 |pages=1819-1860 |doi=10.2140/gt.2021.25.1819}}{{cite journal |last1=Hughes |first1=Sam |last2=Valiunas |first2=Motiejus |title=Commensurating HNN-extensions: Hierarchical hyperbolicity and biautomaticity |journal=Comment. Math. Helv. |date=2024 |volume=99 |issue=2 |pages=397–436 |doi=10.4171/CMH/572|arxiv=2203.11996 }}

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.{{citation | title=Algorithmic problems in groups and semigroups | series=Trends in mathematics | first=Jean-Camille | last=Birget | publisher=Birkhäuser | year=2000 | isbn=0-8176-4130-0 | page=82}}

Examples include:

Hyperbolic groups.{{citation | last=Charney | first=Ruth |authorlink=Ruth Charney| title=Artin groups of finite type are biautomatic | journal=Mathematische Annalen | volume= 292 | year=1992 | doi=10.1007/BF01444642 | pages=671–683| s2cid=120654588 }}
Any Artin group of finite type, including braid groups.

Automatic structures

The idea of describing algebraic structures with finite-automata can be generalized from groups to other structures.{{citation | title = Some Thoughts On Automatic Structures | citeseerx = 10.1.1.7.3913 | first1 = Bakhadyr | last1 = Khoussainov | first2 = Sasha | last2 = Rubin | year = 2002 }} For instance, it generalizes naturally to automatic semigroups.{{harvtxt|Epstein|Cannon|Holt|Levy|1992}}, Section 6.1, "Semigroups and Specialized Axioms", pp. 114–116.