DIAGRAM GROUPS 9 1. Suppose that xy — » s,yz — » t are in 1Z, where y is not empty. Then there exists a word w such that sz A wyxt A w. 2. Suppose that xyz — • s,y - t are in 71. Then there exists a word w such that s A w,xtz A w. Let us consider a few examples of complete string rewriting systems. Example 2.3 Let V = (a, b \ a2ba - a). It is obvious that this system is terminating since for any words x, y, if x — » y then \x\ \y\. Condition 2 is obviously true. The situation from Condition 1 may occur if and only if x = a26, y = a, z = a6a, 5 = * = a. Thus sz = xt = a2ba. So, the system is complete. Example 2.4 Let us consider the ShortLex order - on the set E*. If u and v are words from E~ then u • v if and only if either \u\ \v\ or \u\ = |* | and u is less than u in the lexicographic order. Take 71 to be the set of all rules of the form u — v, where u, v € E+ and v - w. It is clear that { E | 7£) is complete. Example 2.5 Let M be any monoid which is a quotient of the free monoid E". Let 71 consist of all rules u — v such that the words u, v € E* are equal in M and i - u. It is clear that for any word u its congruence class contains the smallest (in the ShortLex order) word v(u) and u — i/(u). This implies that (E | 71) is complete. Example 2.6 Suppose that S is a semigroup. Let us consider the system V = (S \ 7Z) where 7Z is the multiplication table of 5 that is 7£ = {xy — » 2: | x,y € 5, 2 = xy in 5}. It is obvious that this string rewriting system is terminating. It is easy to check that the conditions of Lemma 2.2 hold, so this system is confluent. 3 Semigroup Diagrams If V is a semigroup presentation then with every derivation u = w0,..., wn = v one can associate a simple geometrical object called a semigroup diagram. We will illustrate this important concept by three examples. Example 3.1 Let V = (a,b \ ab = 6a). Then aabb and baba are equal modulo V and aabb = a • ab • b — a • 6a • b = a& • a& — 6a • a& — • 6a • 6a = 6a6a (1) is the corresponding derivation. The diagram associated with this derivation is con- structed as follows.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 1997 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.