Marc Autord

COMPARING GR ÖBNER BASES AND WORD REVERSING

published or not. The documents may come

Comparing Gröbner bases and word reversing

Introduction

When an algebraic structure is given by generators and relations, typically a semigroup or a group, each element admits in general several word representatives. The word problem is the question of deciding whether two words represent the same element. It is known that, both in case of semigroups and groups, the word problem can be undecidable [START_REF] Miller | On Group Theoretic Decision and Their Classification[END_REF]. However a number of methods have been developed that solve the word problem in good cases. The aim of this paper is to compare two such methods, namely the well-known Gröbner basis method [START_REF] Ufnarovskij | Combinatorial and Asymptotic Methods in Algebra[END_REF] as adapted to semigroups, and the word reversing method of [START_REF] Dehornoy | Deux propriétés des groupes de tresses[END_REF]. Originally designed to answer questions in the context of free commutative algebras, the method of Gröbner bases has subsequently been adapted to noncommutative algebras and, via the inclusion of a semigroup G in the algebra K S , to general semigroups. In the latter case, the method consists in starting with a semigroup presentation (S; R) and in running a certain completion procedure that adds new relations that are consequences of the initial ones until one possibly obtains a so-called reduced Gröbner basis [START_REF] Mora | Gröbner bases for non-commutative polynomial rings[END_REF][START_REF] Bokut | Gröbner-Shirshov bases for algebras, groups, and semigroups[END_REF] see [START_REF] Ufnarovskij | Combinatorial and Asymptotic Methods in Algebra[END_REF] for a survey.

Word reversing is another combinatorial method [START_REF] Dehornoy | Deux propriétés des groupes de tresses[END_REF] for investigating presented semigroups. It also consists in iterating some simple syntactic transformation on words. In good cases, the method can be used to solve the word problem. However, this only happens when the initial presentation satisfies a certain completeness condition. When this is not the case, there exists a completion procedure that, as in the case of the Gröbner completion, consists in adding new relations to the initial presentation [START_REF] Dehornoy | Complete positive group presentations[END_REF].

We thus have two a priori unrelated completion procedures. Now, it can be observed on some simple examples that the two processes lead to adding the same relations. It is therefore natural to address the question of how the two completions are connected. The aim of this paper is to show that, actually, there is no simple general relation:

Proposition. There exist finite semigroup presentations for which the Gröbner completion and the reversing completion disagree.

Actually, we shall prove a more precise statement-Proposition 3.1 belowshowing really independent behaviours, namely examples where one completion is finite and the other is infinite, or where there is an inclusion or no inclusion.

Thus the paper is mainly composed of negative results and counter-examples. However, we think it is interesting to list these many examples because neither the Gröbner nor the reversing completion procedures have been much investigated so far, and their global behaviour is not well understood. Also, we point out that most of the examples we investigate below are not just artificial ad hoc constructions, but they involve well-known and interesting semigroups, in particular the braid semigroups and the Heisenberg semigroup: so, in particular, our results give explicit Gröbner bases for these cases.

The paper is organized as follows. In Section 1, we recall the notion of a Gröbner basis in the context of presented monoids. In Section 2, we similarly describe word reversing and its associated notion of completion and observe that the latter coincides with the Gröbner completion of Section 1 on simple examples. Then, in Section 3, we establish the main results by constructing explicit counter-examples witnessing all possible types of divergence for the two completions. In Section 4, we quit the word problem and address another problem involving presented semigroups, namely recognizing cancellativity, and we examine its possible connections with Gröbner bases.

Gröbner bases in the framework of presented monoids

Both in the commutative and noncommutative cases, Gröbner bases have been originally designed to decide whether a polynomial belongs to a given ideal of some algebra K[X 1 , . . . , X n ] or K X 1 , . . . , X n . It is however easy to adapt the Gröbner bases machinery so as to solve the word problem of presented semigroups.

In this section, we briefly review the method, in the specific case of semigroups. In particular, we recall how, in that case, the Gröbner completion procedure can be entirely performed in the language of semigroups, and how Gröbner bases can be used to solve the word problem.

1.1. Gröbner bases. Following standard notation, if S is a nonempty set, S * denotes the free monoid generated by S, i. e., the set of all words on S together with concatenation. The empty word is denoted by ε. In the sequel, R is a set of pairs of nonempty words on S. A pair (S; R) is called a semigroup presentation and we call S the set of generators and R the set of relations. In the sequel, it will be convenient-in particular for Section 2-to work with monoids rather than semigroups, that is, to add a unit. We then define S; R + to be the monoid S * / ≡, where ≡ is the smallest congruence on S * containing R. We denote ≡ (1) the relation so defined: "w ≡ (1) w ′ holds if and only if going from w to w ′ can be done by applying one relation of R".

For a field K, the free associative K-algebra (or simply free algebra) with set of generators S and unity is denoted by K S . As a set it can be viewed as the set of all linear combinations of elements of S * with coefficients in K. The free monoid S * embeds in the free algebra K S , and, more generally, the monoid S; R + embeds in the factor algebra K S /I, where I is the two-sided ideal generated by all the elements u -v, with (u, v) ∈ R.

For details about Gröbner bases in the context of algebras we refer to [START_REF] Ufnarovskij | Combinatorial and Asymptotic Methods in Algebra[END_REF], of which we follow the notation and the terminology. We fix a well-ordering < on the set of words S * , that is, any two words are comparable and every nonempty subset has a smallest element. This enables us to perform inductive proofs on the rank of words. Moreover, we assume that the ordering is compatible with the operation of the monoid: f < g implies uf v < ugv for all words u, v. Such an ordering is called admissible. There always exists an admissible ordering: for each linear ordering of S the associated deglex ordering (or homogeneous lexicographic ordering) satisfies all these conditions: the words are first ordered by their length, and, if the lengths are the same, lexicographically. In the sequel, we shall often write u = v instead of (u, v) for relations of a presentation.

Adapting Gröbner techniques to the context of monoids-or semigroups-is easy, and it is alluded to in [START_REF] Mora | Gröbner bases for non-commutative polynomial rings[END_REF], but it seems not to have been written explicitly in literature, and, therefore, we include some details. The next proposition is the first step: equalities in a presented monoid S; R + correspond to equalities of monomials in the algebra K S /I, where I is an ideal determined by R.

Proposition 1.1. Assume (S; R) is a semigroup presentation. Let I be the twosided ideal of the free algebra K S generated by the elements u -v with (u, v) ∈ R. Then, for all words w, w ′ on S, the following are equivalent:

(i) w ≡ w ′ , (ii) w -w ′ ∈ I.
Proof. Suppose w ≡ w ′ . This means that there exists a finite sequence of words w 0 = w, . . . , w n = w ′ such that w i ≡ (1) w i+1 holds for every i < n. We prove by induction on n that w -w ′ lies in I. Assume n = 1; there exist words t, u on S and a relation v = v ′ of R such that both w = tvu and w ′ = tv ′ u hold. By hypothesis, (v, v ′ ) ∈ R implies v -v ′ ∈ I and hence t(v -v ′ )u ∈ I, that is w -w ′ ∈ I. Assume n > 1. Then we have w ′ = w 0 ≡ (1) w 1 ≡ w n = w.

By induction hypothesis we get w n -w 1 ∈ I and w 1 -w 0 ∈ I, and, writing w -w ′ = (w n -w 1 ) + (w 1 -w 0 ) shows that w -w ′ lies in I. Suppose w -w ′ ∈ I. First observe that there is a decomposition w -

w ′ = n i=1 t i (v i -v ′ i )u i for some t i , u i ∈ K S and (v i , v ′ i ) ∈ R; this decomposition implies that there is a relation v = v ′ such that v is a subword of w, say w = tvu, with t, u ∈ S * . Therefore w -w ′ ∈ I implies w -w ′ -(tvu -tv ′ u) ∈ I and then tv ′ u -w ′ ∈ I. Suppose w > w ′
and that w is the smallest element for which the conclusion does not hold. Thus we get tv ′ u ≡ w ′ , hence w = tvu ≡ (1)

tv ′ u ≡ w ′ .
With Proposition 1.1, we established a connection between words being equivalent and their difference lying in a particular ideal. The next lemma shows that for such ideals, that is to say ideals generated by differences of monomials, the elements of the reduced Gröbner basis are again differences of monomials. Lemma 1.2. Assume I is the ideal of K S generated by u 1 -v 1 , . . . , u n -v n with u i , v i in S * . Then all the elements added during the G-completion have the type u -v, with u and v in S * .

Proof. Three steps are involved in the algorithm, namely normalization, reduction and completion.

Define B to be the set of the elements u i -v i , 1 ≤ i ≤ n. The normalization process consists in substituting every element of B with a proportional element with leading coefficient 1. In our context, this step does not change any of the elements of B.

In the sequel, if p is a polynomial, p denotes the term of highest rank and p denotes p -p. Assume t ∈ B. Suppose there is a u in B such that û is a subword of t; in other words, there are words t l and t r satisfying t = t l ût r . Then the reduction step consists in discarding t from B and replacing it by t -t l ut r . We check now that t -t l ut r has the prescribed type:

t -t l ut r = ( t -t l ut r ) -ť + t l ǔt r = t l ǔt r -ť.
The third step is composition, which forces leading terms to collapse when appropriately combined. Given u = xy -ǔ and v = yz -v, the composition is uz -xv, in which the two leading terms xy and yz cancel. Now we have uz -xv = xv -ǔz, again a difference of two monomials.

Thus, along the G-completion, i. e., the computation of the Gröbner basis, the elements added to the basis are differences of monomials. By Proposition 1.1, they correspond to equalities in the monoid S; R + and therefore to equivalent words on S. This allows us to redefine the Gröbner operations at the level of words directly: Definition 1.3 (reduction of a relation). Let (S; R) be a semigroup presentation. Let (w, w ′ ) and (v, v ′ ) be relations satisfying v > v ′ and w = v l vv d , with v l , v d ∈ S * . Then the relation (v l v ′ v r , w ′ ) is said to be obtained by reduction of (w, w ′ ) by (v, v ′ ). We say that the relation (w, w ′ ) reduces to 0 with respect to the set R, or simply, when the set of relations is clear from the context, that (w, w ′ ) reduces to 0, if there is a sequence of relations (w, w ′ ) = (w 0 , w ′ 0 ), . . . , (w n , w ′ n ) = (u, u) of ≡ such that every (w i+1 , w ′ i+1 ) is a reduction of (w i , w ′ i ) by a relation (u i , u ′ i ) of R. Note that a reduction of w = w ′ by any relation yields a relation z = z ′ that satisfies z < w or z ′ < w ′ . Since S * is well-ordered, reducing iteratively a relation eventually stops; otherwise we would get an infinite decreasing sequence of words. When no reduction applies to a relation, it is said to be reduced. Definition 1.4 (composition of relations). Let (S; R) be a semigroup presentation. Let w = w ′ and v = v ′ be relations in R such that w and v overlap, i. e., we have w = xy and v = yz with y a nonempty word. The composition of w = w ′ and v = v ′ with overlapping y is the element (xv ′ , w ′ z) of S * × S * . Fact 1.5. The composition of two elements of ≡ is again in ≡.

Remark 1.6. To compute the composition of (xy, w ′ ) and (yz, v ′ ) with overlapping y, we write (xy

-w ′ )z -x(yz -v ′ ) = xv ′ -w ′ z
and we deduce that the composition is (xv ′ , w ′ z). This convenient way of composing relations is in fact the way of composing polynomials in algebras.

Adapting the classical notions-see for instance [START_REF] Ufnarovskij | Combinatorial and Asymptotic Methods in Algebra[END_REF]-we introduce:

Definition 1.7 (Gröbner basis and G-completeness). Let (S; R) be a semigroup presentation. A subset B of the congruence ≡ generated by R is a Gröbner basis of (S; R) if every element (u, v) of B satisfies u > v and if, for any two equivalent words w, w ′ in S * with w > w ′ , there exists an element (u, v) in B such that u is a subword of w. If R is a Gröbner basis, the presentation is said to be G-complete.

Not every presentation is G-complete: in the monoid associated to the presentation (a, b; abababa = bb) with homogeneous lexicographic order, the words b 3 a and ab 3 are equivalent and yet none of them admits abababa as a subword.

Nevertheless, Gröbner bases do exist: starting from (S; R), complete the set of relations with every equality u = v that holds in S; R + . The set of relations obtained this way is a Gröbner basis but there is no practical interest of such a completion as it is noneffective: it requires a former solution to the word problem. Moreover, there is redundancy in such a basis in the sense that if u = v is a relation, then wu = wv is also a relation and both appear in the basis, although wu = wv can be reduced by u = v. We shall see in the sequel, however, that running Algorithm 1.11 completes the set of relations into a smaller Gröbner basis than the set of all relations, that it does not need a solution to the word problem and that no redundancy is left in the Gröbner basis so obtained, i. e., the Gröbner basis is reduced. Definition 1.8. A Gröbner basis is minimal if no subset of it is a Gröbner basis. A set of relations U is reduced if every relation of the presentation is reduced.

Remark 1.9. A set U of relations in which there exist two relations involving the same leading word is not reduced: if u = v and u = w are two relations of U satisfying v < w, one reduces u = v by u = w to w = v and then u = w to u = v.

To recognize whether a set of relations is a reduced Gröbner basis, we have the following criterion: Proposition 1.10. Assume (S; R) is a semigroup presentation and U a set satisfying R ⊆ U ⊆≡. If U is reduced and if every composition of two relations of U reduces to 0, then U is a reduced Gröbner basis of (S; R).

Proof. The result is a rewriting of Lemma on Composition [9, p. 30] adapted to the context of monoids using Proposition 1.1.

The conjunction of Proposition 1.1 and Lemma 1.2 give an algorithm (based on the one working in the free algebras) that computes a reduced Gröbner basis for a semigroup presentation. There are no references to algebras nor to ideals either, the whole process taking place in the monoid. In a reduced set of relations, we order pairs by putting

(u 1 = v 1 , u 2 = v 2 ) < (u 3 = v 3 , u 4 = v 4 ) ⇔ u 1 u 2 < u 3 u 4 .
Since the set of relations is reduced, the order < is linear.

Algorithm 1.11 (G-completion). Assume (S; R) is a presentation. Start with U = R.
1. Reduce all the relations of U until no possible reduction is left; 2. Delete all relations v = v of U; 3. WHILE there exist two relations of U that can be composed Add the result of composition of the smallest pair to U;

Go to 1; OUTPUT : U. Proposition 1.12. If Algorithm 1.11 terminates, the final set of relations U is a reduced Gröbner basis of (S; R).

Proof. The set of relations U eventually obtained fulfills the conditions of Proposition 1.10. Algorithm 1.11 need not terminate in a finite number of steps. In fact, as we will see in Section 1.3, whenever G-completion stops, we can solve the word problem. Conversely, if (S; R) is a presentation for a semigroup with undecidable word problem-and such presentations exist-then the execution of Algorithm 1.11 on (S; R) cannot terminate. But we shall see below that this may also happen for presentations of semigroups with an easy word problem. 1.2. An example. We now illustrate Algorithm 1.11 by computing a reduced Gröbner basis explicitly. This example also shows that Algorithm 1.11 may not terminate.

Example 1.13. Consider the presentation (a, b; bab = ba 2 ) and the deglex ordering induced by b > a. Following Algorithm 1.11, we alternatively perform reduction steps and composition steps. A reduction by the relation numbered (i) will be denoted (i) . We start with U = {bab = ba 2 } and we number (1) the relation bab = ba 2 . Since there is no reduction at this stage, we first compose (1) with itself to get:

(bab -ba 2 )ab -ba(bab -ba 2 ) = -ba 2 ab + bab 2 (1) -ba 3 b + a 4 b,
that is, the relation We prove it by induction on n. The case n = 1 is clear. Suppose n > 1 and compose relation (n) with relation (1) to get (n + 1):

(ba 2n-1 b -ba 2n )ab -ba 2n-1 (bab -ba 2 ) = -ba 2n ab + ba 2n+1 ba 2 (n) -ba 2(n+1)-1 b + ba 2n+2 = -ba 2(n+1)-1 b + ba 2(n+1) .
Hence we obtain U ∞ = {ba 2n-1 b = ba 2n ; n ≥ 1}. We claim that U ∞ is a reduced Gröbner basis of the presentation (a, b; bab = ba 2 ). By Proposition 1.10, it suffices to check that all compositions in U ∞ reduce to 0. Now the composition of (n) and (m) is:

(ba 2n-1 b -ba 2n )a 2m-1 b -ba 2n-1 (ba 2m-1 b -ba 2m ) = -ba 2n a 2m-1 b + ba 2n-1 ba 2m (n) -ba 2(m+n)-1 b + a 2(m+n) b (m+n) -ba 2(m+n) + ba 2(m+n) = 0.
So there is no reduction and no composition left in U ∞ . Thus, the set U ∞ is a reduced Gröbner basis.

1.3. Using Gröbner bases. In this section, we recall that the knowledge of a Gröbner basis of a semigroup presentation allows to solve the word problem of the associated monoid.

Definition 1.14. Let (S; R) be a G-complete semigroup presentation. A word u of S * is G-reduced (or simply reduced ) if none of its subwords appears in a relation of R as a leading word. The G-reduction of a word u of S * is the G-reduced word u R-equivalent to u.

Remark 1.15. The unicity of G-reduction follows from the properties of Gröbner bases: let w and w ′ be two G-reductions of a word u; the equivalence w ≡ w ′ implies that there exists a relation v = v ′ in R, with v a subword of max(w, w ′ ), contradicting the hypothesis that both words were reduced.

G-reduction provides a unique normal form for each element of the considered monoid, and therefore solves the word problem: Proposition 1.16. Assume that (S; R) is a G-complete presentation. Then two words w, w ′ of S * represent the same element of S; R + if and only if the reductions of w and w ′ are equal.

Example 1.17. With the setting of Section 1.2, the word aba 3 is G-reduced; the word aba 3 bab is not reduced however, since both ba 3 b and bab appear in U ∞ as leading words of relations, namely ba 3 b = ba 4 and bab = ba 2 . To reduce aba 3 bab, we substitute, for example, the subword ba 3 b with ba 4 to get aba 5 b and then ba 5 b with ba 6 to obtain the G-reduced word aba 6 equivalent to aba 3 bab. Starting the reduction with the relation bab = ba 2 instead yields aba 3 ba 2 and then reducing with the relation ba 3 b = ba 4 , we get again the reduced word aba 6 .

Word reversing

Word reversing is a combinatorial operation on words that also solves the word problem for a presented monoid whenever the considered presentation satisfies an ad hoc condition called completeness. Not every presentation is complete for reversing, but, as in the case of Gröbner bases, there exists a completion procedure that possibly transforms an initially incomplete presentation into a complete one.

2.1. Word reversing. We recall results about word reversing (and refer to [START_REF] Dehornoy | Complete positive group presentations[END_REF] for more details) so as to be able to compare this technique with the Gröbner methods exposed in Section 1.1.

Let (S; R) be a semigroup presentation. For every letter s in S, we introduce a disjoint copy s -1 of s and we denote by S -1 the set of all s -1 's. The elements of S (resp. S -1 ) are said to be positive (resp. negative). For s 1 , . . . , s n ∈ S and u = s 1 . . . s n a word in S * , we write u -1 for the word s -1 n . . . s -1 1 in S -1 * . Definition 2.1 (reversing). Let (S; R) be a semigroup presentation and let w and w ′ be words on S ∪ S -1 . We say that w (1) w ′ is true if w ′ is obtained from w -either by deleting a subword u -1 u with u ∈ S + , -or by replacing a subword u -1 v where u, v are nonempty words on S with a word v ′ u ′-1 such that uv ′ = vu ′ is a relation of R. We say that w is reversible to w ′ , and we write w w ′ , if there exists a sequence of words w 0 , w 1 , . . ., w n satisfying w i (1) w i+1 for every i and w = w 0 and w ′ = w n . We say in that case that w ′ is a reversing of w.

Example 2.2. Take the standard Artin presentation (a, b; bab = aba) and start with the word a -1 b 2 : we successively get

a -1 b 2 bab -1 a -1 b bab -1 bab -1 a -1 baεab -1 a -1 = baab -1 a -1 .
Note that reversing sequences need not terminate. We say that word reversing is convergent if, starting from any word, there exists a terminating reversing sequence. The presentation above is convergent, whereas (a, b; ba = a 2 b) is not:

b -1 ab ab -1 a -1 b ab -1 aba -1 .
The next proposition exhibits a link between and ≡.

Proposition 2.3 ([5, Prop. 1.9]). Assume that (S; R) is a semigroup presentation, and u, v are words in S * . Then

u -1 v ε implies u ≡ v.
The converse is not true in general: there exist presentations for which word reversing fails to detect equivalence and thus does not solve the associated word problem; these presentations lack the completeness property, which we define as follows.

Definition 2.4 (R-completeness). A semigroup presentation is

R-complete if u ≡ v implies u -1 v ε.
By very definition, we have Proposition 2.5. Assume that (S; R) is a R-complete presentation such that Rword reversing is convergent. Then two words w, w ′ of S * represent the same element of S; R + if and only if w -1 w ′ ε holds.

In the sequel, we shall need a criterion for establishing whether a presentation is possibly R-complete. We shall use the one we describe now. Definition 2.6 (homogeneity). We say that a positive presentation (S; R) is homogeneous if it admits a pseudolength, the latter being defined as a map λ of S * to the nonnegative integers, satisfying λ(su) > λ(u) for each s in S and u in S * , and invariant under ≡.

Note that if all pairs in R have the same length then the length itself is a pseudolength for (S; R). We state now a criterion to check R-completeness: Algorithm 2.7. Let (S; R) be a homogeneous semigroup presentation. For each triple of letters s, t, r in S:

1. Reverse s -1 rr -1 t to all possible words of the form uv -1 , with u, v ∈ S * ; 2. For each uv -1 so obtained, check (su) -1 (tv) ε.

Proposition 2.8 ([5, Algorithm 4.8]). Assume that (S; R) is a semigroup homogeneous presentation. Then (S; R) is R-complete if and only if the answer at Step 2 of Algorithm 2.7 is positive for each triple of letters (r, s, t) and each word uv -1 obtained at Step 1.

2.2.

Reversing-completion. When a presentation is not R-complete, i. e., when word reversing fails to prove some equivalence u ≡ v, there are completion procedures, in particular when the presentation is homogeneous:

Algorithm 2.9. The setting is the one of Algorithm 2.7.

REPEAT

Reverse s -1 rr -1 t to all possible words of the form uv -1 ; FOR each uv -1 so obtained: IF (su) -1 (tv) ε THEN add the relation su = tv to the presentation; UNTIL no new relation has been added to the presentation; OUTPUT : a presentation. Proposition 2.10 ([5, § 5]). When Algorithm 2.9 terminates, it yields a R-complete presentation.

Algorithm 2.9 and Proposition 2.10 are comparable to Algorithm 1.11 and Proposition 1.12 in the sense that if the considered presentation fails at a completeness test, namely (su) -1 tv ε for word reversing and whether it exists compositions not reducing to 0 for Gröbner, then both algorithms add the obstruction to the presentation.

2.3. An example. In this section, we apply Algorithms 2.7 and 2.9 to the example of Section 1.2. We first have to check whether the presentation (a, b; bab = ba 2 ) is R-complete and then, if needed, R-complete it.

In this case, the length of a word is invariant under ≡ and is therefore a pseudolength; hence the presentation is homogeneous and we can apply Algorithm 2.9. There are eight triples of letters to deal with but as no relation of the presentation is of the type a . . . = b . . ., we are left with a single triple, namely (b, b, b).

Before reversing b -1 bb -1 b, we introduce the notion of reversing graph and refer to [START_REF] Dehornoy | Gaussian groups and Garside groups, two generalizations of Artin groups[END_REF] for more details. A reversing graph is a directed and labelled graph that we associate to a reversing sequence w 0 , w 1 ,... as follows. First, we associate with w 0 a path labelled with the successive letters of w 0 : we associate to every positive letter s an horizontal right-oriented edge labelled s, and to every negative letter s -1 a vertical down-oriented edge labelled s. Then we successively represent the words w 1 , w 2 ,... as follows: if w i+1 is obtained from w i by replacing u -1 v with v ′ u ′-1 (such that uv ′ = vu ′ is a relation of the considered presentation), then the involved factor u -1 v is associated with a diverging pair of edges in a path labelled w i and we complete the graph by closing the open pattern u -1 v using right-oriented edges labelled v ′ and down-oriented edges labelled u ′ , see Fig. 1.

The case of the empty word ε, which appears when a factor u -1 u is deleted or some relation uv ′ = v is used, is treated similarly: we introduce ε-labelled edges and use them according to the conventions ε -1 u uε -1 , u -1 ε εu -1 , and

ε -1 ε εε -1 . u u is completed into v v Figure 1. Reversing of u -1 v into v ′ u ′-1 .
The word that is being reversed along the reversing sequence appears on the graph as the top left border: concatenate the labels of the top left border (with the convention that an arrow crossed backwards contributes with an exponent -1) to get the word. See Fig. 2 -1 and a 2 (ab) -1 , and, symmetrically, into a 3 b(a 4 ) -1 and ab(a 2 ) -1 (Fig. 2). Hence, according to Algorithm 2.7, we have to check (ba 4 ) -1 ba 3 b ε and (ba 2 ) -1 bab ε (the symmetric cases are similar). Since bab = ba 2 is a relation of the presentation, (ba 2 )

-1 bab ε trivially holds.

As for (ba 4 ) -1 ba 3 b, Fig. 3 shows that it cannot be reversed to ε. Indeed, there is no relation of the type a . . . = b . . . in the presentation, therefore the words (a 2 b)

-1 a 3 and a -1 b cannot be reversed . Hence, by Proposition 2.8, the presentation is not R-complete, and, applying Algorithm 2.9, we add the relation ba -1 ba 3 b: despite the equivalence ba 4 ≡ ba 3 b, the word (ba 4 ) -1 ba 3 b does not reverse to ε. The relation ba 4 = ba 3 b is therefore added to the presentation so that this equivalence is now provable in terms of reversing.

We prove now, by induction on n, that the presentation (a, b; bab = a 2 b, . . . , ba 2n-1 b = ba 2n ) is not R-complete and that Algorithm 2.9 leads to adding the relation ba 2n+1 b = ba 2n+2 . The case n = 1 was treated above. Assume n ≥ 2. As illustrated in Fig. 4, b -1 bb -1 b reverses to a 2n (a 2n-1 b)

-1 and (ba 2n+2 ) -1 ba 2n+1 b does not reverse to ε, so the criterion of Proposition 2.8 fails, and, according to Algorithm 2.9, we add ba 2n+1 b = ba 2n+2 .

We claim now that the presentation (a, b; ba 2n-1 b = ba 2n , n ≥ 1) is R-complete. To prove this, as we have seen above, we reverse the word b -1 bb -1 b to all possible words of the form uv -1 , as required by the completeness criterion (Algorithm 2.7). Thus, for any m < n, we have the following sequence of reversings:

b -1 bb -1 b (1) a 2n b -1 (a 2n-1 ) -1 b -1 b (1) a 2n b -1 (a 2n-1 ) -1 a 2m-1 b(a 2m ) -1 (1) a 2n b -1 (a 2(n-m) ) -1 b(a 2m ) -1 .
From the latter word, unless m = n holds and because there is no relation a . . . = b . . ., there cannot be a reversing of b -1 bb -1 b to a word of the type uv -1 . Suppose we have m = n, then for every p we get

b -1 bb -1 b (1) a 2m b -1 b(a 2m ) -1 (1) a 2m a 2p b -1 (a 2p-1 ) -1 (a 2m ) -1 (1) a 2(m+p) b -1 (a 2(p+m)-1 ) -1 .
Now, since ba 2(p+m) = ba 2(p+m)-1 b is a relation of the presentation, the criterion for R-completeness is satisfied (Algorithm 2.7), which proves that the presentation (a, b; ba 2n-1 b = ba 2n , n ≥ 1) is R-complete. So we can conclude with: So it is natural to raise Question 2.12. Do the G-completion and the R-completion necessarily coincide for every semigroup presentation?-or, at least, on every presentation in some natural family?

Divergence results

In this section, we answer Question 2.12 in the negative: Proposition 3.1. There exist finite semigroup presentations for which the G-completion and the R-completion do not agree. More precisely, using R G (resp. R R ) for the G-completion (resp. the R-completion), there exist finite semigroup presentations (S; R) exhibiting each of the following behaviours:

• type 1: R R is a proper subset of R G , with R R finite and R G infinite;

• type 1': R R is a proper subset of R G , with both R R and R G finite;

• type 2: R G is a proper subset of R R , with R G finite and R R infinite;

• type 3: R G and R R are not comparable with respect to inclusion.

We shall now successively construct examples displaying the various abovementioned behaviours. together with any homogeneous lexicographic order with a minimal is a type 1 counter-example.

Proof. Let Π w be the presentation of (3.1). Each presentation Π w is homogeneous (the length is a pseudolength) and has exactly one relation, which is of the type a . . . = b . . .; by Proposition 2.8, the presentation Π w is R-complete. First, consider the case w = ε. Then the composition of bb = ab with itself iteratively leads to the relations R m : ba m b = a m+1 b. Now the composition of R m with R n reduces to 0. Proposition 1.10 implies that {ba m b = a m+1 b; m ≥ 0} is a reduced Gröbner basis of Π ε . So in this case, the R-completion of Π ε , which is Π ε , is properly included in the G-completion of Π ε , and Π ε is a type 1 counter-example.

Assume now w = ε. Composing bwb = abw with itself gives bwabw = abw 2 b, which, composed with bwb = abw, gives bwa 2 bw = abw 2 b 2 . Iterating this, i. e., composing bwb = abw with the result of each previous composition, produces all relations bwa m bw = abw 2 b m with m ≥ 1.

We want to prove that the G-completion B of the presentation (3.1) is infinite. We have seen that, for each m ≥ 1, we have bwa m bw ≡ abw 2 b m . It suffices to show that no relation of B may reduce infinitely many different words bwa m bw. For a contradiction, assume that (i) u = v is a relation of B with ℓ := |u| and (ii) there exists A N infinite with ℓ ≤ min A such that u = v reduces all words bwa m bw for m ∈ A.

In the sequel, a word w is called isolated if it is ≡-equivalent to no other word. For a word w, we shall denote by ♯ b (w) the number of b's in w.

If we have ℓ ≤ 1 + |w| then u is too short to include bwb or abw, and hence u is isolated, contradicting (i).

Case 0 : the word u starts at position at least 2 + |w| and finishes at position at most 2 + |w| to the end, hence u has the form a ℓ . But a ℓ does not include neither bwb nor abw and is therefore isolated, which contradicts (i).

Case 1 : there is a q such that u is a prefix of bwa q . Because m > ℓ, the word u has the form bwa p , p ≥ 1. Then it contains no subword bwb because we have ♯ b (bwb) > ♯ b (bwa p ). Similarly, u contains no subword abw because abw ⊆ bwa p implies abw ⊆ wa p , hence ♯ b (bw) ≤ ♯ b (w), and therefore u is isolated, which contradicts (i).

Case 2 : the word u starts at position i, with i ≥ 2; hence there is a q such that u is a prefix of w ′ a q for some suffix w ′ of w. We have ♯ b (u) < ♯ b (bwb) and ♯ b (u) < ♯ b (abw) and so neither bwb nor abw is a subword of u; hence u is isolated, which contradicts (i).

Case 3 : the word u finishes at position at most 1 + |w| to the end. Then we have u = a p bw ′ with p ≥ 1 and w ′ prefix of w; since ℓ > 1 + |w|, we exclude the case where u is a prefix of w. Because of the homogeneous lexicographic ordering, a matching word v has the form a p v ′ and then, by cancellativity (see [START_REF] Dehornoy | Complete positive group presentations[END_REF]Prop. 6.1]), bw reduces to v ′ , which is impossible because bw is of length 1 + |w| and therefore too short not to be isolated. This contradicts (i).

Observe in the previous proof that, although the reduced Gröbner basis is not computable, we are able to determine that it is necessarily infinite.

A typical instance of Proposition 3.2 is the standard presentation of the braid monoid B + 3 .

Example 3. Take any i ≤ n -2; put b = max(σ i , σ i+1 ) and a = min(σ i , σ i+1 ). As in the case of B + 3 , the relation bab = aba of B + n leads Algorithm 1.11 to add all the relations ba n ba = aba 2 b n-1 , with n ≥ 2. It suffices to prove that these relations are not reduced by the relations of the reduced Gröbner basis B. For a contradiction, suppose there is a relation u = v in B -{bab = aba} ∪ {ba n ba = aba 2 b n-1 ; n ≥ 2} reducing at least one relation ba n ba = aba 2 b n-1 . So we have u ∈ {a, b} * . Now, u ≡ v implies that there exist words u 0 , u 1 , . . . , u n satisfying u = u 0 ≡ (1)

u 1 ≡ (1) • • • ≡ (1) u n-1 ≡ (1) u n = v.
But there is a single relation in the presentation of B + n involving a's and b's, namely bab = aba. Therefore, u 0 ≡ (1) u 1 implies u 1 ∈ {a, b} * , and it follows that v is in {a, b} * and that the relation u = v holds in B + 3 ; hence the relations ba n ba = aba 2 b n-1 , with n ≥ 2, and bab = aba reduce u = v to zero, contradicting the fact that B was reduced.

Example 3.6. By Proposition 3.5, we know that the standard Artin presentation of the braid monoid B + 4 (a, b, c; bab = aba, ca = ac, cbc = bcb) and order induced by c > b > a is a counter-example of type 1. Actually, a direct computation shows that its G-completion is:

bab = aba, cbc = bcb, ca = ac, ba n ba = aba 2 b n-1 , n ≥ 2, cb n cb = bcb 2 c n-1 , n ≥ 2, cba n c = bcba n , n ≥ 1, cba n b p cb = bcba n bc p , n ≥ 2, p ≥ 1, cb n1 a n2 b n3 . . . b n k cba = bcb 2 ac n1-1 b n2 c n3 . . . c n k ,
with k ≥ 2, and the n i 's are positive integers satisfying n 2 , n 3 , . . . , n k-1 ≥ 2, with the additional constraints: n 1 ≥ 2 if k = 2 or k = 3 holds, and n k ≥ 2 if k is odd. Remark 3.7. Bokut et al. [START_REF] Bokut | Gröbner-Shirshov bases for the braid semigroup[END_REF]Th. 4.2] give Gröbner bases for every braid monoid B + n , with n ≥ 3. The latter coincide with the ones computed in Examples 3.3 and 3.6. Although almost explicit, these bases are neither reduced nor minimal for the cases n ≥ 5 and therefore do not allow to conclude that the presentation of (3.2) is a type 1 counter-example, contrary to Proposition 3.5.

So far, we considered type 1 counter-examples. We conclude with what was called a type 1' counter-example, namely one where the R-completion is a proper subset of the G-completion and both are finite. The next result is another application of Lemma 3.9 differing from Proposition 3.10 in that the set R is nonempty. Proposition 3.12. For every n, q, p satisfying n + q > p, the presentation (a, b; a n b q = b p , ba = b) with order induced by b > a is a counter-example of type 2.

Proof. We first compute the G-completion. There is only one composition available:

(a n b q -b p )a -a n b q-1 (ba -b) = -b p a + a n b q -b p + a n b q 0.
Hence the presentation (a, b; a n b q = b p , ba = b) is G-complete. Lemma 3.9 yields the result.

Remark 3.13. It is natural, as in Section 3.1, to define a type 2' presentation to be a presentation (S; R) satisfying R G R R and | R R | < ∞. However, contrary to the type 1', we could not find a presentation of type 2' so far. Most of the difficulty resides in the computation of R-completions. Indeed, during the completing process, the reversing operation often becomes, if it was not already, non-deterministic: if, at some point, we have two relations s . . . = s . . . at our disposal and s -1 s is to be reversed, then we can reverse in two different ways, leading to two different words. We denote by X 1 ⊔X 2 the disjoint union of two sets X 1 and X 2 (that is, X 1 ⊔X 2 = X 1 × {1} ∪ X 2 × {2}). Definition 3.14. Let (S 1 , R 1 ) and (S 2 , R 2 ) be two presentations. The direct product

(S 1 , R 1 ) × (S 2 , R 2 ) is the presentation (S 1 ⊔ S 2 , R 1 ⊔ R 2 ⊔ R) with R = {s 1 s 2 = s 2 s 1 ; s 1 ∈ S 1 , s 2 ∈ S 2 }.
In the sequel, the orderings considered on the direct product of two ordered presentations will be the deglex order where the letters are ordered as follows: the orders on S 1 and S 2 are preserved and we put max S 1 < min S 2 . Lemma 3.15. Let P be the direct product of the semigroup presentations (S 1 , R 1 ) and (S 2 , R 2 ). Then, using above notation, the reduced Gröbner basis of G and R 2 G . Because s 2 > s 1 holds for each s 2 in S 2 and s 1 in S 1 , the first letter of the leading word of every relation of R lies in S 2 and the last letter lies in S 1 . We leave the reader check that every composition of relations of R 2

P is R 1 G ⊔ R 2 G ⊔ R and its R-completed set of relations is R 1 R ⊔ R 2 R ⊔ R. Proof. To prove that R 1 G ⊔ R 2 G ⊔ R
G and R reduces to zero, the case involving R 1 G being similar. To prove that (S 1 ⊔ S

2 ; R 1 R ⊔ R 2 R ⊔ R
) is R-complete, it suffices to check that every two equivalent words can be proven so by reversing. Now, if u and v are equivalent, then we have u ≡ u 1 u 2 and v ≡ v 1 v 2 , with u 1 , v 1 in S * 1 and u 2 , v 2 in S * 2 , satisfying u 1 ≡ v 1 and u 2 ≡ v 2 . These latter equivalences are provable by reversing (since we have all the relations of R 1 R and R 2 R ) and one can check that finding a reversing of u -1 v to ε amounts to finding reversings of u -1 1 v 1 and u -1 2 v 2 to ε.

The next result gives a method to get type 3 counter-examples starting from counter-examples of type 1 and type 2. Proposition 3.16. Assume that (S 1 , R 1 ) is a counter-example of type 1, and that

(S 2 , R 2 ) is a counter-example of type 2. Then (S 1 , R 1 ) × (S 2 , R 2 ) is a counter- example of type 3. Proof. By hypothesis, the sets R 1 R ⊔ R 2 R and R 1 G ⊔ R 2 G
are not comparable. Thus, by Lemma 3.15, the Gröbner-and R-completions of (S 1 , R 1 ) × (S 2 , R 2 ) are not comparable.

The latter proposition gave a way to build type 3 counter-examples as direct products of type 1 and type 2 counter-examples. There are however less trivial presentations of type 3 not arising as direct products. Proposition 3.17. When equipped with the order c > b > a, the presentation (a, b, c; ab = bac, ac = ca, bc = cb) of the Heisenberg semigroup is a counter-example of type type 3.

Proof. Following [START_REF] Dehornoy | Complete positive group presentations[END_REF]Ex. 5.4], the R-completed presentation is (a, b, c; ab = bac, ac = ca, bc = cb, cba = ab). Using Algorithm 1.11, we find for the G-completion the set

{cb = bc, ca = ac} ∪ {ba n+1 c = aba n ; n ≥ 0} ∪ {ba 2n b = a n b 2 a n ; n ≥ 1} ∪ {ba 2n+1 b = a n baba n ; n ≥ 1}.
We first notice that the G-completion is infinite and therefore Heisenberg presentation is neither of type1', nor type 2, nor type 2'. We see that the relation ab = bac of the R-completion is not in the G-completion and thus Heisenberg presentation is not a type 1 counter-example.

Cancellativity

In this section, we compare R-complete and G-complete presentations in terms of cancellativity of the associated monoids. Here also, the two notions of complete presentations lead to divergent results: in the case of an R-complete presentation, left cancellativity can be read from the presentation directly, while no such result exists for a G-complete presentation.

4.1.

Reading cancellativity off a complete presentation. One of the nice features of an R-complete presentation is that one can very easily establish the possible left cancellativity property for the associated monoid by only inspecting the relations. In particular, we get that proving that a monoid is not left cancellative amounts to finding a relation su = sv in R for which u -1 v ε does not hold, i. e., the presentation being R-complete, a relation su = sv for which u ≡ v does not hold. This means that if there is an obstruction to cancellativity, then it appears in the relations of the presentation, as soon as it is R-complete.

When we consider G-complete presentations instead, the criterion of Proposition 4.1 remains necessary, but it is no longer sufficient. Proposition 4.2. (i) Assume (S; R) is a reduced G-complete presentation. If R contains a relation of the type su = sv with u, v nonempty words of S * , then the monoid S; R + is not left cancellative.

(ii) There exists a G-complete presentation (S; R) such that R contains no relation of the type su = sv with u, v nonempty words of S * , and nevertheless the monoid S; R + does not admit left cancellation.

Proof. (i) Suppose the monoid S; R + is left cancellative. Thus we have u ≡ v and u = v is not a relation of R, otherwise the presentation (S; R) would not be reduced. We prove that this is not possible.

Since we fixed an order compatible with the concatenation in the monoid, the inequality su > sv implies u > v. This latter inequality combined with the equivalence u ≡ v means that u or v can be reduced to its normal form. Hence suppose there is a relation w = w ′ in R with w a subword of u. This means that the relation su = sv was not reduced, which contradicts the hypothesis. The same applies to v. Thus there is no relation w = w ′ with w a subword of u or v. Therefore u and v must be reduced, which contradicts u > v.

(ii) Take the monoid presented by (a, b, c; ca = ba, cb = ba). With the homogeneous lexicographic order induced by c > b > a, this presentation is G-complete. From ca = ba and cb = ba we get ca ≡ cb. Now, a ≡ b does not hold and hence the monoid is not left cancellative. Proposition 4.2 establishes that for a presentation to give rise to a cancellative monoid, there has to be no relation s . . . = s . . . and conversely, that even without relation of the type s . . . = s . . ., there exist G-complete presentations associated to non cancellative monoids. In the proof, the relations of the presentation (a, b, c; ca = ba, cb = ba) suggest that cancellativity might be linked to the particular presentations possessing two relations su = w and sv = w with u = v and w not starting with an s. This is not the case: Proposition 4.3. There exist a G-complete presentation (S; R) such that the monoid S; R + is not left cancellative yet R contains no pair of relations su = w, sv = w with u = v and w not starting with s.

Proof. Consider the presentation (S; R) = (a, b, c, r, s, t; sba = tca, cab = bb, tbb = rcb, sa = rc) and the homogeneous lexicographic order induced by a < b < c < r < t < s. By Prop. 1.10 this presentation is G-complete. In the monoid S; R + , we have sab ≡ rcb and sbab ≡ rcb and hence sbab ≡ sab. If the monoid is left cancellative, then we must have bab ≡ ab. Now bab and ab are both reduced and therefore not equivalent. 4.2. Infinite completions. We have considered in Section 3.1 many infinite Gcompletions of presentations associated to cancellative monoids. Contrastingly, all above-mentioned examples involving an infinite R-completion turn out to be associated with monoids that are not left cancellative, and one could wonder whether this situation necessarily occurs. Actually, it is not the case: Denote by ♯ a<b (u) (resp. ♯ b<a (u)) the number of pairs (i, j) with i < j such that the ith letter of u is an a (resp. b) and the jth letter is a b (resp. a). We define λ on the set of words as follows:

λ(u) = |u| + 2♯ a<b (u) + ♯ b<a (u).

One checks on the relations of (4.1) that λ is a pseudolength. Applying Algorithm 2.9, we find that the R-completion for the presentation of (4.1) is the set {ab = bac, bc = cbd, da = ad, bd = db, dc = cd} ∪ {b(ac) n c = da n cb; n ≥ 0}.

Finally, Proposition 4.1 and the fact that there is no relation s . . . = s . . . in (4.1) imply that the associated monoid is left cancellative.

As for right cancellativity, we appeal to left reversing [START_REF] Dehornoy | Complete positive group presentations[END_REF], a notion symmetric to that of (right) reversing. As the (right) R-completeness involved in Proposition 4.1 leads to left cancellativity, left R-completeness leads to right cancellativity. So it suffices to prove that the presentation (4.1) is left R-complete; this is similar to proving its right R-completeness and hence we omit it.

( 2 )

 2 ba 3 b = a 4 b. Thus we obtain U 1 = {bab = ba 2 , ba 3 b = ba 4 }. There is no reduction since bab is not a subword of ba 3 b. Composing (2) with (1), we get: (ba 3 b -ba 4 )ab -ba 3 (bab -ba 2 ) = -ba 4 ab + ba 3 ba 2 (2) -ba 5 b + a 6 b, and therefore the relation (3) ba 5 b = a 6 b. We obtain U 2 = {bab = ba 2 , ba 3 b = ba 4 , ba 5 b = ba 6 }. We claim that the algorithm successively adds all relations (n) ba 2n-1 b = a 2n b.

Figure 2 .

 2 Figure 2. Case of the presentation (a, b; bab = ba 2 ), reversing of b -1 bb -1 b. Because the relation bab = ba 2 is of the type b . . . = b . . ., the reversing of b -1 bb -1 b is not deterministic: at each reversing step of the type b -1 b, one can either delete the subword b -1 b or replace it with aba -2 . Among the possible reversings, we only consider those of the form b -1 bb -1 buv -1 in order to apply Proposition 2.10.

4 =Figure 3 .

 43 Figure 3. Case of the presentation (a, b; bab = ba 2 ), reversing of (ba 4 )-1 ba 3 b: despite the equivalence ba 4 ≡ ba 3 b, the word (ba 4 ) -1 ba 3 b does not reverse to ε. The relation ba 4 = ba 3 b is therefore added to the presentation so that this equivalence is now provable in terms of reversing.

Fact 2 .Figure 4 .

 24 Figure 4. Reversing of the word b -1 bb -1 b to a 2n+2 (a 2n+1 b) -1 , using relations added to the presentation (a, b; bab = ba 2 ). The word ba 2n+2 -1 ba 2n+1 b does not reverse to ε since no relation of the type b . . . = a . . . has been added so far. Other simple presentations, such as (a, b; a 2 b = ba 2 , ba 2 = a 2 b) or the Baumslag-Solitar presentations (a, b; ba = a n b), give rise to a similar coincidence phenomenon. So it is natural to raise

3. 1 .

 1 Type 1 counter-examples. It is relatively easy to find type 1 counterexamples, and we shall exhibit various families. Proposition 3.2. Every presentation (3.1) (a, b, c, . . . ; bwb = abw), w ∈ {a, b, c, . . .} *

3 .

 3 The presentation (a, b; bab = aba) of the braid monoid B + 3 , with deglex order induced by b > a, satisfies the hypotheses of Proposition 3.2 and is therefore a type 1 counter-example. An easy computation [1, Lemma 4.1] gives the Proof. It is a standard result, deduced from Proposition 2.10, that the monoids B + n are R-complete.

Proposition 3 . 8 . 3 . 2 .Lemma 3 . 9 .

 383239 For every n ≥ 1 and p ≥ 1, the presentation (3.3) (a, b; (ab) n a = b p ) together with the homogeneous lexicographic ordering induced by b > a is a type 1' counter-example. Proof. A 2-generator presentation (a, b; R) whose sole relation has the form a . . . = b . . . is R-complete [4, Prop. 6.4], and hence the presentation (3.3) is R-complete. Then, using Proposition 1.10, one checks that the set B = {(ab) n a = b p , b p+1 a = ab p+1 } is the reduced Gröbner basis of the presentation (3.3). Type 2 counter-examples. In this section, we give examples of presentations whose G-completion is properly included in their R-completion. Assume that (a, b; R) is a presentation with no relation a . . . = a . . . or b . . . = b . . .. Then, for each nonempty word w on {a, b}, the R-completion of (a, b; R, bw = b) includes {bw n = b; n ∈ N}.Proof. The relation bw = b implies bw n ≡ b, with n ≥ 1. We prove by induction on n, that (bw n ) -1 b cannot be reversed to ε even if all the relations bw m = b, m < n, have been added to the presentation. Since (bw 2 ) -1 b reverses to w -1 , we can assume n > 2. By hypothesis, there is no relation s . . . = s . . . in R and hence, the only reversings of (bw n ) -1 b are, for every p and m satisfying p < m < n, (bw n )-1 b w -m w p (w m-p ) -1 ; this completes the induction. Proposition 3.10. Under hypotheses of Lemma 3.9, every G-complete presentation (a, b; bw = b) is a counter-example of type 2. Proof. By Lemma 3.9, the R-completion of (a, b; bw = b) contains the set {bw n = b; n ∈ N} which, in turn, contains the G-completion, namely {bw = b}. Example 3.11. The simpliest instance of Proposition 3.10 is the presentation (a, b; ba = b) whose Gröbner basis consists in the sole relation ba = b and whose R-completion is {ba n = b; n ∈ N}.

Proposition 4 . 1 (

 41 [START_REF] Dehornoy | Complete positive group presentations[END_REF] Prop. 6.1]). Assume that (S; R) is an R-complete presentation. Then the monoid S; R + admits left cancellation if and only if u -1 v ε holds for every relation of the form su = sv in R with s ∈ S.

Proposition 4 . 4 .

 44 There exists a finite presentation admitting an infinite R-completion yet the associated monoid is left and right cancellative. Proof. Consider the presentation (4.1) (a, b, c, d; ab = bac, bc = cbd, da = ad, bd = db, dc = cd).

  3.3. Type 3 counter-examples. We conclude with examples where both completions are incomparable with respect to inclusion. First, we observe that mixing examples of what were called types 1 and 2 immediately leads to examples of type 3. But, then, we show that less artificial examples exist, namely the standard Heisenberg presentation.

  is the reduced Gröbner basis of P, by Proposition 1.10, it suffices to check that all compositions reduce to zero. There are no compositions left neither in R 1 G nor in R 2 G since both sets are reduced. It is obvious that R contains no composition either. The only possible compositions not reducing to zero must therefore involve relations of two different sets among R 1 G , R 2 G and R. Since S 1 and S 2 have no intersection, there are no possible compositions between R 1

Acknoledgments.

The author is greatly indebted to Patrick Dehornoy for suggesting the problem and for his many helpful comments.

We may assume that the presentation has the form (a, b;

n with itself as follows:

Compose the resulting relation with (ba) n = (ab) n to get

Iterating these compositions yields the family of relations

By Proposition 1.10, it suffices to check that every composition reduces to zero. We compute the composition of ba p (ba) n = (ba) n ba p with ba q (ba) n = (ba) n ba q and leave the other compositions to the reader: (ba p (ab)

n -(ab) n ba p )a q (ab) n -ba p (ab) n-1 a(ba q (ab) n -(ab) n ba q ) = -(ab) n ba p+q (ab) n + ba p (ab) n-1 a(ab) n ba q -(ab) n (ab) n ba p+q + ba p (ab) n-2 aba(ab) n ba q -(ab) 2n ba p+q + ba p+1 (ab) n (ba) n-1 ba q -(ab) 2n ba p+q + (ab) n ba p+1 (ba) n-1 ba q -(ab) 2n ba p+q + (ab) n ba p (ab) n a q -(ab) 2n ba p+q + (ab) n (ab) n ba p a q = 0.

Another infinite family of type 1 counter-examples extending Example 3.3 in an other direction than Proposition 3.4 is the family of standard presentations of braid monoids: Proposition 3.5. For n ≥ 3, the Artin presentation (3.2) σ 1 , . . . , σ n-1 σ i σ j σ i = σ j σ i σ j for |j -i| = 1 σ i σ j = σ j σ i for |j -i| ≥ 2 of the braid monoid B + n is a type 1 counter-example.


Sarah Wassermann
email: sarah.wassermann@inria.fr

Pedro Casas
email: pedro.casas@ait.ac.at

Distributed Internet Paths Performance Analysis through Machine Learning

Keywords: Distributed Active Measurements, Reverse Traceroute, RIPE Atlas Measurement Framework, Machine Learning, M-Lab

Internet path changes are frequently linked to path inflation and performance degradation; therefore, predicting their occurrence is highly relevant for performance monitoring and dynamic traffic engineering. In this paper we showcase Dis-NETPerf and NETPerfTrace, two different and complementary tools for distributed Internet paths performance analysis, using machine learning models.

I. INTRODUCTION

Monitoring Internet paths performance is critical for general network management. DisNETPerf [START_REF] Wassermann | On the Analysis of Internet Paths with DisNET-Perf, a Distributed Paths Performance Analyzer[END_REF] and NETPerfTrace [START_REF] Wassermann | NETPerfTrace -Predicting Internet Path Dynamics and Performance with Machine Learning[END_REF] serve as powerful tools for tracking and analyzing Internet paths. DisNETPerf is a distributed platform capable of doing reverse traceroute measurements, collecting path measurements from any source to any destination, even when the source is not under the control of the experimenter. DisNETPerf uses RIPE Atlas, a largely distributed active measurements platform to perform traceroute measurements from any arbitrarily selected server in the Internet. NETPerfTrace is an Internet Path Tracking system capable of forecasting path changes and path latency variations, by analyzing traceroute measurements through machine learning models. NETPerfTrace can predict the remaining life time of a path before it actually changes, the number of path changes in a certain time-slot, as well as path latency metrics, providing a system which could not only predict path changes but also forecast their impact in terms of performance variations. Both DisNETPerf and NETPerfTrace are distributed as open software to the network measurement community.

II. REVERSE TRACEROUTE WITH DISNETPERF

The primary goal of DisNETPerf is to compute and monitor the path from a given content server to a specific user. The current version of DisNETPerf locates the closest RIPE Atlas probe to this content server, and gathers information about the path leading from the selected probe to the customer. DisNETPerf is open source and freely available on GitHub (https://github.com/SAWassermann/DisNETPerf).

DisNETPerf uses a combined topology-and delay-based distance notion to locate a RIPE Atlas probe that is as close as possible to a desired target destination, from which reverse traceroute measurements should be run. By doing so, DisNETPerf aims at locating probes which offer a very high path similarity to the real reverse path. Fig. 1 describes the overall idea behind the DisNETPerf approach. In a nutshell, given a certain content server with IP address IP s , and a destination customer with IP address IP d , DisNETPerf pinpoints the closest box, namely IP c , using a combined topology-and delay-based distance: probes are located first by AS -using BGP routing proximity to select probes in the same AS as IP s -and then by propagation delay -for electing the closest probe to IP s . DisNETPerf then periodically runs traceroute measurements from IP c to IP d , collecting different path performance metrics such as RTT per hop, end-to-end RTT, etc. This data might then be used to troubleshoot paths from the content server (mimicked by IP c ) to the target customer.

Current DisNETPerf implementation uses two different probe-selection approaches for locating IP c , partially proposed in the literature for IP geolocation [START_REF] Katz-Bassett | Towards IP geolocaiton using delay and topology measurements[END_REF], [START_REF] Padmanabhan | An investigation of geographic mapping techniques for Internet hosts[END_REF], [START_REF] Liao | A lightweight network proximity service based on neighborhood models[END_REF]. We called these selection approaches the smallest latency (SL) approach and the landmark (LM) approach, which we describe next.

A. Probe Selection by Smallest Latency

The SL approach starts by determining whether RIPE Atlas probes are located in the same AS as the targeted content server IP s . If this is not the case, the SL approach tries to locate probes in the neighbor ASes of IP s . Neighborhood information is obtained through AS relationships. We use CAIDA's AS relationships dataset [START_REF]AS relationships[END_REF]. If no probes are found in the neighbor ASes, then the SL approach randomly selects a large (and configurable) set of boxes among all the available ones. We call these pre-selected probes the "candidate probes". Once the candidate probes have been identified, the selection of IP c can start.

The SL approach then selects as IP c the candidate probe with the smallest latency to the target IP s . Latency is computed on the basis of standard ping measurements; more precisely, the SL approach issues 10 ping measurements from each of the candidate probes toward IP s . The candidate probe with the smallest minimum RTT to IP s is finally elected as the representative probe of the content server, i.e., IP c . We consider the minimum RTT as it provides a rough estimation of the propagation delay between two IP addresses.

B. Probe Selection using Landmarks

The first step of the LM approach is exactly the same as the one followed by the SL approach, i.e., candidate probes are firstly selected based on their AS. However, the continuation is slightly different. The next step consists of grouping the candidate probes in two different sets: the landmarks and the probes that can be elected as IP c . Landmarks are chosen randomly among all the candidate probes. Then, 10 ping measurements are issued from of the landmarks toward IP s and toward all the candidate probes belonging to the other set. For each pinged IP address, a feature vector d is computed, containing the minimum RTT from each landmark to this IP address. Finally, IP c is selected as the probe with the most similar feature vector to the one of IP s , according to the following normalized distance:

D ij = 1 K K l=1 |d il -d jl |,
where K is the number of landmarks providing a RTT for both IP i and IP j , and d il is the minimum RTT between IP i and landmark l. When D ij is small, we assume that IP i and IP j are close to each other. Current DisNETPerf implementation uses 20 landmarks for each IP s .

III. PREDICTING INTERNET PATH DYNAMICS WITH NETPERFTRACE

We define a path P as a sequence of links connecting a certain fixed source s to a fixed destination d. At any time t, path P (t) is realized by a specific route r: this route consists of a specific sequence of links connecting s to d, and has an associated initial time t 0 when the route becomes active or in-place, and a final time t f which corresponds to the time when r changes to another route realization, i.e., when the actual route changes. From now on, we therefore refer to route changes instead of path changes. As such, a path P (t) can be considered as a statistical time process, composed of a set of time-contiguous routes r i (t i 0 , t i f ), each one with a duration D(r i ) = t i f -t i 0 . For the sake of notation, we say that r i ∈ P . We additionally define the duration of a route r as D(r) = t f -t 0 , its current life time or route age at time t as L r (t) = t -t 0 , and its remaining life (i.e., time before a route change) at time t as R r (t) = t f -t. Finally, we define rc P (t) as the total number of route changes observed so far at time t for path P and rc P T (t) as the number of route changes observed so far at time t for path P in the current time-slot T .

Given a new traceroute measurement at time t, the prediction problem solved by NETPerfTrace includes three prediction targets: (i) the remaining life time R r (t) of route r, namely R r (t), (ii) the number of route changes a path P experiences over a specific future time-window of length T , defined as rc P T , and (iii) the average RTT that path P will experience in the next traceroute measurement, defined as avgRT T P (t + ε), where ε represents the duration until the next measurement. The first two targets correspond to path dynamics prediction, whereas the third target consists of path performance forecasting. In practice, when R r (t) comes closer to zero, we would increase the sampling rate to better monitor the path performance in the event of a route change. Predicting rc P T allows to dynamically identify which paths are more prone to frequent changes, and thus better allocate new traceroute measurements. Based on previous results on route stability [START_REF] Paxson | End-to-end Routing Behavior in the Internet[END_REF], [START_REF] Cunha | Measuring and Characterizing End-to-End Route Dynamics in the Presence of Load Balancing[END_REF] and similar to [START_REF] Cunha | Predicting and Tracking Internet Path Changes[END_REF], we focus on predicting the number of daily route changes for the next day, i.e., T = 24 hours from now on. At last, predicting the average RTT that a certain path P would experience next becomes highly relevant for dynamic traffic engineering purposes, and when combined with the prediction of route changes, it can provide a very powerful approach to forecast those performance-harmful route changes. To predict these three targets, NETPerfTrace uses a rich set of input features describing the statistical properties of route dynamics and path latency [START_REF] Wassermann | NETPerfTrace -Predicting Internet Path Dynamics and Performance with Machine Learning[END_REF]. NET-PerfTrace is released as open software to the communityhttps://github.com/SAWassermann/NETPerfTrace.

By carefully engineering NETPerfTrace underlying model and input features, we show in [START_REF] Wassermann | NETPerfTrace -Predicting Internet Path Dynamics and Performance with Machine Learning[END_REF] that NETPerfTrace highly outperforms DTRACK [START_REF] Cunha | DTRACK: A system to Predict and Track Internet Path Changes[END_REF], a previous system with the same prediction targets. In particular, NETPerfTrace outperforms DTRACK by a factor of 5 when forecasting the residual lifetime of a path with relative prediction errors below 10%, and by a factor of 7 in correctly predicting daily path changes.

Figure 1 .

 1 Figure 1. DisNETPerf overview. The first step of DisNETPerf consists of selecting a monitoring point or probe located as close as possible to a target server, to later on perform traceroute measurements towards specific destinations.