# The development of the theory of automatic groups

Sarah Rees,
University of Newcastle,
<EMAIL_ADDRESS>
###### Abstract

We describe the development of the theory of automatic groups. We begin with a
historical introduction, define the concepts of automatic, biautomatic and
combable groups, derive basic properties, then explain how hyperbolic groups
and the groups of compact 3-manifolds based on six of Thurston’s eight
geometries can be proved automatic. We describe software developed in Warwick
to compute automatic structures, as well as the development of practical
algorithms that use those structures. We explain how actions of groups on
spaces displaying various notions of negative curvature can be used to prove
automaticity or biautomaticity, and show how these results have been used to
derive these properties for groups in some infinite families (braid groups,
mapping class groups, families of Artin groups, and Coxeter groups).
Throughout the text we flag up open problems as well as problems that remained
open for some time but have now been resolved.

AMS subject classifications: 20F10, 20F36, 20F55, 20F65, 20F67, 57M60,
secondary classification: 03D10, 68Q04

Keywords: automatic group, hyperbolic group, finite state automaton, combing,
3-manifold group, decision problem, word problem, conjugacy problem, Artin
group, Coxeter group, mapping class group.

###### Contents

  1. 1 Introduction
    1. 1.1 Historical background
    2. 1.2 Mathematical background and notation
  2. 2 Automatic groups
    1. 2.1 Definition of an automatic group
    2. 2.2 Basic properties of automatic groups
    3. 2.3 Basic examples and non-examples
      1. 2.3.1 Virtually abelian groups, soluble groups
      2. 2.3.2 Hyperbolic groups
      3. 2.3.3 Fundamental groups of compact 3-manifolds
  3. 3 Computing with automatic groups
    1. 3.1 Building automatic structures
    2. 3.2 Calculation using the automatic structure
  4. 4 Group actions and negative curvature
  5. 5 Some automatic and biautomatic families
    1. 5.1 Braid groups, Artin groups and Mapping Class groups
    2. 5.2 Coxeter groups
  6. 6 Open problems

##  1 Introduction

This chapter describes the development of the theory of automatic groups. It
aims to explain the definition, and put that into mathematical and historical
context, to detail what is known, give brief accounts of some of the big
problems in the subject that have already been solved, and describe those
problems that remain open.

Thurston is credited with the definition of automatic groups, and is one of
six authors of one of the primary early references of the subject [26]; but
some of the foundations were laid in particular in work of Gromov on
hyperbolic groups [37], Cannon on properties of the fundamental groups of
compact hyperbolic manifolds [18], Gilman on groups with rational cross-
sections [36]. The standard reference is certainly the book [26], but that is
supplemented by some powerful results in [7, 34, 35], while Farb’s article
[31] gives a useful and readable overview of early development of the subject.

The definition of an automatic group was originally designed to identify
properties of a group that were observed in the fundamental groups of compact
hyperbolic 3-manifolds, and which facilitated computation with those groups.
Such groups are finitely generated. When a group is automatic, its associated
automatic structure allows the elements of the group to be represented as
strings belonging to a particularly well structured set of strings, for which
certain computations can be easily performed using finite state automata, as
we shall see below.

Within this introductory section, we shall give some historical background,
then define the notation and terminology that we shall need in the remainder
of this chapter. Section 2 contains the definition of an automatic group,
identifies the basic properties, and describes the most natural examples, and
non-examples. Section 3 describes computation with automatic groups, how
automatic structures may be computed, how they may, and have been, used.
Section 4 describes how automaticity or biautomaticity of a group may be
deduced from the geometry of a space on which the group has a good action.
Section 5 describes the derivation of results proving automaticity or
biautomaticity of groups in some well known families of group, which often
used techniques or results described in Section 4. Finally Section 6 describes
some problems that remain open.

###  1.1 Historical background

Alongside Thurston, it is natural to indentify Cannon, Epstein and Holt as the
key figures in the early development of automatic groups. Much of the
information in this section comes from discussion with these three people [19,
30, 43], or can be found in the preface of the standard reference [26].

Cannon’s article [19] identifies the International Congress of Mathematicians
in Helsinki in 1978 as a location at which key ideas that influenced the
development of the concept of an automatic group were discussed.

In his plenary address, Thurston discussed the construction of geometric
structures on a 3-manifold $M$, and the tesselation of its universal cover
$\tilde{M}$ by a structure dual to the Cayley graph of $\pi_{1}(M)$.
Thurston’s geometrisation conjecture [72], subsequently proved by Perelman,
claimed that every closed 3-manifold was geometrisable, that is, admitted a
canonical decomposition into pieces each admitting one of eight types of
geometric structure.

In his article [19], Cannon attributes to Thurston at that conference the
conjecture that the growth series of a group $G$ acting discretely,
cocompactly and isometrically on a finite dimensional hyperbolic space
${\mathbb{H}}_{n}$ should be a rational function. Cannon proved that
conjecture in [18], where he identified features of ${\mathbb{H}}_{n}$ within
the Cayley graph ${\sf Cay}(G,X)$ for $G$ with respect to a finite generating
set $X$. In particular, he proved that ${\sf Cay}(G,X)$ admits finitely many
types of “cones” on geodesics, and deduced from this the rationality of the
growth function of $G$. Cannon also proved that the word and conjugacy
problems for $G$ could be solved using analogues of Dehn’s algorithms for
those in hyperbolic surface groups . Gromov’s 1987 article [37] defined a
combinatorial notion of hyperbolicity for a graph, and hence for a group (via
its Cayley graph), and generalised Cannon’s results to groups satisfying this
definition of hyperbolicity. There is a substantial body of material studying
(Gromov) hyperbolic groups, in particular [2].

Thurston realised that the finiteness of the set of cone types in one of
Cannon’s groups of hyperbolic isometries allowed the construction of a finite
state automaton recognising the set of geodesic words within the group;
rationality of the growth function is an immediate consequence of that set of
words being the language of a finite state automaton. “Fellow travelling”
properties of quasi-geodesic paths in ${\mathbb{H}}_{n}$ that had been
recognised by Cannon allowed the construction of further automata that
recognised right multiplication in the goup by a generator.

Now Thurston defined the concept of an automatic group. He called a group with
finite generating set $X$ automatic if it possessed a representative set of
words $L$ over $X$, such that one finite state automaton recognised the words
in $L$, and other automata recognised pairs of words in $L$ related in the
group under right multiplication by the generators in $X$. Very early on,
groups of this type were known as regular groups [43]. But this terminology
conflicted with other uses of the term regular, and so was soon changed.

Initially, in particular in [26, 7], the study of the family of automatic
groups was largely driven by the desire to find within it the groups of the
geometrisable 3-manifolds, and hence to harness computational techniques that
were provided by the association of automatic groups with regular languages.
Epstein realised very early on that any automatic group must be finitely
presented, while Thurston deduced that any such group had quadratic Dehn
function and hence word problem soluble in quadratic time. Epstein and Holt in
Warwick worked, together with the author of this chapter, to develop practical
procedures to (attempt to) build automatic structures for finitely presented
groups, and to compute within the groups using those structures.

###  1.2 Mathematical background and notation

All the groups that we consider will be finitely generated. If $X$ is a finite
generating set for a group $G$, then we write $G=\langle X\rangle$. In that
case every element of $G$ can be represented as a product (or string) of
elements of $X$ and their inverses. We denote by $X^{-1}$ the set of symbols
$x^{-1}$ for which $x\in X$, and then by $X^{\pm}$ the disjoint union of $X$
and $X^{-1}$; every non-identity element of $G$ can now be described as a
string of elements of $X^{\pm}$. The identity element, which we denote by $1$,
can be described as a product of length 0.

Given a finite set $A$, we define a string $w$ over $A$ to be a sequence
$a_{1}a_{2}\cdots a_{n}$ with $a_{i}\in A$, and call $n$ the length of $w$,
denoted by $|w|$; we may alternatively use the term word over $A$ rather than
string. A subsequence $a_{i}a_{i+1}\cdots a_{j}$ of $w$ is called a substring
or subword. We write $w(i)$ for the prefix $a_{1}\cdots a_{i}$ of $w$. We call
the string or word of length $0$ over $A$ the empty string or empty word and
denote that by $\varepsilon$. As is standard, we denote by $A^{+}$ the set of
all strings over $A$ of finite length $>0$ and by $A^{*}$ the union
$A^{+}\cup\\{\varepsilon\\}$. Given an ordering of the elements of $A$, we
define the shortlex ordering on $A^{*}$ as follows: for words $u=x_{1}\ldots
x_{r}$ and $v=y_{1}\ldots y_{s}$ , we define $v<_{\rm slex}u$ if $|v|<|u|$, or
if $|u|=|v|$ and for some $i$, $y_{1}=x_{1},\ldots,y_{i-1}=x_{i-1}$ but
$y_{i}<x_{i}$.

When $X$ is a generating set for a group $G$, and $w\in(X^{\pm})^{*}$, it is
often convenient to abuse notation and use $w$ to indicate not only that
string over $X^{\pm}$ but also the group element that the string represents;
if $w,v\in X^{\pm}$, we write $w=v$ to denote that $w,v$ are identical as
strings, and $w=_{G}v$ to denote that $w,v$ represent the same group element.
If $g\in G$, we denote by $|g|$ the length of the shortest word over $X^{\pm}$
that represents $g$. Suppose that ${\sf Cay}={\sf Cay}(G,X)$ is the Cayley
graph of $G$ over $X$, that is the graph with vertex set $G$ and, for each
$g\in G$, $x\in X$, directed edges labelled $x$ and $x^{-1}$ connecting the
ordered pairs of vertices $(g,gx)$ and $(gx,g)$. Then for each $g\in G$, a
path labelled by $w$ joins the vertex $g$ of ${\sf Cay}$ to the vertex $gw$;
we shall represent that path as ${}_{g}w$.

When $G$ is finitely generated by $X$, we define a language for $G$ over $X$
to be a subset of $(X^{\pm})^{*}$ that contains at least one representative of
each element of $G$, that is, that maps onto $G$ under the map assigning each
product over $X$ to the element it represents.

For the free group $F_{n}$ on a set $X$ of $n$ generators
$x_{1},\ldots,x_{n}$, a language is provided by the set of all freely reduced
words of length $\geq 0$ over $X^{\pm}$, that is, the set of all words within
which no subword $x_{i}x_{i}^{-1}$ or $x_{i}^{-1}x_{i}$ appears. For the free
abelian group ${\mathbb{Z}}^{n}$ on the same set of $n$ generators, a language
is provided by the set of all words of the form
$x_{i_{1}}^{r_{1}}x_{i_{2}}^{r_{2}}\cdots x_{i_{k}}^{r_{k}}$, with $k\geq 0$,
$i_{1}<i_{2}<\cdots<i_{k}$ and $r_{i}\in{\mathbb{Z}}\setminus\\{0\\}$. In each
of these two examples the language provides a unique representative for each
group element.

Each of the two languages just described is an example of a regular language,
that is, it is the set $L(M)$ of strings accepted by a finite state automaton
(fsa) $M$ with alphabet $\\{x_{1}^{\pm 1},x_{2}^{\pm 1}\,\ldots,x_{n}^{\pm
1}\\}$. Finite state automata provide standard models of bounded memory
computation and are defined and studied in [46]. It is common to represent a
finite state automaton $M$ with alphabet $A$ as a finite directed graph, with
each directed edge labelled by one or more elements of $A$, one vertex
identified as the start, and a subset of the vertices selected as accepting. A
word $w$ is then accepted by $M$ if it labels at least one directed path from
the start to an accepting vertex; if there is no such path, or if the end
point (target) of every such path is a non-accepting vertex then $w$ is not
accepted. It is standard to call the vertices of $M$ its states, the directed
edges its transitions and the set of accepted words its language $L(M)$. In
the cases where $n=2$, the languages described above for the free and free
abelian groups over $\\{a,b\\}$ are accepted by the two finite state automata
shown in Figure 1; in each diagram, following convention, the start state is
indicated by an arrow, and the accepting states are ringed. In each of the two
examples, each of the five states shown in the diagram is accepting, but a
further failure state is not shown, which constitutes a sixth state; the
failure state is non-accepting, any transitions not shown in the diagram are
assumed to be to that failure state, and all transitions from the failure
state are to the failure state.

$a$$a^{-1}$$b$$b^{-1}$$a$$a^{-1}$$b$$b^{-1}$$b$$b^{-1}$$b$$b^{-1}$$a$$a^{-1}$$a$$a^{-1}$

$a$$a^{-1}$$b$$b^{-1}$$a$$a^{-1}$$b$$b^{-1}$$b$$b^{-1}$$b$$b^{-1}$

Figure 1: fsa $M_{1},M_{2}$ giving the languages described in the text for
$F^{2}$ and ${\mathbb{Z}}^{2}$

##  2 Automatic groups

###  2.1 Definition of an automatic group

Now suppose that $G$ is a group with finite generating set $X$. For
$k\in{\mathbb{N}}$, words $w,v$ over $X^{\pm}$ are said to $k$-fellow travel
in $G$ if for each $i\leq\max\\{|w|,|v|\\}$ the distance between the vertices
$w(i)$ and $v(i)$ of ${\sf Cay}={\sf Cay}(G,X)$ (using the graph metric) is at
most $k$. Equivalently, we say that the paths ${}_{1}w$ and ${}_{1}v$ of ${\sf
Cay}$ $k$-fellow travel. A group $G$ with finite generating set $X$ is defined
to be automatic over $X$ if

A1

there is a language $L$ for $G$ over $X$ that is regular,

A2

there is an integer $k$ such that, for each $y\in X\cup\\{1\\}$, and for any
$w,v\in L$ with $wy=_{G}v$, the paths ${}_{1}w,{}_{1}v$ $k$-fellow travel in
${\sf Cay}$.

We call $L$ the language, the fsa accepting $L$ the word acceptor and $k$ the
fellow traveller constant of an automatic structure for $G$.

The fsa $M_{1}$ illustrated in Figure 1 is the word acceptor of an automatic
structure with fellow traveller constant 1 for $F_{2}$ over $\\{a,b\\}$; each
element of the group has a unique representative in the language, and given
two words $w,v\in L(M_{1})$ and $y\in\\{a^{\pm 1},b^{\pm}\\}$ with
$wy=_{F_{2}}v$, one of the words is a maximal prefix of the other, and so the
words $1$-fellow travel in $G$.

Similarly, the fsa $M_{2}$ of Figure 1 is the word acceptor of an automatic
structure with fellow traveller constant 2 for ${\mathbb{Z}}^{2}$ over
$\\{a,b\\}$. Again each element of the group has a unique representative in
the language, and given two words $w,v\in L(M_{2})$ and $y\in\\{a^{\pm
1},b^{\pm 1}\\}$ with $wy=_{{\mathbb{Z}}^{2}}v$, corresponding vertices on the
paths ${}_{1}w$ and ${}_{1}v$ in ${\sf Cay}({\mathbb{Z}}^{2},\\{a,b\\})$ are
joined in the graph by a path of length 1 or 2. The language $L(M_{2})$ is the
set of all Shortlex minimal geodesic representatives of group elements; we
call this a shortlex automatic structure for ${\mathbb{Z}}^{2}$. Note that we
can define a similar shortlex automatic structure for ${\mathbb{Z}}^{n}$.

In the definition of automaticity given in [26] the condition A2 given above
is replaced by the following condition:

A2’

For each $y\in X\cup\\{\\{1\\}\\}$, the set of pairs $(w,v)$ for which $w,v\in
L$ and $wy=_{G}v$ is a regular language when viewed as a set of strings over
the alphabet of pairs $\\{(a,b):a,b\in X^{\pm}\cup\\{\$\\}\\}$; the character
$\$$ is a padding symbol used to deal with the situation where $|w|\neq|v|$,
in which case the shorter of the two words is padded with $\$$s at its end.

The automata recognising the regular languages just described are known as the
multiplier automata of the automatic structure, usually denoted by $M_{y}$,
for each choice of $y$.

In the presence of A1 the conditions A2 and A2’ are equivalent. This is a
consequence of the fact that the $k$-fellow travelling of a pair of words
$w,v$ can be tracked by an automaton whose state set ${\mathcal{D}}$
corresponds to a set of words of length at most $k$; a pair of words $(w,v)$
is accepted by that automaton so long as all the products
$w^{\prime-1}v^{\prime}$ associated with prefixes
$w^{\prime}:=w(i),v^{\prime}:=v(i)$ of $w,v$ are represented by words in
${\mathcal{D}}$. We call such an automaton a word difference machine, and the
associated set ${\mathcal{D}}$ its corresponding set of word differences.

Where $G$ is automatic over its finite generating set $X$, with automatic
structure $L,k$, then $G$ is said to be biautomatic (and $(L,k)$ to be a
biautomatic structure for $G$) if the additional condition A3 is satisfied:

A3

for each $y\in X$, and for any $w,v\in L$ with $yw=_{G}v$, the paths
${}_{y}w,{}_{1}v$ $k$-fellow travel in ${\sf Cay}(G,X)$.

This further fellow traveller condition can be expressed in terms of fsa that
recognise left multiplication, usually denoted by ${}_{y}M$, for $y\in X$. It
is an open question whether all automatic groups are biautomatic.

The concept of automaticity can be generalised to one of asynchronous
automaticity by replacing the fellow traveller condition by an asynchronous
fellow travel condition; for two words $w,v$ to asynchronously fellow travel
within a group $G$ it is the distance between vertices $w(j_{i})$ and
$v(k_{i})$ that must be bounded, where, for some $m\geq\max(|w|,|v|)$, the
sequences $(j_{0},j_{1},\ldots,j_{m})$ and $(k_{0},\ldots,k_{m})$ are both
increasing sequences of integers, with $j_{0}=k_{0}=0$, $j_{m}=|w|$,
$k_{m}=|v|$, and for $0\leq l<m$, $j_{l+1}-j_{l}$ and $k_{l+1}-k_{l}$ are in
$\\{0,1\\}$. Asynchronous automaticity is certainly a more general concept
than automaticity, and it is satisfied by examples such as the
Baumslag–Solitar groups which are certainly not automatic.

It is fairly standard to call a language $L$ for a group $G$ that satisfies
the condition A2 (but not necessarily A1) a combing for $G$, and a language
that satisfies both A2 and A3 a bicombing for $G$; however some authors use
these terms differently, e.g. impose additional (geometric) conditions on $L$.
Again, the fellow travelling condition can be replaced by an asynchronous one,
in order to define asynchronous combings and bicombings. The basic properties
of combable groups are studied in [12], where it is proved that non-automatic
combable groups exist (answering a question posed in [26]), as well as
combable groups that are not bicombable.

Given an automatic (or biautomatic) structure $(L,k)$ for a group $G$, it is
straightforward (using well known properties of regular languages, such as the
“Pumping lemma” [46]) to modify the structure and achieve a new automatic
structure with particular properties. For instance we can achieve a structure
in which every element of $G$ has a unique representative (a structure with
uniqueness) a prefix closed structure in which the language contains every
prefix of every one of its elements, a quasigeodesic structure in which every
element is represented by a $(\lambda,\epsilon)$-quasigeodesic, We note that a
word $w$ representing an element $g$ of a group $G$ is called a
$(\lambda,\epsilon)$-quasigeodesic if every subword $w^{\prime}$ of $w$ has
length at most $\lambda|g^{\prime}|+\epsilon$, where $g^{\prime}$ is the
element represented by $w^{\prime}$. Note that it is not clear that all
combinations of properties can be achieved within the language of a single
automatic structure. In particular it is an open question [26] whether, given
an automatic structure for a group $G$, an automatic structure can be derived
for $G$ that is both prefix closed and has uniqueness.

Note that the definitions of automaticity and biautomaticity are independent
of choice of generating set; that is if $G$ has an automatic structure over a
finite generating set $X$, then it has one over any other finite generating
set $Y$.

###  2.2 Basic properties of automatic groups

Some properties of automatic groups can be deduced very easily from basic
properties of regular languages, which imply certain constraints on their
Cayley graphs. In particular any automatic group is finitely presented with
soluble word problem, and quadratic Dehn function, while any biautomatic group
has soluble conjugacy problem. We recall that the word problem is soluble in
$G$ if an algorithm exists that can decide whether or not any input word
represents the identity, and the conjugacy problem is soluble if an algorithm
exists that can decide whether or not two input words represent elements that
are conjugate within the group; it is an open question whether the conjugacy
problem is soluble for automatic groups. It also is an open question whether
the isomorphism problem is soluble for automatic groups, that is, whether an
algorithm that was given as input automatic structures for a pair of groups
$G,H$ could decide whether or not $G$ and $H$ were isomorphic. It is
conjectured in [26] that this problem is insoluble. Note that it is soluble
for hyperbolic groups [24, 70].

In order to explain these statements in more detail, we use the language of
van Kampen diagrams. Informally (essentially, following [53]), given a group
$G$ with presentation $\langle X\mid R\rangle$ and a word $w$ over $X$ that
represents the identity of $G$, we define a van Kampen diagram $\Delta_{w}$
for $w$ to be a finite, connected, directed, planar graph, with a selected
basepoint, whose directed edges are labelled by elements of $X$, in such a way
that the boundary of every face of the graph (known as a cell) is labelled
(from some starting point, in some orientation) by a word from $R$, while the
boundary of the graph is labelled (from the basepoint) by $w$. As a directed,
edge labelled graph, $\Delta_{w}$ maps (not necessarily injectively) into the
Cayley graph ${\sf Cay}(G,X)$. The area of the diagram ${\sf
Area}(\Delta_{w})$ is defined to be the number of cells it contains; of course
its value is dependent on the set $R$, and would change if $R$ were changed.

We define the area of the word $w$ to be the minimum of the areas of all van
Kampen diagrams that represent $w$. And we define the Dehn function (or
isoperimetric function) for $G$, $f:{\mathbb{N}}\rightarrow{\mathbb{N}}$, to
be the function for which $f(n)$ is the maximum area of all words $w$ of
length $n$ over $X^{\pm}$ that represent the identity of $G$. Although the
precise form of the Dehn function depends on the chosen presentation for $G$,
it can be shown that two Dehn functions corresponding to different
presentatives are related by a natural notion of equivalence, and in
particular if one is polynomially bounded, then both are, by polynomials of
the same degree.

######  Proposition 2.1.

Every automatic group is finitely presented, with a quadratic upper bound on
the Dehn function, and hence soluble word problem.

We sketch the proof, which is that of [45, Theorem 5.2.13].

###### Proof.

We suppose that $L,k$ are the language and fellow traveller constant of an
automatic structure over a generating set $X$; we may assume that $L$ consists
of quasigeodesics. Suppose that $w=a_{1}\cdots a_{n}$ is a word of length $n$
representing the identity. Now we define words $w_{0},\ldots,w_{n}$ as
follows. We define $w_{0}=w_{n}$ to be a representative in $L$ of $1$, and for
each $i=1,\ldots,n-1$ we choose $w_{i}$ to be a representative in $L$ of the
prefix of $w$ of length $i$; since $L$ is quasigeodesic, we can choose $w_{i}$
of length at most $|w_{0}|+Ci$, for some constant $C$ of the automatic
structure. We start with a disk within the plane whose boundary is labelled by
$w$, and divide it into cells to form a van Kampen diagram $\Delta_{w}$ with
boundary $w$ as follows. First, a loop labelled by $w_{0}$ connects the
basepoint to itself, while for each $i$ a path labelled $w_{i}$ connects the
basepoint to the point on the boundary distance $i$ along $w$, and none of
these paths cross each other. Then, since the paths ${}_{1}w_{i-1}$ and
${}_{1}w_{i}$ in ${\sf Cay}(G,X)$ fellow travel at distance at most $k$, we
can construct paths of length at most $k$ that connect corresponding vertices
on the paths within the disk labelled by those two words, and hence divide the
region between the two paths into cells each of length at most $2k+2$. In this
way we divide the interior of the diagram into a number of cells labelled by
words of length at most $2k+2$. together with two cells labelled by the word
$w_{0}=w_{n}$, as illustrated in Figure 2.

$w$$w_{0}$$w_{n}$$a_{1}$$w_{1}$$a_{2}$$w_{2}$$a_{3}$$w_{3}$$a_{n-4}$$a_{n-3}$$w_{n-3}$$a_{n-2}$$w_{n-2}$$a_{n-1}$$w_{n-1}$$a_{n}$$\leq
k$$\leq k$ Figure 2: Van Kampen diagram for a representative of the identity
in an automatic group

Using the bounds on $|w_{i}|$, we see that the total number of cells is
bounded by a quadratic function of $n$. We now define $R$ to be the set of all
words of length up to $2k+2$ that represent the identity, together with the
word $w_{0}$. Then $\langle X\mid R\rangle$ is a finite presentation for $G$,
and, relative to $R$, $\Delta_{w}$ has quadratic area. ∎

A similar argument proves an exponential upper bound on the Dehn function for
any asynchronously automatic group; it is an open question [26] whether a
polynomial time solution to the word problem must exist.

The most straightforward way to prove a group non-automatic is probably to
show that it has a Dehn function that is above quadratic. This argument proves
easily the non-automaticity of the Baumslag–Solitar groups $\langle a,b\mid
ba^{p}b^{-1}=a^{q}$ for which $p,q>0$ and $p\neq q$, since they have
exponential Dehn function; in fact they provide examples of non-automatic
groups that are asynchronously automatic.

But there are many groups with quadratic Dehn functions that are known by
other methods not to be automatic.

The non-automaticity of the groups ${\mathrm{SL}}_{n}({\mathbb{Z}})$ for
$n\geq 3$ is proved in [26]. The group ${\mathrm{SL}}_{2}({\mathbb{Z}})$ is
well known to be virtually free, and hence hyperbolic with linear Dehn
function. The group ${\mathrm{SL}}_{3}({\mathbb{Z}})$ has exponential Dehn
function and so is certainly non-automatic. However, the existence of a
quadratic Dehn function for ${\mathrm{SL}}_{n}({\mathbb{Z}})$ with $n\geq 5$
was proved in [77] in 2013 (and had been conjectured by Thurston, in fact for
$n\geq 4$). In order to prove non-automaticity of the group for all $n\geq 3$,
Epstein and Thurston derived higher dimensional isoperimetric inequalities
that would have to hold in any combable group of isometries acting properly
discontinuously with compact quotient on a $k$-connected Riemannian manifold
[26, Theorem 10.3.5]. The non-automaticity of
${\mathrm{SL}}_{n}({\mathbb{Z}})$ now follows by the construction of a proper
discontinous cocompact action on a suitable contractible manifold, and the
demonstration that a higher dimensional isoperimetric inequality fails; hence
${\mathrm{SL}}_{n}({\mathbb{Z}})$ is proved to be non-combable and so non-
automatic.

Van Kampen diagrams can also be used to prove solubility of the conjugacy
problem in any biautomatic group, by demonstrating the existence of a
conjugator of bounded length. The proof below, valid for any bicombable group,
is taken from [71]; an earlier result of [35] constructs an automaton out of
the biautomatic structure to solve the problem.

######  Proposition 2.2.

Given a biautomatic group $G$, any two words $u,v$ representing conjugate
elements are conjugate by an element of length at most $a^{|u|+|v|}$, for some
constant $a$ (depending only on the biautomatic structure). Hence any
biautomatic group has soluble conjugacy problem.

###### Proof.

We choose a biautomatic structure $(L,k)$ over a finite generating set $X$,
and suppose that the words $u,v$ over $X^{\pm}$ represent conjugate elements
of $G$. Let $N:=|X^{\pm}|^{k(|u|+|v|)}$. We find a conjugator of length at
most $N$, and so $a=|X^{\pm}|^{k}$.

For suppose that an element $g\in G$ conjugates $u$ to $v$, that is that
$gu=_{G}vg$, and that $w,w^{\prime}\in L$ represent the elements $g$ and $ug$,
respectively. We consider the paths ${}_{1}w$, ${}_{1}w^{\prime}$ and
${}_{u}w$ within the Cayley graph ${\sf Cay}(G,X)$, and see that the
biautomaticity of $G$ ensures that ${}_{1}w$ and ${}_{1}w^{\prime}$ fellow
travel at distance at most $|u|k$, and that ${}_{1}w^{\prime}$ and ${}_{u}w$
fellow travel at distance at most $|v|k$. We deduce that we can construct a
van Kampen diagram with boundary labelled by $wuw^{-1}v^{-1}$ in which chords
of length at most $(|u|+|v|)k$ join boundary vertices in corresponding
positions on the two boundary subwords labelled by $w$, as shown on the left
hand side of Figure 3. Where $|w|=n$, let $d_{1},d_{2},\ldots,d_{n-1}$ be the
words that label those chords.

$u$$w$$v$$w$$1$$w^{\prime}$$d_{i}$$d_{j}$

$u$$\hat{w}$$v$$\hat{w}$$1$$d_{i}=d_{j}$

Figure 3: Finding a conjugator of bounded length

Now if $n>|X^{\pm}|^{(|u|+|v|)k}$, then for some $i,j$ we have $d_{i}=d_{j}$.
In that case, where $\hat{w}$ is the word formed from $w$ by deleting its
middle section of length $j-i$, from its $(i+1)$-th to its $j$-th letter, we
can form the van Kampen diagram with boundary word
$\hat{w}u\hat{w}^{-1}v^{-1}$ shown on the right hand side of Figure 3 by
deleting the central part of the diagram we already constructed for
$wuw^{-1}v^{-1}$.

∎

Various combinations of automatic groups are known to be automatic [26, 7]:
these include free products, direct products, certain amalgamated products and
HNN extensions of automatic groups, as well as subgroups of finite index in
automatic groups, groups with automatic groups as subgroups of finite index,
quotients of automatic groups by finite normal subgroups. Some, but not all,
of these closure properties also hold for biautomatic groups. It is an open
question whether direct factors of automatic groups must be automatic (but the
analogous result is proved for biautomatic groups [61]). It is also open [26]
whether a group with a biautomatic group as a subgroup of finite index must be
biautomatic.

###  2.3 Basic examples and non-examples

####  2.3.1 Virtually abelian groups, soluble groups

We already described shortlex automatic structures for the free abelian group
${\mathbb{Z}}^{n}$. In fact ${\mathbb{Z}}^{n}$ is also biautomatic, but with a
different (less straightforward) language, and indeed so is every virtually
abelian group. However it was already proved in [26] that an automatic
nilpotent group must be virtually abelian; the proof uses the fact that a
regular language with polynomial growth cannot satisfy a (synchronous) fellow
traveller property. It was conjectured by Thurston that the same result must
hold for an automatic soluble group. That conjecture remains open, but it was
proved for automatic polycylic groups in [39], using an embedding of a finite
index subgroup of a polycyclic group of exponential growth as a lattice in an
appropriate Lie group, where [26, Theorem 10.3.5] about higher dimensional
isoperimetric functions could be applied, which had previously been used to
prove the non-automaticity of ${\mathrm{SL}}_{n}({\mathbb{Z}})$ for $n\geq 3$.
Much more recently it was proved in [69] that biautomatic soluble groups must
be virtually abelian.

####  2.3.2 Hyperbolic groups

Maybe the most natural examples of non-abelian automatic groups are provided
by the large family of word hyperbolic groups, which contains all finitely
generated free groups as well as the fundamental groups of all compact
hyperbolic manifolds.

A group $G$ with finite generating set $X$ is said to be word hyperbolic if
its Cayley graph ${\sf Cay}(G,X)$ is a $\delta$-hyperbolic metric space, for
some $\delta\geq 0$; a geodesic metric space $({\mathcal{X}},d)$ is
$\delta$-hyperbolic if for any triangle in ${\mathcal{X}}$ with geodesic sides
$\gamma_{1},\gamma_{2},\gamma_{3}$ and for any vertex $p$ on the side
$\gamma_{1}$ there is a vertex $q$ on the union $\gamma_{2}\cup\gamma_{3}$ of
the other two sides for which $d(p,q)<\delta$ (we say that triangles in
${\mathcal{X}}$ are $\delta$-slim). The property of being word hyperbolic is
independent of the choice of a finite generating set for $G$, although the
value of $\delta$ is not. The fundamental groups of compact hyperbolic
manifolds give examples, as do finitely generated free groups (which are
$0$-hyperbolic with respect to free generating sets).

We note that there are many equivalent definitions of hyperbolicity for metric
spaces (and hence for finitely generated groups), which are explained in [2].
In particular there is a characterisation in terms of thin rather than slim
triangles (and a linear relationship between the associated parameters
“$\delta$”).

It is proved in [26] that a word hyperbolic group $G$ is automatic over any
generating set $X$, with an automatic structure whose language consists of all
geodesic words over the selected generating set. The regularity of that set of
geodesic words is equivalent to the fact that the Cayley graph ${\sf Cay}={\sf
Cay}(G,X)$ contains finitely many cone types. For $g\in G$, represented by a
geodesic word $w$, we define the cone $C(g)$ (or $C(w)$) on the vertex $g$ of
${\sf Cay}$ to be the set of (geodesic) paths $\gamma$ within ${\sf Cay}$
starting at $g$ for which the concatenation $\eta\gamma$ of a geodesic path
$\eta$ from $1$ to $g$ with $\gamma$ is also geodesic. The cone type $[C(g)]$
or $[C(w)]$ of the cone is defined to be the set of words that label the paths
within it. Now for $y\in X\cup X^{-1}$, if $wy$ is also geodesic then for any
word $v$,

$v\in[C(wy)]\iff yv\in[C(w)].$

It follows that we can recognise the set of geodesic words over $X^{\pm}$ with
an fsa whose states correspond to the cone types, with a transition from
$[C(w)]$ to $[C(wy)]$ on $y$ whenever $wy$ is geodesic, but otherwise to a
single failure state (i.e. a non-accepting sink state). We can illustrate this
construction in the free abelian group ${\mathbb{Z}}^{2}$ with generating set
$\\{a,b\\}$, where there are nine cone types $[C(w)]$, defined by the nine
geodesic words $\varepsilon$, $a$, $b$, $a^{-1}$, $b^{-1}$, $ab$, $ab^{-1}$,
$a^{-1}b$, $a^{-1}b^{-1}$, and consisting of the nine possible sets of
geodesic words in which each generator appears either only with positive
exponent, or only with negative exponent, or not at all. The fsa is
illustrated in Figure 4. This automaton is not part of an automatic structure
for ${\mathbb{Z}}^{2}$; it cannot be since, for example, the vertices distance
$i$ from the origin on the geodesic words $a^{i}b^{i}$ and $b^{i}a^{i}$ are
distance $2i$ apart within the Cayley graph, and hence this language does not
satisfy a fellow travelling property.

$a$$a^{-1}$$b$$b^{-1}$$a$$a^{-1}$$b$$b^{-1}$$a$$a,b$$b$$a$$a,b^{-1}$$b^{-1}$$a^{-1}$$a^{-1},b$$b$$a^{-1}$$a^{-1},b^{-1}$$b^{-1}$
Figure 4: fsa recognising geodesics in ${\mathbb{Z}}^{2}$

Given the finiteness of the set of cone types in a word hyperbolic group,
biautomaticity of any word hyperbolic group now follows once it is observed
that the fellow travelling of two geodesic words with common (or adjacent)
start and end vertices can be derived from the slimness of triangles. In fact,
it is proved by Papasoglu [67] that this fellow traveller condition
characterises word hyperbolic groups, and hence so does the existence of a
(bi)automatic structure that consists of all geodesic words. A procedure to
test for hyperbolicity that is based on this result is described in [75].
Starting with a shortlex automatic structure $(L,k)$ for a group $G$ over $X$,
the procedure attempts to construct an automatic structure
$(\widehat{L},\widehat{k})$ with $\widehat{L}\supset L$ and $\widehat{k}\geq
k$, and such that $\widehat{L}$ contains all geodesic words over $X^{\pm}$. It
will terminate with such a structure precisely when $G$ is hyperbolic. An
improved procedure, based on the same result was developed by Holt and Epstein
[27] and implemented in kbmag.

The fundamental groups of finite volume hyperbolic manifolds (geometrically
finite hyperbolic groups) were proved biautomatic by Epstein [26], with a
further biautomatic structure subsequently described by Lang [55].

Geometrically finite hyperbolic groups were the motivating examples for
Bowditch’s definition [9] of a group hyperbolic relative to a collection of
subgroups; a geometrically finite hyperbolic group is hyperbolic relative to a
collection of abelian groups. The major part of the definition of relative
hyperbolicity is the requirement that the Cayley graph of a group hyperbolic
relative to a collection ${\mathcal{H}}$ of subgroups becomes hyperbolic after
the contraction of edges within left cosets of subgroups in ${\mathcal{H}}$.
However weaker and stronger versions of the definition exist depending on
whether or not a condition of bounded coset penetration is required to hold.
Under the stronger definition (studied in [66]) it is proved, in particular in
[5], that groups hyperbolic relative to shortlex biautomatic subgroups are
themselves shortlex biautomatic. The shortlex biautomaticity of geometrically
finite hyperbolic groups is a consequence of this result.

A further generalisation of hyperbolic groups is provided by semihyperbolic
groups, which were introduced by Bridson and Alonso in [3]; the class contains
all biautomatic groups (hence all hyperbolic groups) and all CAT(0) groups
(see Section 4). A group $G$ with finite generating set $X$ is defined to be
weakly semihyperbolic if ${\sf Cay}(G,X)$ admits a bounded quasi-geodesic
bicombing (with a unique combing path $s_{g_{1},g_{2}}(t)$ identified between
any pair $g_{1},g_{2}$ of vertices of the graph), and semihyperbolic if it has
such a bicombing that is equivariant under the action of $G$ (so that
$g.s_{g_{1},g_{2}}(g)=s_{gg_{1},gg_{2}}(t)$). This class of groups satisfies
many closure properties, and all groups within it are finitely presented, with
soluble word and conjugacy problems.

####  2.3.3 Fundamental groups of compact 3-manifolds

It is proved in [26] that the fundamental groups of compact 3-manifolds based
on six of Thurston’s eight model geometries for compact 3-manifolds [73] admit
automatic structures. But it is also proved that the fundamental groups of
closed manifolds based on the Nil and Sol geometries (which are non-abelian,
nilpotent and soluble, respectively) cannot even be asynchronously automatic
[26, 10].

However, using combination theorems for automatic groups, it can be proved (as
in [26, Theorem 12.4.7], but our wording is slightly different) that an
orientable, connected, compact 3-manifold with incompressible toral boundary
whose prime factors have JSJ decompositions containing only hyperbolic pieces
has automatic fundamental group. It was proved in [13, Theorem B] that the
fundamental group of a manifold as above in which manifolds based on Nil and
Sol are allowed within the JSJ decomposition, while not automatic, still
admits an asynchronous combing based on an indexed language [1].

##  3 Computing with automatic groups

###  3.1 Building automatic structures

The original motivation for the definition of automatic groups was
computational, and so it was important from the beginning of the subject to be
able to construct automatic structures, that is, given a presentation for a
group $G$, to have a mechanism for building the word acceptor and multiplier
automata of an associated automatic structure. Software to build these
automata was developed at the University of Warwick, and the procedure used is
described in [29]. The original programs were subsequently rewritten by Holt,
and released within his kbmag package [54], now available within both GAP and
Magma computational systems [33, 59].

The basic procedure is the same in both versions (the ideas are due to Holt)
and we describe it briefly now, but refer the reader to [29] or [42] for more
details.

A presentation for a group $G$ over a finite generating set $X$ is input,
together with an ordering of the set $X^{\pm}$. The procedure attempts to
prove $G$ to be shortlex automatic over $X$ (with the given ordering) by first
constructing a set of automata consisting of $W$ and $M_{y}$ for $y\in
X^{\pm}\cup\\{\varepsilon\\}$, and then attempting to verify that those
automata are indeed the automata of a shortlex automatic structure. If
verification tests fail, some looping is possible within the procedure, and
indeed that looping could continue indefinitely (or at least until the
computer runs out of resources). If all verification tests pass, then the
procedure will have verified the shortlex automaticity of $G$ by construction
and checking of a shortlex automatic structure.

So the procedure may succeed in proving shortlex automaticity of $G$. But if
it fails, it has certainly not proved that $G$ is not automatic, or even that
$G$ is not shortlex automatic, but rather it suggests that $G$ is unlikely to
be shortlex automatic over the given generating set $X$, with the given
ordering of the elements of $X$. We note that the question of automaticity for
a finitely presented group is undecidable in general; this follows from the
undecidability of questions such as triviality for a group. We note too that
it is an open question [26] whether every automatic group must be shortlex
automatic with respect to some ordered generating set.

The first step of the procedure to prove shortlex automaticity is the
construction of a rewrite system ${\mathcal{R}}$ from the group presentation
that is compatible with the shortlex order. By definition, ${\mathcal{R}}$ is
a set of substitution rules $\rho:u\rightarrow v$, for $u,v\in(X^{\pm})^{*}$,
and with $v<_{\rm slex}u$; in order that ${\mathcal{R}}$ encodes the
presentation we require that every relator from the group presentation is a
cyclic conjugate of the product $uv^{-1}$ or its inverse for at least one such
rule.

The next step is to run the Knuth–Bendix procedure for a while on
${\mathcal{R}}$. The Knuth–Bendix procedure (described in [45]) is a general
procedure that, given as input a rewrite system ${\mathcal{R}}$ for strings
compatible with a partial order, modifies it by adding rules that are
consequences of existing rules and deleting rules that have become redundant,
in order to produce a new rewrite system. The procedure attempts to build a
finite complete system, for which any input word $w$ can be rewritten after a
finite number of steps to a unique irreducible word $w^{\prime}$ (where
irreducible means that $w^{\prime}$ cannot be rewritten further). However with
this goal the procedure may never terminate; all that is guaranteed is that
after bounded time the modified system must contain enough rules to reduce any
word up to some bounded length to an irreducible.

In fact the procedure to construct a shortlex automatic structure for $G$ does
not need the Knuth–Bendix procedure to terminate on the input rewrite system
${\mathcal{R}}$. Instead, while the Knuth–Bendix procedure is running it
accumulates the set ${\mathcal{D}}$ of word differences $u(i)^{-1}v(i)$ and
their inverses (reduced according to the current modification of
${\mathcal{R}}$) that correspond to prefixes of the rules $u\rightarrow v$ in
the system. Where $u=u_{1}\cdots u_{m}$, and $v=v_{1}\cdots v_{m^{\prime}}$, a
transition is added from each word difference $u(i)^{-1}v(i)$ to
$u(i+1)^{-1}v(i+1)$, creating a word difference machine that can recognise
fellow travelling with respect to ${\mathcal{D}}$.

The Knuth–Bendix procedure is paused when it seems that the set
${\mathcal{D}}$ and the associated automaton have stabilised. And then a
candidate word acceptor ${\sf WA}$ is constructed, designed to reject a word
$u$ if a string $v$ exists with $v<_{\rm slex}u$ for which $(u,v)$ fellow
travels according to ${\mathcal{D}}$ while also the word difference $u^{-1}v$
reduces, according to the current rewrite system, to the empty word.

Similarly, multiplier automata are constructed for each $y\in
X^{\pm}\cup\\{\varepsilon\\}$, using a direct product construction on automata
to recognise pairs of words $u,v$ for which $u,v\in L(W)$, $(u,v)$ fellow
travels according to ${\mathcal{D}}$, while also the word difference $u^{-1}v$
reduces, according to the current rewrite system, to $y$.

Now a series of elementary tests is applied to the candidate automata. If some
of these tests fail, then ${\mathcal{D}}$ has been proved to be inadequate,
and the Knuth–Bendix procedure is restarted. If and when those tests are
passed, further tests known as axiom checking are applied, and a positive
result for these tests proves the automata to provide a shortlex automatic
structure for $G$. If the axiom checks fail then the procedure is abandoned.

###  3.2 Calculation using the automatic structure

Once an automatic structure has been constructed for a group $G$, much can be
computed using the automata of that structure. Various of these functions are
available within the kbmag package [54].

It is straightforward to enumerate the language of a finite state automaton.
Hence we can enumerate a set of representative words for an automatic group,
with unique representation if necessary (recall that once an automatic
structure has been derived, a structure with unique representation can be
derived from that).

For any regular language $L$ the generating function
$\sum_{n=0}^{\infty}s_{L}(n)x^{n}$, where $s_{L}(n)$ denotes the number of
words of length $n$ in $L$, is a rational function, and can be computed from
an automaton recognising $L$. Hence the growth series of an automatic group is
computable, given a geodesic automatic structure.

Reduction of an input word to the “normal form” defined by the language $L$ of
the automatic structure for $G$ can be performed using a combination of the
word acceptor and multiplier automata, or alternatively using the word
difference machine.

Finiteness of otherwise of an automatic group is immediately recognisable from
a word acceptor for an automatic structure; the language is infinite precisely
when the automaton admits loops. In this way, the Heineken group $G=\langle
x,y,z\mid[x,[x,y]]=z,\,[y,[y,z]]=x,\,[z,[z,x]]=y\rangle$ was proved infinite,
by Holt using kbmag; computation with the automatic structure subsequently
revealed the group to be hyperbolic. Previously that group had been proposed
as a possible example of a finite group with a balanced presentation.
Similarly, a second proof of the infiniteness of the Fibonacci group $F(2,9)$
was provided by the construction of an automatic structure for it [41].

Tests for hyperbolicity [75, 27] that make use of automatic structures for $G$
together with Papasoglu’s characterisation of hyperbolic groups have already
been described in Section 2.3.2. The second of those is implemented in kbmag,
as is an algorithm [27] estimating the thinness constant (related to, but not
equal to, the slimness constant) for geodesic triangles in the Cayley graph of
a word hyperbolic group.

Quadratic and linear time solutions to the conjugacy problem in a hyperbolic
group are described in [15] and [28, 17]. A practical cubic time solution that
restricts to infinite order elements is due to Marshall [58], using some ideas
from Swenson, and has been implemented in the GAP system.

##  4 Group actions and negative curvature

One of the basic principles of geometric group theory is generally referred to
as the the Milnor–S̆varc lemma:

If a group $G$ has a “nice” (properly discontinuous and cocompact) discrete,
isometric action on a metric space ${\mathcal{X}}$ then its Cayley graph is
quasi-isometric to ${\mathcal{X}}$. In particular a group with such an action
on a $\delta$-hyperbolic space is word hyperbolic.

A variety of results derive automaticity or biautomaticity of a group from its
“nice” actions on spaces in which some kind of non-positive curvature can be
found.

######  Theorem 4.1 (Gersten, Short, 1990, 1991 [34, 35]).

A group acting discretely and fixed point freely on a piecewise Euclidean
2-complex of type $A_{1}\times A_{1}$, $A_{2}$, $B_{2}$ or $G_{2}$
(corresponding to tesselations of the Euclidean plane by squares, equilateral
triangles, or triangles with angles $(\pi/2,\pi/4,\pi/4)$ or
$(\pi/2,\pi/3,\pi/6)$) is biautomatic.

As a consequence of the above results, and within the same two articles,
Gersten and Short deduce that groups satisfying any of the small cancellation
conditions C(7) or else T(p) and T(q) with
$(p,q)\in\\{(3,7),\,(4,5),\,(5,4)\\}$ (defined in [57]) are hyperbolic, and
hence in particular biautomatic, and then that groups satisfying the small
cancellation conditions C(6), or C(4) and T(4), or C(3) and T(6) are
biautomatic.

A geodesic metric space ${\mathcal{X}}$ is defined to be CAT(0) if for any
geodesic triangle in the space, and for any two points $p,q$ on the sides of
that triangle, the distance between $p$ and $q$ in ${\mathcal{X}}$ is no more
than the distance between the points in corresponding positions on the sides
of a geodesic triangle with the same side lengths in the Euclidean plane, as
illustrated in Figure 5. A complete CAT(0) space is often called a Hadamard
space. A group is called CAT(0) if it acts properly and cocompactly on a
CAT(0) space.

$p$$q$$r$$p^{\prime}$$q^{\prime}$$d$$p$$q$$r$$p^{\prime}$$q^{\prime}$$\leq d$
Figure 5: Comparable triangles in Euclidean and CAT(0) spaces

The CAT(-1) condition is defined similarly with respect to the hyperbolic
plane; any CAT(-1) space is $\delta$-hyperbolic, for some $\delta$, and hence
CAT(-1) groups are word hyperbolic.

A (not necessarily geodesic) metric space $(X,d)$ is said to have non-positive
curvature (or curvature $\leq 0$) if every point of $X$ is contained in a
CAT(0) neighbourhood. By the Cartan-Hadamard theorem [14] the universal cover
of a complete connected space of non-positive curvature is CAT(0).

Niblo and Reeves studied in particular groups acting on CAT(0) cube complexes:

######  Theorem 4.2 (Niblo, Reeves 1998 [64]).

A group acting faithfully, properly discontinuously and cocompactly on a
simply connected and non-positively curved cube complex is biautomatic.

A cube complex is defined to be a metric polyhedral complex in which each cell
is isometric to the Euclidean cube with side lengths 1, where the gluing maps
are isometries. Such a complex is non-positively curved provided that it
contains at most one edge joining any two vertices, and no triangles of edges,
and (by a result of Gromov [37]) is CAT(0) if non-positively curved and simply
connected.

Actions of Coxeter groups on CAT(0) cube complexes are constructed in [65],
but are not necessarily cocompact. However in some cases it follows from those
or related constructions that the Coxeter groups are biautomatic (see Section
5.2).

There are many open problems relating to CAT(0) groups (see for example [32]).
The question of whether every CAT(0) group must be biautomatic was recently
resolved in the negative by Leary and Minasyan [56], who constructed an
example of a 3-dimensional CAT(0) group which could admit no biautomatic
subgroup of finite index. It is still unknown whether non-automatic CAT(0)
groups can exist.

However a restricted class of CAT(0) groups is provided by groups that act
geometrically on CAT(0) spaces with isolated flats. A $k$-flat in a CAT(0)
space is an isometrically embedded copy of Euclidean space ${\mathbb{R}}^{k}$.
This family contains a number of interesting examples, including geometrically
finite Kleinian groups, the fundamental groups of various compact manifolds,
and limit groups, arising from the solutions of equations over free groups.
Groups of this type are studied in [48], where more details (of definition and
examples) can be found. Theorem 1.2.2 of that article establishes a number of
properties of such groups, including their biautomaticity.

A form of non-positive curvature in simplicial complexes is defined in [52]: a
flag simplicial complex ${\mathcal{X}}$ is called $k$-systolic if connected,
simply connected and locally $k$-large (no minimal $\ell$-cycle with
$3<\ell<k$ in the link of a vertex). A group is called $k$-systolic if it acts
simplicially, properly discontinuously and cocompactly on a $k$-systolic
simplical complex, and is called systolic if 6-systolic.

######  Theorem 4.3 (Januszkiewicz, Swiatkowski, 2006 [52]).

7-systolic groups are hyperbolic, 6-systolic groups are biautomatic.

This result is used to prove biautomaticity of a large class of Artin groups
[49], as detailed in Section 5.1.

A Helly graph is a graph in which every family of pairwise intersecting balls
has a non-empty intersection. A group is called Helly if it acts properly and
cocompactly by graph automorphisms on a Helly graph; word hyperbolic groups,
CAT(0) cubical groups and C(4)-T(4) small cancellation groups are all
examples. It is proved in [22] that all Helly groups are biautomatic. This
result is used to prove biautomaticity of another large class of Artin groups
[50], as detailed in Section 5.1.

##  5 Some automatic and biautomatic families

Over a period of more than 30 years, automatic and biautomatic structures were
found for various families of groups, including braid groups, many Artin
groups, mapping class groups, and Coxeter groups. But some questions remain
open for these families.

###  5.1 Braid groups, Artin groups and Mapping Class groups

Automatic structures for the braid group $B_{n}$ on $n$ strands and also for
the (closely related) mapping class group of the $(n+1)$-punctured sphere were
constructed by Thurston and are described in [26]; one of the structures
described for the braid groups is symmetric, proving the braid groups to be
biautomatic. The automaticity (but not necessarily biautomaticity) of the
mapping class group of the $n+1$-punctured sphere then follows from the fact
that it contains the quotient of the braid group $B_{n}$ by its centre as a
subgroup of index $n+1$.

The braid group on $n+1$ strands is isomorphic to the Artin group of finite
type $A_{n}$. We recall that an Artin group is a group defined by a
presentation of the form

$\langle x_{1},x_{2},\cdots,x_{n}\mid\overbrace{x_{i}x_{j}x_{i}\cdots}^{{\sf
m_{ij}}}=\overbrace{x_{j}x_{i}x_{j}\cdots}^{{\sf m_{ij}}},\,i\neq
j\in\\{1,2,\ldots,n\\}\rangle,$

relating to a symmetric, integer Coxeter matrix $({\sf m_{ij}})$, or
equivalently a Coxeter diagram $\Gamma$ on $n$ vertices, whose edge
$\\{i,j\\}$ is labelled ${\sf m_{ij}}$, and is naturally associated with a
Coxeter group by adding relations $x_{i}^{2}=1$ for each $i$. The Artin group
has finite type if the associated Coxeter group is finite (and hence $\Gamma$
is a disjoint union of diagrams from the well–known list of spherical Coxeter
diagrams).

In [23], Charney used results of Deligne to extend Thurston’s construction for
the braid groups to all finite type Artin groups. Charney’s construction
provided biautomatic structures for all finite type Artin groups; these
biautomatic structures were geodesic over the “Garside” generating sets, but
not over the standard generators $x_{i}$. Biautomatic structures for all
Garside groups (of which finite type Artin groups are examples) were described
by Dehornoy [25].

For Artin groups of FC type (free products of finite type groups with
amalgamation over parabolic subgroups, for which the complete subgraphs of the
labelled graph formed by deleting all $\infty$-labelled edges from $\Gamma$
are all of finite type), asynchronously automatic structures were constructed
in [4], and used to define quadratic time solutions to the word problem; we
recall that an exponential (rather then quadratic) time solution is guaranteed
by asynchronous automaticity. Right-angled Artin groups (those for which all
the parameters ${\sf m_{ij}}$ are within the set $\\{2,\infty\\}$, which form
a subset of FC type) were then proved automatic in [40, 74]. Very recently
[50] Artin groups of FC type have been proved to be Helly, and hence
biautomatic.

Mosher’s paper [60] answered a major open question raised by Thurston’s proof
of the automaticity of the mapping class group of the punctured sphere. Using
quite different techniques from Thurston, Mosher proved automaticity of the
mapping class group of any surface of finite type, that is, the group of
(orientation preserving) homeomorphisms modulo isotopy of any surface obtained
from a compact surface by removing at most finitely many points. In the case
of a surface with at least one puncture the automatic structure is explicitly
defined (and could be constructed), in terms of a complex whose vertices are
ideal triangulations on S (triangulations with vertex set the puncture set)
and whose edges are elementary moves between ideal triangulations. The more
general case can be reduced to the case of a punctured surface using a short
exact sequence. The question of whether the mapping class group was in fact
biautomatic was finally solved by Hamenstaedt’s construction of a biautomatic
structure in 2009 [38].

An Artin group is defined to have large type if all the associated parameters
${\sf m_{ij}}$ are at least 3, extra large type if all ${\sf m_{ij}}$ are at
least 4. For large and especially extra large groups small cancellation
techniques associated with negatively curved geometry were developed in [6].
All extra large Artin groups were proved biautomatic in [68], using those
small cancellation techniques; the language is a set of geodesics over the
standard generating set. All those groups and many others of large type were
found by Brady and McCammond [11] to act appropriately on piecewise Euclidean
non-positively curved 2-complexes of types $A_{2}$ or $B_{2}$, and hence, by
results of [34, 35] to be biautomatic (but in this case the biautomatic
structure is defined over a non-standard generating set).

All Artin groups of large type were proved to be shortlex automatic over their
standard generating sets in [44]. A rewrite system was described, which
rewrote any word to shortlex geodesic form using sequences of moves on
2-generator substrings. The result extended beyond large type to sufficiently
large type, where some parameters ${\sf m_{ij}}$ might take the value $2$
(provided that for any triple $i,j,k$, if ${\sf m_{ij}}=2$, then either ${\sf
m_{ik}}={\sf m_{jk}}=2$ or at least one of ${\sf m_{ik}}$ and ${\sf m_{jk}}$
is infinite). Biautomatic structures for all large type Artin groups (and in
fact for the slightly large class of almost large groups) were proved to exist
in [49], where all those groups were proved to have appropriate actions on
systolic complexes. An Artin group is called almost large if for any triple
$i,j,k$ it is only possible to have ${\sf m_{ij}}=2$ if one of ${\sf m_{ik}}$
or ${\sf m_{jk}}$ is infinite, and for any 4-set $i,j,k,l$ at most 2 of ${\sf
m_{ij}}$, ${\sf m_{jk}}$, ${\sf m_{kl}}$, ${\sf m_{il}}$ can be equal to 2
unless one of the four parameters is infinite.

###  5.2 Coxeter groups

The proof in [16] of shortlex automaticity of any Coxeter group relative to
its standard generating set provided a result that had long been conjectured.
We recall that a Coxeter group $W$ is described by a presentation

$\langle x_{1},\ldots,x_{n}\mid x_{i}^{2}=1,\,(x_{i}x_{j})^{{\sf
m_{ij}}}=1,\,i\neq j\in\\{1,\ldots,n\\}\rangle,$

relative to a Coxeter matrix $({\sf m_{ij}})$ and associated Coxeter diagram
$\Gamma$; the set $X=\\{x_{1},\ldots,x_{n}\\}$ is its standard generating set.

The proof of the theorem constructs an automatic structure for $W$ using
properties of its associated root system, which arises from the natural
isomorphism between $W$ and a reflection group $\overline{W}$ as we now
describe; more details can be found in [51]. The group $\overline{W}$ is
generated by a set of reflections $r_{1},\ldots,r_{n}$ of ${\mathbb{R}}^{n}$
defined by $r_{i}(v):=v-2\langle v,e_{i}\rangle e_{i}$, for
$v\in{\mathbb{R}}^{n}$, where $e_{i}:i=1,\ldots,n$ is a basis for
${\mathbb{R}}^{n}$ and $\langle,\rangle$ is the symmetric, bilinear form on
${\mathbb{R}}^{n}$ defined by $\langle e_{i},e_{j}\rangle=-\cos(\pi/{\sf
m_{ij}})$. The isomorphism from $W$ to $\overline{W}$ maps $x_{i}$ to $r_{i}$,
and induces an action of $W$ on ${\mathbb{R}}^{n}$. The roots of $W$ are
defined to be the elements of the set $\Phi=W\\{e_{1},\ldots,e_{n}\\}$, which
decomposes as a disjoint union $\Phi^{+}\cup\Phi^{-}$ of positive roots
(vectors $\sum\lambda_{i}e_{i}$ with all $\lambda_{i}\geq 0$) and their
negatives.

Brink and Howlett’s proof of regularity of the set of shortlex geodesic words
in $W$ is derived from their proof in [16] of the finiteness of the set of
positive roots for $W$ that dominate any given positive root; a positive root
$\alpha$ is said to dominate a second positive root $\beta$ if whenever
$w(\alpha)$ is negative, for $w\in W$, then so is $w(\beta)$. We define
$\widetilde{\Delta}_{W}$ to be the set of positive roots that dominate no
others. Then a word acceptor ${\sf WA}$ for a shortlex automatic structure for
$W$ can be built whose accepting states are all subsets of
$\widetilde{\Delta}_{W}$ [16, Proposition 3.3].

The transitions in ${\sf WA}$ are determined by the following observation from
[16, Lemma 3.1]. When $w=x_{i_{1}}\cdots x_{i_{l}}$ is a shortlex geodesic
word representing an element of $W$ then, for $x_{i}\in X$, the word
$w^{\prime}=wx_{i}$ is non-geodesic if and only if there exists
$j\in\\{1,\ldots,l\\}$ for which $e_{i}=x_{i_{l}}\cdots
x_{i_{j+1}}(e_{i_{j}})$. In the case where $w^{\prime}=wx_{i}$ is geodesic,
that fails to be shortlex minimal if and only if there exists
$j\in\\{1,\ldots,l\\}$ and a generator $x_{k}\prec x_{i_{j}}$ for which
$e_{i}=x_{i_{l}}\cdots x_{i_{j}}(e_{k})$. In that case the word
$x_{i_{1}}\cdots x_{i_{j-1}}x_{k}x_{i_{j}}\cdots x_{i_{l}}$ is shortlex
minimal. Based on these two facts, transition on a generator $x_{i}$ from (the
state corresponding to) a subset $S$ of $\widetilde{\Delta}_{W}$ is to a
failure state $F$ if $e_{i}\in S$. But for $e_{i}\not\in S$, transition is to
the intersection with $\widetilde{\Delta}_{W}$ of the set

$S^{\prime\prime}=\\{x_{i}(\alpha)\mid\alpha\in
S\\}\cup\\{e_{i}\\}\cup\\{x_{i}(e_{k})\mid x_{k}\prec x_{i}\\}.$

A similar construction to the above, described in [47], proves regularity of
the set of all geodesic words in $G$ over $S$.

The question of whether all Coxeter groups are not just automatic but actually
biautomatic remains open. Work of Niblo and Reeves [65] shows that any
finitely generated Coxeter group $G$ acts properly discontinuously by
isometries on a locally finite, finite dimensional CAT(0) cube complex; their
construction is based on the root system $\Phi$ associated with $G$, and an
extension of the dominance relation of [16] from $\Phi^{+}$ to $\Phi$. When
the action of $G$ on the cube complex is cocompact, then biautomaticity
follows, using [64]. Cocompact actions are proved in [65] to exist whenever
$G$ is right-angled or word hyperbolic (by [62] word hyperbolicity of $G$ is
recognisable from the diagram $\Gamma$). It is also observed in [65] that, by
[76], cocompact actions are guaranteed whenever $G$ contains only finitely
many conjugacy classes of subgroups isomorphic to rank 3 parabolic subgroups
$\langle x_{i},x_{j},x_{k}\rangle$ (associated with rank 3 subdiagrams
$\Gamma_{ijk}$ of $\Gamma$) for which ${\sf m_{ij}},{\sf m_{ik}},{\sf m_{jk}}$
are all finite; [21] used this result to derive biautomaticity of $G$ provided
that $\Gamma$ contains no affine subdiagram of rank 3 or more. Subsequently,
Caprace [20] proved biautomaticity of all relatively hyperbolic Coxeter groups
using results from [48].

The dimension of a Coxeter group is defined to be the dimension of its Davis
complex, equivalently the maximal rank of any of its spherical parabolic
subgroups. It follows that a Coxeter group is 2-dimensional if none of the
rank 3 subdiagrams $\Gamma_{ijk}$ is spherical, equivalently if for all
$i,j,k$, $\frac{1}{{\sf m_{ij}}}+\frac{1}{{\sf m_{ik}}}+\frac{1}{{\sf
m_{jk}}}\leq 1$. The biautomaticity of all 2-dimensional Coxeter groups is
proved in [63]. The construction of a geodesic language generalises ideas from
[65], and the result generalises an earlier result proving biautomaticity for
certain 2-dimensional groups that used the results of [65].

##  6 Open problems

More than 30 years after the subject started there continue to be many open
problems involving automatic groups. Some of these problems date from the
beginning of the subject, and are listed in [26]. Some but not all of these
have been mentioned within this chapter. In particular, it remains open
whether automatic groups exist that are not biautomatic (see Section 2) also
whether automatic groups exist that do not have soluble conjugacy problem (see
Section 2.2) , whether all soluble automatic groups must be virtually abelian.
The most recent progress on this last question was made by the proof of
Romankov [69], that a soluble biautomatic group must be virtually abelian (see
Section 2.3.1).

It is still unknown whether a non-biautomatic Coxeter group can exist (Section
5.2), or a non-automatic Artin group (Section 5.1).

There are many open problems relating to group actions, in particular, whether
a CAT(0) group must be automatic. The very recent construction in [56] of a
3-dimensional CAT(0) group that cannot be biautomatic (Section 4) represents a
major advance on this problem; it does not resolve the question of
automaticity. The question of whether biautomaticity or automaticity are
implied for a 2-dimensional, piecewise Euclidean CAT(0) group remains open
(but we note the recent contribution to this problem of the main result of
[63], see Section 5.2). The 2-dimensional problem is number 43 on a list of
open problems within geometric group theory that was published ten years ago
in [32], and motivated a body of research, and rapid solution of some of the
problems. However, some of the problems listed in this useful and extensive
list, or in the earlier list [8], remain open.

## References

  * [1] A.V. Aho, Indexed grammars – an extension of context-free grammars, Assoc. Comput. Mach. 15 (1968) 647–671.
  * [2] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro and H. Short, Notes on word-hyperbolic groups, Proc. Conf. Group Theory from a Geometrical Viewpoint, eds. E. Ghys, A. Haefliger and A. Verjovsky, held in I.C.T.P., Trieste, March 1990, World Scientific, Singapore, 1991.
  * [3] J. Alonso, M.R. Bridson, Semihyperbolic groups, Proc. London Math. Soc. (3) 70 (1995), no. 1, 56–114.
  * [4] J.A. Altobelli, The word problem for Artin groups of FC type. J. Pure Appl. Algebra 129 (1998), no. 1, 1–22.
  * [5] Y. Antolin, L. Ciobanu, Finite generating sets of relatively hyperbolic groups and applications to geodesic languages, International Journal of Algebra and Computation 11 (2001) No. 04, 467–487.
  * [6] K.I. Appel, P.E. Schupp, Artin groups and infinite Coxeter groups. Invent. Math. 72 (1983), no. 2, 201–220.
  * [7] G. Baumslag, S.M. Gersten, M. Shapiro, H.B. Short, Automatic groups and amalgams. J. Pure Appl. Algebra 76 (1991), no. 3, 229–316.
  * [8] M. Bestvina, Questions in geometric group theory,
http://www.math.utah.edu/b̃estvina/eprints/questions-updated.pdf

  * [9] B.H. Bowditch, Relatively hyperbolic groups, Internat. J. Algebra Comput. 22 (2012) no. 3, 1250016, 66pp.
  * [10] N. Brady, Sol geometry groups are not asynchronously automatic. Proc. London Math. Soc. (3) 83 (2001) no. 1, 93–119.
  * [11] T. Brady, J. McCammond, Three-generator Artin groups of large type are biautomatic. J. Pure Appl. Algebra 151 (2000), no. 1, 1–9.
  * [12] M.R. Bridson, Combings of groups and the grammar of reparameterization. Comment. Math. Helv. 78 (2003), no. 4, 752–771.
  * [13] M.R. Bridson, R.H. Gilman, Formal language theory and the geometry of 3-manifolds. Comment. Math. Helv. 71 (1996), no. 4, 525–555.
  * [14] M.R. Bridson, A. Haefliger, Metric spaces of non-positive curvature, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 319. Springer-Verlag, Berlin, 1999. xxii+643pp.
  * [15] M.R. Bridson, J. Howie, Conjugacy of finite subsets in hyperbolic groups, Internat. J. Algebra Comput. 15 (2005), no. 4, 725–756.
  * [16] B. Brink, R.B. Howlett, A finiteness property and an automatic structure for Coxeter groups. Math. Ann. 296 (1993), no. 1, 179–190.
  * [17] D.J. Buckley, D.F. Holt, The conjugacy problem in hyperbolic groups for finite lists of group elements. Internat. J. Algebra Comput. 23 (2013), no. 5, 1127–-1150.
  * [18] J.W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups, Geom. Dedicata 16 (1984) 123–148.
  * [19] J.W. Cannon, Max Dehn and the word problem, Max Dehn: Polymathis mathematician. Edited by J. Lorenat, J. Mccleary, D. Rowe, M. Senechal, ed. AMS, to appear.
  * [20] P.-E. Caprace, Buildings with isolated subspaces and relatively hyperbolic Coxeter groups, Innov. Incidence Geom. 10 (2009) 15–31.
  * [21] P.-E. Caprace, B. Mühlherr,Reflection triangles in Coxeter groups and biautomaticity, J Group Theory 8 (2005), no 4, 467–489.
  * [22] J. Chalopin, V. Chepo, A. Genevois, H. Hirai, D. Osajda, Helly groups, arXiv:2002.06895
  * [23] R. Charney, Artin groups of finite type are biautomatic. Math. Ann. 292 (1992), no. 4, 671–683.
  * [24] F. Dahmani, V. Guirardel, The isomorphism problem for all hyperbolic groups, Geom. Funct. Anal. 21 (2011), no. 2, 223–300.
  * [25] P. Dehornoy, Groupes de Garside, Ann. Sci. Ecole Norm. Sup. (4) 35 (2002), no. 2, 267–306.
  * [26] D.B.A. Epstein, J.W. Cannon, D.F. Holt, S. Levy, M.S. Patterson, W.P. Thurston, Word processing in groups, Jones and Bartlett, 1992.
  * [27] D.B.A. Epstein, D.F. Holt, Computation in word hyperbolic groups, International Journal of Algebra and Computation 11 (2001) No. 04, 467–487.
  * [28] D.B.A. Epstein, D.F. Holt, The linearity of the conjugacy problem in word-hyperbolic groups, Internat. J. Algebra Comput. 16 (2006), no. 2, 287–-305.
  * [29] D.B.A. Epstein, D.F. Holt, S.E. Rees, The use of Knuth–Bendix methods to solve the word problem in automatic groups, J. of Symbolic Computation, 12 (1991), 397–414.
  * [30] D.B.A. Epstein, private communication.
  * [31] B. Farb, Automatic groups: a guided tour. Enseign. Math. (2) 38 (1992), no. 3-4, 291–-313.
  * [32] B. Farb, C. Hruska, A. Thomas, Problems on automorphism groups of nonpositively curved polyhedral complexes and their lattices. Geometry, rigidity, and group actions, 515–-560, Chicago Lectures in Math., Univ. Chicago Press, Chicago, IL, 2011.
  * [33] The GAP Group. GAP — Groups, Algorithms, and Programming, Version 4.8.10, 2018\. `(http://www.gap-system.org)`.
  * [34] S.M. Gersten, H.B. Short, Small cancellation theory and automatic groups, Invent. Math. 102 (1990), no. 2, 305–334.
  * [35] S.M. Gersten, H.B. Short, Small cancellation theory and automatic groups. II, Invent. Math. 105 (1991), no. 3, 641–662.
  * [36] R.H. Gilman, Groups with a rational cross-section, Combinatorial group theory and topology (Alta, Utah, 1984), 175–183, Ann. of Math. Stud., 111, Princeton Univ. Press, Princeton, NJ, 1987.
  * [37] M. Gromov, Hyperbolic groups, Essays in group theory, 75–263, Math. Sci. Res. Inst. Publ., 8, Springer, New York, 1987.
  * [38] U. Hamenstaedt, Geometry of the mapping class group II: A biautomatic structure, arXiv:0912.0137
  * [39] A. Harkins, Combing lattices of soluble Lie groups, PhD thesis, University of Newcastle, 2001.
  * [40] S. Hermiller and J. Meier, Algorithms and geometry for graph products of groups, J. Alg. 171 (1995), 230–257.
  * [41] D.F. Holt, An alternative proof that the Fibonacci group F(2,9) is infinite. Experiment. Math. 4 (1995), no. 2, 97–100.
  * [42] D.F. Holt, The Warwick automatic groups software, Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), 69–82, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 25, Amer. Math. Soc., Providence, RI, 1996.
  * [43] D.F. Holt, provate communication.
  * [44] D.F. Holt, S. Rees, Shortlex automaticity and geodesic regularity in Artin groups, Groups, Complex. Cryptol. 5 (2013) 1–23.
  * [45] D.F. Holt, S. Rees,C.E. Röver, Groups, Languages and Automata, LMS Student Texts 88, Cambridge University Press. London 2017.
  * [46] J.E. Hopcroft, J.D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.
  * [47] R.B. Howlett, Miscellaneous facts about Coxeter groups, Lectures given at the ANU Group Actions Worshop, October 1993, Research Report 93-38.
  * [48] G.C. Hruska, B. Kleiner, Hadamard spaces with isolated flats, Geom. Top. 9 (2005) 1501–1538.
  * [49] J. Huang, D. Osajda, Large-type Artin groups are systolic. Proc. Lond. Math. Soc. (3) 120 (2020), no. 1, 95–123.
  * [50] J. Huang, D. Osajda, Helly meets Garside and Artin, arXiv:1904.09060
  * [51] J.E. Humphreys, Reflection groups and Coxeter groups, Cambridge Studies in Advanced Mathematics 29, CUP, Cambridge, 1990.
  * [52] T. Januszkiewicz and J. Świa̧tkowski, Simplicial nonpositive curvature, Publ. Math. Inst. Hautes Etudes Sci. No. 104 (2006), 1–85.
  * [53] D.L. Johnson, Presentations of Groups, LMS Student Texts 15, CUP 1990, Cambridge.
  * [54] D.F. Holt, KBMAG—Knuth–Bendix in Monoids and Automatic Groups, software package (1995), available from `(http://homepages.warwick.ac.uk/~mareg/download/kbmag2/)`
  * [55] U. Lang, Quasigeodesics outside horoballs. Geom. Dedicata 63 (1996), no. 2, 205–215.
  * [56] I. Leary, A. Minasyan, Commensurating HNNextensions: nonpositive curvature and biautomaticity, arXiv:1907.03515
  * [57] R.C. Lyndon, P.E. Schupp, Combinatorial group theory. Reprint of the 1977 edition. Classics in Mathematics. Springer-Verlag, Berlin, 2001.
  * [58] J. Marshall, Computational problems in hyperbolic groups, Internat. J. Algebra Comput. 15 (2005), no. 1, 1–13.
  * [59] Magma Computational Algebra System version 2.26-8, available at http://magma.maths.usyd.edu.au/magma/
  * [60] L. Mosher, Mapping class groups are automatic, Ann. of Math., 142 (1995) no. 2, 303–384.
  * [61] L. Mosher, Central quotients of biautomatic groups, Comment. Math. Helv., 72, (1997) no. 1, 16–29.
  * [62] G. Moussong, Hyperbolic Coxeter groups, PhD thesis, Ohio State University 1988.
  * [63] Z. Munro, D. Osajda, P. Przytycki, 2-dimensional Coxeter groups are biautomatic, arXiv:2006.07947
  * [64] G.A. Niblo, L.D. Reeves, The geometry of cube complexes and the complexity of their fundamental groups, Topology 37 (1998), 621–633.
  * [65] G.A. Niblo, L.D. Reeves, Coxeter groups act on CAT(0) cube complexes. J. Group Theory 6 (2003), no. 3, 399–413.
  * [66] D. Osin, Relatively hyperbolic groups: intrinsic geometry, algebraic properties, and algorithmic problems, Mem. Amer. Math. Soc. 179 (2006), no. 843.
  * [67] P. Papasoglu, Strongly geodesically automatic groups are hyperbolic. Invent. Math. 121 (1995), no. 2, 323–334.
  * [68] D. Peifer, Artin groups of extra-large type are biautomatic. J. Pure Appl. Algebra 110 (1996), no. 1, 15–56.
  * [69] V. Romankov, Polycyclic, metabelian or soluble of type $(FP)_{\infty}$ groups with Boolean algebra of rational sets and biautomatic soluble groups are virtually abelian, Glasg. Math. J. 60 (2018), no. 1, 209–218.
  * [70] Z. Sela, The isomorphism problem for hyperbolic groups. I, Ann. of Math. (2) 141 (1995), no. 2, 217–283.
  * [71] H.B. Short, Groups and combings,
https://www.i2m.univ-amu.fr/ short/Papers/bicomball.pdf

  * [72] W.P. Thurston, Three-dimensional manifolds, Kleinian groups and hyperbolic geometry, Bull. Amer. Math. Soc. (NS) 6(3) (1982) 357–381.
  * [73] W.P. Thurston, Three-dimensional geometry and topology, Princeton University Press, Princeton 1997.
  * [74] L.A. VanWyk, Graph groups are biautomatic, J. Pure Appl. Algebra 94 (1994), no. 3, 341–352.
  * [75] P. Wakefield, Procedures for automatic groups, PhD thesis, University of Newcastle 1998.
  * [76] B.T. Williams, Two topics in geometric group theory, PhD thesis, University of Southampton, 1999.
  * [77] R. Young, The Dehn function of ${\mathrm{SL}}(n;{\mathbb{Z}})$, Ann. of Math. (2) 177 (2013), no. 3, 969–1027.


org33Dipartimento Interateneo di Fisica ‘M. Merlin’ and Sezione INFN, Bari,
Italy

org34Division of Experimental High Energy Physics, University of Lund, Lund,
Sweden

org35Eberhard Karls Universität Tübingen, Tübingen, Germany

org36European Organization for Nuclear Research (CERN), Geneva, Switzerland

org37Excellence Cluster Universe, Technische Universität München, Munich,
Germany

org38Faculty of Engineering, Bergen University College, Bergen, Norway

org39Faculty of Mathematics, Physics and Informatics, Comenius University,
Bratislava, Slovakia

org40Faculty of Nuclear Sciences and Physical Engineering, Czech Technical
University in Prague, Prague, Czech Republic

org41Faculty of Science, P.J. Šafárik University, Košice, Slovakia

org42Faculty of Technology, Buskerud and Vestfold University College,
Vestfold, Norway

org43Frankfurt Institute for Advanced Studies, Johann Wolfgang Goethe-
Universität Frankfurt, Frankfurt, Germany

org44Gangneung-Wonju National University, Gangneung, South Korea

org45Gauhati University, Department of Physics, Guwahati, India

org46Helsinki Institute of Physics (HIP), Helsinki, Finland

org47Hiroshima University, Hiroshima, Japan

org48Indian Institute of Technology Bombay (IIT), Mumbai, India

org49Indian Institute of Technology Indore, Indore (IITI), India

org50Inha University, Incheon, South Korea

org51Institut de Physique Nucléaire d’Orsay (IPNO), Université Paris-Sud,
CNRS-IN2P3, Orsay, France

org52Institut für Informatik, Johann Wolfgang Goethe-Universität Frankfurt,
Frankfurt, Germany

org53Institut für Kernphysik, Johann Wolfgang Goethe-Universität Frankfurt,
Frankfurt, Germany

org54Institut für Kernphysik, Westfälische Wilhelms-Universität Münster,
Münster, Germany

org55Institut Pluridisciplinaire Hubert Curien (IPHC), Université de
Strasbourg, CNRS-IN2P3, Strasbourg, France

org56Institute for Nuclear Research, Academy of Sciences, Moscow, Russia

org57Institute for Subatomic Physics of Utrecht University, Utrecht,
Netherlands

org58Institute for Theoretical and Experimental Physics, Moscow, Russia

org59Institute of Experimental Physics, Slovak Academy of Sciences, Košice,
Slovakia

org60Institute of Physics, Academy of Sciences of the Czech Republic, Prague,
Czech Republic

org61Institute of Physics, Bhubaneswar, India

org62Institute of Space Science (ISS), Bucharest, Romania

org63Instituto de Ciencias Nucleares, Universidad Nacional Autónoma de México,
Mexico City, Mexico

org64Instituto de Física, Universidad Nacional Autónoma de México, Mexico
City, Mexico

org65iThemba LABS, National Research Foundation, Somerset West, South Africa

org66Joint Institute for Nuclear Research (JINR), Dubna, Russia

org67Konkuk University, Seoul, South Korea

org68Korea Institute of Science and Technology Information, Daejeon, South
Korea

org69KTO Karatay University, Konya, Turkey

org70Laboratoire de Physique Corpusculaire (LPC), Clermont Université,
Université Blaise Pascal, CNRS–IN2P3, Clermont-Ferrand, France

org71Laboratoire de Physique Subatomique et de Cosmologie, Université
Grenoble-Alpes, CNRS-IN2P3, Grenoble, France

org72Laboratori Nazionali di Frascati, INFN, Frascati, Italy

org73Laboratori Nazionali di Legnaro, INFN, Legnaro, Italy

org74Lawrence Berkeley National Laboratory, Berkeley, California, United
States

org75Moscow Engineering Physics Institute, Moscow, Russia

org76Nagasaki Institute of Applied Science, Nagasaki, Japan

org77National Centre for Nuclear Studies, Warsaw, Poland

org78National Institute for Physics and Nuclear Engineering, Bucharest,
Romania

org79National Institute of Science Education and Research, Bhubaneswar, India

org80Niels Bohr Institute, University of Copenhagen, Copenhagen, Denmark

org81Nikhef, Nationaal instituut voor subatomaire fysica, Amsterdam,
Netherlands

org82Nuclear Physics Group, STFC Daresbury Laboratory, Daresbury, United
Kingdom

org83Nuclear Physics Institute, Academy of Sciences of the Czech Republic, Řež
u Prahy, Czech Republic

org84Oak Ridge National Laboratory, Oak Ridge, Tennessee, United States

org85Petersburg Nuclear Physics Institute, Gatchina, Russia

org86Physics Department, Creighton University, Omaha, Nebraska, United States

org87Physics Department, Panjab University, Chandigarh, India

org88Physics Department, University of Athens, Athens, Greece

org89Physics Department, University of Cape Town, Cape Town, South Africa

org90Physics Department, University of Jammu, Jammu, India

org91Physics Department, University of Rajasthan, Jaipur, India

org92Physik Department, Technische Universität München, Munich, Germany

org93Physikalisches Institut, Ruprecht-Karls-Universität Heidelberg,
Heidelberg, Germany

org94Purdue University, West Lafayette, Indiana, United States

org95Pusan National University, Pusan, South Korea

org96Research Division and ExtreMe Matter Institute EMMI, GSI Helmholtzzentrum
für Schwerionenforschung, Darmstadt, Germany

org97Rudjer Bošković Institute, Zagreb, Croatia

org98Russian Federal Nuclear Center (VNIIEF), Sarov, Russia

org99Russian Research Centre Kurchatov Institute, Moscow, Russia

org100Saha Institute of Nuclear Physics, Kolkata, India

org101School of Physics and Astronomy, University of Birmingham, Birmingham,
United Kingdom

org102Sección Física, Departamento de Ciencias, Pontificia Universidad
Católica del Perú, Lima, Peru

org103Sezione INFN, Bari, Italy

org104Sezione INFN, Bologna, Italy

org105Sezione INFN, Cagliari, Italy

org106Sezione INFN, Catania, Italy

org107Sezione INFN, Padova, Italy

org108Sezione INFN, Rome, Italy

org109Sezione INFN, Trieste, Italy

org110Sezione INFN, Turin, Italy

org111SSC IHEP of NRC Kurchatov institute, Protvino, Russia

org112Stefan Meyer Institut für Subatomare Physik (SMI), Vienna, Austria

org113SUBATECH, Ecole des Mines de Nantes, Université de Nantes, CNRS-IN2P3,
Nantes, France

org114Suranaree University of Technology, Nakhon Ratchasima, Thailand

org115Technical University of Košice, Košice, Slovakia

org116Technical University of Split FESB, Split, Croatia

org117The Henryk Niewodniczanski Institute of Nuclear Physics, Polish Academy
of Sciences, Cracow, Poland

org118The University of Texas at Austin, Physics Department, Austin, Texas,
USA

org119Universidad Autónoma de Sinaloa, Culiacán, Mexico

org120Universidade de São Paulo (USP), São Paulo, Brazil

org121Universidade Estadual de Campinas (UNICAMP), Campinas, Brazil

org122University of Houston, Houston, Texas, United States

org123University of Jyväskylä, Jyväskylä, Finland

org124University of Liverpool, Liverpool, United Kingdom

org125University of Tennessee, Knoxville, Tennessee, United States

org126University of the Witwatersrand, Johannesburg, South Africa

org127University of Tokyo, Tokyo, Japan

org128University of Tsukuba, Tsukuba, Japan

org129University of Zagreb, Zagreb, Croatia

org130Université de Lyon, Université Lyon 1, CNRS/IN2P3, IPN-Lyon,
Villeurbanne, France

org131V. Fock Institute for Physics, St. Petersburg State University, St.
Petersburg, Russia

org132Variable Energy Cyclotron Centre, Kolkata, India

org133Warsaw University of Technology, Warsaw, Poland

org134Wayne State University, Detroit, Michigan, United States

org135Wigner Research Centre for Physics, Hungarian Academy of Sciences,
Budapest, Hungary

org136Yale University, New Haven, Connecticut, United States

org137Yonsei University, Seoul, South Korea

org138Zentrum für Technologietransfer und Telekommunikation (ZTT),
Fachhochschule Worms, Worms, Germany