\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\part{Automatic and Biautomatic Groups}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In the late 1980s and early 1990s the theory of automatic groups was
rapidly developed by a number of different researchers and the basic
theory was recorded in a book and a survey article that were both
published in 1992.  These continue to be two of the main sources of
basic information about automatic groups.  The book is ``Word
processing in groups'' by David Epstein, Jim Cannon, Derek Holt,
Silvio Levy, Michael Paterson and Bill Thurston \cite{ECHLPT92}.  It
carefully defines automatic, biautomatic, asynchronously automatic,
combable, bicombable and asynchronously bicombable groups, and many
foundational results about these classes of groups appear there in
print for the first time.\footnote{The introduction also contains a
  detailed description of the early history of these concepts.}  The
survey article is ``Automatic Groups: A Guided Tour'' by Benson Farb
\cite{Fa92}.  It is a short and leisurely introduction to the theory
that surveys the basic ideas, major results, key examples and
non-examples without delving too far into the details of the proofs.
(A third source of basic information is the proceedings of the 1989
MSRI conference on algorithms in combinatorial group theory
\cite{MSRI92}, also published in 1992.)  The main drawback of these
sources is that they were published $15$ years ago, and thus their
descriptions of open problems need to be brought up to date.

Since 1990 there have been significant papers on
\begin{itemize}
\item biautomaticity and small cancellation groups (Gersten and Short \cite{GeSh90,GeSh91b}),
\item rational subgroups of biautomatic groups (Gersten and Short \cite{GeSh91a}),
\item automaticity of Coxeter groups (Brink and Howlett \cite{BrHo93}).
\item biautomaticity of finite-type Artin groups (Charney \cite{Ch95}),
\item automaticity of mapping class groups (Mosher \cite{Mo95}), 
\item central quotients of biautomatic groups (Mosher \cite{Mo97}), 
\item biautomaticity of fundamental groups of nonpositively curved
  cube complexes (Niblo and Reeves \cite{NiRe98}),
\item introduction and biautomaticity of Garside groups (Dehornoy \cite{De02}), 
\item biautomaticity of many Coxeter groups (Niblo and Reeves \cite{NiRe03})
\end{itemize}


 (via actions on cube complexes), and the 2003 paper by Martin Bridson
that finally distinguished the classes of automatic, combable and
bicombable groups \cite{Bri03}.

\mcomment{Q: Any other highpoints that I overlooked?  include Neumann-Shapiro,
and Rebecchi somewhere}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Eight Families of Groups}

Let $\Gamma$ be a connected graph with a cocompact group action.
There are eight closely-related families of groups that are defined by
the existence of such a graph $\Gamma$ together with a collection of
distinguished paths in $\Gamma$ with additional properties.  Such
properties might include that the collection be recognized by a finite
state automaton, that every path in the collection must be a
$(k,\epsilon)$-quasi-geodesic, or that the paths in the collection
that start and/or end close together must $k$-fellow travel.  The
schematic relationships among the eight families are shown in
Figure~\ref{fig:8groups} and their definitions can easily be found in
the references, particularly \cite{ECHLPT92}, except for
semi-hyperbolic groups which were only introduced by Alonso and
Bridson in 1995 \cite{AlBr95}.  For semi-hyperbolic groups,
\cite{BrHa99} is a good reference.


\begin{figure}[ht]
$\begin{CD}
\textrm{hyperbolic} @>\neq >> \textrm{biautomatic} @>?>>
\textrm{automatic} @>\neq >> \textrm{asyn. automatic}\\ 
@V\neq VV @V\neq VV @V\neq VV @V\neq VV\\
\textrm{semi-hyperbolic} @>? >> \textrm{bicombable} @>\neq >>
\textrm{combable} @>? >> \textrm{asyn. combable} 
\end{CD}$
\caption{Eight related families of groups.\label{fig:8groups}}
\end{figure}

In Figure~\ref{fig:8groups} an arrow $A\rightarrow B$ indicate that
every group of type $A$ is a group of type $B$.  Thus Gromov
hyperbolic groups are the most and asynchronously combable groups are
the less restrictive of the eight classes depicted.  The question
marks and inequality signs indicate whether or not these inclusions
are known to be strict.  Some of the counterexamples are easy.  The
group $\Z^2$ is biautomatic and semi-hyperbolic but not hyperbolic and
it is shown in \cite{ECHLPT92} that the non-solvable Baumslag-Solitar
groups are asynchronouslly automatic but not automatic.
\mcomment{Some of the other questionmarks probably have easy
  counterexamples that I am overlooking.}  For a long time it was an
open question whether combable groups were automatic or bicombable,
but in 2003 Martin Bridson gave examples of combable groups that are
not bicombable and examples of combable groups that are not automatic
\cite{Bri03}.  An asynchronously combable but not asynchronously
automatic example can be found in \cite{Bri93} and is further explored
in \cite{BrGi95} and \cite{BrGi96}.  In addition, there is a
free-by-cyclic group that a bicombable but not biautomatic group
constructed by Brady and Bridson (unpublished) and this example is not
even automatic (Bridson and Reeves, also unpublished).  At this point
there are at least three major questions along these lines that are
still wide open.

\begin{q}[Automatic vs. Biautomatic]
Is every automatic group biautomatic?
\end{q}

Most experts agree that the answer is probably no, and several
potential counterexamples have been suggested. \mcomment{add
  citations}


\begin{q}[$\cat(0)$ vs. Biautomatic]\label{q:cat-aut}
Is every $\cat(0)$ group biautomatic?
\end{q}

The class of $\cat(0)$ groups is contained in the class of
semi-hyperbolic groups and its relationship to hyperbolicity is a
well-known open problem.  Some partial positive results are discussed
below in \S\ref{sec:npc}.  The converse of Question~\ref{q:cat-aut} is
known to be false. \mcomment{add cites} The third question along these
lines is the biautomatic analog of Thurston's hyperbolization
conjecture.

\begin{q}[Hyperbolic vs. Biautomatic]
Is every biautomatic group with no $\Z\times \Z$ subgroup word
hyperbolic?
\end{q}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Basic Structural Properties}


There were two early problem collections focused on automatic groups:
one collected by Steve Gersten and published in \cite{Ge92} and the
other in Benson Farb's survey article \cite{Fa92}.  The two lists have
significant overlap, and neither seriously addresses the open
questions about the then recently invented theory of biautomatic
groups.

\comment{Finish pulling together the next several jotted notes}

The principal examples of automatic groups are finite groups,
Euclidean groups, negatively curved groups (including word-hyperbolic
groups), various small cancellation groups, Coxeter groups,
geometrically finite groups and braid groups.  Many of these

Groups that have been shown to not support an automatic structre
include infinite torsion groups, nilpotent groups that are not
virtually abelian, ${\rm SL}_n(Z)$ for $n\geq 3$, and non-solvable
Baumslag-Solitar groups.

Some of the most important properties of automatic groups are that
they are finitely presented and have solvable word problem. They are
closed under direct and free products (with finite amalgamated
subgroup) and under finite extension.

Biautomatic groups are known to have a solvable conjugacy problem,
polycyclic subgroups of biautomatic groups are abelian by finite, the
Baumslag-Solitar group $BS(1,2)$ cannot be isomorphic to a subgroup of
a biautomatic group,  and the center of a biautomatic group is always
finitely generated.

Biautomatic groups include all word hyperbolic groups, all fundamental
groups of finite volume hyperbolic and Euclidean orbifolds, the braid
groups and central extnensions of word hyperbolic groups.  


%question $7$ has an affirmative solution for biautomatic groups, Is
% this the infinite cyclic subgroup one?

Several important structural results about subgroups and quotients of
biautomatic groups were shown by Gersten and Short in \cite{GeSh91a}
and Lee Mosher in \cite{Mo97}.  Together these two papers establish
all of the following results.

\begin{thm}
If $G$ is a biautomatic group and $H$ is the centralizer in $G$ of a
finite set of elements, then $H$ is biautomatic.  If $C$ is a subgroup
of the center of $G$ then $G/C$ is biautomatic.  If $L$ is a direct
factor of $G$ then $L$ is biautomatic.  If $K$ is a polycyclic
subgroup of $G$ then $K$ is virtually abelian.  And finally, the group
$G$ does not contain any subgroups isomorphic to $BS(k,l)$ with
$|k|\neq |l|$.
\end{thm}

Combined with the foundational results shown in \cite{ECHLPT92}, we
thus know that free products, direct products, free factors and direct
factors of biautomatic groups are biautomatic.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Structural Questions}

The care that needs to be taken to distinguish between automatic and
biautomatic is illustrated by their known closure properties.  For the
most part, every closure property that is known to hold for automatic
groups, is also known to hold for biautomatic groups with one glaring
exception: every virtually automatic group (i.e. a group that contains
a finite index automatic subgroup) is itself automatic.  This is an
open question for biautomatic groups.

\begin{q}[Finite Extensions]
Is a virtually biautomatic group biautomatic?
\end{q}

With that sole exception, the rest of the questions posed here are
either open for both automatic and biautomatic groups or they are
known for biaumatic groups and open for automatic groups.

\mcomment{Any progress on these? Are any others known for
  biautomatic?}

\begin{p}[Conjugacy Problem]
Biautomatic groups are known to have a solvable conjugacy problem.
Determine whether or not every automatic group has a solvable
conjugacy problem.
\end{p}

\begin{q}[Tits alternative]
Do either automatic or biautomatic groups satisfy the Tits
alternative?  That is, does every subgroup that is not virtually
abelian contain a copy of a non-abelian free group?  \mcomment{Are
  these both still open?}
\end{q}


\begin{q}[Hopfian]\label{q:aut-hopf}
Are automatic groups Hopfian? Are biautomatic groups?
\end{q}


%GL8
\begin{q}[Center]
Is the center of an automatic group finitely generated?  Is there a
bound on the order of the torsion elements in the center?
\end{q}

The center of a biautomatic group is known to be finitely
generated. \mcomment{add cite}

\begin{q}[Retracts]
Is a retract of an automatic group automatic?  \mcomment{Known for biautomatic?}
\end{q}

%GL14
\begin{q}[Cyclic Amalgamations]
Let $G = A \ast_C B$ where $A$ and $B$ are automatic and $C$ is
infinite cyclic.  Is $G$ automatic? \mcomment{Known for biautomatic?}
\end{q}


The next four questions ask about properties of subgroups of automatic
and biautomatic groups.  

%GL16
\begin{q}[Finite-index subgroups]
Is every automatic group residually finite?  Does an automatic group
necessarily have even one nontrivial subgroup of finite index?
Similar questions can be asked about biautomatic groups.
\end{q}

%GL7
\begin{q}[Cyclic subgroups]
Let $G$ be a automatic group and let $x \in G$ be an element of
infinite order.  Is the map of the set of integers into the Cayley
graph of $G$ given by $n \mapsto x^n$ a quasi-isometry?
\end{q}

%GL4
\begin{q}[Polycyclic subgroups]
Every polycyclic subgroup of a biautomatic group and every virtuallly
nilpotent subgroup of an automatic group is virtually abelian.  Must
every polycyclic subgroup of an automatic group be virtually abelian?
\end{q}


\begin{q}[Baumslag-Solitar subgroups]
Biautomatic groups do not contain any subgroups isomorphic to
$BS(k,l)$ with $|k|\neq |l|$.  Is the same true for automatic groups?
More specifically, can an automatic group contain a $BS(1,2)$
subgroup?
\end{q}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Connections to Negative and Nonpositive Curvature}\label{sec:npc}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

There are many results that connect presence of negative or
nonpositive curvature to the existence of an automatic or biautomatic
struture.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Riemannian Manifolds}

\comment{Describe the key automaticity results about Riemannian
  manifolds (in arbitary dimensions) with strictly negative sectional
  curvature.  Include the finite volume hyperbolic and euclidean
  orbifold results, and mention the Neumann and Shapiro \cite{NeSh95}
  paper that classifies \emph{all} automatic and biautomatic
  structures on geometrically finite hyperbolic groups.}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Piecewise Euclidean Complexes}

In modern terminology, two of the main results that Gersten and Short
proved in \cite{GeSh90} and \cite{GeSh91b} are that groups that act
freely, cellularly and cocompactly on either (1) $\cat(0)$ square
complexes or (2) $\cat(0)$ triangle complexes, are biautomatic.  A
triangle complex is a simplicial $2$-complex in which every edge has
unit length and the $2$-cells are isometric to equilateral triangles.
Since {\'S}wi{\.a}tkowski \cite{Sw06} recently proved a theorem (using
what he calls regular path systems) that allows many previous theorems
proving biautomaticity that assumed the group actions on various
complexes were free to be weakened to actions that are merely proper,
the Gersten and Short results can be strengthened to assert that all
groups acting geometrically on $\cat(0)$ square complexes or on
$\cat(0)$ triangle complexes are biautomatic.

Both of these results have been generalized to higher dimensions.  The
square complex result was generalized to cube complexes by Niblo and
Reeves \cite{NiRe98}.  Combined with {\'S}wi{\.a}tkowski's results, we
now know that groups that act geometrically on $\cat(0)$ cube
complexes are biautomatic.  The triangle complex result have been
generalized by Januszkiewicz and {\'S}wi{\.a}tkowski through their
theory of simplicial non-positive curvature \cite{JaSw06}.  It is
still an open question whether the straightforward $\cat(0)$
generalization of the triangle complex result is true.

\begin{conj}\label{conj:simplicial}
If $G$ acts geometrically on a $\cat(0)$ piecewise Euclidean
simplicial complex with unit edge lengths, then $G$ is biautomatic.
\end{conj}

Recently, Rena Levitt has shown \cite{Le-biaut} that any group that
acts geometrically on a $\cat(0)$ triangle-square complex is
biautomatic.  By a triangle-square complex, I mean a piecewise
Euclidean complex with unit edge lengths in which each $2$-cell is a
triangle or a square.  This leads to the following conjecture that
would encompass cube complexes and Conjecture~\ref{conj:simplicial} as
special cases.  Call a piecewise Euclidean cell complex a
\emph{simplicial product complex} if every cell is isometric to a
direct product of regular Euclidean simplices with edges of unit
length.

\begin{conj}
If $G$ acts geometrically on a $\cat(0)$ simplicial product complex,
then $G$ should be biautomatic.
\end{conj}

Alternatively, find conditions similar to Januszkiewicz and
{\'S}wi{\.a}tkowski simplicial nonpositive curvature that ensure
biautomaticity.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Relations with Standard Classes of Groups}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Much of the recent work on automaticity and biautomaticity has been on
directed towards clarifying how these concepts interact with
well-known classes of groups.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{$3$-Manifold Groups}

\comment{Describe the geometrization-automatic results from
  \cite{ECHLPT92}.  Thurston's geometries and the no nil or sol pieces
  implies automatic.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Mapping Class Groups}

In 1995, Lee Mosher proved that all mapping class groups are automatic
\cite{Mo95}, a result that can be viewed as a vast generalization of
the automaticity of the braid groups.  This leads to an obvious
question that remains wide open.

\begin{q}[Mod(\script{S}) biautomaticity]
Are mapping class groups biautomatic?
\end{q}


Based on Mosher's result and the usual analogy between mapping class
groups and automorphisms of free groups, one might conjecture that
$\aut(\F_n)$ and $\out(\F_n)$ would at the least be automatic, but
Martin Bridson and Karen proved in \cite{BrVo95} that this is not the
case.

\begin{thm}
For $n\geq 3$ the groups $\aut(\F_n)$ and $\out(\F_n)$ do not admit a
bounded bicombing of subexponential length.  As a consequence, they
are not biautomatic, or semihyperbolic, or $\cat(0)$.
\end{thm}

\begin{q}
Is $\aut(\F_n)$ or $\out(\F_n)$ automatic?
\end{q}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Free-by-$\Z$ Groups}

A related class of groups are those that can be constructed from a
single free group automorphism.

%GL10
\begin{p}[Free-by-$\Z$ Groups]
For a finitely generated free group $\F$ and each $\phi\in \aut(\F)$,
let $G = \F \rtimes_\phi \Z$ be the corresponding mapping torus.  When
is $G$ automatic? when is $G$ biautomatic?
\end{p}

Martin and Noel have an example showing that not all are biautomatic
and then Martin and Lawrence have shown that the same example is not
automatic.  The example is the $\F_3 \rtimes_\phi \Z$ defined by the
automorphism $\phi$ sending $a\mapsto a$, $b\mapsto ba$, and $c\mapsto
ca^2$.  Gersten previously proved that this example is not
$\cat(0)$. \comment{add cites}

Note that Martin Bridson and Daniel Groves have recently been able to
show that all finitely generated free-by-$\Z$ groups have a quadratic
isoperimetric inequality.  \mcomment{add cites and other partial results}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Lattices in Lie Groups}

Two questions from the original problem lists asked about the
automaticity of lattices in specific Lie groups.  In particlular, he
asked whether every lattice in $\SL_3(\R)$ is automatic and whether
every cocompact irreducible lattice in $\isom(\hyp^2)\times
\isom(\hyp^2)$ is automatic.  Notice that this is a completely
explicit class of groups.  \comment{Cite Dave Witte-Morris}
These questions can be placed in a larger context.

\begin{p}[Lattices]
Classify which lattices in Lie groups are automatic and which ones are
biautomatic.
\end{p}

\mcomment{Ask Benson}

The original questions are still open.  Of course many non-cocompact
lattices can be immediately ruled out by the strong restrictions on
nilpotent subgroups.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Tubular Groups}

Tubular groups include several particular examples that are potential
counterexamples to other open questions.  In particular, the groups
\[G_{p,p} = \langle a,b,s,t\ |\ ab=ba, s^{-1}a^p s=a^p b, t^{-1}a^p t =
a^p b^{-1} \rangle\] have a quadratic Dehn function \cite{BraBri00}
but are not $\cat(0)$ \cite{Ge94} or biautomatic (Brady and Bridson,
unpublished), and $G_{1,1}$ at least is asynchronously automatic
\cite{El00}.

\begin{q}
Are the tubular groups $G_{p,p}$ automatic?
\end{q}

The tubular group $W=\langle a,b,s,t\ |\ ab=ba, s^{-1}as = (ab)^2,
t^{-1}bt = (ab)^2 \rangle$ is known as \emph{Wise's group}.  Dani Wise
has shown \cite{Wi96} that it is $\cat(0)$ and non-Hopfian, and Murray
Elder has found an asynchronous automatic structure on $W$
\cite{El00}.  It is unknown whether or not it is automatic.

\begin{q}[Wise's group]\label{q:wise-gp}
Is Wise's tubular group automatic?
\end{q}

Resolving this Question~\ref{q:wise-gp} in either direction would
answer an open question about automatic groups.  It either provides an
example of a $\cat(0)$ group that is not automatic
(Question~\ref{q:cat-aut}), or it provides an example of an automatic
group that is not Hopfian (Question~\ref{q:aut-hopf}).

%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Coxeter groups}

As is the case for mapping class groups, the automaticity of Coxeter
groups has been known for a while now. Brink and Howlett proved that
all Coxeter groups are automatic in 1993 \cite{BrHo93}.  Progress on
biautomaticity has been slower.

\begin{q}[Coxeter Groups]
Are all Coxeter groups biautomatic?
\end{q}

Significant progress on this question occured when Graham Niblo and
Lawrence Reeves were able to show in \cite{NiRe03} that all Coxeter
groups act on properly discontinuously by isometries on $\cat(0)$ cube
complexes, and in many cases, these actions are cocompact.  In
particular, they were able to prove the following result.

\begin{thm}
If $G$ is a finitely generated Coxeter group that contains only
finitely many conjugacy classes of subgroups isomorphic to triangle
groups, then $G$ is biautomatic.
\end{thm}

The analysis of the conditions under which the action is cocompact was
completed by Niblo's Ph.D. student Ben William in his dissertation
\cite{Wi99}.  On a separate note, Bill Cassell has written a survey
article that describes how to efficiently carry out computations in
Coxeter groups using the $\gap$ package called $\chevie$ \cite{Ca02}.
Several of the algorithms he describes are based on the work of du
Cloux \cite{duCl99} and the automatic structures on Coxeter groups
figure heavily in these algorithms.  See also, the webpages he has set
up based on the 2002 CRM conference on compuatations in Coxeter groups
\cite{Ca-web}.

%\comment{Many many many are biautomatic (Bahls,Caprace-Muehlheer,etc.)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Artin groups and Garside structures}

In the same paper where Garside groups were first defined, Patrick
Dehornoy showed that every group with a Garside structure is
biautomatic \cite{De02}.  One consequence of this theorem is that it
shows that every Artin group of finite type is biautomatic (a result
first proved by Ruth Charney in \cite{Ch95}).  In particular, this
reproves once again the basic result that the braid groups are
biautomatic.

\begin{p}[Artin groups]
Determine which Artin groups are biautomatic, automatic, or
asynchronously automatic.  
\end{p}

This problem remains wide open, predominantly because for most Artin
groups, we do not even know how to solve the word problem.  First
things, first. Eventually, this may become an interesting question.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{One relator groups}

The class of one-relator groups have an uneasy relationship with the
classes of groups under discussion since it clearly contains many
hyperbolic examples (such as any one-relator group with torsion), but
it also contains groups such as $BS(1,2)$ that are asynchronously
automatic but not automatic, and groups such as Baumslag's group that
are not even asynchronously combable.  In particular, it is not yet
clear which one-relator groups belong to which classes.

\begin{p}[One-relator groups]\label{p:one-relator}
Determine which one-relator groups are hyperbolic, biautomatic,
automatic, or asynchronously automatic.
\end{p}

Although Problem~\ref{p:one-relator} is wide open, some answers have
been conjectured.

\begin{conj}
A one-relator group is hyperbolic iff it contains no Baumslag-Solitar
subgroups, and it is automatic iff it contains no metabelian
subgroups.
\end{conj}



