In
mathematics, an automatic group is a
finitely generated group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses o ...
equipped with several
finite-state automata
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
. These automata represent the
Cayley graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cay ...
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.
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
representing it;
*''multipliers'', one for each
, which accept a pair (''w''
1, ''w''
2), for words ''w''
''i'' accepted by the word-acceptor, precisely when
in ''G''.
The property of being automatic does not depend on the set of generators.
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
).
Automatic groups are characterized by the ''fellow traveler property''. Let
denote the distance between
in the Cayley graph of
. Then, ''G'' is automatic with respect to a word acceptor ''L'' if and only if there is a constant
such that for all words
which differ by at most one generator, the distance between the respective prefixes of ''u'' and ''v'' is bounded by ''C''. In other words,
where
for the k-th prefix of
(or
itself if
). 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 group
In mathematics, a Coxeter group, named after H. S. M. Coxeter, is an abstract group that admits a formal description in terms of reflections (or kaleidoscopic mirrors). Indeed, the finite Coxeter groups are precisely the finite Euclidean refle ...
s
*
Geometrically finite groups
Examples of non-automatic groups
*
Baumslag–Solitar groups
* Non-
Euclidean nilpotent group
In mathematics, specifically group theory, a nilpotent group ''G'' is a group that has an upper central series that terminates with ''G''. Equivalently, its central series is of finite length or its lower central series terminates with .
Intui ...
s
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.
Examples include:
*
Hyperbolic group
In group theory, more precisely in geometric group theory, a hyperbolic group, also known as a ''word hyperbolic group'' or ''Gromov hyperbolic group'', is a finitely generated group equipped with a word metric satisfying certain properties abstra ...
s.
* Any
Artin group of finite type, including
braid group
A braid (also referred to as a plait) is a complex structure or pattern formed by interlacing two or more strands of flexible material such as textile yarns, wire, or hair.
The simplest and most common version is a flat, solid, three-strande ...
s.
[
]
Automatic structures
The idea of describing algebraic structures with finite-automata can be generalized from groups to other structures. For instance, it generalizes naturally to automatic semigroups.[, Section 6.1, "Semigroups and Specialized Axioms", pp. 114–116.]
References
Further reading
*{{citation
, last1 = Chiswell , first1 = Ian
, title = A Course in Formal Languages, Automata and Groups
, publisher = Springer , year = 2008 , isbn = 978-1-84800-939-4.
Computability theory
Properties of groups
Combinatorics on words
Computational group theory