Patrick Dehornoy
email: dehornoy@math.unicaen.fr

MONOIDS OF O-TYPE, SUBWORD REVERSING, AND ORDERED GROUPS

Keywords: Classification. 06F15, 20M05, 20F60 monoid presentation, subword reversing, divisibility, quasi-central element, ordered group, space of orderings, Garside theory

Monoids of O-type, subword reversing, and ordered groups

main new observation is that subword reversing can be useful even in a context where the traditional Noetherianity assumptions fail.

The outcome is the construction of families of finitely generated monoids of O-type, hence of ordered groups with isolated points in the space of left-orderings, together with algorithmic tools for analysing these structures. There is a close connection with Garside theory [START_REF] Dehornoy | Garside Theory[END_REF] as most of the mentioned examples admit a Garside element. The scheme can be summarized as follows (see Theorem 6.5 for a more general version): Theorem 1. A sufficient condition for a group G to be orderable is that G admits a (finite or infinite) presentation ( * ) (a 1 , a 2 , ... ; a 1 = a 2 w 2 a 2 , a 2 = a 3 w 3 a 3 , ...) where w 2 , w 3 , ... are words in {a 1 , a 2 , ...} (no a -1 i ) and there exists in the monoid presented by ( * ) an element ∆ such that there exist g 1 , g ′ 1 , g 2 , g ′ 2 ,... satisfying a 1 g 1 = ∆ = g ′ 1 a 1 and a i ∆ = ∆g i and ∆a i = g ′ i ∆ for i 2. Then, the subsemigroup of G generated by a 1 , a 2 ,... is the positive cone of a left-invariant ordering on G. If ( * ) is finite, this ordering is isolated in the space LO(G). If ( * ) is finite or recursive, the word problem of G and the decision problem of the ordering are decidable.

Among others, the approach applies to the above mentioned torus knot groups, providing a short construction of an isolated ordering, and in particular to the group B 3 of 3-strand braids, providing one more proof of its orderability. More examples are listed in Table 1 and in Section 8 below.

1:

x, y | x p+1 =y q+1 (a, b ; a = b(a p b) q ) ∆ = a p+1 central (Proposition 8.1); 2:

x, y, z | x p+1 = y q+1 , y r+1 = z s+1 (a, b, c ; a = b(a p b) q , b = c((a p b) r a p c) s ) ∆ = a (p+1)(r+1) central (Proposition 8.4); 3:

x, y | x p+1 = (y(x r-p y) s ) q+1 (a, b ; a = b(a r b) s (a p b(a r b) s ) q ) with r p δ = a dominating (Proposition 8.7); is also a, b, c | a = b(a p b) q , b = c(a r c) s ; 4:

x, y | x r+1 = (yx 2 y) q+1 (a, b, c ; a = ba 2 (b 2 a 2 ) q c, b = c(ba 2 ) r ba) with r = 0 or r = 1 ∆ = (ba 2 ) 2q+r+3 central (Proposition 8.9).

Table 1. Some groups eligible for the current approach, hence ordered with an isolated point in the space of orderings: on the right, a presentation eligible for Theorem 1 or its extensions and the involved distinguished element ∆.

The paper is organized as follows. In Section 1, we introduce the notion of a monoid of O-type and describe its connection with ordered groups. In Section 2, we define triangular presentations, raise the central question, namely recognizing when a (right)-triangular presentation defines a monoid of (right)-O-type (and therefore leads to an ordered group), and state without proof the main technical result ("Main Lemma"), which reduces the central question to the existence of common right-multiples. Section 3 contains a brief introduction to subword reversing, with observations about the particular form it takes in the context of right-triangular presentations. In Section 4, we establish that every right-triangular presentation is what we call complete for right-reversing, and deduce a proof of the Main Lemma. Next, we investigate in Section 5 the notions of a dominating and a quasi-central element in a monoid and, putting things together, we obtain the expected sufficient conditions for a presentation to define a monoid of O-type. The proof of Theorem 1 is then completed in Section 6. Then, we report in Section 7 about some computer investigations and, in Section 8, we describe some examples, in particular those mentioned in Table 1. Finally, in Section 9, we establish some negative results about the existence of triangular presentations, and gather some open questions in Section 10.

The author thanks A. Navas, L. Paris, C. Rivas, and D. Rolfsen for discussions about the subject of the paper.

Monoids of O-type

If G is an orderable group and < is a left-invariant ordering of G, the positive cone P < of <, i.e., the set {g ∈ G | g > 1}, is a subsemigroup of G satisfying G = P < ∐ P < -1 ∐ {1}. Conversely, if P is a subsemigroup of G satisfying G = P ∐ P -1 ∐ {1}, then the relation g -1 h ∈ P defines a left-invariant ordering on G and P is the associated positive cone.

In the sequel, the notions of divisors and multiples will play a central role. It is convenient to consider them in the context of monoids, i.e., semigroups with a unit. Definition 1.1. Assume that M is a monoid. For g, h in M , we say that g is a left-divisor of h, or, equivalently, h is a right-multiple of g, denoted g h, if there exists h ′ in M satisfying gh ′ = h. Symmetrically, we say that g is a right-divisor of h, or, equivalently, h is a left-multiple of g, denoted h g, if there exists h ′ in M satisfying h = h ′ g.

For every monoid M , left-and right-divisibility are partial preorders on M , and they are partial orders whenever 1 is the only invertible element of M . Note that the right-divisibility relation of a monoid M is the left-divisibility relation of the opposite monoid M , i.e., the monoid with the same domain equipped with the operation defined by g • h = hg.

It is easy to translate the existence of an invariant ordering in a group into the language of monoids and divisibility. We recall that a monoid is called left-cancellative (resp. rightcancellative), for all g, g ′ , h in the monoid, hg = hg ′ (resp. gh = g ′ h) implies g = g ′ . A monoid is cancellative if it is both left-and right-cancellative. The monoids we shall investigate are as follows.

Definition 1.2. A monoid M is said to be of right-O-type (resp. left-O-type) if M is leftcancellative (resp. right-cancellative), 1 is the only invertible element in M , and, for all g, h in M , at least one of g h, h g (resp. g h, h g) holds. A monoid is of O-type if it is both of right-and left-O-type.

In other words, a monoid M is of right-O-type if it is left-cancellative and left-divisibility is a linear ordering on M , and it is of O-type if it is cancellative and left-and rightdivisibility are linear orderings on M . The letter O stands for "order"; it may seem strange that the notion connected with left-divisibility is called "right-O-type", but this option is natural when one thinks in terms of multiples and it is more coherent with the forthcoming terminology. The connection with ordered groups is easy.

Lemma 1.3. For G a group and M a submonoid of G, the following are equivalent:

(i) The group G admits a left-invariant ordering whose positive cone is M \{1};

(ii) The monoid M is of O-type.

Proof. Assume (i). Put P = M \{1}. First, by assumption, M is included in a group, hence it must be cancellative. Next, assume that g is an invertible element of M , i.e., there exists h in M satisfying gh = 1. If g belongs to P , then so does h and, therefore, g belongs to P ∩ P -1 , contradicting the assumption that P is a positive cone. So 1 must be the only invertible element of M . Now, let g, h be distinct elements of M . Then one of g -1 h, h -1 g belongs to P , hence to M : in the first case, g h holds, in the second, h g. Symmetrically, one of gh -1 , hg -1 belongs to P , hence to M , now implying g h or h g. So any two elements of M are comparable with respect to and . Hence M is of O-type, and (i) implies (ii).

Conversely, assume that M is of O-type. Put P = M \{1} again. Then P is a subsemigroup of G. The assumption that 1 is the only invertible element in M implies P ∩ P -1 = ∅. Next, the assumption that any two elements of M are comparable with respect to implies a fortiori that any two of its elements admit a common right-multiple. By Ore's theorem [START_REF] Clifford | The algebraic Theory of Semigroups[END_REF], this implies that G is a group of right-fractions for M , i.e., every element of G admits an expression of the form gh -1 with g, h in M . Now, let f be an element of G. As said above, there exist g, h in M satisfying f = gh -1 . By assumption, at least one of g h, h g holds in M . This means that at least one of f ∈ M , f ∈ M -1 holds. Therefore, we have G = M ∪ M -1 , which is also G = P ∪ P -1 ∪ {1}. So P is a positive cone on G, and (ii) implies (i).

It will be convenient to restate the orderability criterion of Lemma 1.3 in terms of presentations. A group presentation (S ; R) is called positive [START_REF] Dehornoy | Complete positive group presentations[END_REF] if R a family of relations of the form u = v, where u, v are nonempty words in the alphabet S (no empty word, and no letter s -1 ). Every positive presentation (S ; R) gives rise to two structures, namely a monoid, here denoted S | R + , and a group, denoted S | R . Note that a monoid admits a positive presentation if and only if 1 is the only invertible element. Also remember that, in general, the monoid S | R + need not embed in the group S | R . Proposition 1.4. A necessary and sufficient condition for a group G to be orderable is that G admits a positive presentation (S ; R) such that the monoid S | R + is of O-type.

In this case, the subsemigroup of G generated by S is the positive cone of a left-invariant ordering on G. If S is finite, this ordering is an isolated point in the space LO(G).

Proof. Assume that G is an orderable group. Let P be the positive cone of a left-invariant ordering on G, and let M = P ∪ {1}. By the implication (i) ⇒ (ii) of Lemma 1.3, the monoid M is of O-type. As 1 is the only invertible element in M , the latter admits a positive presentation (S ; R). As G = M ∪ M -1 holds, G is a group of right-fractions for M . By standard arguments, this implies that (S ; R) is also a presentation of G.

Conversely, assume that G admits a positive presentation (S ; R) such that the monoid S | R + is of O-type. Let M be the submonoid of G generated by S, and let P = M \{1}. As observed in the proof of Lemma 1.3, Ore's theorem implies that S | R + embeds in a group of fractions, and the latter admits the presentation (S; R), hence is isomorphic to G. Hence, the identity mapping on S induces an embedding ι of S | R + into G. Therefore, the image of ι, which is the submonoid of G generated by S, hence is M , admits the presentation (S ; R). So the assumption implies that M is of O-type. Then, by the implication (ii) ⇒ (i) of Lemma 1.3, P is the positive cone of a left-invariant ordering on G.

As for the last point, the definition of the topology on the space LO(G) [START_REF] Sikora | Ceilingology on the spaces of orderings of groups[END_REF] implies that, if the positive cone of a left-ordering on the group G is generated, as a semigroup, by a finite set S, then the ordering is an isolated point in the space LO(G) because this ordering is the only one in which S is positive and the set of all such orderings is open.

Triangular presentations

We are thus led to looking for monoids of O-type and, more specifically, for recognizing which presentations define monoids of O-type. Owing to the symmetry of the definition, we shall mainly focus on recognizing monoids of right-O-type and then use the criteria for the opposite presentation. Now, if a monoid M is of right-O-type and it is generated by some subset S, then, for all s, s ′ in S, the elements s and s ′ are comparable with respect to , i.e., s ′ = sg holds for some g, or vice versa. In other words, some relation of the particular form s ′ = sw must be satisfied in M . We shall consider presentations in which all relations have this form (see Section 9 for a discussion about the relevance of this approach). Clearly, the problem in Example 2.3 is the existence of several relations c = ... simultaneously. We are thus led to restricting to particular families of triangular relations. If S is a nonempty set, we denote by S * the free monoid of all words in the alphabet S. We use ε for the empty word. Definition 2.4. A positive presentation (S; R) is called right-triangular if there exist S ′ ⊆ S and maps N ("next") : S ′ → S and C ("complement") : S ′ → S * \{ε} such that N is injective with no fixpoint and R consists of the relations N (s) = sC(s) for s in S ′ . We write If (S ; R) is a right-triangular presentation, the family R is a sort of transitive closure of R, and the presentations (S ; R) and (S ; R) define the same monoid and the same group. Triangular presentations can be described in terms of the left-and right-graphs [START_REF] Adyan | Defining relations and algorithmic problems for groups and semigroups[END_REF][START_REF] Remmers | On the geometry of positive presentations[END_REF]. The left-graph (resp. right-graph) of (S ; R) is the unoriented graph with vertex set S such that {s, s ′ } is an edge if and only if there exists a relation s... = s ′ ... (resp. ...s = ...s ′ ) in R. Then a presentation (S ; R) is right-triangular if it consists of triangular relations and, in addition, the left-graph of (S ; R) is a union of discrete chains. In practice, we shall be mostly interested in the case when there is only one (countable) chain, in which case there exists a (finite or infinite) subset I of Z such that S is {a i | i ∈ I} and R consists of one relation a i-1 = a i w i for each i in I that is not minimal.

C i (s) for C(s)C(N (s))•••C(N i-1 (s)) when N i (s) is defined, and R for R ∪ {N i (s) = sC i (s) | i 2}. A left-
Our main technical result will be a criterion for recognizing which right-triangular presentations give rise to a monoid of right-O-type. The proof of the Main Lemma will be completed at the end of Section 4 below. Merging the result with Proposition 1.4 immediately provides the following sufficient condition of orderability.

Corollary 2.7. A sufficient condition for a group G to be orderable is that G admits a triangular presentation (S ; R) such that any two elements of the monoid S | R + have a common right-multiple and a common left-multiple. In this case, the subsemigroup of G generated by S is the positive cone of a left-invariant ordering on G. If S is finite, this ordering is an isolated point in the space LO(G).

Proof. By the Main Lemma, the monoid S | R + , which admits a right-triangular presentation is of right-O-type, and so is the opposite monoid. Hence S | R + is also of left-O-type, and therefore it is of O-type. Then Proposition 1.4 implies that G is orderable, with the expected explicit ordering.

Subword reversing

We shall prove the Main Lemma by using subword reversing. In essence, subword reversing is a strategy for constructing van Kampen diagrams in a context of monoids, i.e., equivalently, for finding derivations between words, and we shall see that it is especially relevant for investigating triangular presentations (due to the special form of triangular presentations, it might well be that alternative arguments using rewrite systems or other approaches also exist, but this is not clear).

The description given below is sketchy, as we only mention the definition and the needed technical results. We refer to [START_REF] Dehornoy | Complete positive group presentations[END_REF][START_REF] Dehornoy | The subword reversing method[END_REF] for additional motivation and explanation.

As is usual with presented groups, if S is an alphabet, we introduce a formal copy S -1 of S consisting of one letter s -1 for each letter of S. The letters of S are then called positive, whereas those of S -1 are called negative. Accordingly, a word in the alphabet S ∪ S -1 will be called a signed S-word, whereas a word in the alphabet S is called an S-word, or a positive S-word if we wish to insist that there is no negative letter. If w is a signed S-word, w -1 denotes the word obtained from w by exchanging s and s -1 everywhere and reversing the order of the letters. A word of the form u -1 v with u, v positive is called negative-positive. Definition 3.1. Assume that (S ; R) a positive presentation and w, w ′ are signed S-words. We say that w is right-R-reversible to w ′ in one step, denoted w

w = w 1 s -1 s ′ w 2 and w ′ = w 1 v ′ v -1 w 2 ,
or there exist s in S and signed S-words w 1 , w 2 satisfying

(3.2) w = w 1 s -1 s w 2 and w ′ = w 1 w 2 .
We say that w is right-R-reversible to w ′ in n steps, denoted w

(n)
R w ′ , if there exist w 0 , ..., w n satisfying w 0 = w, w n = w ′ and w i (1) R w i+1 for each i. We write w R w ′ if w (n) R w ′ holds for some n. Note that (3.2) becomes an instance of (3.1) if, for every s in S, the trivial relation s = s is considered to belong to R. Right-reversing consists in replacing a negative-positive length two subword with a positive-negative word, hence somehow reversing the signs, whence the terminology. We shall often write "reversing" for "right-reversing" (except at the end of Section 5 where left-reversing, the symmetric counterpart of right-reversing, occurs).

w = a -1 c -1 a (1) R a -1 bcab (1) R b -1 a -1 cab,
where, at each step, the reversed subword is underlined. Observe that the word obtained after two reversing steps is b -1 w -1 b, so that w (4n) R b -2n wb 2n holds for every n.

It is useful to associate with every sequence of reversing steps a rectangular grid diagram that illustrates it (see [START_REF] Dehornoy | The subword reversing method[END_REF] for full details). Assume that w 0 , w 1 , ... is an R-reversing sequence, i.e., w i (1) R w i+1 holds for every i. The diagram is analogous to a van Kampen diagram, and it is constructed inductively. First we associate with w 0 a path shaped like an ascending staircase by reading w 0 from left to right and iteratively appending a horizontal rightoriented edge labeled s for each letter s, and a vertical down-oriented edge labeled s for each letter s -1 . Then, assume that the diagram for w 0 , ..., w i has been constructed, and w i+1 is obtained from w i by reversing some subword s -1 s ′ into v ′ v -1 . Inductively, the subword s - If (S ; R) is a positive presentation, and u, v are S-words, applying iterated subword reversing to the signed word u -1 v may lead to three different behaviours:

-either the process continues for ever (as in the case of Example 3.2), -or one gets stuck with a factor s -1 s ′ such that R contains no relation s... = s ′ ..., -or the process leads in finitely many steps to a positive-negative word v ′ u ′-1 where u ′ and v ′ are S-words (no letter s -1 ): then the sequence cannot be extended since the last word contains no subword of the form s -1 s ′ ; this case corresponds to a reversing diagram of the form

v u v ′ u ′ R
, and we shall then say that the reversing of u -1 v is terminating.

We shall use without proof two (elementary) results about reversing. The first one connects R-reversing with R-equivalence and it expresses that a reversing diagram projects to a van Kampen diagram when the vertices connected with equality signs are identified. Notation 3.3. For (S ; R) a positive presentation, we denote by ≡ + R the smallest congruence on S * that includes R, so that S | R + is S * /≡ + R . For w an S-word, we denote by [w] + the ≡ + R -class of w, i.e., the element of the monoid S | R + represented by w.

Lemma 3.4. [7, Proposition 1.9] Assume that (S; R) is a positive presentation, and u, v, u ′ , v ′ are S-words satisfying u

-1 v R v ′ u ′-1 . Then uv ′ ≡ + R vu ′ holds. In particular, u -1 v R ε implies u ≡ + R v.
In other words, the existence of a reversing diagram

v u v ′ u ′ R implies uv ′ ≡ + R vu ′ , which also reads [u] + [v ′ ] + = [v] + [u ′
] + : the element represented by uv ′ and vu ′ is a common right-multiple of [u] + and [v] + in the associated monoid. Thus subword reversing can be seen as a tool for constructing common right-multiples in presented monoids.

The second basic result says that, when the reversing of a compound word u -1 v 1 v 2 terminates, the reversing steps involving v 1 and v 2 can be separated.

Lemma 3.5. [7, Lemma 1.8] Assume that (S ; R) is a positive presentation and u, v, u ′ , v ′ are S-words satisfying u -1 v (n) R v ′ u ′-1 .
Then, for every decomposition v = v 1 v 2 , there exist an S-word u 0 and decompositions

v ′ = v ′ 1 v ′ 2 and n = n 1 + n 2 such that u -1 v 1 (n1) R v ′ 1 u -1 0 and u -1 0 v 2 (n2) R v ′ 2 u ′-1 hold.
In other words, every diagram

v 1 v 2 u v ′ u ′ (n) R splits into v 1 v 2 u v ′ 1 v ′ 2 u 0 u ′ (n1) R (n2) R .
Here comes the first specific observation about reversing with triangular relations.

Lemma 3.6. If (S ; R) is a positive presentation consisting of triangular relations, and

u, v, u ′ , v ′ are S-words satisfying u -1 v R v ′ u ′-1 , then at least one of u ′ , v ′ is empty.
Proof. We use induction on the number of reversing steps, i.e., the number n such that

u -1 v (n) R v ′ u ′-1 holds.
For n = 0, the only possibility is that u, v, u ′ , v ′ all are empty and the result is trivial. For n = 1, the only possibility is that u or v consists of one letter, say for instance u = s ∈ S. Write v = s ′ w with s ′ in S. If the (unique) reversing step is of the type s -1 s ε, we obtain u ′ = ε (and v ′ = w). Otherwise, the reversing step is either of the type s -1 s ′ w ′ with sw ′ = s ′ a relation of R, or of the type s -1 s ′ w ′-1 with s ′ w ′ = s a relation of R. In the first case, we obtain u ′ = ε (and v ′ = w ′ w); in the second case, the final word w ′-1 w is positive-negative only if w is empty, and, in this case, we have v ′ = ε (and u ′ = w ′ ). The argument is similar if v, instead of u, has length one.

Assume now n 2. Then at least one of the words u, v has length two or more. Assume that v does, and write it as v 1 v 2 with v 1 , v 2 nonempty. By Lemma 3.5, the assumption that u -1 v 1 v 2 reverses to v ′ u ′-1 in n steps implies the existence of S-words v ′ 1 , v ′ 2 , u 0 and of numbers n 1 , n 2 satisfying

v ′ = v ′ 1 v ′ 2 , n = n 1 + n 2 , u -1 v 1 (n1) R v ′ 1 u -1 0 , and u -1 0 v 2 (n2) R v ′ 1 u ′-1 .
Two cases are possible. Assume first n 1 = n, whence n 2 = 0. As, by assumption, v 2 is nonempty, the hypothesis that u -1 0 v 2 is a positive-negative word implies that u 0 is empty, and so is u ′ . Assume now n 1 < n. The value n 1 = 0 is impossible as it would imply that u or v 1 is empty, contrary to the assumption. Hence we also have n 2 < n. Now assume that u ′ is nonempty. Then, as we have n 2 < n, the induction hypothesis implies that v ′ 2 is empty. Next, u ′ can be nonempty only if u 0 is nonempty. Then, as we have n 1 < n, the induction hypothesis implies that v ′ 1 is empty as well, and we conclude that v ′ , which is

v ′ 1 v ′ 2 , is empty. See Figure 2.
So, in the context of triangular relations, when reversing is terminating, it shows not only that the elements of the monoid represented by the initial words admit a common right-multiple, but also that these elements are comparable with respect to left-divisibility. Indeed, by Lemma 3.4, if we have u

-1 v R v ′ with v ′ a (positive) S-word, we deduce [u] + [v ′ ] + = [v] + , whence [u] + [v] + in the monoid S | R + and, symmetrically, if we have u -1 v R u ′-1 with u ′ an S-word, we deduce [v] + [u ′ ] + = [u] + , whence [v] + [u] + .

Completeness of subword reversing

Owing to Lemma 3.6, if (S ; R) is a positive presentation that consists of triangular relations, in order to prove that any two elements of the monoid S | R + are comparable with respect to left-divisibility, it is enough to show that, for all S-words u, v, there exists at least one reversing sequence from u -1 v that is terminating, i.e., is finite and finishes with a positive-negative word.

A natural situation in which reversing is guaranteed to be terminating is the case when, for every pair of letters s, s ′ , there exists at least one relation s... = s ′ ... in R (so that one never gets stuck) and all relations u = v of R involve words u, v of length at most two, so that reversing does not increase the length of words. More generally, termination is guaranteed when one can identify a set of S-words S including S so that, for all u, v in S, there exist u ′ , v ′ in S satisfying u -1 v R v ′ u ′-1 (which amounts to meet the above conditions with respect to the extended alphabet S). However, except in a few trivial examples, this approach fails when applied to presentations with triangular relations: usually, the closure S of S under reversing is infinite and difficult to work with. Therefore, we must use a more subtle approach in two steps, namely showing that (i) if two elements represented by words u, v admit a common right-multiple, then the reversing of u -1 v terminates, and

(ii) any two elements of the considered monoids admit a common right-multiple. When this is done, Lemma 3.6 can be applied and one is close to concluding that the considered monoid is of right-O-type. In this section, we address point (i). Here comes the second, more important observation of the paper, namely that (i) is always true for a righttriangular presentation. Technically, the proof relies on what is known as the completeness condition.

If (S ; R) is any positive presentation, then, by Lemma 3.4, u -1 v R ε, i.e., the existence

of a diagram v u R , implies u ≡ + R v.
We consider now the converse implication.

Definition 4.1 (complete). A positive presentation (S ; R) is called complete for rightreversing if, for all S-words u, v,

(4.1) u ≡ + R v implies u -1 v R ε.
As the converse of (4.1) is always true, if (S ; R) is complete, (4.1) is an equivalence.

Remark 4.2. If there exist two letters s, s ′ of S such that, in the presentation R, there is more than one relation of the type s... = s ′ ... (including the case when there exists a relation s... = s... different from the implicit trivial relation s = s), then R-reversing need not be a deterministic process and, starting from some words u, v, there may exist

several pairs u ′ , v ′ satisfying u -1 v R v ′ u ′-1 .
According to our definitions, the condition u -1 v R ε involved in (4.1) means that there exists at least one way of obtaining the empty word starting from u -1 v. However, this type of non-determinism never occurs with a righttriangular presentation (S ; R) or its completion (S, R): by definition, R contains at most one relation s... = s ′ ... for each pair of letters, so R-and R-reversings are deterministic.

The intuition behind completeness is that, when a presentation is complete for rightreversing, the a priori complicated relation ≡ + R can be replaced with the more simple relation R . As explained in [START_REF] Dehornoy | The subword reversing method[END_REF], this makes recognizing some properties of the associated monoid and group easy. In our current context, in order to address point (i) above, we are interested in connecting the existence of common multiples and termination of reversing. When the completeness condition is satisfied, this is easy. Lemma 4.3. Assume that (S ; R) is a positive presentation that is complete for rightreversing. Then, for all g, h in S | R + , the following are equivalent:

(i) The elements g and h admit a common right-multiple;

(ii) For some S-words u, v representing g and h, the reversing of u -1 v is terminating;

(iii) For all S-words u, v representing g and h, the reversing of u -1 v is terminating.

Proof. Assume that g and h admit a common right-multiple f . By definition, there exist g ′ , h ′ satisfying f = gh ′ = hg ′ . Let u, v, u ′ , v ′ be arbitrary S-words representing g, h, g ′ , and h ′ . Then we have uv ′ ≡ + R vu ′ , whence (uv ′ ) -1 (vu ′ ) R ε, i.e., v ′-1 u -1 vu ′ R ε since (S ; R) is complete for right-reversing. Applying Lemma 3.5 twice, we split the reversing diagram of (uv ′ ) -1 (vu ′ ) into four diagrams:

v u ′ u v ′ R R R R
.

Each of the four diagrams above necessarily corresponds to a terminating reversing and, in particular, the reversing of u -1 v must terminate. So (i) implies (iii).

On the other hand, it is obvious that (iii) implies (ii). Finally, by Lemma 3.4, any relation u -1 v R v ′ u ′-1 implies that the element of S | R + both represented by uv ′ and vu ′ is a common right-multiple of the elements represented by u and v, so (ii) implies (i).

Owing to Lemmas 3.6 and 4.3, we are led to wondering whether a presentation consisting of triangular relations is necessarily complete for right-reversing. A priori, the question may seem hopeless as the only method known so far for establishing that a presentation (S ; R) is complete for right-reversing [START_REF] Dehornoy | Groups with a complemented presentation[END_REF][START_REF] Dehornoy | Complete positive group presentations[END_REF] consists in establishing a certain combinatorial condition (the "cube condition") using an induction that is possible only when the associated monoid M satisfies some Noetherianity condition, namely that, for every g in M , (4.2)

there is no infinite sequence g 0 , g 1 , ...

satisfying g 0 ≺ g 1 ≺ g 2 ≺ ••• g,
where g ≺ h means g h with g = h. Now, (4.2) turns out to fail whenever R contains a relation of the form s = ...s..., hence in most of the cases we are interested in. However, righttriangular presentations turn out to be eligible for an alternative completeness argument.

Proposition 4.4. For every right-triangular presentation (S ; R), the associated presentation (S, R) is complete for right-reversing.

The proof will be split into several steps. Until the end of the proof, we assume that (S ; R) is a fixed right-triangular presentation, with associated functions N and C. We recall that this means that R consists of the relations N (s) = sC(s) with s in S. We recall also that

C i (s) stands for C(s)C(N (s))•••C(N i-1 (s)) whenever N i (s) is defined.
By definition, if u, v are S-words, then u ≡ + R v holds, i.e., u and v represent the same element in S | R + , if and only if there exists an R-derivation from u to v, i.e., a sequence w 0 = u, w 1 , ..., w n = v such that each word w k is obtained from w k-1 by applying exactly one relation of R. We write u ≡

+(n) R
v when there exists a length n derivation from u to v. Definition 4.5. Assume that w is a nonempty S-word. We denote by I(w) the initial letter of w, and by T (w) (like "tail") the subword satisfying w = I(w)T (w). We say that a letter s of S underlies w if I(w) = N i (s) holds for some i 0. In this case, we put E s (w) = sC i (s)T (w); otherwise, we put E s (w) = w.

A straightforward induction on i gives N i (s) ≡ + R sC i (s) whenever defined, and we deduce

w = N i (s)T (w) ≡ + R sC i (s)T (w) = E s (w) whenever I(w) = N i (s) holds.
We begin with a direct consequence of the definition of a right-triangular presentation.

Lemma 4.6. Assume that (w 0 , ..., w n ) is a sequence of S-words such that, for every k, some letter of S underlies w k and w k+1 . Then some letter underlies all of w 0 , ..., w n .

Proof. We use induction on n. The result is obvious for n 1. Assume n 2. By induction hypothesis, there exists s underlying w 0 and w 1 , and s ′ underlying w 1 , ..., w n . So there exist i, j such that I(w 1 ) is both N i (s) and N j (s ′ ). Assume first i j. The injectivity of the map N implies s = N j-i (s ′ ). Hence s ′ underlies w 0 as well, and, therefore, s ′ underlies all of w 0 , ..., w n . The argument is similar in the case i j, with now s ′ = N i-j (s ′ ) and s underlying all of w 0 , ..., w n . Proof. The assumption that u ≡ +(1) R v holds means that there exist a number p 1 and a relation of R such that v is obtained from u by applying that relation to its subword starting at position p. Assume first p 2. In this case, the initial letter is not changed, i.e., we have I(u) = I(v), whereas T (v) is obtained from T (u) by applying a relation of R at position p -1, and T (u) ≡ +(1) R T (v) holds. Next, underlying a word w depends on the initial letter of w only, hence, as u and v have the same initial letter, the letters underlying u and v coincide. Finally, let s belong to S. Assume first that I(u), which is also

I(v), is N i (s). Then, by definition, we have E s (u) = sC i (s)T (u) and E s (v) = sC i (s)T (v), so that T (u) ≡ +(1) R T (v) implies E s (u) ≡ +(1) R E s (v). Otherwise, we have E s (u) = u and E s (v) = v, whence E s (u) ≡ +(1) R E s (v) again. Hence E s (u) ≡ +(1) R E s (v)
holds for every s in this case. Assume now p = 1. This means that there exists s and w satisfying u = sC(s)w and v = N (s)w, or vice versa. In this case, we have I(u) = s = N (s) = I(v) and, by definition, s underlies both u and v. Now, assume that s ′ is any element of S that underlies u. This means that we have I(u) = s = N i (s ′ ) for some i 0, and we then have

I(v) = N (s) = N i+1 (s ′ ), so s ′ underlies v as well. Then we find E s ′ (u) = s ′ C i (s ′ )T (u) = s ′ C i (s ′ )C(s)w = s ′ C i+1 (s ′ )w = E s ′ (v).
On the other hand, assume that s ′ is an element of S that does not underlie u. Then we have E s ′ (u) = u. If s ′ underlies v, owing to the fact that I(v) is N (I(u)) and N is injective, the only possibility is s ′ = N (s) and, in this case, we have -we have I(u) = I(v) and T (u) ≡

E s ′ (v) = v. If s ′ does not underlie v, by definition we have E s ′ (v) = v as well. So, in every such case, we find E s ′ (u) = u ≡ +(1) R v = E s ′ (v). The case u = N (s)w, v = sC(s)w is of course similar. Then the proof is complete since the relation E s (u) ≡ +( 1) R E s (v)
+(n) R
T (v); -there exists s underlying u and v and satisfying E s (u) ≡

+(<n) R E s (v).
Proof. Let (w 0 , ..., w n ) be an R-derivation from u to v. Two cases are possible. Assume first that the initial letter never changes in the considered derivation, i.e., I(w k ) = I(u) holds for every k. Then all one step derivations (w k , w k+1 ) correspond to case (i) in Lemma 4.7. The latter implies I(w k ) = I(w k+1 ) and T (w k ) ≡

+(1) R T (w k+1 ) for every k, whence I(u) = I(v) and T (u) ≡ +(n) R T (v).
Assume now that the initial letter changes at least once in (w 0 , ..., w n ), say I(w i ) = I(w i+1 ). First, Lemma 4.7 together with Lemma 4.6 implies the existence of s in S that underlies w k for every k. Next, each one step derivation (w i , w i+1 ) corresponds to case (ii) in Lemma 4.7. So, as s underlies w i and w i+1 , we have E s (w i ) = E s (w i+1 ). On the other hand, by Lemma 4.7 again, we have

E s (w k ) ≡ +( 1) R E s (w k+1 ) for k = i, so, summing up, we obtain E s (u) ≡ +(<n) R E s (v)
for this particular choice of s.

We can now complete the argument establishing that the presentation (S, R) is complete for right-reversing. We denote by |w| the length (number of letters) of a word w.

Proof of Proposition 4.4. We show using induction on n 0 and, for a given value of n, on max(|u|, |v|), that u ≡

+(n) R v implies u -1 v R ε.
Assume first n = 0. Then the assumption implies u = v, in which case u -1 v reverses to the empty word by |u| successive deletions of subwords s -1 s.

Assume now n 1. Then u and v must be nonempty. Assume first that I(u) = I(v) and

T (u) ≡ +(n) R T (v) hold. By definition, we have max(|T (u)|, |T (v)|) = max(|u|, |v|) -1, so the induction hypothesis implies T (u) -1 T (v) R ε.
On the other hand, as I(u) and I(v) are equal, we have

u -1 v = T (u) -1 I(u) -1 I(v)T (v) (1) R T (u) -1 T (v). By transitivity of reversing, we deduce u -1 v R ε. Assume now that I(u) = I(v) and T (u) ≡ +(n) R
T (v) do not hold. Then, by Lemma 4.8, there must exist s such that s underlies u and v and E s (u) ≡

+(n ′ ) R E s (v) holds for some n ′ < n. Then the induction hypothesis implies E s (u) -1 E s (v) R ε. Write s k for N k (s).
As s underlies u and v, there exist i, j satisfying I(u) = s i and I(v) = s j . Assume for instance i j.

By definition, we have E s (u) = sC i (s)T (u) and E s (v) = sC j (s)T (v) = sC i (s)C j-i (s i )T (v), so that, if ℓ is the length of the word sC i (s), the first ℓ steps in any reversing sequence starting from

E s (u) -1 E s (v) must be E s (u) -1 E s (v) = T (u) -1 C i (s) -1 s -1 sC i (s)C j-i (s i )T (v) (ℓ) R T (u) -1 C j-i (s i )T (v). It follows that the relation E s (u) -1 E s (v) R ε deduced above from the induction hypothesis implies (4.3) T (u) -1 C j-i (s i )T (v) R ε. Now, let us consider the R-reversing of u -1 v, i.e., of T (u) -1 s -1 i s j T (v)
. By definition, the only relation of R of the form s i ... = s j ... is s i C j-i (s i ) = s j , so the first step in the reversing must be T (u

) -1 s -1 i s j T (v) R T (u) -1 C j-i (s i )T (v).
Concatenating this with (4.3), we deduce u -1 v R ε again, which completes the induction.

With the above completeness at hand, we are now ready for assembling pieces and establishing the Main Lemma (Proposition 2.6).

Proof of the Main

Lemma. Put M = S | R + . If M is of right-O-type,
any two elements of M are comparable with respect to left-divisibility, hence they certainly admit a common right-multiple, namely the larger of them. So (i) trivially implies (ii).

Conversely, assume that any two elements of M admit a common right-multiple. First, as M admits a right-triangular presentation, hence a positive presentation, 1 is the only invertible element in M .

Next, M must be left-cancellative. Indeed, the point is to prove that, if s belongs to S and u, v are S-words satisfying su ≡ + R sv, then u ≡ + R v holds. By Proposition 4.4, the presentation (S, R) is complete for right-reversing. Hence su

≡ + R sv implies (su) -1 (sv) R ε, i.e., u -1 s -1 sv R ε. Now, the first step in any reversing sequence from u -1 s -1 sv is u -1 s -1 sv R u -1 v, so the assumption implies u -1 v R ε, whence u ≡ + R v.
Finally, let g, h be two elements of M . Hence, by Lemma 4.3, which is relevant as (S, R) is complete for right-reversing, there exist S-words u, v representing g and h and such that the R-reversing of u -1 v is terminating, i.e., there exist S-words u

′ , v ′ satisfying u -1 v R v ′ u ′-1 .
By construction, the family R consists of triangular relations so, by Lemma 3.6, at least one of the words u ′ , v ′ is empty. This means that at least one of g h or h g holds in M , i.e., g and h are comparable with respect to left-divisibility. So M is a monoid of right-O-type, and (ii) implies (i).

To conclude this section, we observe in view of future examples that the triangular presentations defining monoids admitting common right-multiples must be of some simple type. Lemma 4.9. Assume that (S ; R) is a right-triangular presentation defining a monoid in which any two elements admit a common right-multiple. Then there exists a (finite or infinite) interval

I of Z such that S is {a i | i ∈ I} and R consists of one relation a i-1 = a i C(a i ) for each non-minimal i in I.
Proof. Let s, s ′ belong to S. As s and s ′ admit a common right-multiple, Lemma 4.3 implies that the R-reversing of s -1 s ′ terminates, which in turn requires that R contains at least one relation of the form s... = s ′ ... . Hence the left-graph of (S ; R) consists of a unique chain, which, by definition of a right-triangular presentation, means that (S ; R) has the form stated in the lemma.

Existence of common multiples

Owing to the Main Lemma (Proposition 2.6), the point for establishing that a monoid specified by a right-triangular presentation is of right-O-type is to prove that any two elements admit a common right-multiple. We now establish several sufficient conditions in this direction.

Top words and ceiling. The first criterion deals with the existence of what will be called top words. We recall that, for w a word, |w| denotes the length of w. Definition 5.1. Assume that M is a monoid generated by a set S. An S-word w is called a right-top word in M if g

[w] + holds for every g in S |w| . A right-S-ceiling for M is a left-infinite S-word ...s 2 s 1 such that, for every n, the word

s n •••s 1 is a right-top S-word.
The criterion we obtain is as follows.

Proposition 5.2. Assume that M is a monoid that admits a triangular presentation based on a finite set S. Then the following are equivalent:

(i) The monoid M is of right-O-type;

(ii) The monoid M admits a right-S-ceiling;

(iii) There exist s 1 , s 2 , ... in S satisfying

(5.1) ∀n ∀s∈S (s s n-1 •••s 1 s n s n-1 •••s 1 );
(iv) The monoid M admits right-top S-words of unbounded length.

We naturally say that a presentation is based on S if it has the form (S ; R) for some R. Before proving Proposition 5.2, we begin with easy preliminary observations about top words and ceilings. (iii) Assume that ...s 2 s 1 is a right-S-ceiling in M . Then, for all n and s in S, the element

ss n-1 •••s 1 belongs to S n hence, by definition, ss n-1 •••s 1 s n s n-1 •••s 1 holds, whence (5.1).
Conversely, assume that s 1 , s 2 , ... satisfy (5.1). We prove using induction on n that g ∈ S n implies g s n •••s 1 . For n = 1, (5.1) directly gives s s 1 for every s in S. Assume n 2 and g ∈ S n . Write g = sh with s ∈ S and h ∈ S n-1 . The induction hypothesis gives h s n-1 •••s 1 , and then (5.1) implies g = sh ss n-1

•••s 1 s n s n-1 •••s 1 .
Lemma 5.4. Assume that M is a cancellative monoid with no nontrivial invertible element, and S generates M . Then, for every ℓ, there exists at most one right-top S-word of length ℓ, and there exists at most one right-S-ceiling in M ; when the latter exists, every right-top word is a final fragment of it.

Proof. First, if w, w ′ are right-top S-words of the same length, then, by definition, we have

[w] + [w ′ ] + and [w ′ ] + [w] + , whence [w] + = [w ′ ] +
owing to the assumption that there is no nontrivial invertible element in M . Now, we prove the uniqueness of a right-top word of length ℓ using induction on ℓ. For ℓ = 0, the empty word is the unique word of length ℓ. For ℓ = 1, if s and s ′ are distinct elements of S, then [s] + = [s ′ ] + is impossible by hypothesis. Assume now that w, w ′ are right-top words of length ℓ with ℓ 2. Write w = sv, w ′ = s ′ v ′ . By Lemma 5.3(ii), v and v ′ are right-top words, so, by induction hypothesis, v = v ′ holds. By the above observation, we have [w] + = [w ′ ] + . Then the assumption that M is right-cancellative implies [s] + = [s ′ ] + , hence s = s ′ , and, finally, w = w ′ .

Next, assume that W, W ′ are right-S-ceilings in M . Then, for every n, the length n final fragments of W and W ′ are right-top words of length n, and, therefore, by the above result, they coincide. As this holds for every n, so do W and W ′ . By the same argument, if w is a length n right-top word and W is a right-S-ceiling, then the length n final fragment of W is a right-top word, hence it coincides with w. So, w is a final fragment of W .

Proof of Proposition 5.2. First, (ii), (iii), and (iv) are equivalent. Indeed, the equivalence of (ii) and (iii) directly follows from Lemma 5.3(iii). Next, (ii) implies (iv) by definition. Conversely, the assumption that M admits a triangular presentation implies that M is cancellative and admits no nontrivial invertible element. If M admits right-top S-words of unbounded length, then, by Lemma 5.4(i), there exists a well defined left-infinite word W such that the latter all are final fragments of W . Then W is a right-S-ceiling, and (iv) implies (ii).

Assume now that M is of right-O-type. By assumption, the relation is a linear ordering on M . Hence, as S is finite, we can inductively select elements s 1 , s 2 , ... in S such that s n (s n-1 •••s 1 ) is the upper bound of the elements s (s n-1 •••s 1 ) with s in S. Then (5.1) holds, and (i) implies (iii), hence (ii) and (iv).

Conversely, assume that M admits right-top words of unbounded length. Let g, h be two elements of M . As S generates M , there exist n, p such that g lies in S n and h lies in S p . Let w be a right-top word of length at least equal to n and p. By Lemma 5.3(i), [w] + is a common right-multiple of g and h. So any two elements of M admit a common right-multiple and, therefore, by the Main Lemma (Proposition 2.6), M is of right-O-type. So (iv) implies (i).

Note that, in the above proof, the hypothesis that the monoid admits a triangular presentation is not used to establish the existence of the ceiling: in every cancellative monoid of right-O-type, hence in particular in every monoid of O-type, generated by a finite set, there exists a unique ceiling. However, for the converse direction (the one we are mainly interested in), the existence of a ceiling is sufficient to guarantee that is a linear ordering only when the Main Lemma is valid, hence, in practice, for monoids that admit a (right)-triangular presentation.

Dominating elements. The approach of Proposition 5.2 is concrete and makes experiments easy (see Section 7). However, it is in general not easy to prove the existence of a ceiling explicitly, and it is often more convenient to use the following notion. Definition 5.5. Assume that M is a monoid. For δ, g in M , we say that δ right-dominates g if we have (5.2) ∀n 0 ( gδ n δ n+1 )

For S ⊆ M , we say that δ right-dominates S if it right-dominates every element of S.

Note that an element always dominates oneself. The counterpart of Proposition 5.2 is now an implication, not an equivalence. Proposition 5.6. Assume that M is a monoid that admits a right-triangular presentation based on a set S, and there exists in M an element that right-dominates S. Then M is of right-O-type.

The result will directly follow from Lemma 5.7. Assume that M is a monoid and δ is an element of M that right-dominates some subset S of M . Then g δ n holds for every n and every g in S n , and any two elements in the submonoid of M generated by S admit a common right-multiple. In particular, if S generates M , any two elements of M admit a common right-multiple.

Proof. We prove using induction on n that g ∈ S n implies g δ n . For n = 0, i.e., for g = 1, the property is obvious and, for n = 1, it is (5.2). Assume n 2 and g ∈ S n . Write g = sh with s ∈ S and h ∈ S n-1 . By induction hypothesis, we have h δ n-1 , whence g = sh sδ n-1 , whence g δ n by (5.2). Now, let M ′ be the submonoid of M generated by S, i.e., the union of {1} and all S n for n 1. Let g, h belong to M ′ \{1}. There exist n, p such that g belongs to S n and h belongs to S p . Then δ max(n,p) is a common right-multiple of f and g.

Proof of Proposition 5.6. By hypothesis, the set S generates M . So Lemma 5.7 implies that any two elements of M admit a common right-multiple, and the Main Lemma (Proposition 2.6 then implies that M is of right-O-type.

We add two observations. The first one says that, in order to establish that an element dominates another one, it can be enough to consider exponents lying in an arithmetic series.

Lemma 5.8. For δ, g in a monoid M , a necessary and sufficient condition for δ to rightdominate g is that there exist m 1 satisfying

(5.3)
∀k 0 ( gδ km+m-1 δ km+1 ).

Proof. If δ right-dominates g, then, by definition, (5.3) holds with m = 1. Conversely, assume (5.3). Let n be a nonnegative integer. Let k be maximal with km n. Then we have n km + m -1, and (5.3) implies gδ n gδ km+m-1 δ km+1 δ n+1 , so δ right-dominates s.

The second observation is a connection between ceiling and dominating element. Lemma 5.9. Assume that M is a cancellative monoid that admits no nontrivial invertible element and is generated by a set S. Then the following are equivalent:

(i) The monoid M admits a right-S-ceiling that is periodic with period

s ℓ •••s 1 ; (ii) The element s ℓ •••s 1 right-dominates S ℓ in M . Proof. Assume (i). Put δ = s ℓ •••s 1 .
For all n and g in S ℓ , the element gδ n belongs to S ℓ(n+1) , so, by definition, we have

gδ n s ℓ(n+1) •••s 1 = (s ℓ •••s 1 ) n+1 = δ n+1
. So δ right-dominates S ℓ , and (i) implies (ii).

Conversely, assume that s ℓ •••s 1 right-dominates S ℓ , and let g belong to S nℓ . As g belongs to (S ℓ ) n , Lemma 5.7 implies g δ n , i.e., g [(s ℓ •••s 1 ) n ] + . This shows that, for every n, the S-word (s ℓ •••s 1 ) n is a right-top word. By Proposition 5.2, we deduce that there exists a right-S-ceiling in M and, by Lemma 5.4(ii), that this sequence is ∞ (s ℓ •••s 1 ).

An important special case of Lemma 5.9 is when some element s of S dominates S, i.e., when the top generator of S dominates S. By Lemma 5.9, this is equivalent to the existence of a constant ceiling ∞ s. We shall see in Sections 7 and 8 that this situation often occurs. However, there are also cases when the ceiling is not constant, corresponding to a dominating element δ that belongs to S ℓ for some ℓ 2. In that case, by Lemma 5.7, the condition that δ dominates S, and not S ℓ as in Lemma 5.9, is sufficient to establish the existence of common multiples.

Quasi-central elements. Checking that an element is possibly dominating requires considering unbounded exponents. We consider now a notion that is stronger, but easier to establish.

Definition 5.10. An element ∆ of a monoid M is called right-quasi-central if there exists an endomorphism φ of M such that, for every g in M , we have (5.4) g∆ = ∆φ(g).

When φ is the identity, we recover the standard notion of a central element, i.e., one that commutes with every element. Once again, we obtain a sufficient condition for a monoid to be of right-O-type. Proposition 5.11. Assume that M is a monoid that admits a right-triangular presentation based on a set S, and there exists in M a right-quasi-central element ∆ satisfying ∀s∈S (s ∆). Then M is of right-O-type.

The proof will relie on the following connection with dominating elements. Lemma 5.12. Assume that M is a left-cancellative monoid generated by a set S and δ m is right-quasi-central in M . Then δ right-dominates every element g that satisfies gδ m-1 δ.

Proof. Put ∆ = δ m , and let φ be the (necessarily unique) endomorphism of M witnessing that ∆ is right-quasi-central. First, (5.4) applied with g = ∆ gives δ∆ = δ m+1 = ∆φ(δ), whence φ(δ) = δ since M is left-cancellative.

Next, we claim that g h implies φ(g) φ(h). Indeed, by definition, g h implies the existence of h ′ satisfying gh ′ = h, whence φ(g)φ(h ′ ) = φ(h) since φ is an endomorphism. This shows that φ(g) φ(h) is satisfied. So, in particular, and owing to the above equality, g δ implies φ(g) δ.

Now assume gδ m-1 δ. Then, for every k, we find

gδ km+m-1 = gδ m-1 ∆ k = ∆ k φ k (gδ m-1 ) ∆ k φ k (δ) = ∆ k δ = δ km+1 ,
and, by Lemma 5.8, we conclude that δ right-dominates g.

Proof of Proposition 5.11. Under the hypotheses, by Lemma 5.12, the element ∆ rightdominates S. Then Proposition 5.6 implies that M is of right-O-type.

The main interest of considering quasi-central elements here is that, due to the following characterization, establishing that an element is quasi-central is easy, involving in particular finitely many verifications only. Lemma 5.13. Assume that M is a left-cancellative monoid generated by a set S. Then, for every ∆ in M , the following are equivalent:

(i) The element ∆ is right-quasi-central and satisfies s ∆ for every s in S, (ii) The relation ∀s∈S (s ∆ s∆) holds.

Proof. Assume (i) and let φ be the witnessing endomorphism. Let s belong to S. By assumption, s ∆ is true. Let g be the element satisfying sg = ∆. Then (5.4) implies s∆ = ∆φ(s), whence s∆ = sgφ(s), and ∆ = gφ(s) since M is left-cancellative. We deduce ∆ = sg sgφ(s) = s∆, and (i) implies (ii).

Conversely, assume (ii). We shall define an endomorphism φ witnessing that ∆ is rightquasi-central in M . First, for s in S, we define φ(s) to be the unique element satisfying (5.5) s∆ = ∆φ(s), which exists since, by assumption, ∆ s∆ holds. Now, assume that s 1 , ..., s n , s ′ 1 , ..., s ′ p belong to S and

s 1 •••s n = s ′ 1 •••s ′ p holds in M . By applying (5.5) repeatedly, we obtain ∆φ(s 1 )•••φ(s n ) = s 1 •••s n ∆ = s ′ 1 •••s ′ p ∆ = ∆φ(s ′ 1 )•••φ(s ′ p ), whence φ(s 1 )•••φ(s n ) = φ(s ′ 1 )•••φ(s ′ p ) since M is left-cancellative.
It follows that, for every g in M \{1}, we can define φ(g) to be the common value of φ(s 1 )•••φ(s n ) for all expressions of g as a product of elements of S. We complete with φ(1) = 1. Then, by construction, φ is an endomorphism of M and (5.4) is satisfied for every g in M .

We conclude the section with a connection between central element and ceiling. Lemma 5.14. Assume that M is a cancellative monoid of right-O-type, and that

s ℓ •••s 1 is a right-top S-word in M such that [s ℓ •••s 1 ] + is central in M .
Then we have s i = s 1 for every i, and ∞ s 1 is the right-S-ceiling in M .

Proof. Let ∆ = s ℓ •••s 1 . First, we have g ∆ for every g in S ℓ . Then Lemma 5.12 implies that ∆ right-dominates S ℓ . Hence, by Lemma 5.9, the right-S-ceiling is periodic with period

s ℓ •••s 1 . Now consider its length ℓ + 1 final fragment s 1 s ℓ •••s 1 . Then, in M , we have s 1 s ℓ •••s 1 = s ℓ •••s 1 s 1 , so s 1 s ℓ •••s 1 and s ℓ •••s 1 s 1 are
two right-top S-words of length ℓ + 1. By Lemma 5.4, these words must coincide, which is possible only for s 1 = ... = s ℓ .

Thus the only situation when a right-top word can be central is when it is a power of the top generator. Note that Lemma 5.14 says nothing about central elements that admit no expression as a right-top word.

Back to ordered groups

In Section 5, we established several sufficient conditions for a monoid to be of right-O-type. Returning to the context of ordered groups, we immediately deduce orderability conditions. We recall that, if (S ; R) is a positive group presentation, (S ; R) is the opposite presentation (same generators, reversed relations). Let us now address the solvability of the decision problem for the ordering involved in Proposition 6.1. We shall establish the correctness of Algorithm 6.2 below. The latter simultaneously appeals to right-reversing as defined in Section 3 and to left-reversing , the symmetric procedure that replaces s ′ s -1 with v -1 v ′ such that vs ′ = v ′ s is a relation. The properties of left-reversing are of course symmetric to those of right-reversing: formally, using w for the mirror-image of w (same letters in reserved order), w R w ′ is equivalent to w R w ′ where, as usual, R is the family of all relations u = v for u = v in R. We denote by R the family obtained by adding to R the relations N i (s) = C i (s)s with i 2 (the left-completion of R, symmetric to the right-completion R). If w is a signed S-word, we denote by [w] the element of the group S | R represented by w.

Algorithm 6.2 (decision problem of the ordering).

• Data: A finite (or recursive) triangular presentation (S ; R);

• Input: A signed S-word w; • Procedure: -Right-R-reverse w into vu -1 with u, v in S * ; -Left-R-reverse vu -1 into u ′-1 v ′ with u ′ , v ′ in S * ; • Output: -For u ′ = ε and v ′ = ε, return " [w] < 1"; -For u ′ = v ′ = ε, return " [w] = 1"; -For u ′ = ε and v ′ = ε, return " [w] > 1".
Proposition 6.3. Under the hypotheses of Proposition 6.1, if (S ; R) is finite or recursive, Algorithm 6.2 solves the decision problem for the ordering, and the word problem of G.

Proof. Put M = S | R + . First, as (S ; R) is finite or, at least, recursive, the relations R and R are recursive, so Algorithm 6.2 is indeed effective. Next, as the presentation (S, R) is complete for right-reversing and, by Proposition 6.1, any two elements of the monoid M admit a common right-multiple, every right-R-reversing sequence is terminating: for every signed S-word w, there exist positive S-words u, v satisfying w R uv -1 . Similarly, as (S, R) is complete for left-reversing and any two elements of M admit a common left-multiple, every R-reversing sequence is terminating and, therefore, there exist positive S-words u ′ , v ′ satisfying uv -1 R u ′-1 v ′ . Hence Algorithm 6.2 always terminates. Moreover, by (the counterpart of) Lemma 3.6, at least one of the words u ′ , v ′ is empty.

By construction,

w R uv -1 R u ′-1 v ′ implies [w] = [u ′-1 v ′ ] in S | R . If u ′ is nonempty and v ′ is empty, we deduce [w] = [u ′-1 ] ∈ M -1 \{1}, whence [w] < 1 for the ordering whose positive cone is M -1 \{1}. If u ′ and v ′ are empty, we deduce [w] = [ε] = 1. Finally, if u ′ is empty and v ′ is nonempty, we obtain [w] = [v ′ ] ∈ M \{1}, whence [w] > 1.
So Algorithm 6.2 decides the relation <. As < is a strict linear ordering, the algorithm also solves the word problem as [w] = 1 is equivalent to the disjunction of [w] < 1 and [w] > 1.

Remark 6.4. Algorithm 6.2 does not only give a YES/NO answer: for every initial signed S-word w, the method provides a positive S-word w ′ such that w is equivalent either to w ′ or or to w ′-1 . In other words, it gives for every element g of the group S | R an explicit positive or negative decomposition of g in terms of the distinguished generators of the positive cone.

The proof of Theorem 1 can now be completed. We state the results in a more general form that avoids unnecessary symmetries and corresponds to the case of dominating or quasicentral elements; a similar statement involving right-ceilings and (5.1) exists of course. Theorem 6.5. A sufficient condition for a group G to be orderable is that G admits a triangular presentation (S ; R) and, in the monoid S | R + , there exist ∆, ∆ satisfying ∀s∈S (s ∆ s∆) or ∀s∈S ∀n (s∆ n ∆ n+1 ), and ∀s∈S ( ∆s ∆ s) or ∀s∈S ∀n ( ∆ n+1 ∆ n s).

In this case, the subsemigroup of G generated by S is the positive cone of a left-invariant ordering on G. If S is finite, this ordering is isolated in the space LO(G). If (S ; R) is finite or recursive, the word problem of G and the decision problem of the ordering are decidable.

Proof. Owing to Lemmas 5.12 and 5.13, the element ∆ right-dominates S in S | R + , so the latter is eligible for Proposition 5.6. Symmetrically, ∆ right-dominates S in S | R + , and S | R + is eligible for Proposition 5.6 as well. Then the hypotheses of Propositions 6.1 and 6.3 are satisfied, and the latter give the results.

We add two more observations. The first one involves monoids that are of right-O-type but not necessarily of O-type. In this case, the termination of left-reversing is not guaranteed, and the monoid need not be connected with a left-invariant ordering in the group. However, the group is still a group of right-fractions for the monoid, and we can solve its word problem by appealing to right-reversing only.

Algorithm 6.6 (word problem).

• Data: A finite (or recursive) right-triangular presentation (S ; R); • Input: A signed S-word w;

• Procedure: -Right-R-reverse w into vu -1 with u, v in S * ; -Right-R-reverse u -1 v into v ′ u ′-1 with u ′ , v ′ in S * ; • Output: -For u ′ = v ′ = ε, return " [w] = 1"; -For u ′ = ε or v ′ = ε, return " [w] = 1".
u] + = [v] + , i.e., to u ≡ + R v.
As (S, R) is complete for right-reversing, the latter condition is equivalent to u -1 v R ε, i.e., with the notation of Algorithm 6.6, to u ′ = v ′ = ε.

The second observation is a connection with Garside theory [START_REF] Dehornoy | Garside Theory[END_REF]. Say that an element ∆ is left-quasi-central in a monoid M if it is right-quasi-central in the opposite monoid M . Proof. By assumption, the monoid M is left-cancellative and the left-divisors of ∆ generate M . As ∆ is right-quasi-central, every right-divisor of ∆ is left-divides ∆ since, as noted in the proof of Lemma 5.12, ∆ = g ′ g implies gφ(g ′ ) = ∆. Finally, for every g in M , the elements g and ∆ admit a greatest common left-divisor (left-gcd), namely the smaller of them with respect to . Hence, by definition, ∆ is a right-Garside element in M .

If ∆ is also left-quasi-central, then, by symmetry, the left-divisors of ∆ must be included in its right-divisors, and, therefore, the left-and right-divisors of ∆ coincide. Then ∆ is a Garside element in M .

It follows that, under the hypotheses of Proposition 6.8, the left-divisors of ∆ in M form what is called a Garside family [9, Definition I.1.34] and every element of M admits a distinguished decomposition in terms of these elements. However, as left-divisibility is a linear ordering in this case, this decomposition is rather trivial: every element is leftdivisible by some maximal power of ∆, and the normal decompositions all have the simple form (∆, ..., ∆, g) with g ∆.

Experimental approach

Subword reversing is easily implemented, allowing for computer experiments. Thus we can consider arbitrary (right)-triangular presentations and investigate whether the associated monoids are of (right)-O-type. Owing to Lemma 4.9, we consider presentations of form

(7.1) (a 1 , ..., a n ; a 1 = a 2 C(a 2 ), ..., a n-1 = a n C(a n ))
where C(a 2 ), ..., C(a n ) are words in the alphabet {a 1 , ..., a n }. Then the first natural step in the investigation consists in (trying to) compute (a final fragment of) the right-ceiling, if it exists. The principle is as follows.

Lemma 7.1. Assume that (S ; R) is a presentation of the form (7.1). Starting from s 1 = a 1 , inductively find s n in S so that, for every i,

(7.2) (a i s n-1 •••s 1 ) -1 (s n s n-1 •••s 1 ) is R-reversible to a positive word.
Then S | R + is of right-O-type if and only if the construction never stops.

Proof. By Lemma 3.6, and by completeness of the presentation (S ; R) for subword reversing, the only possibilities, when a negative-positive word u -1 v is reversed are -either the reversing terminates in finitely many steps with a word that is either positive or negative, in which case

[u] + [v] + or [v] + [u] + holds in S | R + ,
-or the reversing never terminates, in which case [u] + and [v] + have no common rightmultiple in S | R + . So, assuming that s 1 , ..., s n-1 have been found, two cases may occur in the search of s n satisfying (7.2):

-either all reversings terminate in finitely many steps, s n is found, and the process continues; then (5.1) is satisfied, s n •••s 1 is a right-top S-word, and, if this continues for every n, then, by Proposition 5.2, S | R + is of right-O-type, -or some reversing does not terminate, and the process stops; then two elements ss n-1 •••s 1 and s ′ s n-1 •••s 1 admit no common right-multiple, and S | R + cannot be of right-O-type.

Note that, for an alphabet S of size m, determining the final ℓ + 1 letters in the rightceiling requires only ℓ(n -1) word reversings and, in particular, only ℓ reversing are required in the case of two generators.

Although easy, the previous step can lead to suspicions, and not to a proven conclusion: on the positive side, one obtains a finite fragment of the ceiling, from which it is a priori impossible to deduce the existence of the ceiling; symmetrically, on the negative side, a long finite reversing sequence is not a proof of a non-terminating reversing. However, so far, the suspicions provided by Lemma 7.1 never turned to be wrong: although ad hoc examples could certainly be constructed, we know of no monoid containing a right-top word of length 20 that eventually turned to be not of O-type, and of no reversing sequence of length 10, 000 that eventually turned to be terminating. Now, the good point is that, in some cases, proven conclusions can be obtained. Let us begin with the negative case, i.e., establishing that a monoid is not of O-type. The following result shows that some syntactic conditions a priori discard certain presentations. (ii) If a relation of R has the form s = w with w beginning with (uv) r us with r 1, u nonempty, and v such that v -1 s reverses to a word beginning with s, hence in particular if v is empty or it can be decomposed as u 1 , ..., u m where u k s is a prefix of w for every k, then the elements s and [u] + s have no common right-multiple in S | R + and, therefore,

S | R + is not of right-O-type. Proof. (i) If R contains a relation s = us with u nonempty, s = [u] + s holds in S | R + , whereas 1 = [u] + fails. So S | R + is not right-cancellative.
(ii) We claim that the right-R-reversing of s -1 us cannot be terminating, see Figure 3. Indeed, writing the involved relation s = (uv) r usw 1 with v -1 s R sw 2 , we find

s -1 us R w -1 1 s -1 (vu) -(r-1) u -1 v -1 s R w -1 1 s -1 (vu) -(r-1) u -1 sw 2 R w -1 1 s -1 (vu) -(r-1) (vu) r-1 vusw 1 w 2 R w -1 1 s -1 vusw 1 w 2 R w -1 1 w -1 2 • s -1 us • w 1 w 2 . We deduce that s -1 us R (w -1 1 w -1 2 ) n • s -1 us • (w 1 w 2 )
n holds for every n and, therefore, it is impossible that s -1 us leads in finitely many steps to a positive-negative word. Then, by reverses to a word that includes it and, therefore, the reversing cannot be terminating.

For instance, a relation a = babab 3 a 2 ... is impossible in a right-triangular presentation for a monoid of right-O-type: indeed, the right-hand side of the relation can be written as (ba)bab 2 (ba)a..., which is eligible for Lemma 7.2(ii) with u = ba and v = bab • b, a product of two words u 1 , u 2 such that u i a is a prefix of the right-hand term of the relation.

Symmetrically, on the positive side, i.e., for establishing that a monoid is of right-O-type, the existence of a quasi-central element is can be checked in finite time.

Lemma 7.3. Assume that (S ; R) is a presentation of the form (7.1), and w is an S-word beginning with a 1 and such that, for 2 i n, Thus, the generic program for investigating a right-triangular presentation (S ; R) is (i) check if (S ; R) is eligible for Lemma 7.2-in which case S | R + is not of right-O-type; (ii) if not, compute the right-ceiling using Lemma 7.1 with escape conditions on the length of the reversing sequences and of the ceiling; (iii) if some reversing in step (ii) seems to be non-terminating, try to extract a cyclic reversing pattern, i.e., finding an S-word u satisfying u (n) R ...u... for some n > 0-in which case S | R + is not of right-O-type; (iv) otherwise try to find a right-quasi-central element-in which case S | R + is of right-Otype; if the ceiling seems to be periodic with period w, then [w] + is a natural candidate.

It turns out that the above program works well, at least for presentations that are short enough. In the case of two generators, almost all presentations we tried are either discarded by Lemma 7.3 or contain a quasi-central element that is a power of the top generator. See Table 2 for some typical examples. Results are entirely similar in the case of three generators or more. Again, most of the cases that are not discarded by Lemma 7.2 or its counterpart turn out to be eligible for Lemma 7.3, and the exceptions can be successfully addressed directly. It is probably useless to give more details here.

Some families of monoids of O-type

We shall now describe five infinite families for which we can exhibit central, quasi-central, or dominating elements and which therefore are of right-O-type or of O-type. We begin with the simplest case, namely when some power of the top generator is central or quasi-central. Proposition 8.1. For p, q, r 1, let M be the monoid defined by

(8.1) (a, b ; a = b(a p b r ) q ). (i) The element a p+1 is right-quasi-central in M and M is of right-O-type. (ii) For r = 1, the element a p+1 is central in M and M is of O-type.
Proof. (i) Applying (8.1), we first find

a = b(a p b r ) q = b • a • (a p-1 b r )(a p b r ) q-1 ,
whence, repeating the operation r times and moving the brackets,

a = b r • a • ((a p-1 b r )(a p b r ) q-1 ) r = b r (a p b r ) q • ((a p-1 b r )(a p b r ) q-1 ) r-1
. Let ∆ = a p+1 . Substituting the above value of a at the underlined position, moving the brackets, and applying the relation once in the contracting direction, we find

b • ∆ = ba p a = ba p • b r (a p b r ) q • ((a p-1 b r )(a p b r ) q-1 ) r-1 = b(a p b r ) q • a p b r ((a p-1 b r )(a p b r ) q-1 ) r-1 = a • a p • b r ((a p-1 b r )(a p b r ) q-1 ) r-1 = ∆ • b r ((a p-1 b r )(a p b r ) q-1 ) r-1 .
Now, we have b a a p+1 = ∆ in M . Next, as ∆ is a power of a, it commutes with a. So, by Lemma 5.13, ∆ is right-quasi-central in M , with associated endomorphism defined by

(8.2) φ(a) = a, φ(b) = b r ((a p-1 b r )(a p b r ) q-1 ) r-1 .
By Proposition 5.11, M is of right-O-type.

(ii) Assume now r = 1. By (i), M is of right-O-type. Now (8.1) reduces here to a = b(a p b) q , which is symmetric. Hence, by (i), the opposite monoid M is of right-O-type, so M is of left-O-type, and, therefore, of O-type. Finally, by (8.2), the endomorphism φ is the identity here, so that ∆ is central.

By Proposition 1.4, every monoid of O-type gives rise to an ordered group. The groups occurring in connection with the monoids of Proposition 8.1 are the torus knot groups.

Corollary 8.2. For p, q 1, let G be the torus knot group x, y | x p+1 = y q+1 . Then G is orderable, the subsemigroup of G generated by x and x -p y is the positive cone of a left-invariant ordering on G which is isolated in LO(G).

Proof. In view of Propositions 1.4 and 8.1, it is sufficient to prove that (8.1) is a presentation of G in terms of the mentioned elements. Now, put a = x and b = x -p y in G. We find a p+1 = b(a p b) q a p , whence a = b(a p b) q , so, if G ′ is the group defined by the presentation (8.1), there exists a well defined homomorphism Φ of G ′ to G mapping a to a and b to b. Moreover Φ is surjective as a and b generate G. Conversely, put x = a and y = a p b in G ′ . We obtain now x p+1 = aa p = b(a p b) q b = (ba p ) q+1 = y q+1 , and there exists a surjective homomorphism Φ ′ of G to G ′ mapping x to x and y to y. By construction, Φ ′

• Φ is the identity, so Φ is an isomorphism, and (8.1) is a presentation of G.

Remark 8.3. Once noted that the group a, b | a = b(a p b) q is isomorphic to the group x, y | x p+1 = y q+1 , it is obvious that x p+1 , i.e., a p+1 , is central in the group. However, this is not sufficient to deduce that a p+1 is central in the monoid a, b | a = b(a p b) q + as the latter is not a priori known to embed in the group. So, in order to apply the scheme of Theorem 6.5, it is crucial to make all verifications inside the monoid, i.e., without using inverses except possibly those provided by cancellativity.

For p = q = 1, the group G of Corollary 8.2 is the Klein bottle group a, b | a = bab . For p = 2 and q = 1, the group G, i.e., a, b | a = ba 2 b , is Artin's braid group B 3 . In terms of the standard Artin generators σ i , the elements a and b can be realized as σ 1 σ 2 and σ -1 2 , and the associated ordering is the isolated ordering described by Dubrovina-Dubrovin in [START_REF] Dubrovina | On braid groups[END_REF] (see also [START_REF] Picantin | Petits groupes gaussiens[END_REF]). The braid group B 3 is also obtained for p = 1 and q = 2, i.e., for a, b | a = babab , with a and b now realizable as σ 1 σ 2 σ 1 and σ -1 2 . Note that, when realized as above, the associated submonoids of B 3 coincide as, using a in the case p = 2, q = 1 and a ′ in the case p = 1, q = 2, we find a = a ′ b and a ′ = ba 2 . Therefore the associated (isolated) orderings of B 3 coincide.

For r 2, the monoid M of Proposition 8.1 embeds in a group of right-fractions G. However, the left counterpart of Lemma 7.2 ("Lemma 7.2") implies that a and ab have no common left-multiple in M . Hence M is not of left-O-type, and the group G is not a group of left-fractions for M : the right-fraction aba -1 is an element of G that cannot be expressed as a left-fraction. As a consequence, the semigroup M \{1} defines a partial left-invariant ordering on G only: for instance, the elements b -1 a -1 and a -1 are not comparable as their quotient aba -1 belongs neither to M nor to M -1 . Note that, for p = q = 1, the group G, i.e., a, b | a = bab r+1 , is the Baumslag-Solitar group BS(r + 1, -1), whereas the opposite group a, b | a = b r+1 ab is BS(-1, q + 1). Besides these examples, the case p = r = 2, q = 1, i.e., a, b | a = ba 2 b 2 , is the first non-classical example in the family. In this case, a 3 is a right-quasi-central element that is not central, and the associated endomorphism is given by φ(a) = a and φ(b) = b 2 ab 2 .

We now describe a family involving an arbitrarily large family of generators. Proposition 8.4. Assume ℓ 2 and m 2 , n 2 , m 3 , n 3 , ..., m ℓ , n ℓ 1. Let M the be monoid defined by (8.3) (a 1 , ..., a ℓ ; a 1 = a 2 w n2 2 , ..., a ℓ-1 = a ℓ w n ℓ ℓ ), with w 1 = a 1 and w i inductively defined by

w i = w mi i-1 •••w m3 2 w m2 1 a i . Then M is of O-type. Proof.
First, the presentation (8.3) is triangular (and symmetric). Now put g i = [w i ] + in M . For i 2, we obtain

g mi+1 i-1 = g mi i-1 • g i-1 = g mi i-1 g mi-1 i-2 •••g m2 1 a i-1 , g ni+1 i = g i • g ni i = g mi i-1 •••g m2 1 a i • g ni i .
The relations of (8.3) are valid in M , so, in particular, we have

a i-1 = a i • g ni i . It follows that g mi+1 i-1 = g ni+1 i holds for i = 2, ..., ℓ. Put ∆ = a m 1 where m is such that m(n 2 + 1)•••(n i + 1) is a multiple of (m 2 + 1)•••(m i + 1) for each i-which, for instance, is the case if m is a common multiple of m 2 + 1, ..., m ℓ + 1- say m(n 2 + 1)•••(n i + 1) = e i (m 2 + 1)•••(m i + 1
). Then, for every i, we have ∆ = g ei i , and, therefore, ∆ commutes with every g i . Then an induction on i shows that ∆ commutes with every a i : for i = 1, the result is obvious as ∆ is a power of a 1 , for i > 1, we have a i-1 = a i g i , whence, using the induction hypothesis,

∆a i g i = ∆a i-1 = a i-1 ∆ = a i-1 g i ∆ = a i ∆g i ,
and ∆a i = a i ∆ by right-cancelling g i , which is legitimate as M , which admits a lefttriangular presentation, must be right-cancellative. As a 1 , ..., a ℓ generate M , the element ∆ is central in M , and, by Proposition 5.11, M is of O-type.

The corresponding groups turn out to be amalgamated products of torus knot groups.

Corollary 8.5. For ℓ 2 and m 2 , n 2 , m 3 , n 3 , ..., m ℓ , n ℓ 1, let G be a group

(8.4) (x 1 , x 2 , ..., x ℓ ; x m2+1 1 = x n2+1 2 , x m3+1 2 = x n3+1 3 , ..., x m ℓ +1 ℓ-1 = x n ℓ +1 ℓ ).
Then G is orderable, the subsemigroup of G generated by x 1 , x -m2

1 x 2 , ..., x -m2 1 •••x -mi i-1
x i is the positive cone of a left-invariant ordering on G which is isolated in LO(G).

Proof. We just have to show that G admits the presentation (8.3) with respect to the specified generators. Now, in G, put a 1 = x 1 and, inductively,

a i = x -m2 1 •••x -mi
i-1 x i . An immediate induction gives x i = [w i ] for each i, where [w i ] means the evaluation of the word w i when the letter a i is given the value a i . Then (as above) we obtain

x mi i1 •••x m2 1 a i-1 = x mi+1 i-1 = x ni+1 i = x mi i1 •••x m2 1 a i x ni i , whence a i-1 = a i [w i ] ni
. This shows that the relations of (8.3) are satisfied by a 1 , ..., a ℓ in G, yielding an homomorphism Φ of the group G ′ presented by (8.3) to G that maps a i to a i .

Conversely, in G ′ , define x 1 to be a 1 and x i to be [w i ] for i 2. Then the same computation as above in the monoid M shows that

x mi+1 i-1 = x ni+1 i holds for every i in G ′ , leading to an homomorphism of G to G ′ that is the inverse of Φ. So G admits (8.3) as a presentation. Example 8.6. Assume m 2 = n 2 = ••• = m ℓ = n ℓ = p. Then G admits the presentation (x 1 , ..., x ℓ ; x p+1 1 = x p+1 2 = ••• = x p+1 ℓ
), and the result applies with ∆ = x p+1 1 . The positive cone of the associated isolated ordering is defined by the presentation (8.3), whose relations, in the current case, take the form (as usual, we write a, b, ... for a 1 , a 2 , ...)

a = b(a p b) p , b = c((a p b) p a p c) p , c = d(((a p b) p a p c) p (a p b) p a p d) p , etc.
See Table 1 (row 2) for other particular cases.

We now turn to a family of a different type, where the verification of the O-type relies not on the existence of a quasi-central element as in the previous examples, but on the existence of a dominating element-hence an infinitary condition. Proposition 8.7. For p, q, r, s 0, let M be the monoid defined by

(8.5) (a, b, c ; a = b(a p b) q , b = c(a r c) s ),
For r p or q = 0, the element a dominates a, b, c in M , and M is of O-type; for r < p with q 1, it is not.

Proof. As a preliminary remark, we note that the case q = 0 is trivial, as (8.5) then reduces to a = b and M is isomorphic to a, b | a = b(a r b) s + , in which, by Proposition 8.1, a r+1 is central, hence it right-dominates a, b, c by Lemma 5.12, and M is of O-type. So, from now on, we assume q 1. Assume first p < r. Then the relation a = c(a r c) s (a p b) q belongs to the completion R of the presentation, and it can be written as a = (ca r ) s+1 a.... Hence, by Lemma 7.2 with u = ca r , the monoid M cannot be of O-type.

From now on, we assume r p. As a preliminary remark, we compute

(8.6) a p+1 • b = aa p b = (b(a p b) q )a p b = b(a p b) q+1 = ba p (b(a p b) q ) = ba p a = b • a p+1 ,
which shows that a p+1 commutes with a and b. Moreover, as ba p a holds, applying Lemma 5.12 in the submonoid of M generated by a and b shows that a right-dominates b.

Next, let us write r = m + p ′ with p + 1 | m and 0 p ′ p. Then a m is a power of a p+1 , hence it commutes with a and b. From here, we separate two cases.

Assume first that p + 1 does not divide r + 1, i.e., p ′ < p holds. Put c ′ = ca p , and let M ′ be the submonoid of M generated by a, b, and c ′ . Let ∆ = a m . We shall prove that ∆ is right-quasi-central in M ′ . First, we can write a • a m-1 = ∆ and ∆ • a = a∆ both in M and in M ′ , so a ∆ a∆ holds in M ′ as it does in M . Next, we have b • (a p b) q a m-1 = ∆ and ∆ • b = b∆ in M and M ′ , so b ∆ b∆ holds in M ′ . It remains to treat c ′ . One the one hand, starting from a = c(a r c) s (a p b) q , which we re-arrange into a = c ′ • (a r-p c ′ ) s (ba p ) q-1 b by moving brackets, we see that c ′ a holds in M ′ , whence a fortiori c ′ ∆. On the other hand, in M , we find

c ′ • ∆ = ca r • a • a p-p ′ -1 by r = m + p ′ with p ′ < p (8.7) = ca r • b(a p b) q • a p-p ′ -1 by (8.5) for a = ca r • c(a r c) s • (a p b) q • a p-p ′ -1 by (8.5) for b = c(a r c) s • a r c • a p • (ba p ) q-1 ba p-p ′ -1 by moving brackets = b • a r • ca p • (ba p ) q-1 ba p-p ′ -1 by (8.5) for b = b • ∆ • a p ′ • c ′ • (ba p ) q-1 ba p-p ′ -1 by r = m + p ′ = ∆ • ba p ′ • c ′ • (ba p ) q-1 ba p-p ′ -1 by (8.6),
which shows that ∆ c ′ ∆ holds in M ′ . Being a submonoid of a cancellative monoid, the monoid M ′ is cancellative, so, by Lemma 5.12, ∆, i.e., a m , is right-quasi-central in M ′ . Moreover, in M , we have a = ca p • (a r-p ca p ) s (ba p ) q-1 b, which we can re-arrange as a = ca p (a r-p ca p ) s (ba p ) q-1 b, i.e., a = c ′ (a r-p c ′ ) s (ba p ) q-1 b, a relation that makes sense in M ′ . So, in M ′ , we have c ′ a r-p a. Applying Lemma 5.12 in M ′ is not sufficient, but, repeating its proof, we obtain, writing φ ′ for the endomorphism of M ′ associated with ∆,

c ′ a r-p ∆ k = ∆ k φ ′k (c ′ a r-p ) ∆ k φ ′k (a) = ∆ k a,
which implies in M the relation ca km+r a km+1 for every k. As m -1 r is true by definition, Lemma 5.8 implies that a right-dominates c in M . We saw above that a rightdominates b, hence a right-dominates all of a, b, c. By Proposition 5.6, M is of right-O-type, hence of O-type by symmetry.

Assume now that p + 1 divides r + 1, i.e., We have p ′ = p holds. Then, starting from a = b(a p ) q , we obtain a qm+1 = b(a p b) q (a m ) q = b(a p a m b) q = b(a r b) q , whence, substituting b with c(a r c) s , a qm+1 = c(a r c) q (a r c(a r c) s = c(a r c) (s+1)q+s = (ca r ) (s+1)q+s c, and, now putting ∆ = a qm+r+1 (not the same value as above),

c • ∆ = ca r • a qm+1 = ca r • (ca r ) (s+1)q+s c = (ca r ) (s+1)q+s c • a r c = a qm+1 • a r c = ∆ • c, so ∆ commutes with c.
As it is a power of a p+1 , it commutes with b, and with a, so ∆ is central in M , and M is of right-O-type, hence of O-type by symmetry.

To complete the study of M , we shall check that a is dominating in all cases. We already proved that a right-dominates a and b, and the point is to show that a right-dominates c in the case p + 1 | r + 1. Above we proved that a qm+r+1 is central in this case. Now, we only have ca r a so, unless in the degenerated case q = 0, we are not in position for applying Lemma 5.12 directly. Instead we shall prove ca r+km a 1+km for k = 0, ..., q. As m r holds (we have r = m + p by definition), we deduce ca n a n+1 for 0 n qm + r using the argument of Lemma 5.12. Now, as a qm+r+1 is central, the same relations then repeat periodically, and ca n a n+1 holds for every n. What we shall do is to prove

(8.8) a 1+km = ca r+km • (ba p ) k c(a r c) s-1 (a p b) q-k
using induction on k. For k = 0, we have a = b(a p b) q = ca r a(a r c) s-1 (a p b) q , which is (8.8). Assume q k > 0. We find

a 1+km = a 1+(k-1)m • a m = ca r+(k-1)m • (ba p ) k-1 c(a r c) s-1 (a p b) q-k+1 • a m by induction hyp. = ca r+(k-1)m • (ba p ) k-1 c(a r c) s-1 a m (a p b) q-k+1 by a m b = b a m = ca r+(k-1)m • (ba p ) k-1 c(a r c) s-1 a r b(a p b) q-k by r = m + p = ca r+(k-1)m • (ba p ) k-1 c(a r c) s-1 a r b(a p b) q-k by r = m + p = ca r+(k-1)m • (ba p ) k-1 c(a r c) s-1 a r c(a r c) s-1 (a p b) q-k by (8.5) for b = ca r+(k-1)m • (ba p ) k-1 c(a r c) s a r c(a r c) s-1 (a p b) q-k by moving brackets = ca r+(k-1)m • (ba p ) k-1 ba r c(a r c) s-1 (a p b) q-k by (8.5) for b = ca r+(k-1)m • (ba p ) k-1 ba m a p c(a r c) s-1 (a p b) q-k by r = m + p = ca r+(k-1)m • a m (ba p ) k-1 ba p c(a r c) s-1 (a p b) q-k by by a m b = b a m = ca r+km • (ba p ) k c(a r c) s-1 (a p b) q-k which is (8.8).
So the argument is complete and, even in the case p + 1 | r + 1, the element a dominates each of a, b, and c.

Note that the monoid of Proposition 8.7 is generated by a and c alone and admits the corresponding (less readable) presentation (a, c ; a = c(a r c) s (a p c(a r c) s ) q ). The 4-parameter family of Proposition 8.7 contains in particular all presentations (a, b ; a = ba r ba p ba r b), and all presentations (a, b ; a = (b(a r b) s ) q ). In terms of orderable groups, we deduce Corollary 8.8. For p, q, s 0 and r p, let G be the group x, y | x p+1 = (y(x r-p y) s ) q+1 . Then G is orderable, the subsemigroup of G generated by x and yx -p is the positive cone of a left-invariant ordering on G which is isolated in LO(G).

Proof. Once more, it suffices to show that G admits the presentation (8.5) in terms of the mentioned elements. Put a = x, c = yx -p , and b = c(a r c) s in G. The second relation of (8.5) is automatically satisfied; on the other hand, we find a p+1 = (y(x r-p y) s ) q+1 = (ca p (a r-p ca p ) s ) q+1 = (c(a r c) s a p ) q+1 = (ba p ) q+1 = b(a p b) q a p , whence the first relation of (8.5) by right-cancelling a p , yielding an homomorphism of the group G ′ defined by (8.5) to G. Conversely, put x = a and y = ca p in G ′ . Then x and y generate G ′ and satisfy x p+1 = (y(x r-p y) s ) q+1 , whence an homomorphism of G to G ′ , and, finally, an isomorphism. So G admits the expected presentation.

We finish with a family of still another type, namely one where the third generator is used to split an initially not triangular relation into two triangular relations, by observing that a two-generator relation au = bvb defines the same group as the two triangular relations a = bvc, b = cu. The example we choose is interesting as it corresponds to groups that are not torus knot groups. Proposition 8.9. For p, q, r 0, let M be the monoid defined by (8.9) (a, b, c ; a = ba p+2 (ba p ba p+2 ) q c, b = c(ba p+2 ) r ba),

Then, for r = 0 and for r = 1, the monoid M is of O-type.

Proof (sketch). The presentation (8.9) is triangular. Put ∆ = (a p+2 b) 2q+r+3 . Then ∆ is central in M and a ∆ holds. Hence, by Proposition 5.11, M is of right-O-type, hence of O-type as the opposite relations also are triangular (with the ordering of a and b exchanged).

Corollary 8.10. For q, r 0, let G be the group x, y | x r+1 = (yx 2 y) q+1 . Then, for r = 0 and 1, the group G is orderable and, for every p, the subsemigroup of G generated by x -1 , xy p+2 , and xyx -(r+1) is the positive cone of a left-invariant ordering on G which is isolated in LO(G).

Proof. According to the principle stated before Proposition 8.9, the group defined by (8.9) admits the presentation a, b | a(ba p+2 ) r ba = ba p+2 (ba p ba p+2 ) q b . Introducing x = ba p+2 , this becomes a, b, x | ax r ba = x(xa -2 x) q b, x = ba p+2 , whence a, x | ax r+1 a = x(xa -2 x) q x . Putting y = a -1 , this becomes x, y | x r+1 = yx(xy 2 x) q xy , whence x, y | x r+1 = (yx 2 y) q+1 by arranging the brackets. The result then follows from the converse relations a = x -1 , b = xy p+2 , and c = xyx -(r+1) .

For r 2, it seems that the monoid M of Proposition 8.9 is still of O-type: experiments suggest that, for p = 0 and r = 2, the right-ceiling of M is the periodic word ∞ (b 2 a 3 ) for every q but, as no central or quasi-central element seems to exist, this remains a conjecture.

A few further families are displayed in Table 3. We skip the verifications.

Limits of the approach

So far, we did not discuss the range of our approach, namely the question of whether many monoids of (right)-O-type admit (right)-triangular presentations. Owing to the positive results of Sections 7 and 8, which provide a number of such monoids of O-type, it would even be conceivable that all monoids of O-type could admit a triangular presentation. In this section, we show that this is not the case, and give a simple criterion discarding a number of such monoids, in particular the n-strand Dubrovina-Dubrovin braid monoids for n 4.

So our starting point is What is significant in a right-triangular presentation is not the fact that it consists of triangular relations, but the condition that there is at most one letter N (s) and one relation N (s) = sC(s) for every s: every positive presentation can be trivially transformed into a presentation of the same monoid consisting of triangular relations by introducing, for every relation u = v, a new letter s and replacing u = v with the triangular relations s = u, s = v.

The following result, which is a special case of a result of [START_REF] Dehornoy | Gaussian groups and Garside groups, two generalizations of Artin groups[END_REF] for monoids in which any two elements admit a least common right-multiple, may appear relevant for Question 9.1. Fact 9.2. Assume that M is a monoid of right-O-type that satisfies Condition (4.2), and S is any generating subfamily of M . For all s, s ′ in S with s s ′ , choose an S-word w such that sw represents s ′ . Let R be the family of all relations sw = s ′ so obtained. Then (S ; R) is a presentation of M . Proof (sketch). We wish to prove for all S-words u, v that [u] + = [v] + is equivalent to u ≡ + R v. By construction, R consists of relations that are valid in M , hence u ≡ + R v always implies [u] + = [v] + , and the problem is the converse implication. Standard arguments show that (4.2) is equivalent to the existence of a map λ from M to the ordinals such that s = 1 implies λ(sg) > λ(g). Then one proves that

[u] + = [v] + with λ([u] + ) = α implies u ≡ + R v using induction on α. For α = 0, we have λ([u] + ) = λ([v] + ) = 0, hence [u] + is minimum with respect to proper right-divisibility in M , implying [u] + = [v] + = 1, whence u = v = ε.
Assume now α > 0. Then u and v cannot be empty. Write u = su 0 , v = s ′ v 0 with s, s ′ in S. Then, by definition, we have (*) λ([u 0 ] + ) < λ([u] + ) and λ([v 0 ] + ) < λ([v] + ). Assume first s ′ = s. By assumption, we have [u] + = [v] + , i.e., s[u 0 ] + = s[v 0 ] + . As M is left-cancellative, we deduce [u 0 ] + = [v 0 ] + . By (*) and the induction hypothesis, this implies u 0 ≡ + R v 0 , whence a fortiori u = su 0 ≡ + R sv 0 = v. Finally, assume s ′ = s. In M , the elements s and s ′ are comparable for , say for instance s s ′ . Then, by construction, there exists in R one relation sw = s ′ such that s[w] + = s ′ holds in M . We deduce s

[u 0 ] + = s ′ [v 0 ] + = s[w] + [v 0 ] + = s[wv 0 ] + , whence [u 0 ] + = [wv 0 ] + since M is left-cancellative.
By (*) and the induction hypothesis, this implies u 0 ≡ + R wv 0 , whence u = su 0 ≡ + R swv 0 ≡ + R s ′ v 0 = v. So the induction is complete.

The above positive result is misleading. The range of Fact 9.2 is nonempty since it applies at least to the monoid (N, +), but, as already mentioned, the Noetherianity condition (4.2) fails in almost all monoids that admit triangular presentations, and the following example shows that, when (4.2) fails, we cannot hope for a result similar to Fact 9.2. Actually, we shall establish a rather general negative answer to Question 9.1 in the case of generating families with at least three elements. Definition 9.4. Assume that M is a monoid and S is included in M . An element s of S is called preponderant in S if g hs holds for all g, h in the submonoid generated by S\{s}. Proposition 9.5. Assume that M is a monoid of right-O-type and S is a generating subfamily of M that contains a preponderant element and has at least three elements. Then M admits no right-triangular presentation based on S.

Proof. We assume that M admits a right-triangular presentation (S ; R) and shall derive a contradiction by exhibiting two elements of M that cannot admit a common right-multiple.

As M is of right-O-type, owing to Lemma 4.9, we can enumerate S as {a i | i ∈ I} so that all relations in R have the form a i-1 = a i C(a i ). Assume that a i is preponderant in S. Then i must be minimal in I as a j ≺ a i holds for every j = i. So we may assume I = {1, 2, ...} (finite or infinite), and that a 1 is preponderant in S.

As a 1 is preponderant in S, it may occur in no word C(a i ) with i 3 for, otherwise, writing C(a i ) = ua 1 v with no a 1 in u, applying the definition of preponderance with g = a 2 i-1 and h = [a i u] + would lead to the contradiction

a i-1 ≺ a 2 i-1 [a i ua 1 ] + [a i C(a i )] + = a i-1 .
On the other hand, a 1 must occur in C(a 2 ) for, otherwise, we would obtain similarly the contradiction [a 2 C(a

2 )] + ≺ [a 2 C(a 2 )a 2 ] + a 1 = [a 2 C(a 2 )] + . Write a 2 C(a 2 ) = u 0 a 1 v 0 with no a 1 in u 0 .
Claim. Assume that w is an S-word that is ≡ + R -equivalent to a word beginning with a 1 . Then w contains at least one letter a 1 and, if u is the initial fragment of w that goes up to the first letter a 1 , there exists r 0 satisfying u ≡ + R u r 0 . We prove the claim using induction on the combinatorial distance n of w to a word beginning with a 1 , i.e., on the length of an R-derivation from w to such a word. For n = 0, i.e., if w begins with a 1 , the word u is empty, and we have u = ε = u 0 0 . Assume n > 0. Let w ′ be a word obtained from w by applying one relation of R that lies at distance n -1 from a word beginning with a 1 . By induction hypothesis, w ′ contains at least one letter a 1 , and we have w ′ = u ′ a 1 v ′ with no a 1 in u ′ and u ′ ≡ + R u r ′ 0 for some r ′ . We consider the various ways w can be obtained from w ′ . First, if one relation of R is applied inside v ′ , we have w = u ′ a 1 v with v ≡ + R v ′ and the result is clear with u = u ′ and r = r ′ . Next, assume that the distinguished letter a 1 is involved. By hypothesis, N (a 1 ) is not defined, so there is no relation s = a 1 C(a 1 ) in R. On the other hand, u ′ contains no a 1 and, therefore, a 1 occurs in no relation s = ... for s occurring in u ′ . So the only ways a 1 may be involved is either a 1 being replaced with a 2 C(a 2 ), or a 2 C(a 2 ) (which contains at least one a 1 ) being replaced with a 1 . In the first case, we obtain u = u ′ u 0 a 1 v 0 v ′ , which shows that w contains a letter a 1 and gives u = u ′ u 0 , whence u ≡ + R u r ′ +1 0 , the expected result with r = r ′ + 1. In the second case, there must exist decompositions u ′ = uu 0 and v ′ = v 0 v so that we have w ′ = uu 0 a 1 v 0 v and w = ua 1 v. Again w contains a 1 , and we find now uu 0 ≡ + R u ′ ≡ + R u r ′ 0 , whence u ≡ + R u r-1 0 because, by assumption, M is right-cancellative. This is again the expected result, this time with r = r ′ -1. Finally, it remains the case when one relation of R is applied inside u ′ . In this case, we obtain w = ua 1 v ′ with u ≡ + R u ′ , whence u ≡ + R u ′ ≡ + R u r ′ 0 , and the result is clear with r = r ′ . So the proof of the claim is complete.

We shall now easily obtain a contradiction. Indeed, by construction, the word u 0 begins with the letter a 2 , so a 2 [u 0 ] + holds. By assumption, a 2 and a 3 are distinct, so C(a 3 ) is nonempty, and we obtain 1 ≺ a 3 ≺ a 3 [C(a 3 )] + = a 2 [u 0 ] + , so that a 3 = [u r 0 ] + fails for every r. Then the above claim implies that no S-word beginning with a 3 a 1 may be ≡ + R -equivalent to an S-word beginning with a 1 . In other words, the elements a 1 and a 3 a 1 cannot admit a common right-multiple in M , contrary to the assumption that M is of right-O-type. Proof. For a contradiction, assume that (a, b, c; a = bu, b = cv) is a presentation of M . If there is no a in u, the assumption that a = bu is valid in M implies that a belongs to the submonoid generated by b and c, so M must be generated by b and c.

Assume now that there is at least one a in u. As a does not occur in b = cv, a word containing a cannot be equivalent to a word not containing a. This implies that a is preponderant in {a, b, c}. Indeed, assume that g, h belong to the submonoid of M generated by b and c. By the above remark, hag ′ = g is impossible, hence so is ha g. As, by assumption, M is of right-O-type, we deduce g ha. Then Proposition 9.5 gives the result.

1 = σ 1 •••σ n-1 , s 2 = (σ 2 •••σ n-1 ) -1 , s 3 = σ 3 •••σ n-1 , ..., s n-1 = σ (-1) n n-1 . Then B ⊕
n is a monoid of O-type that admits no right-triangular presentation based on {s 1 , ..., s n-1 } for n 4.

Proof. That B ⊕

n is of O-type was established by Dubrovina-Dubrovin in [START_REF] Dubrovina | On braid groups[END_REF]. Now, as a braid that admits an expression containing at least one σ 1 and no σ -1 1 cannot admit an expression with no σ ±1

Further questions

Although triangular presentations may seem to be extremely particular, it turns out that a number of monoids of O-type with such presentations exist-much more than was expected first. So the main question is to further explore the range of the approach and understand which ordered groups are eligible. In particular, we started here from a monoid viewpoint and did not address the question of starting from an (ordered) group and possibly finding a relevant monoid with a triangular presentation. We now mention a few more specific problems.

Two-generator monoids of O-type. Whereas describing all monoids of O-type is certainly out of reach, the particular case of two-generator monoids seems more accessible, and several natural questions arise.

First, we saw in Section 9 that some monoids of O-type admit no triangular presentation, but the argument of Proposition 9.5 requires the existence of at least three generators. If M is a monoid of right-O-type generated by a ≻ b, some triangular relation a = bw is satisfied in M . However, the word w is not unique and Question 10.1 asks in particular for a preferred choice of w. Here is a negative observation about what could be a natural approach. Let (w n ) n 1 be the shortlex-enumeration of {a, b} * . Using induction on n, we can construct a triangular presentation (w 1 , ..., w n ; R n ) that specifies the -adjacent elements in Next, all identified monoids of O-type with two generators share some properties.

{[w i ] + | i n} in M : assuming that the evaluation [w n ] + of w n lies between [w i ] + and [w j ] + in {[w 1 ] + , ..., [w n ] + }, we obtain R n from R n-
Question 10.2. Is every two-generator triangular presentation defining a monoid of O-type necessarily palindromic, i.e., the relation is invariant under reversing the order of letters? Is the right-ceiling necessarily equal to ∞ s, where s is the top generator?

At the moment, we have no counter-example. More generally, we can wonder whether a complete description of all monoids of O-type that admit a two-generator triangular presentation could be possible. When stated in terms of two-generator presentation, Proposition 8.7 may appear promising, but a complete solution still seems out of reach. The general form of the relation in a two-generator triangular presentation is a = ba e1 ba e2 b.... Proposition 8.1 corresponds to the case when all exponents e i are equal, whereas Proposition 8.7 corresponds to the case when two exponents p, r occur with a periodic distribution a = b(a r b) s (a p b)(a r b) s (a p b)... . Inductively extending Proposition 8.7 seems doable-the next case would be that of three relations a = b(a p b) q , b = c(a r c) s , c = d(a t d) u involving three exponents p, r, t-even finding methods that cover all cases with two exponents seems problematic. We give below an example of such a monoid that is indeed of O-type but enters no identified family.

aδ n • cacbc(bc) 2n = bδ n • b = cδ n • acacb = δ n+1 .
It follows that δ dominates a, b, and c in M . Hence, by Proposition 5.6, M is of Otype. Experiments suggest that the right-ceiling is ∞ a, so that, by Lemma 5.9, a should dominate a, b, c as well, but we have no proof.

Periodicity of the right-ceiling. Many of the monoids mentioned in Sections 7 and 8 admit a central or a quasi-central element that is a power of the top generator, and we could wonder whether this is always the case. It is not.

Example 10.4. Consider the monoid M of Proposition 8.7 with r 2 and p + 1 | r + 1. We have seen in the proof that the relation ca km+r a km+1 holds for every k. As m r holds by definition, we deduce ca (k+1)m a km+1 for each k, which in turns implies ca n ≺ a n for every n. So a n ca n is always impossible, a n is not quasi-central for any n.

This however says nothing about quasi-central elements that are not a power of the top generator, and we can raise Question 10.5. Does every monoid of O-type that admits a triangular presentation contain a quasi-central element?

A positive answer seems unlikely but, on the other hand, it is uneasy to a priori discard the existence of exotic quasi-central elements. In particular, looking at the right-ceiling is irrelevant in general: a quasi-central element ∆ dominates all generators but, if ∆ admits no expression that is a right-top word, Lemma 5.9 cannot be used. For instance, for the presentation (ab ; a = bab 3 ab) (row 5 in Table 2), the right-ceiling ∞ a does not discard the existence of the central element (ab) 3 . Owing to the explicit formulas in the proof of Proposition 8.7, we think it might be possible to prove that no nontrivial quasi-central element exists in the case of (a, b, c ; a = ba 2 b, b = ca 4 c).

The situation is also open for dominating elements. As for the top generator to necessarily dominate the other generators, the answer is negative. Indeed, according to Lemma 5.9, the top generator s dominates the other generators if and only if the right-ceiling is ∞ s. So, to discard a positive answer, it suffices to exhibit one presentation where the right-ceiling has a different form. The following example does, and, in addition, it shows that not only the top generator, but even any power of it need not dominate the other generators. (case p = q = r = 0 in row 6 of Table 3). One easily checks that b 2 a 2 is right-quasicentral in M , with φ(a) = aba 2 cac 3 , φ(b) = ba 2 c 2 , and φ(c) = c, and that b 2 a 2 dominates {a, b, c} 4 . By Lemma 5.9, it follows that the right-ceiling is the periodic word ∞ (b 2 a 2 ) and, therefore, a cannot dominate b and c in M . Moreover, we find ba 2 = a 3 • ba 2 c 3 , and b(a n ) = (a n ) 2 • ba 2 c 2n a n-2 for n 2. This shows that a n does not dominate b for any n. Now, as in the case of quasi-central elements, this says nothing about dominating elements that are not powers of the top generator and leaves the following natural questions open: Question 10.7. Does every monoid of O-type that admits a triangular presentation based on a set S contain an element that dominates S? Is the right-ceiling necessarily periodic in a monoid of O-type that admits a finite triangular presentation? By Lemma 5.9, a positive answer to the second question means the existence of an element of S n that dominates all of S n for some n 1, hence a fortiori S, so it implies a positive answer to the first question. Owing to the examples known so far, we conjecture a positive answer to both questions, but we have no clue toward a proof.

We add two more related examples. The first one shows that a power of the top generator may dominate the other generators although the top generator does not. The second one shows that the period of the right-ceiling can be arbitrarily large.

Example 10.9. Let M n be defined by the cycling presentation (a 1 , ..., a n ;

a 1 = a 2 •••a n , a 2 = a 3 •••a n a 1 , ..., a n-1 = a n a 1 •••a n-1 ).
Then a 2 1 is central in M n , and the right-ceiling is ∞ (a n-1 •••a 1 ), hence it has period n -1. A similar behaviour can be found with three generators in the family of row 6 in Table 3.

Complexity of reversing. In the context of a presentation that is complete for rightreversing, the existence of common right-multiples implies the termination of every rightreversing. However, the argument gives no complexity bound, at least no polynomial bound.

Example 10.10. Consider the presentation (a, b ; a = bab r+1 ) of the Baumslag-Solitar group BS(r + 1, -1). For every n, the signed word a -n ba n reverses to the word b (r+1) n , whose length is exponential in n. As every reversing step adds at most r letters, the number of steps needed to reverse the length 2n + 1 word a -n ba n must be exponential in n.

An exponential complexity may occur whenever there exists a right-quasi-central element such that the associated endomorphism duplicates some letter. Now, in all examples, the monoid is not of left-O-type: this is the case in Example 10.10 or, for instance, for (a, b, c ; a = bacb, b = cac), where a 2 is right-quasi-central with φ(c) = (cb) 2 but the oppopresentation leads to the non-terminating reversing u (12) v -1 uv for u = b -1 c 2 ab and v = c 2 . By contrast, such behaviours could not be found for monoids of O-type. Question 10.11. If a triangular presentation defines a monoid of O-type, does the associated reversing necessarily have a polynomial (quadratic?) complexity?

Note that the existence of a quasi-central element that is not central need not imply an exponential complexity. For instance, for the presentation (a, b ; a = ba 2 baba 2 b) (row 2 of Table 3) with ∆ = (a 2 b) 2 quasi-central, we have φ(a) = a(ba 2 b) 2 , and the shortest expression of φ(a) is longer by 8 letters than that of a. However, φ(a 2 ) = a 2 holds in the monoid, and reversing ∆ -n a∆ n leads to a word of length linear in n in a quadratic number of steps. The monoid of Example 10.3 is a good test-case for Question 10.11. It turns out that reversing the length 2n word a -(n-1) b -1 a n leads to a word of length (2n) 2 in a number of steps that is cubic in n: this is compatible with a positive answer to Question 10.11, but discards a uniform quadratic upper bound.

Connection with rewrite systems. Triangular presentations are simple in many respects, and they could be eligible for alternative approaches, in particular rewrite systems.

Example 10.12. Consider the presentation (a, b ; a = bab) of the Klein bottle group. To obtain Noetherianity, we orientate the relation as bab → a. Then there is a critical pair as babab rewrites into a 2 b and ba 2 . Adding ba 2 → a 2 b yields a system that is locally confluent and Noetherian (the rules diminish the length or replace a word with a word of the same length and lexicographically smaller), hence confluent. Then every word rewrites in finitely many steps into a unique, well defined terminal word, providing a unique normal form for the elements of the monoid.

The existence of a normal form as above gives an easy solution to the word problem of the monoid, and can in turn be extended to the group. However recognizing divisibility properties is not clear. Question 10.13. Can one use the rewrite system approach to investigate the existence of common multiples in the associated monoid?

We have no answer. Let us also observe that using (as above) the lexicographical ordering to solve critical pairs need not lead to a Noetherian system in general. Isolated points in the case of a direct limit. Theorems 1 and 6.5 are valid in the case of an infinite presentation, thus leading to orderable groups with an explicit positive cone. But the argument showing that the involved ordering is isolated in its space of orderings is valid only when the presentation is finite. However, as observed by C. Rivas [START_REF] Rivas | Left-orderings on free products of groups[END_REF], a non-finitely generated monoid may give rise to an isolated ordering, so it makes sense to raise Question 10.15. If (S, R) is an infinite triangular presentation defining a monoid of Otype, may the associated ordering be isolated in the space LO( S | R )?

In the direction of a positive answer, it would be natural to address Question 10.15 in the context of a direct limit of finitely generated monoids. The properties of subword reversing make this situation easy to analyze. + ) if and only if u -1 v is R n -reversible (resp. R m -reversible) to the empty word. By definition of reversing, the relations in R m \ R n are never involved in the reversing of u -1 v, so the latter two relations are both equivalent to u -1 v being R-reversible to ε. It follows that the identity on S n induces an embedding of

S n | R n + into S m | R m + . So S n | R n +
identifies with the submonoid of S m | R m + generated by S n and S | R + is then the direct limit, here the union, of all monoids S n | R n + . It follows that S | R + is of O-type. Indeed, a direct limit of monoids of right-O-type is of right-O-type: any two elements of the limit belong to some monoid of the considered direct system, hence are comparable with respect to left-divisibility in that monoid, and therefore in the limit.

The interest of Proposition 10.16 is to provide local conditions for recognizing a monoid of O-type: in order to show that the monoid S | R + is, say, of right-O-type, it is sufficient to consider the finite type monoids S n | R n + . A typical example is the group (10.3) x 1 , x 2 ... | x 2 1 = x q 2 , x 2 2 = x q 3 , ...

Definition 2 . 1 .Example 2 . 3 .

 2123 A semigroup relation u = v is called triangular if either u or v consists of a single letter. So, a triangular relation has the generic form s ′ = sw, where s, s ′ belong to the reference alphabet. For instance, a = bab and b = c 2 ba are typical triangular relations in the alphabet {a, b, c}. The problem we shall address now is Question 2.2. Assume that (S ; R) is a presentation consisting of triangular relations. Is the associated monoid necessarily of right-O-type? The following counter-example shows that a uniform positive answer is impossible. The presentation (a, b, c; c = ab, c = ba) consists of two triangular relations. The associated monoid M is a rank 2 free Abelian monoid based on a and b, and neither of a, b is a right-multiple of the other. So M is not of right-O-type.

  triangular presentation is defined symmetrically by relations N (s) = C(s)s. A presentation is triangular if it is both right-and left-triangular. Example 2.5. Assume S = {a, b, c} and R = {a = bac, b = cba}. Then (S ; R) is a righttriangular presentation. The associated maps N and C are given by N (b) = a, C(b) = ac, N (c) = b, C(c) = ba, and we have R = R ∪ {a = cba 2 c}. The presentation (S ; R) is also left-triangular, with N and C defined by N (a) = b, C(a) = cb, N (c) = a, C(c) = ba.

Proposition 2 . 6 (

 26 Main Lemma). Assume that (S ; R) is a right-triangular presentation. Then the following are equivalent: (i) The monoid S | R + is of right-O-type; (ii) Any two elements of S | R + admit a common right-multiple.

( 1 )

 1 R w ′ , if either there exist s, s ′ in S, a relation sv ′ = s ′ v of R, and signed words w 1 , w 2 satisfying (3.1)

Example 3 . 2 .

 32 Assume S = {a, b, c} and R = {a = bab, b = cbc, a = cbcab}. Starting for instance with w = a -1 c -1 a, we find

.Figure 1 .

 1 Figure 1. Reversing diagram associated with the reversing sequence of Example 3.2: starting from the signed word a -1 c -1 a, which corresponds to the left and top arrows, we successively reverse c -1 a into bcab, and a -1 b into b -1 a -1 , thus obtaining the final word b -1 a -1 cab.

Figure 2 .

 2 Figure 2. The three possible ways of concatenating two reversing diagrams in which one of the output words is empty: in each case, one of the final output words has to be empty.

Lemma 4 . 7 .

 47 Assume that u, v are nonempty S-words satisfying u ≡ +(1) R v. Then there exists s underlying u and v and, for every s in S, we have E s (u) ≡ +( 1) R E s (v). Moreover, exactly one of the following holds: (i) we have I(u) = I(v) and T (u) ≡ +(1) R T (v); (ii) we have I(u) = I(v) and E s (u) = E s (v) for all s underlying u and v.

Lemma 4 . 8 .

 48 has been established for every s in every case. Assume that u, v are nonempty S-words satisfying u ≡+(n) R v.Then at least one of the following holds:

Lemma 5 . 3 .

 53 Assume that M is a left-cancellative monoid generated by a set S. (i) If w is a right-top S-word in M , then g [w] + holds for every g in S |w| . (ii) A final fragment of a right-top word is a right-top word. (iii) A left-infinite S-word ...s 2 s 1 is a right-S-ceiling in M if and only (5.1) is satisfied. Proof. (i) Assume that w is a right-top word and we have g ∈ S n with n |w|. Let s be an arbitrary element of S. Then gs |w|-n belongs to S |w| , and we have g gs |w|-n [w] + , whence g [w] + . (ii) Assume that w is a right-top word and v is a final fragment of w, say w = uv. Let h belong to S |v| . By construction, [u] + h belongs to S |w| , so [u] + h [w] + holds. As M is left-cancellative and [w] + = [u] + [v] + holds, we deduce h [v] + , so v is a right-top word.

Proposition 6 . 1 .

 61 A sufficient condition for a group G to be orderable is that G admits a triangular presentation (S ; R) such that the monoids S | R + and S | R + are eligible for at least one of Propositions 5.2, 5.6, or 5.11. In this case, the subsemigroup of G generated by S is the positive cone of a left-invariant ordering on G. If S is finite, this ordering is an isolated point in the space LO(G).Proof. Whenever the monoid S | R + is eligible for one of the mentioned results, it is of right-O-type. For a similar reason, the monoid S | R + is of right-O-type, hence S | R + is of left-O-type. Therefore, S | R + is of O-type, and then we apply Corollary 2.7.

Proposition 6 . 7 .

 67 Assume that (S ; R) is a right-triangular presentation and there exists an element ∆ in S | R + satisfying ∀s∈S (s ∆ s∆) or ∀s∈S ∀n (s∆ n ∆ n+1 ). Then Algorithm 6.6 solves the word problem of the group S | R . Proof. By Proposition 4.4, the presentation (S, R) is complete for right-reversing and, by Proposition 6.1, any two elements of the monoid S | R + admit a common right-multiple, hence every R-reversing sequence is terminating: for every signed S-word w, there exist positive S-words u, v satisfying w R uv -1 . Hence Algorithm 6.6, which consists of two concatenated reversings, always terminates.Then, by construction, w R uv -1 implies [w] = [uv -1 ] in S | R . Hence [w] = 1 holds if and only if we have [uv -1 ] = 1, or, equivalently, [u] = [v]. By Ores's theorem, the monoid S | R + embeds in the group S | R , so the latter condition is equivalent to [

Proposition 6 . 8 .

 68 Assume that M is a monoid of right-O-type and ∆ is right-quasi-central (resp. simultaneously right-and left-quasi-central) in M and its left-divisors generate M . Then ∆ is a right-Garside element (resp. a Garside element) in M in the sense of [9, Definitions VI.1.36 and 2.29].

Lemma 7 . 2 .

 72 Assume that (S ; R) is a triangular presentation. (i) If a relation of R has the form s = w with |w| > 1 and w finishing with s, then S | R + is not right-cancellative and, therefore, S | R + is not of right-O-type.

Lemma 4 . 3 , 2 Figure 3 .

 4323 Figure 3. Proof of Lemma 7.2(ii): in a positive number of steps, the word s -1 us

( 7 . 3 )

 73 w -1 a i w is R-reversible to a positive word. Then [w] + is right-quasi-central in S | R + and the latter is a monoid of right-O-type. Proof. That [w] + is right-quasi-central in S | R + directly follows from Lemma 5.13, since (7.3) implies [w] + a i [w] + . Moreover, by construction, we have a n ••• a 1 [w] + , whence a i [w] + for every i. Hence, by Proposition 5.11, S | R + is of right-O-type.

Fact 7 . 4 . 3 a

 743 Among the 1,023 presentations (a, b; a = bw) with w of length 9 in {a, b} * , -854 are eligible for Lemma 7.2, yielding a monoid not of right-O-type. -3 lead to a cyclic reversing, yielding a monoid not of right-O-type. -166 are eligible for Lemma 7.3, yielding a monoid of right-O-type (33 are of O-type).right-O left-O a = bababab YES YES ∆ = a 2 central; a = ba 2 babab YES ∆ = a 3 right-quasi-central, φ(a) = a, φ(b) = (babab) 3 NO a = ...a(ab)(ab)(ab): Lemma 7.2 with u = (ab), v = ε a = baba 2 bab NO NO a = (ba)(ba)a...: Lemma 7.2 with u = ba and v = ε a = ba 3 babab YES ∆ = a 4 right-quasi-central, φ(a) = a, φ(b) = b(ab) 8 NO a = ...a(ab)(ab): Lemma 7.2 with u = (ab) and v = ε a = bab 3 ab YES YES ∆ = (ab) 3 = (ba) 3 central a = ba 2 baba 2 b YES YES ∆ = (a 2 b) 2 = (ba 2 ) 2 right-and left-quasi-central, φ(a) = a(ba 2 b) 2 , φ(a) = (ba 2 b) 2 a, φ(b) = φ(b) = b a = ba 2 b 3 a 2 b NO NO non-terminating right-reversing: u (10) v -1 uv for u = a -2 ba 2 ba and v = ba 2 b = ba 2 bab 2 a 2 b YES ∆ = (a 2 b) 2 right-quasi-central, φ(a) = (ab 2 a) 2 ab, φ(b) = (ba 2 b 2 ) 2 NO non-terminating left-reversing: u (26) vuv -1 for u = a 2 b 2 a 2 bab 3 a 2 ba -1 and v = b a = ba 2 b 4 a 2 b NO NO non-terminating right-reversing: u (12) v -1 uv for u = b -1 a -2 ba 2 ba and v = b 4 a 2 bab 4 a 2 b

  b ; a = b(ab p ) q ab) ∆ = (ab p-1 ) 2 central x, y | x q+2 =y 2 2: (a, b ; a = ba r ba p ba r b) ∆ = (a r b) 2 right-quasi-central with p + 1 | r with φ(a) = a p (ba r b) 2 , φ(b) = b x, y | x p = (yx r-p y) 2 3: (a, b, c ; a = ba p b, b = cba r c) ∆ = a p(r-p)+1 central with p + 1 | r + 1 x, y, z | x p+1 = y 2 , y = zyx r-p z 4: (a, b, c ; a = ba p b, b = cba r c) ∆ = a r b 2 quasi-central with p + 1 | r with φ(a) = a p ba p-1 b 3 , φ(b) = b, φ(c) = c; x, y, z | x p+1 = y 2 , y = zyx r-p z 5: (a, b, c ; a = b(ab) p , b = cb(a r b) p c) ∆ = a p(p+1)(r-1)+2 central with r odd x, y, z | x 2 = (xy) p+1 , zyz = y(x r y) q 6: (a, b, c ; a = ba p+1 (ba p ba p+1 ) q c, ... ∆ = (a p+1 b) r+3 central b = c(ba p+1 ) r ba) x, y | y r+3 = x q+2

Question 9 . 1 .

 91 Assume that M is a monoid of right-O-type and S is a generating subfamily of M . Does M admit a right-triangular presentation based on S?

Example 9 . 3 .

 93 Let M be the Klein bottle monoid a, b | a = bab + . Then M is of right-O-type, and it is generated by a and b. Now, in M , we have a = b 2 ab 2 , so, if Fact 9.2 were valid here, (a, b ; a = b 2 ab 2 ) would be an alternative presentation of M . This is not the case: by Lemma 7.2 applied with u = b and v = ε, monoid a, b | a = b 2 ab 2 + is not of right-O-type and, therefore, it is not isomorphic to M .

Proposition 9 .

 9 5 prevents a number of monoids of right-O-type from admitting a righttriangular presentation. Corollary 9.6. Assume that M is a monoid of right-O-type that is generated by a, b, c with a ≻ b ≻ c and b, c satisfying some relation b = cv with no a in v. Then, unless M is generated by b and c, there is no way to complete b = cv with a relation a = bu so as to obtain a presentation of M .

  So, for instance, no right-triangular presentation made of b = cbc (Klein bottle relation) or b = cb 2 c (Dubrovina-Dubrovin braid relation) plus a relation of the form a = b... may define a monoid of right-O-type. In the case of braids, we obtain the following general result. Corollary 9.7. Let B ⊕ n be the submonoid of the braid group B n generated by s

1 [ 10 ]

 110 , the generator s 1 is preponderant in {s 1 , ..., s n-1 }. Proposition 9.5 implies that B ⊕ n admits no triangular presentation based on {s 1 , ..., s n-1 } for n 4. One can indeed convert the standard presentation of the braid group B n into a presentation in terms of the generators s 1 , ..., s n-1 of Corollary 9.7. For instance, writing a, b, ... for s 1 , s 2 , ..., one can check that B ⊕ 4 admits the presentation (9.1) (a, b, c ; a = b 2 a 2 baba 2 b 2 , b = cb 2 c, abc = cab), a triangular presentation augmented with a third, additional relation. But the triangular presentation made of the first two relations in (9.1) is not a presentation of B ⊕ 4 , nor of any monoid of O-type either.

Question 10 . 1 .

 101 Does every two-generator monoid of right-O-type admit a right-triangular presentation?

1

 1 by removing the former relation w j = w i • ... and adding two new relations w n = w i • u, w j = w n • v with u, v (say) shortlex-minimal. We could expect that, at least if a central element exists, the process converges and leads to a triangular presentation of M . Let M = a, b | a = bab + . Then R 3 specifies ε < b < a and contains the relation a = b • ab, whereas R 4 corresponds to inserting b 2 between b and a, so we remove a = b • ab and add b 2 = b • b and a = b 2 • ab 2 . Now we observed in Example 9.3 that a = b•ab is not a consequence of the latter two relations, so the process cannot converge to a presentation of M , and Question 10.1 remains open.

Example 10 . 3 .

 103 Let M be the monoid defined by (a, b ; a = babab 2 ab 2 abab), which is also defined by (a, b, c ; a = bcacb, b = cacac). Working with the second presentation and putting δ = b 2 , one can establish the formulas

Example 10 . 6 .

 106 Let M be defined by the presentation (10.1) a, b, c | a = bac, b = cba +

Example 10 . 8 .

 108 Let M be defined by (a, b, c ; a = bcb, b = cbabc). Then M is generated by b and c, with the presentation (b, c ; b = cb 2 cb 2 c). So, by Proposition 8.1, b 3 is central and M is of O-type. Now a 3 = b 3 happens to hold and, therefore, a 3 dominates b and c. On the other hand, we find ba = a 2 • bc 2 b, whence ba a 2 , and a does not dominate b.

Example 10 . 14 .

 1014 Consider the triangular presentation (a, b, c ; a = bc, b = cb 2 ). Starting with the two rules bc → a, cb 2 → b, a critical pair comes from rewriting bcb 2 into ab 2 and b 2 . Using the lexicographical ordering would lead to adding the rule b 2 → ab 2 , which clearly contradicts Noetherianity.

Proposition 10 . 16 .

 1016 Assume that (S ; R) is an infinite triangular presentation(10.2) (a 1 , a 2 , ... ; a 1 = a 2 w 2 a 2 , a 2 = a 3 w 3 a 3 , ...)with w i in {a 1 , ..., a i } * and, putting S n = {a 1 , ..., a n } andR n = {a i-1 = a i w i a i | i n}, that the monoid S n | R n + is of O-typefor every n (or, at least, for unboundedly many n). Then S | R + is a direct limit of the monoids S n | R n + , it is of O-type, and S | R + \{1} is the positive cone of a left-invariant ordering on the group S | R . Proof. Assume n < m. Owing to the assumption about w i , the presentations (S n ; R n ) and (S m ; R m ) are well defined and, by definition, they are right-triangular, so that, by Proposition 4.4, (S n ; R n ) and (S m ; R m ) are complete for right-reversing. Now assume that u, v are S n -words. Then u and v represent the same element in S n | R n + (resp. in S m | R m

Table 2 .

 2 Examples of two-generator monoids with a triangular presentation: in all cases that are not a priori discarded by Lemma 7.2 or its symmetric counterpart "Lemma 7.2 " , one can either find a (quasi)-central element or identify a nonterminating reversing, hence decide whether the associated monoid is of right-or left-O-type.

Table 3 .

 3 More examples of monoids of O-type, with the justification and an alternative presentation of the associated group; in 1, two-generator symmetric presentations with central elements that are not a power of a; in 2 (a special case of Proposition 8.4), two-generators symmetric presentations with quasi-central elements that are not central (for p 1); in 6, an example similar to Proposition 8.9 (which corresponds to replacing p + 1 with p + 2).

1 Work partially supported by the ANR grant ANR-08-BLAN-0269-02 1991 Mathematics Subject

considered in Proposition 8.4. For q = 2, the element ∆ = x 2 1 is central in S | R + , and Theorem 1 implies that S | R + is of O-type. By contrast, for q odd, the element

It follows that S n | R n + is of O-type for every n, and S | R + is of O-type by Proposition 10.16, but, in this case, no power of x 1 is central in S | R + . The multi-toric groups (10.3) are natural test-cases for Question 10.15.

The specific case of braids. The braid group B 3 is eligible for our current approach, as the submonoid B ⊕ 3 generated by σ 1 σ 2 and σ -1 2 turns out to be a monoid of O-type with the triangular presentation (a, b; a = ba 2 b). By contrast, we saw in Section 9 that, for n 4, the submonoid B ⊕ n of B n generated by the Dubrovina-Dubrovin generators s 1 , ..., s n-1 admits no triangular presentation based on {s 1 , ..., s n-1 }. This however does not discard the possibility that B ⊕ n admits a triangular presentation based on other generators. Question 10.17. Does the monoid B ⊕ n admit a (finite) triangular presentation for n 4? Natural candidates could be the Birman-Ko-Lee band generators [START_REF] Birman | A new approach to the word problem in the braid groups[END_REF]. For 1 i < j n,

. Then the family (a i,j ) 1 i<j n generates B n , and the submonoid of B n generated by the a i,j 's, which is known as the dual braid monoid, has many nice properties. Now there exists a simple connection between the monoid B ⊕ n and the elements a i,j .

Proposition 10.18. Put b i,j = a

. Then, for every n, the monoid B ⊕ n is generated by the elements b i,j .

Proof. We recall from [START_REF] Dehornoy | Ordering Braids[END_REF] that a braid is called σ i -positive (resp. negative) if it admits a decomposition in terms of the generators σ k that contains no letter σ ±1 k with k < i, and contains at least one letter σ i and no letter σ -1 i (resp. at least one letter σ -1 i and no letter σ i ). Then an element of B n belongs to B ⊕ n if and only if it is either σ i -positive for some odd i or σ i -negative for some even i. The braid relations imply

j-1 for i < j, hence a i,j is σ i -positive, and b i,j is σ i -positive for odd i and σ i -negative for even i. Therefore, b i,j belongs to B ⊕ n for all i, j. Conversely, in B n , we have

whence

Hence s i belongs to the submonoid of B n generated by the b i,j 's and, finally, B ⊕ n coincides with the latter. Proposition 10.18 makes it natural to wonder whether B ⊕ n admit a triangular presentation based on the elements b i,j , or on connected elements. The answer is positive for n = 3. Indeed, starting from the standard presentation of B 3 in terms of the a i,j 's, here

+ , which is (10.1) with a, b, c interpreted as σ 1 , a 1,3 , and σ -1 2 . The quasi-central element is then σ 1 σ 2 2 σ 1 and the associated endomorphism is defined by

and φ(σ 2 ) = σ 2 . For n 4, the question remains open. It might be natural to replace, for even i, the generators a -1 i,j with the symmetric versions σ 4 , but the associated monoid is not B ⊕ 4 because ae = ea is missing. We conclude with an amusing application. For small values of n, the connection of Proposition 10.18 between the Dubrovina-Dubrovin ordering and the Birman-Ko-Lee generators of braid groups implies the existence of a braid ordering on B n that is isolated (contrary to the Dehornoy ordering) and, at the same time, includes the positive braid monoid B + n (contrary to the Dubrovina-Dubrovina ordering).

Corollary 10.19. The subsemigroup generated by σ 1 , σ 2 , and σ 1 σ -1 2 σ -1

is the positive cone of an isolated left-invariant ordering on the braid group B 3 . The subsemigroup generated by σ

is the positive cone of an isolated left-invariant ordering on the braid group B 4 .

Proof. Conjugation by σ 1 •••σ n defines an order n automorphism φ n of B n that rotates the Birman-Ko-Lee generators [START_REF] Dehornoy | Ordering Braids[END_REF]. For n = 3, one has φ 3 : σ 1 → σ 2 → a 1,3 → σ 1 . By Proposition 10.18, B ⊕ 3 is generated by σ 1 , a 1,3 , σ -1 2 . Hence the monoid φ 3 (B ⊕ 3 ) is generated by σ 2 , σ 1 , a -1 1,3 , and it is (when 1 is removed) the positive cone of a left-invariant ordering on B 3 . Similarly, for n = 4, we have φ 4 : ) is generated by σ 3 , a 1,3 , σ 2 , σ 3 , a -1 1,4 , a -1 2,4 , σ 1 , and it is (with 1 removed) the positive cone of a left-invariant ordering.

By the above remarks, the monoid φ 3 (B ⊕

3 ) admits the presentation (10.1) with a = σ 2 , b = σ 1 , c = a -1 1,3 = σ 1 σ -1 2 σ -1 1 . The construction does not extend to n 5, because the negative entries σ -1 2 and σ -1 4 cannot be eliminated simultaneously.