Word processing in groups. (English) Zbl 0764.20017

Boston, MA etc.: Jones and Bartlett Publishers. xi, 330 p. (1992).
The authors of this book have created the new theory of automatic structures on groups (automatic groups), a branch of combinatorial group theory. This book is the first to develop this new theory, and in fact it has been cited prior to publication as a reference in many papers [its versions as J. Cannon, D. Epstein, D. Holt, M. Paterson, W. Thurston, “Word processing and group theory” were widely distributed in preprint form].
The origins of this book lie in the work of J. W. Cannon [Geom. Dedicata 16, 123-148 (1984; Zbl 0606.57003)], the central idea of which goes back to M. Dehn [Math. Ann. 72, 413-421 (1912; JFM 43.0571.03)]. Namely, Cannon showed the existence of a recursive structure on the set of geodesics of a group acting properly discontinuous in a space, with compact quotient (the Cayley graph is one such space). Another fundamental idea is an observation of W. P. Thurston that Cannon’s result had an appropriate expression in terms of finite state automata. On the other hand, use of D. E. Knuth and P. B. Bendix’s procedure [Comput. Probl. abstract Algebra, 263-297 (1970; Zbl 0188.04902)] is a central element of practical computer programs for automatic groups made under the auspices of the Geometry Supercomputer Center at Minnesota. A major class of automatic groups (to geometers, this class is probably the most important general class) is the class of word hyperbolic or negatively curved groups of M. Gromov [Publ., Math. Sci. Res. Inst. 8, 75-263 (1987; Zbl 0634.20015)].
The book is divided into two parts. The first part is suitable for use as a graduate level introduction to the theory of automatic groups. It also contains a readable introduction to the theory of finite state automata and regular languages which makes this book autonomous in spite of the fact that it uses some old concepts and notions (for example, the original concept of an asynchronous two tape automaton is from the work of M. Rabin and D. Scott [Finite automata and their decision problems, in “Sequential machines: selected papers”, 63-91 (1964; Zbl 0158.25404)]). For a source of many references related to geometric aspects of the book, the reader may use the book of B. Apanasov [Discrete groups in space and uniformization problems (1991; Zbl 0732.57001)]. The chapters of this part are the following. 1. Finite state automata, regular languages and predicate calculus. 2. Automatic groups. 3. Quasigeodesics, pseudoisometries and combings. 4. Abelian and Euclidean groups. 5. Finding the automatic structure: theory. 6. Finding the automatic structure: practical methods. 7. Asynchronous automatic groups. 8. Nilpotent groups.
The second part of the book gives a discussion of related topics in combinatorial group theory and connections between automatic groups and geometry, connections which largely motivated the development of the new theory. Many of the problems presented here are still under investigation. Four chapters of this part are: 9. Braid groups. 10. Higher-dimensional isoperimetric inequalities. 11. Geometrically finite groups. 12. Three-dimensional manifolds.


20F05 Generators, relations, and presentations of groups
20F65 Geometric group theory
20-02 Research exposition (monographs, survey articles) pertaining to group theory
57M05 Fundamental group, presentations, free differential calculus
20F34 Fundamental groups and their automorphisms (group-theoretic aspects)
20M35 Semigroups in automata theory, linguistics, etc.
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
53C22 Geodesics in global differential geometry
57N65 Algebraic topology of manifolds
57S30 Discontinuous groups of transformations