Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental groups of 3-dim manifolds etc. However, the book is from 1992, so much of the material summarizes research done by Cannon, Thurston, Holt etc. back in the '80s. I'm interested in how the theory of automatic groups (and, more generally, applications of formal languages in group theory) has progressed since then – have there been any significant new results, open problems, novel ideas, examples?
[Math] Automatic groups – recent progress
automata-theoryformal-languagesgr.group-theory
Related Solutions
I think there are a few different ways in which Automatic Groups affected the history of Geometric Group Theory.
One was mentioned by Derek Holt, which I will spin in a slightly different way: if you really want to know the group, and if it has an automatic structure, you had better know that structure. For an individual group, the way to find out is to plug its presentation into the programs that Derek mentions. For classes of groups things can be trickier, but the effort is rewarding and sometimes even quite beautiful, for instance the proofs on automaticity of braid groups and Euclidean groups in "Word processing in groups", and the proof by Niblo and Reeves on biautomaticity of cubulated groups; and I retain a lot of affection for my paper proving automaticity of mapping class groups (and no offense taken, Misha).
Another thread of influence is the theory of biautomatic groups. To me, this theory is not yet played out, although as others say perhaps the open questions are hard. However, there are various beautiful pieces of this theory which had some interesting effects, and I think there is still some gold to mine here. The theory starts with the papers of Gersten and Short. Some applications of that theory are: the proof by Bridson and Vogtmann that $Out(F_n)$ is not biautomatic when $n \ge 3$; and my proof that direct factors of biautomatic groups are biautomatic. I also like the beautiful papers of Neumann and Shapiro which describe completely all possible automatic and biautomatic structures on $Z^n$, and the paper of Neumann and Reeves and its followup by Neumann and Shapiro which describe how to construct biautomatic structures on central extensions. I like to think that one of the effects of the Gersten/Short theory is that it gives a hint to a "hierarchical" structure on a biautomatic group. Farb's thesis follows this idea up with his notion of relatively automatic and bi-automatic groups, and the thesis of my student Donovan Rebbechi pins some of this down by giving rigorous proofs of some statements in Farb's thesis regarding bi-automatic structures on relatively hyperbolic groups. The theory of biautomatic groups is definitely still alive; poking around on MathSciNet just this very moment I find a paper that slipped my notice and that I want to go read right now, by Bridson and Reeves studying the isomorphism problem for biautomatic groups.
A separate and very important thread of influence is how the theory of automatic groups stoked interest in certain classes of quasi-isometry invariants. Gromov had already proved that hyperbolicity of a group is equivalent to linearity of the Dehn function (the isoperimetric function). One of the big applications of an automatic structure is Thurston's theorem that an automatic group has a quadratic (or better) Dehn function, which combined with the theorem that every subquadratic Dehn function is actually linear proves that nonhyperbolic automatic groups have quadratic Dehn functions on the nose. Thurston's proof of the quadratic upper bound introduced the concept of a combing of a group, and this led to a whole industry of studying different classes of combings, and the upper bounds they impose on the Dehn function. I particularly like the proof by Hatcher and Vogtmann finding an exponential upper bound to the Dehn function of $Out(F_n)$, which proceeds by finding a quite broadly stretched (pun intended) combing for $Out(F_n)$. Finding bounds on Dehn functions, and pinning down exact Dehn functions can be far from obvious, e.g. Robert Young's proof that $SL(n,Z)$ has quadratic Dehn function for $n \ge 5$, and the proof by Handel and myself of the exponential lower bound for the Dehn function of $Out(F_n)$. The issue of lower bounds is not particularly connected to automatic groups in any mathematical sense, but the historical connection is what I am trying to emphasize. Combings and Dehn functions have continued to grow from these and various seeds, and although I don't want to overstate the particular influence of Thurston's theorem in this context, nonetheless it is (besides Gromov's) one of the earliest concrete computations of Dehn functions.
I wrote that quote, and I'll take the hint of @SamNead and try to write an answer, although the best I can do is to write a somewhat speculative extension of the story behind the quote, laced with some mathematical musings.
From my memories of that period (sometime in the mid-late 1980's), I only vaguely recall looking at any actual output of Bill Thurston's computer experiments using grep to compute in groups. My memory is not at all precise enough regarding any actual examples he might have produced, but I suspect that they must have been pretty simple examples, for the following reasons.
In the theory of regular languages and FDAs (finite deterministic automata), there are reasonably simple algorithms for going back and forth between regular expressions and finite deterministic automata, producing an expression matching exactly the words accepted by a given automaton, and producing an automaton accepting exactly the words matched by a given expression. The algorithm from regular expressions to FDAs works pretty efficiently and is the basis of the grep utility. The algorithm from FDAs to regular expressions seems to be horribly inefficient, as reported by Derek Holt in his comment. So one might expect that writing an actual regular expression that matches normal forms for a certain group could be quite tedious.
Nonetheless if one is clever enough one can sometimes just manually come up with a regular expression to match a given language. See the exercise Derek Holt suggests in his comment; carrying out that exercise will likely give you the most direct answer to your question.
I suspect that this is what Thurston was doing during this discovery period: noticing that certain finitely generated groups have a regular language of normal forms.
Thurston was also very familiar with concepts of cone types (developed by Jim Cannon around that time; Thurston and Cannon talked together a lot during that period). So at some point during this process he certainly also noticed the connections between cone types and what we now call the 2-tape "multiplier automata" which are at the heart of the theory of automatic groups. It is tempting to speculate whether Thurston's grep experiments extended to writing regular expressions for 2-tape multiplier automata, but honestly I have no idea.
Best Answer
I'm not an expert in the area, but here's a few highlights:
Bridson distinguished automatic and combable groups.
Burger and Mozes found examples of biautomatic simple groups.
Mapping class groups were originally shown to be automatic by Mosher. Recently, Hamenstadt has shown that they are biautomatic.
See part 3 of McCammond's survey for an update on open problems.
A well-known open problem is whether automatic groups have solvable conjugacy problem.