4 - Rewriting systems

Summary

Rewriting systems in monoids and groups

When working with an infinite finitely generated group G = X, a principal goal is to find a normal form for the group elements. More precisely, for each element of G, we would like to find a representative word in A* (where A := X±1) for that element, and we refer to these representative elements as words in normal form. This normal form should ideally satisfy two requirements:

1. (i) it should be easy to recognise whether a given word is in normal form;

2. (ii) for a given word, it should be possible to find the unique word w in normal form with v =_G w.

Of course, we can only hope to achieve these objectives if G has soluble word problem. As we will see in Section 10.1, it has been proved by Novikov and Boone [206, 31, 32] that this is not the case in general. Fortunately, many of the interesting classes of finitely presented groups that arise in practice, particularly those that come from topology or geometry, turn out to have soluble word problem. Furthermore, as we shall see in this chapter and in Chapter 5, many of them have convenient normal forms.

Word-acceptors In this chapter, we consider normal forms arising from rewriting systems, and in Chapters 5 and 6 we study automatic groups, and the important special case of hyperbolic groups. In each of these cases, the words in normal form constitute a regular set, and so there is an fsa with alphabet A, known as a word-acceptor, of which the accepted language is the set of normal form words. From this description, one might expect a word-acceptor to accept a unique word for each group element, but it turns out that the following more general definition is more convenient.