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 = {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.
Previous Page Next Page