# A completion procedure for finitely presented groups that is based on word cycles

A Completion Procedure For Finitely Presented Groups That Is Based On Word Cycles ?
Robert Cremanns and Friedrich Otto
Fachbereich Mathematik/Informatik, Universitat Kassel, D{34109 Kassel e-mail: <cremanns,otto>@theory.informatik.uni-kassel.de

March 9, 1998
Abstract. A Knuth-Bendix style completion procedure for groups is presented that, instead of working with sets of string-rewriting rules, manipulates nite sets of word cycles. A characterization is given for the resulting sets of persistent word cycles, from which it follows that the completion procedure terminates successfully if and only if the reduced word problem of the nite group presentation considered is a nite set. In this case the resulting set of persistent word cycles yields a nite canonical string-rewriting system for each total reduction ordering.

1 Introduction
Although the word problem for nitely presented groups is undecidable in general, there are many interesting classes of nitely presented groups for which this problem can be solved e ectively. In particular rewriting techniques have been applied successfully in many instances. If a group G has a nite (monoid-) presentation ( ; R) containing a string-rewriting system R that is both noetherian and con uent, then the set of strings that are irreducible modulo R forms a set of unique representatives for the group G. Given a string w 2 , the representative of the group element presented by w can be computed simply by reducing w to its irreducible descendant. Since this is an e ective operation, this means that the word problem for G can be solved by a syntactically simple algorithm. Unfortunately not every nitely presented group with a solvable word problem has a nite presentation involving a noetherian and con uent string-rewriting system Squ87,SOK94]. On the other hand many interesting groups do admit such presentations Sim94]. But even if a given group has presentations of this form, there remains the problem of actually determining one of them. In the setting of universal algebra Knuth and Bendix have presented a completion procedure that, given a nite (string-) rewriting system R and a reduction ordering > as input, attempts to compute a rewriting system R1 that de nes the same equational theory as the given system R, that is compatible with the ordering >, and hence noetherian, and that is con uent KB70]. Actually, if the reduction ordering is a total ordering, then this procedure terminates with success if and only if a nite system R1 with these properties exists. In the setting of presentations of groups, each rule generated induces several other rules based on the group axioms. This process of symmetrization can be taken care of by the general completion method, but to enhance performance this process can be realized through a speci c symmetrization procedure. This has lead to some specialized completion procedures for groups LeC86,Sim94]. For a group G presented by ( ; R), the word problem is e ectively reducible to the membership problem for the congruence class ]R , where denotes the empty string. Hence, to solve the word problem for G by rewriting a nite noetherian string-rewriting system R1 would su ce that is equivalent to R, noetherian, and con uent on ]R MO87]. In Ott92] a completion procedure is presented that tries to generate a nite special string-rewriting system that is con uent on ]R from a given nite special system that presents a group G. Here again a process for symmetrizing sets of rewriting rules is included as a part of the completion procedure. When executing a completion procedure the space being used is a major concern. It depends on the size of the sets of rules computed during the process of completion. Even for small input systems R that result in small systems R1 intermediate sets of rules can become arbitrarily large MSKO93].
?

This work has been supported by the Deutsche Forschungsgemeinschaft (Projekt Ot 79/4-1).

Thus space e cient schemes to store large sets of rules are of utter importance. In the setting of presentations of groups with each rule its cyclic permutations, its inverse and the cyclic permutations thereof are generated through the symmetrization process. All these rules must be stored in some way, although they do not really contribute much to the information on the induced reduction relation. To save space it is proposed in Str95] to store a rule, its inverse, and their cyclic permutations in a cyclic structure (a word cycle ). Actually in Str95] these word cycles are used as the starting point for a geometrical completion procedure that modi es the actual set of word cycles by introducing additional edges between di erent word cycles in order to identify certain parts of them. This, however, results in a very involved geometrical structure. Borrowing the idea of using word cycles to present symmetrized sets of rules, we describe a cyclebased completion procedure that works with sets of word cycles. It may remove certain cycles, thus deleting sets of rules, and add other cycles, thus introducing additional sets of symmetrized rules, according to some inference rules. However, we do not add any edges to word cycles or between di erent word cycles, that is, in our approach the word cycles are simply used as a dense representation of symmetrized sets of string-rewriting rules. If our procedure terminates given a set of rules R as input, then it has determined a nite set of word cycles Z 1 that describes the same congruence as R. When turning these word cycles into a special string-rewriting system we obtain a system that is con uent on ]R . Thus, we have obtained a procedure for weak completion in the sense of Ott92]. In addition we have the following strong property. Given any total reduction ordering >, the set of word cycles Z 1 can be turned into a nite noetherian string-rewriting system R(Z 1; >) that is con uent and interreduced (that is, canonical ). Hence, our procedure can be seen as computing equivalent canonical systems simultaneously for all total reduction orderings. Of course this nice behavior has a price, since the question arizes as to when our procedure terminates. As it turns out it terminates given a nite presentation ( ; R) as input, if and only if the reduced word problem for this presentation is a nite set. Hence, by a result of Haring-Smith HS83] this only happens for certain nite presentations of plain groups. On the other hand, even if our procedure does not terminate, it may at some stage already have computed a nite canonical string-rewriting system for some reduction ordering. Hence, after choosing a reduction ordering we may proceed as follows. At certain stages the completion process is interrupted, and it is checked whether the string-rewriting system resulting from the actual set of word cycles is con uent. If so, we can terminate the completion process successfully, otherwise we run it for some more stages. Unfortunately we do not yet have an e cient way of testing whether a set of word cycles already yields a con uent string-rewriting system. Another question for future research concerns the so-called small cancellation groups. Is there a reasonable way of turning our completion procedure into an e cient weak completion procedure for small cancellation groups or for certain interesting subclasses thereof? Completion methods for small cancellation groups have been considered in Buc79,LeC86], and we would expect that our cycle-based approach can be put to good use in this setting as well.

2 Basic de nitions and results
In this section we restate the basic de nitions and results on string-rewriting systems in short. For details we refer to BO93]. Let be a nite alphabet. Then denotes the set of words over including the empty word . The length of a word w is written as jwj, and the concatenation of two words u and v is simply written as uv. A congruence on is an equivalence relation on which is compatible with concatenation, that is, for all x; y; z; w 2 , if x y, then wxz wyz . For a congruence and a word w 2 , the congruence class fu 2 j u wg of w is denoted by w] , and = denotes the set of all congruence classes. By de ning u] v] := uv] we obtain an associative binary operation on = with identity element ] . Thus, = is a monoid, the factor monoid of modulo . A rewriting rule on is an ordered pair (l; r) 2 . Usually we will denote such a rule as (l ! r). A string-rewriting system (srs) R on is a set of rewriting rules on . It generates a 2

single-step reduction relation !R on which is de ned as follows: for all u; v 2 , u !R v if and only if there exist two words x; y 2 and a rule (l ! r) 2 R such that u = xly and v = xry. A word u 2 is called reducible if there is a word v 2 such that u !R v; otherwise u is called irreducible. The re exive transitive closure !R of !R is the reduction relation generated by R. If u !R v and v is irreducible, then v is called a normal form of u. The re exive, symmetric, and transitive closure \$R of !R is a congruence on , the Thue congruence generated by R. The pair ( ; R) is called a monoid-presentation for the factor monoid = \$R and for any monoid isomorphic to it. A fundamental decision problem for a srs R (a monoidpresentation) is its word problem: given two words u; v 2 , decide whether u and v are congruent (modulo R), that is, decide whether u \$R v holds. A srs R is noetherian if there does not exist an in nite reduction sequence of the form u1 !R u2 !R u3 !R : : :. Two words x and y are called joinable if there is a word z such that x !R z and y !R z . The srs R is locally con uent if u !R v and u !R w imply that v and w are joinable, and R is con uent if u !R v and u !R w imply that v and w are joinable. If R is both noetherian and con uent, then R is called convergent. It is easily proved by noetherian induction that R is convergent if it is noetherian and locally con uent. If R is a convergent srs, then each word has a unique normal form, and two words u and v are congruent (modulo R) if and only if their respective normal forms (modulo R) coincide. Thus, if R is a nite convergent srs, then the word problem for R can simply be solved by reduction. A well-ordering > on is called a reduction ordering if u > v implies that xuy > xvy for all x; y 2 . A srs R is said to be compatible with > if l > r holds for all rules (l ! r) of R. If a srs R is compatible with a reduction ordering, then R is obviously noetherian. Examples of reduction orderings are the so-called length-lexicographical orderings. Given a total ordering > on , we obtain the length-lexicographical ordering >`` on that is induced by > as follows: for u; v 2 , u >`` v provided that either juj > jvj or juj = jvj and u is larger than v in the pure lexicographical ordering that is induced by the given ordering > on . It is well-known that a srs is locally con uent if and only if all its critical pairs are joinable. Actually, there are two types of critical pairs:

1. Let (xyz ! u) and (y ! v) be two di erent rules of R, where x; y; z; u; v 2 . Then xyz !R u and xyz !R xvz , and the pair (u; xvz ) is called a critical pair. 2. Let (xy ! u) and (yz ! v) be two rules of R, where x; y; z; u; v 2 and x; y; z 6= . Then xyz !R uz and xyz !R xv, and the pair (uz; xv) is called a critical pair. Since a noetherian srs is con uent if and only if it is locally con uent, we see that it is decidable whether or not a noetherian srs is con uent. The Knuth-Bendix completion procedure KB70] tries to transform a given nite srs into an equivalent srs that is convergent. Here two srss on are called equivalent if they generate the same congruence. In fact, this procedure takes a nite srs R and a reduction ordering > as input, and it computes a convergent system R0 that is equivalent to R and compatible with >. It terminates whenever there exists a nite srs R0 with these properties. The basic idea of the completion procedure is as follows. First, R is transformed into an equivalent nite noetherian srs R0 simply by orienting the rules according to the reduction ordering >. If R0 is not con uent, then there exists a critical pair (z1 ; z2) which is not joinable. To resolve this critical pair a new rule is introduced, for example, the critical pair itself is taken as a new rule, oriented in accordance with the reduction ordering >. By repeating this process a convergent srs is generated. However, observe that when a new rule is introduced, additional critical pairs may arise. Therefore this process may not terminate. A srs R is called reduced if the right-hand side of every rule of R is irreducible, and if the left-hand side of no rule of R can be reduced by any other rule. The srs R is called canonical if it is convergent and reduced. By reducing right-hand sides to normal forms and then deleting rules with reducible left-hand side, a nite convergent system can always be converted into an equivalent nite canonical system. For each congruence on and each reduction ordering > on , there exists a unique, possibly in nite, canonical srs R on that generates the congruence and that is compatible with >. In fact, it consists of all rules (l ! r) such that l r, l 6= r, r is the minimum in its congruence class with 3

respect to >, and also each proper subword of l is the minimum in its congruence class Ave86]. The srs R is nite if and only if there exists a nite convergent system that generates the congruence and that is compatible with >. For the behavior of the Knuth-Bendix completion procedure this has the following consequence. Let R be a nite srs on , and let > be a reduction ordering on . Then the completion procedure terminates given R and > as input if and only if the unique canonical srs that is equivalent to R and that is compatible with > is nite.

3 A group completion procedure
Let be a nite alphabet, and let ?1 : ! be a function such that (a?1 )?1 = a for all a 2 . The function ?1 is extended to by de ning ?1 := and (wa)?1 := a?1 w?1 for all w 2 and a 2 . By R0 we denote the srs R0 := faa?1 ! j a 2 g. A word w 2 is called freely reduced if it is irreducible modulo R0 . For a subset L of , the pair h ; Li is called a group-presentation. The group presented by h ; Li is the monoid that is presented by the monoid-presentation ( ; RL ), where RL := f(w ! ) j w 2 Lg R0 . Obviously this monoid is indeed a group. The congruence L generated by L is de ned as the congruence on that is generated by the srs RL. Let be a congruence on satisfying aa?1 for all a 2 . Then, for all u; v 2 , u implies u?1 , and uv implies vu . Thus, the congruence class ] is closed under inverses and cyclic permutation. Accordingly we de ne as the smallest equivalence relation on satisfying u u?1 and uv vu for all u; v 2 . The equivalence classes of are called word cycles, and the equivalence class ] = f g is called the empty word cycle. A word cycle z is called freely reduced if, for all w 2 z , w is freely reduced. Let Z be a set of word cycles. The congruence Z on that is generated by Z is de ned as the congruence that is generated by the set L(Z ) := fw 2 j w] 2 Z g, that is, it is the congruence that is generated by the srs RL(Z ) := f(w ! ) j w 2 ; w] 2 Z g R0 . In the setting of group-presentations, the word problem is usually de ned as the set of words that are congruent to the empty word. Here we de ne the word problem as a set of word cycles. Let be a congruence on such that aa?1 for all a 2 . Then the word problem WP is the set of all word cycles w] , for which w 2 satis es w , and the reduced word problem RWP is the set of all word cycles w] , for which w is a nonempty freely reduced word in such that w , but w0 does not hold for any proper nonempty subword w0 of w. For all u; v 2 , if u v, and if u is a nonempty freely reduced word congruent to the empty word such that no proper nonempty subword of u is congruent to the empty word, then also v has these properties. Hence, RWP consists of freely reduced word cycles only. Our completion procedure is based on an inference system P which consists of the following inference rules. Let Z be a set of word cycles. (P.1) If the empty word cycle is in Z , then delete it from Z . (P.2) If there are u 2 and a 2 such that uaa?1] 2 Z , then replace uaa?1] by u] in Z . (P.3) If there are u; v 2 + such that u] 2 Z and uv] 2 Z , then replace uv] by v] in Z . (P.4) If there are u; x; y 2 + such that ux] 2 Z and uy] 2 Z , where x and y neither begin with the same letter nor end with the same letter, then add xy?1 ] to Z . For two sets of word cycles Z and Z 0 , we write Z `P Z 0 if Z 0 is obtained from Z by an application of an inference rule from P. Obviously, if Z `P Z 0 , then Z = Z 0 . A P-derivation is a nite or in nite sequence (Zi )i2I of sets of word cycles (where I = fn 2 N j n kg for some k 2 N or I = N ) such that, for all i 2 I r f0g, Zi?1 `P Zi . Let (Zi )i2I be a P-derivation. A word cycle is called persistent if, for some i 2 I , it belongs to any Zj with jS I and j i. By Z 2 we denote the set of all word cycles that occur in this derivation, that is, Z = i2I Zi , while by Z 1 we denote the set of all persistent word cycles of this derivation. Lemma 1. Let (Zi)i2I be a P-derivation, and let w be a nonempty freely reduced word such that w] 2 Z . Then w has a nonempty subword w0 such that w0 ] 2 Z 1 . 4

Proof. The proof proceeds by induction on the length of w. Let w be a nonempty freely reduced word such that w] 2 Z r Z 1 . Then there is an index i such that w] is in Zi , but not in Zi+1 . Thus, inference rule (P.2) or (P.3) has been applied to transform Zi into Zi+1 . If rule (P.2) has been applied, then w] = uaa?1] for some u 2 and a 2 , and u] 2 Zi+1 . Since w is freely reduced, it follows that w = a?1 ua or w = a?1 u?1 a, and that u is nonempty. If w = a?1 ua, we apply the induction hypothesis to u, and if w = a?1 u?1 a, we apply the induction hypothesis to u?1. Thus, we obtain a nonempty subword w0 of u or of u?1 , respectively, which is thus also a subword of w, such that w0 ] 2 Z 1 . If rule (P.3) has been applied, then w] = uv] for some u; v 2 + such that u] ; v] 2 Zi+1 . Then u, u?1 , v, or v?1 is a proper subword of w. By applying the induction hypothesis to u, u?1 , v, or v?1 , respectively, we obtain a nonempty subword w0 of w such that w0 ] 2 Z 1 . t u

A set of word cycles is called interreduced if none of the inference rules (P.1) to (P.3) is applicable. A P-derivation (Zi )i2I is called fair if the following two properties hold: (a) Z 1 is interreduced. (b) For all u; x; y 2 + , if ux] ; uy] 2 Z 1 , and x and y do neither begin nor end with the same letter, then xy?1 ] 2 Z . A completion procedure takes a nite set of word cycles Z0 as input and generates a fair P-derivation (Zi )i2I such that, whenever the set Z 1 of persistent cycles is nite, then the P-derivation generated is nite as well, and the procedure terminates and returns the set Z 1 as output. By Interreduce we denote a procedure that, given a nite set of word cycles as input, keeps applying the inference rules (P.1) to (P.3) as long as possible. It is obvious that this procedure always terminates. It is being used as a subroutine in the following procedure.

Input: A nite set Z of word cycles. repeat
A := Z0 ; Interreduce(A);
0

B := A; C := the set of all word cycles that are obtained from word cycles in A
by an application of the inference rule (P.4);

until A = B; Output: A

Interreduce(A)

A := A C ;

Theorem 1. The procedure above is a completion procedure.
Proof. Given a nite set Z0 of word cycles as input, the procedure above generates a P-derivation (Zi )i2I . Since at the end of the repeat-loop the set A is always interreduced, it is easily seen that Z 1 is interreduced. Now let u; x; y 2 + such that ux] ; uy] 2 Z 1 and x and y do neither begin nor end with the same letter. Since ux] and uy] are persistent cycles, there is a point in time from which on ux] and uy] are contained in A. Thus, the cycle xy?1 ] will be generated by an application of rule (P.4). Hence, the procedure above generates a fair P-derivation. Assume now that the set of persistent word cycles Z 1 is nite. Then there is a point in time from which on Z 1 is a subset of A. Hence, from that time on the interreduced form of A contains Z 1 each time the end of the repeat-loop is reached. Suppose that Z 1 is a proper subset of A, that is, A contains a word cycle w] which is not in Z 1 . Since A is interreduced, w is nonempty and freely reduced. By Lemma 1, w has a proper nonempty subword w0 such that w0 ] is in Z 1 and so in A. This is a contradiction, since A is interreduced. It follows that A = Z 1 . If the repeat-loop is then executed once again, we obtain analogously that at the end of the repeat-loop A = Z 1 holds. Thus, the procedure terminates. It follows that our procedure is indeed a completion procedure in the sense of the de nition given above. t u

5

In our completion procedure the actual set of word cycles is being interreduced at the end of the body of the repeat-loop. This procedure could be improved by interreducing the set of word cycles after each single application of inference rule (P.4). Let > be a reduction ordering on . Based on > we associate a rewriting rule (u ! v) with a word cycle z , if uv?1 ] = z , u > v, and for all words u1; u2 ; u3 satisfying u = u1 u2u3 and u1 u3 6= , u2 u?1 vu?1 . For a set Z of word cycles, R(Z; >) denotes the set of all rules which are associated 1 3 with the cycles in Z based on >. Starting with a group-presentation h ; Li, we take Z0 to denote the set of word cycles Z0 := f w] j w 2 Lg. Given this set as input, our completion procedure will generate a fair P-derivation. If it terminates, then the set Z 1 of persistent word cycles is nite, and we can turn them into a srs R(Z 1 ; >) for any reduction ordering >. At this point the following two questions become important: have? Concerning the second question we have the following auxiliary result which we will need in the next section to derive the complete answer. Lemma 2. Let be a congruence on such that aa?1 for all a 2 , let > be a reduction ordering on , and let R be the canonical srs that generates and that is compatible with >. If (u ! v) is a rule of R, then (u ! v) = (aa?1 ! ) for some a 2 , or (u ! v) is a rule in R(RWP ; >). Proof. Let (u ! v) be a rule in R. If u = aa?1 for some a 2 , then v = . So we can assume that u 6= aa?1 for all a 2 . We have to verify that (u ! v) is contained in R(RWP ; >). First we will show that uv?1 ] 2 RWP . Obviously, u 6= v, u 6= , and u v implying uv?1 . Since R is canonical, no proper subword of u and no subword of v is reducible. In particular this means that no proper nonempty subword of u and no proper nonempty subword of v is congruent to the empty word. Thus, u and v are freely reduced. If v = , then u , and so uv?1 ] = u] 2 RWP . If v 6= , then neither u nor v is congruent to the empty word. Suppose that uv?1 ] 2 RWP . If uv?1 = aa?1 = for some a 2 , then (u ! v) = (a ! a) contradicting the assumption that R is compatible with >. Hence, uv?1 contains a proper nonempty subword that is congruent to the empty word. Since neither u nor v does contain such a subword, there are words x; y1 ; y2 ; z 2 such that u = xy1 , v?1 = y2 z , y1 y2 , and y1 , y2 , and xz are nonempty. Since y1 y2 , also zx . If x = , then z 6= and z , contradicting the fact that v does not contain any nonempty subword congruent to the empty word. Thus, x 6= . If z = , then x 6= and x , contradicting the fact that u does not contain any nonempty subword congruent to the empty word. Thus, z 6= as well. Since y1 y2 , we have ? ? ? y1 y2 1. If y1 = y2 1 , then u = xy1 , v = z ?1y2 1 , and u 6= v imply x 6= z ?1, and u v implies ?1. Thus, at least one of x and z ?1 is reducible. However, this contradicts the fact that each x z ? ? proper subword of u and of v is irreducible. On the other hand, if y1 6= y2 1 , then y1 y2 1 implies ?1 is reducible, leading to the same contradiction. Thus, it follows that that at least one of y1 or y2 uv?1 ] 2 RWP . Obviously, u > v. Hence, it remains to prove that u2 u?1vu?1 for all words u1 ; u2; u3 satisfying 1 3 u = u1u2 u3 and u1 u3 6= . So let u1 ; u2 ; u3 be words such that u = u1 u2 u3 and u1 u3 6= . Then u2 u?1vu?1 . Since each proper subword of u is irreducible, u2 is irreducible, and so u2 is the 3 1 minimum of its congruence class with respect to the ordering >. Hence, u2 u?1 vu?1. t u 1 3 If RWP is a nite set of word cycles, then the above lemma implies that the canonical srs R that generates the congruence is nite for each reduction ordering >. Further, we see that R is contained in R0 R(RWP ; >). Hence, in this case R0 R(RWP ; >) is a nite and convergent srs. As we will see in the next section our completion procedure computes the set RWP , and hence it terminates if and only if RWP is nite. Thus, we have the following answer to Question 2. Theorem 2. If h ; Li is a nite group-presentation such that the reduced word problem RWP L is a nite set of word cycles, then the completion procedure above will terminate given the set Z0 := f w] j w 2 Lg as input. In this case a nite convergent srs is obtained for each reduction ordering on . 6

Question 1. Under what conditions will the set Z 1 of persistent word cycles be nite? Question 2. If Z 1 is nite, and if > is a reduction ordering, what properties does the srs R(Z 1; >)

The class of groups that have nite presentations with nite reduced word problem has been characterized by Haring-Smith as the class of plain groups HS83]. Here a group is called plain if it is the free product of nitely many nite groups and a nitely generated free group. Unfortunately not every nite group-presentation of a plain group has a nite reduced word problem. Thus, our completion procedure terminates only for certain presentations of plain groups.

4 Termination of the completion procedure
In this section we will prove the above-mentioned result on the behavior of our completion procedure. As a tool we will use group diagrams.

4.1 Group diagrams
Group diagrams play an important role in combinatorial group theory, since they are an adequate tool for studying the word problem LS77]. The de nition of group diagrams is based on planar graphs. Let ? = (V; E; ; ;?1 ) be a graph, where V is the set of vertices, E is the set of directed edges, ; : E ! V are the mappings that associate with each edge e 2 E an initial vertex (e) and a terminal vertex (e), respectively, and ?1 : E ! E is a mapping that associates with each edge e 2 E an inverse edge e?1 2 E satisfying (e?1 ) = (e) and (e?1 ) = (e). Further, let : G ! R2 be a planar embedding of the graph G in the Euclidean plane R2 , where we require that, for each edge e 2 E , (e) and (e?1 ) are identical sets of points in R2 . Hence, e and e?1 can be seen as the opposite orientations of the same undirected edge in the embedded graph. In the following we will actually identify the graph G with its embedded image (G). A path p of length n (n 1) in ? is a sequence e1 en of edges such that (ei ) = (ei+1 ) holds for all i = 1; : : : ; n ? 1. The mappings and can be extended to paths by taking (p) := (e1 ) and (p) := (en ). Also the mapping ?1 can be extended to paths by de ning p?1 := e?1 e?1 . For each n 1 vertex x, we include an empty path "x of length 0 with initial vertex x and terminal vertex x, and we take "?1 := "x. On the set of paths in ? the concatenation of paths is an associative binary operation, x where the concatenation of two paths p and q with (p) = (q) is simply written as pq. The graph ? is called connected if, for all vertices x and y, there is a path from x to y. Let G = h ; Li be a nitely generated group. A group diagram (or simply a diagram ) over G is a planar connected graph ? embedded in the Euclidean plane R2 together with a labelling function : E ! satisfying (e?1 ) := (e)?1 for all e 2 E . Further, is extended to paths in ? by taking the label (p) of a path p to be the product of the labels of its edges. The label of an empty path is the empty word . Observe that for all paths p, (p?1 ) = (p)?1 . A path is called simple if all its vertices (and hence also its edges) are distinct. A path p is closed at vertex x if x is the initial vertex and the terminal vertex of p. Note that a closed path is not simple. On the set of closed paths we de ne an equivalence relation as the smallest equivalence relation such that, for all closed paths p, p p?1 , and, for all paths p and q such that pq is a closed path, pq qp. The equivalence classes of this relation will be called cycles. In particular, the equivalence class of an empty path is called an empty cycle. A cycle p] , where p is a closed path, is called simple if all vertices of p are distinct, except that the initial vertex and the terminal vertex coincide. Observe that p q implies (p) (q) for all closed paths p and q. Thus, it is only natural to de ne the label of a cycle p] , where p is a closed path, as the word cycle (p)] . If S is the set of points in R2 that de nes the graph ? , then the set R2 r S is divided into nitely many connected components, exactly one of which is not bounded. The bounded components are called the regions of ? . Let D be a region, and let p be a closed path of minimal length which includes all the edges of the boundary of D, each in at least one of its orientations. We de ne the boundary cycle of the region D as the cycle p] . The boundary label of D is the label of the boundary cycle of D. A similar terminology applies to the diagram ? itself. Let D be the unbounded component of ? , that is, D is the unbounded component of R2 r S , and let p be a closed path of minimal length which includes all the edges of the boundary of D, each in at least one of its orientations. Here we require 7

that p does not cross itself, that is, if e and f are consecutive edges of p with (e) = x = (f ), then e and f are adjacent in the cyclically ordered set of all edges of ? that are incident with x. We de ne the boundary cycle of ? as the cycle p] . The boundary label of ? is the label of the boundary cycle of ? . Based on diagrams the word problem can be characterized as follows.

Lemma 3. LS77] Let Z be a set of word cycles over , and let z be a word cycle over . Then z 2 WP Z if and only if there is a Z -diagram with boundary label z .
Here a diagram is called a Z -diagram if the boundary labels of all its regions are in Z . We close this section with the some additional de nitions. A subdiagram ? 0 of a diagram ? is a diagram the vertices, edges, and regions of which are themselves vertices, edges, and regions of ? . Obviously, each closed path p of ? uniquely de nes a subdiagram of ? which consists of all vertices and edges of p and everything interior to p. We de ne the size of a diagram as the sum of the number of its vertices and the number of its edges. Obviously, the size of a proper subdiagram ? 0 of ? is strictly smaller than the size of the diagram ? itself. An edge e of a diagram ? is called an inner edge of ? if it is not on the boundary of ? . Finally, let x and y be two di erent vertices of ? , and let p; q; r be simple paths from x to y that do not have any vertices in common apart from the initial and the terminal vertices. If pq?1 ] and qr?1 ] are boundary cycles of regions of ? , then the triple (p; q; r) is called an overlap of ? .

4.2 Properties of group diagrams
Here we establish some properties of group diagrams that we will need in the next subsection to prove the announced termination result.

Lemma 4. A diagram ? with inner edges has overlaps, if the following condition is satis ed for all
vertices x of ? and all nonempty closed paths p and q at x:

( ) if pq] is the boundary cycle of some region, then p] is not the boundary cycle of any region.
Proof. The proof proceeds by induction on the size of diagrams. First assume that ? has a region D with boundary cycle which is not simple. Then there are a vertex x and nonempty closed paths p and q at x such that p] is a simple cycle interior to q] and = pq] (See Figure 1). Thus by condition ( ), p] is not the boundary cycle of any region. Hence, the subdiagram ? 0 of ? that is de ned by p and that is strictly smaller than ? has inner edges. Hence, by the induction hypothesis there are overlaps in ? 0 and therewith in ? .

?:

= pq is the non-simple boundary cycle of region D. 8

' \$ '\$ & %% bb &
Figure 1.
D p ?0 x q

Now assume that the boundary cycles of all regions are simple. Consider an inner edge of ? . This edge lies on the boundaries of two di erent regions D1 and D2 . Thus, there exist an integer n 1, paths p1 ; : : : ; pn , nonempty paths q1 ; : : : ; qn ; r1 ; : : : ; rn such that p1 q1 : : : pn qn ] and p1 r1 : : : pn rn ] ? ? are the boundary cycles of the regions D1 and D2 , the cycles q1 r1 1 ] ; : : : ; qn rn 1 ] are simple, and ?1 ] . Here the paths p1 ; : : : ; pn are the common the regions D1 and D2 are interior to the cycle qn rn ? ? subpaths of the boundary cycles of the regions D1 and D2 (See Figure 2). If n = 1, then (q1 1 ; p1 ; r1 1 ) ?1 ] is the boundary cycle of some region, then is an overlap. Finally assume that n > 1. If q1 r1 ? ? ? n (q1 ; r1 ; p?1 rn 1 p?1 : : : r2 1 p?1 ) is an overlap. On the other hand, if q1 r1 1 ] is not the boundary cycle 1 2 0 of ? that is de ned by q1 r?1 has inner edges. Since it is strictly of any region, then the subdiagram ? 1 smaller than ? , the induction hypothesis applies. Hence, there are overlaps in ? 0 and therewith in ?. t u

qn

p1 ; p2 ; : : : ; pn are the common subpaths of the boundary cycles of the regions D1 and D2 .

' '\$ \$ b &% '\$ b & &% %
Figure 2.
pn qn?1 rn?1 D1 pn?1 D2 rn p2 q1 ?0 r1 p1

The next lemmas show that under certain conditions a diagram ? can be converted into a strictly smaller diagram ? 0 such that the two diagrams have the same boundary label, and also the boundary labels of the regions of ? 0 are closely related to those of ? . Lemma 5. Let ? be a diagram with overlap (p; q; r) such that the labels of p and r are equal. Then there exists a smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is also the boundary label of some region of ? . Proof. The diagram ? 0 is obtained from ? by deleting all vertices and edges of the path q, except its initial and terminal vertex, and by then identifying the paths p and r. Thereby, the regions with the boundary cycles pq?1 ] and qr?1 ] are deleted, while the boundary cycles of all other regions are not changed. Obviously ? 0 satis es the desired properties. t u Lemma 6. Let ? be a diagram with overlap (p; q; r), where the path p is labelled xuy and the path r is labelled xvy for some x; y 2 and u; v 2 +. Then there exists a smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is the boundary label of some region of ? or it is equal to uv?1 ] . Proof. Let p1 ; p2 ; p3 be the paths in ? with labels x; u; y, respectively, such that p = p1 p2 p3 , and let r1 ; r2 ; r3 be the paths in ? with labels x; v; y, respectively, such that r = r1 r2 r3 . The diagram ? 0 9

is obtained from ? by deleting all vertices and edges of the path q, except its initial and terminal vertex, and by then identifying the paths p1 and r1 , and the paths p3 and r3 (See Figure 3). In this way the regions with the boundary cycles pq?1 ] and qr?1 ] are replaced by a single region with ? boundary cycle p2 r2 1 ] , while the boundary cycles of all other regions remain unchanged. Obviously 0 satis es the desired properties. ? t u

Figure 3.

? p ? @r ? @@
3

b b

3

p2

q

r2

p1@ @? ?1 @ ?r
(p1 ) = x = (r1 ) and (p3 ) = y = (r3 )

Lemma 7. Let ? be a diagram containing a region with boundary label uaa? ] for some u 2 and a 2 . Then there exists a smaller diagram ? 0 with the same boundary label as ? such that the
1

boundary label of each region of ? 0 is also the boundary label of some region of ? or it is equal to u] .

Proof. Let D be a region of ? with boundary label uaa?1] . Then there exist vertices x; y; z , an edge e labelled a from x to y, an edge f labelled a?1 from y to z , and a path p with label u from z to x such that efp] is the boundary cycle of D. If u = , then x = z and p is an empty path. In this case the diagram ? 0 is obtained from ? by identifying the edges e and f ?1 . In this way the region with boundary cycle ef ] is deleted, while the boundary cycles of all other regions remain unchanged. If u 6= and x 6= z , then again the diagram ? 0 is obtained from ? by identifying the edges e and f ?1. In this way the region with boundary cycle efp] is replaced by a region with boundary cycle p] , while the boundary cycles of all other regions remain unchanged. Finally, assume that u 6= and x = z . Then ef is a closed path (See Figure 4). In this case ? 0 is obtained from ? by deleting ef and all of ? interior to ef , except the vertex x. In this way the region with boundary cycle efp] is replaced by a region with boundary cycle p] , the regions interior to ef are deleted, and the boundary cycles of all other regions remain unchanged. In all cases ? 0 satis es the desired properties. t u

(e) = a; (f ) = a?1 ; and (p) = u 10

'b \$ b & %
Figure 4.
x=z f e p y D

Lemma 8. Let ? be a diagram containing a region with boundary label uv] for some u; v 2

Then there exists a smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is also the boundary label of some region of ? or it is equal to u] or to v] .

+

.

Proof. Let D be a region with boundary label uv] . Then there exist vertices x and y, a path p from x to y with label u, and a path q from y to x with label v such that pq] is the boundary cycle of D. If x 6= y, then the diagram ? 0 is obtained from ? by identifying the vertices x and y. In this way the region with boundary cycle pq] is divided into two regions with boundary cycles p] and q] , respectively, while the boundary cycles of all other regions remain unchanged. If x = y, then either p is in the interior of the closed path q, or q is in the interior of the closed path p. In the former case the diagram ? 0 is obtained from ? by deleting p and everything interior to p, except the vertex x. In this way the region with boundary cycle pq] is replaced by a region with boundary cycle q] , the regions interior to p] are deleted, and the boundary cycles of all other regions remain unchanged. In the latter case the diagram ? 0 is obtained from ? analogously by deleting q and everything interior to q, except the vertex x. In each case ? 0 satis es the desired properties. t u

4.3 A characterization of the reduced word problem
Let (Zi )i2I be a fair P-derivation, let Z be the set of all word cycles occurring in this derivation, and let Z 1 be the set of the persistent word cycles. Further, let be the congruence generated by Z0 .

Lemma 9. If ? is Z -diagram, then there exists a Z 1-diagram without inner edges which has the
same boundary label as ? . Proof. The proof proceeds by induction on the size of diagrams. If ? is a Z 1 -diagram without inner edges, then ? itself has the desired properties. So let us assume that ? has inner edges or that ? contains a region with boundary label in Z r Z 1 . It su ce to show that there is a smaller Z -diagram ? 0 with the same boundary label as ? . The result then follows by applying the induction hypothesis to ? 0 . We consider two cases. Case 1. The boundary labels of all regions of ? are in Z 1. By our assumption this means that ? has inner edges. Since the boundary labels of all regions of ? are in Z 1 , and since Z 1 is interreduced, it follows that, for all vertices x and all nonempty closed paths p and q at x, if pq] is the boundary cycle of some region of ? , then p] is not the boundary cycle of any region of ? . Thus, ? satis es the condition of Lemma 4. Hence, there exists an overlap (p; q; r) in ? . If the labels of p and r are identical, then Lemma 5 is applicable, and we obtain a strictly smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is the boundary label of some region of ? . So assume that the labels of p and r are not identical. Let x be the maximal common pre x and y be the maximal common su x of the labels of p and r. Since the boundary labels of all regions are in Z 1 , and since Z 1 is interreduced, it follows that there exist u; v 2 + such that p is labelled with xuy and r is labelled with xvy. Since the P-derivation considered is fair, uv?1 ] is in Z . By Lemma 6 we obtain a smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is the boundary label of some region of ? or is equal to uv?1 ] . Hence, ? 0 is again a Z -diagram. This completes Case 1. Case 2. ? contains a region with boundary label z in Z r Z 1. Then

(i) z = uaa?1 ] for some u 2 (ii) z = uv] for some u; v 2

+

and a 2 such that u] 2 Z , or such that u] ; v] 2 Z .

In case (i) we obtain a smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is the boundary label of some region of ? or is equal to u] by Lemma 7. In case (ii) Lemma 8 yields a smaller diagram ? 0 with the same boundary label as ? such that the boundary label of each region of ? 0 is the boundary label of some region of ? or is equal to u] or v] . In each case ? 0 is a Z -diagram, which completes the proof of Lemma 9. t u 11

Based on this technical result we can now establish the following result, which gives a characterization of the set of persistent cycles that are generated by a fair P-derivation.

Theorem 3. For each fair P-derivation, RWP = Z 1. In particular, =

Z1 .

Proof. Let Z0 be a nite set of word cycles, let be the congruence generated by Z0 , and let (Zi )i2I be a fair P-derivation starting with Z0 . Further, let Z be the set of all word cycles occurring in this derivation, and let Z 1 be the set of the persistent word cycles generated. We claim that RWP = Z 1 . First we show that RWP Z 1 . Let z 2 RWP . Note that z is nonempty and freely reduced. By Lemma 3 there exists a Z -diagram ? with boundary label z . Hence, Lemma 9 implies that there exists a Z 1 -diagram ? 0 without inner edges with boundary label z . Let be the boundary cycle of ? 0. If is not simple, then there are a vertex x and nonempty closed paths p and q at x with labels u; v 2 + , respectively, such that p] is a simple cycle and = pq] . Since the label u of p is nonempty and freely reduced, and since ? 0 has no inner edges, it follows that p] is the boundary cycle of some region. Thus, its boundary label u] is in Z 1 . Hence, u contradicting the fact that z = uv] belongs to RWP . Thus, the boundary cycle of ? 0 is simple. Since z is nonempty and freely reduced, and since ? 0 has no inner edges, is the boundary cycle of some region of ? 0 , and so its label z is in Z 1 . Thus, we see that RWP Z 1 . Assume that the converse inclusion does not hold, that is, there is a word cycle z 2 Z 1 r RWP . Since Z 1 is interreduced, there exists a nonempty freely reduced word w 2 such that z = w] . It follows that w has a proper nonempty subword w0 such that w0 ] 2 RWP . By the above inclusion this means that w0 ] 2 Z 1 , thus contradicting the fact that Z 1 is interreduced. Hence, RWP = Z 1 . = Z = RWP , and so the above Since Z 1 Z , Z 1 Z is obvious. On the other hand, t u equality shows that also = Z = Z 1 . This completes the proof of Theorem 3.

5 Concluding remarks
We have presented a completion procedure for nitely presented groups that works with word cycles instead of sets of reduction rules. Since a word cycle presents a symmetrized set of rewrite rules, this procedure is expected to be more space e cient than traditional completion procedures that work with rule sets. Also each inference step of the procedure corresponds to several steps manipulating rules. If Z0 is a nite set of word cycles, and is the congruence generated by Z0 , then the completion procedure terminates on input Z0 if and only if the reduced word problem RWP is a nite set of word cycles. In this case the set Z 1 of the persistent word cycles generated coincides with the set RWP . Thus, if we convert Z 1 into a special srs R , then this system is -con uent. Here a srs is called special if the right-hand side of each rule is the empty word. In addition, if > is a reduction ordering, then it follows from Lemma 2 that the srs R(RWP ; >) R0 is convergent. Obviously it generates the congruence . Thus, in case of success our completion procedure can be seen as generating nite convergent srss simultaneously for all total reduction orderings. Now suppose that our completion procedure does not terminate on input Z0 , but that there exists a nite convergent srs R that generates the congruence and that is compatible with >. Then also the canonical system R0 that generates the congruence and that is compatible with > is nite. Since RWP = Z 1 , Lemma 2 implies that there is a nite subset Z 0 of Z 1 such that, if (u ! v) is a rule in R0 , then (u ! v) = (aa?1 ! ) for some a 2 , or (u ! v) is a rule in R(Z 0; >). It follows that there is an index i 2 I such that, for all j i, R(Zj ; >) R0 is a nite convergent srs that generates the congruence . So even if our completion procedure does not terminate, it may compute a set of word cycles such that, with respect to some reduction ordering, the associated set of rules is a nite convergent srs for the congruence considered. Thus, it may make sense to interrupt the completion procedure at certain stages in order to check whether the set of rules associated with the actual set of word cycles computed so far forms a convergent srs with respect to a chosen reduction ordering. It remains to determine at which stages of the completion procedure such an interrupt is most promising. Also we would need 12

an e cient test for verifying whether a nite set of word cycles and a reduction ordering yield a nite srs that is already con uent without actually generating all the rules explicitly. Finally, by incorporating additional geometrical conditions it should be possible to turn our completion procedure into a procedure that, given a presentation of a small cancellation group as input, returns a nite set of word cycles that yields a weakly con uent srs for the presentation considered Buc79,LeC86].

References
J. Avenhaus. On the descriptive power of term rewriting systems. J. Symbolic Computation, 2:109{122, 1986. BO93] R.V. Book and F. Otto. String-Rewriting Systems. Springer-Verlag, New York, 1993. Buc79] H. Bucken. Reduction-systems and small cancellation theory. In Proceedings 4th Workshop on Automated Deduction, pages 53{59, 1979. HS83] R.H. Haring-Smith. Groups and simple languages. Transactions American Mathematical Society, 279:337{356, 1983. KB70] D. Knuth and P. Bendix. Simple word problems in universal algebras. In J. Leech, editor, Computational Problems in Abstract Algebra, pages 263{297. Pergamon Press, New York, 1970. LeC86] P. LeChenadec. Canonical Forms in Finitely Presented Algebras. Research Notes in Theoretical Computer Science. Pitman, London, 1986. LS77] R.C. Lyndon and P.E. Schupp. Combinatorial Group Theory. Springer-Verlag, Berlin, 1977. MO87] K. Madlener and F. Otto. Using string-rewriting for solving the word problem for nitely presented groups. Information Processing Letters, 24:281{284, 1987. MSKO93] K. Madlener, A. Sattler-Klein, and F. Otto. On the problem of generating small convergent systems. J. Symbolic Computation, 16:167{187, 1993. Ott92] F. Otto. Completing a nite special string-rewriting system on the congruence class of the empty word. Applicable Algebra in Engineering, Communication and Computing, 2:257{274, 1992. Sim94] C.C. Sims. Computation With Finitely Presented Groups, volume 48 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, New York, 1994. SOK94] C.C. Squier, F. Otto, and Y. Kobayashi. A niteness condition for rewriting systems. Theoretical Computer Science, 131:271{294, 1994. Squ87] C.C. Squier. Word problems and a homological niteness condition for monoids. J. Pure Applied Algebra, 49:201{217, 1987. Str95] P. Strogova. Techniques de reecriture pour le traitement de probleme de routage dans les graphes de Cayley. PhD thesis, Universite de Henri Poincare, Nancy, 1995. Ave86]

13