5 - Automatic groups

Summary

In this chapter, we consider the class of automatic groups and some related classes, including the important subclass of (word-)hyperbolic groups, which are studied in more detail in Chapter 6. In the class of automatic groups, the two requirements for a normal form specified at the beginning of Chapter 4 are met. There is a normal form for group elements with the property that the set of words in normal form constitutes a regular set, and for which an arbitrary word can be reduced to normal form in quadratic time. The most comprehensive reference on automatic groups is the six-author book [84], by D.B.A. Epstein and co-authors and we refer the reader there for any necessary further information and references. For an alternative, more rapid, treatment, see the account by Baumslag, Gersten, Shapiro and Short [19, Part II].

A procedure is described by Epstein, Holt and Rees [86], and by Holt [145] and Holt et al. [144, Chapter 16], that starts with a finite presentation of a group and, if successful, outputs a set of fsa that between them define an automatic structure for that group; one fsa defines the normal form and the others enable the definition (and implementation) of an algorithm that reduces any input word to normal form. The most recent implementation of the procedure forms part of Holt's KBMAG package [146]. There is an alternative implementation by Alun Williams [252] which performs better on many examples,

In view of the multitude of existing descriptions, we present only a summary of this procedure here, and we concentrate on the fact that it makes heavy use of logical operations applied to regular languages, such as those described in Proposition 2.5.10, 2.10.5 and 2.10.8. It involves the use of the Knuth–Bendix completion process described in Chapter 4, but can be successful even in cases where this process fails to terminate.