DIAGRAM GROUPS 7 pictures is isomorphic to the group denoted in Higman [14] by G24 (this group was also constructed by R. Thompson, see McKenzie and Thompson [24] or [7]). Recall that these groups were the first known examples of infinite finitely presented simple groups. Finally Section 17 is devoted to open problems. Acknowledgements. The authors are grateful to M. Brin, N. Gilbert, James Howie, V. Kilibarda, R. McKenzie, J. Meakin, A. Olshanskii, S. Pride for many helpful discus- sions. 2 Rewrite Systems In this section we give general definitions concerning rewrite systems, string rewriting systems and monoid presentations. We start with a definition of graph. A graph is a 5-tuple (V, E~l ,I,T) where V, E are disjoint sets of vertices and edges, respectively, - 1 is an involution on E, i,r are functions from E to V. This 5-tuple must satisfy the following axioms: e~~l / e for every e E\ i(e~l) = r(e), r(e _ 1 ) = i(e). If e is an edge then i(e) is called the initial vertex of e and r(e) is called the terminal vertex of e. This definition is often attributed to Serre. Aypath on a graph T is either a vertex or a non-empty sequence of edges e\e2 ... en such that r(et) = t(et+i) for every 1' = 1,..., n 1. If p = e\e2 .. . en is a path then the inverse path p~l is the path e~1e~I1...ef1. A path consisting of one vertex is called an empty path. An empty path coincides with its inverse. An orientation on a graph T is a subset E0 of the set E of edges such that EQUEQ1 = E and EOHEQ1 = 0. The edges of E0 are called positive and the edges of EQ1 are called negative. A path in an oriented graph is called positive if it consists of positive edges. Now let us give a definition of a rewrite system. In the most general form a rewrite system is an oriented graph T that is a graph with an orientation. The vertices of T are called objects and the positive edges are called moves. If a = i{e),b = r(e) for some positive edge e then we write a - r b. The reflexive transitive closure of the relation -r is denoted by A r . We shall omit T from - r and A r if it does not lead to a confusion. A rewrite system T is called terminating if every sequence a\ - a2 —• ... —• an -* ... terminates. A rewrite system T is called confluent if for every three objects a, 6, c such that a A b and a A c there exists an object d such that 6 A d, c A d. T is called locally confluent if for every three objects a, 6, c such that a 6, a -* c there exists an object d such that 6 A d and c 4 d . The following classical result is sometimes called the Diamond Lemma. Lemma 2.1 (Newman, [25J, see also [9]). Every terminating locally confluent rewrite system is confluent.
Previous Page Next Page