Patrick Dehornoy
email: patrick.dehornoy@unicaen.fr

Yves Guiraud
email: yves.guiraud@pps.univ-paris-diderot.fr

Quadratic normalisation in monoids

Keywords: 1991 Mathematics Subject Classification. 20M05, 68Q42, 20F10, 20F36, 18B40 normal form, normalisation, rewriting system, termination, convergence, plactic monoid, Chinese monoid, Artin-Tits monoid, Garside family

Introduction

A normal form for a monoid M , with a specified generating subfamily S, is a map that assigns to each element of M a distinguished representative word over S. Our aim in this paper is to investigate a certain type of such normal forms and, more precisely, the associated normalisation processes, that is, the syntactic transformations that lead from an arbitrary word to a normal word. Here we restrict to geodesic normal forms, which select representatives of minimal length, and investigate the quadratic case, that is, when some locality conditions are satisfied: that a word is normal if, and only if, each of its length-two factors are normal, and that one can always transform a word into a normal word by a finite sequence of steps, each of which consists in normalising a length-two factor.

This general framework includes two well-known classes of normalisation processes: those associated with Garside families as investigated in [START_REF] Dehornoy | Algorithms for Garside calculus[END_REF] and [START_REF] Dehornoy | Foundations of Garside Theory[END_REF], building on the seminal example of the greedy normal form in Artin's braid monoids [START_REF] Adyan | Fragments of the word Delta in a braid group[END_REF][START_REF] El-Rifai | Algorithms for positive braids[END_REF][START_REF] Epstein | Word Processing in Groups[END_REF], and those associated with quadratic rewriting systems as investigated for instance in [START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF] for Artin monoids and in [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] for plactic monoids. So our current development can be seen as an effort to unify various approaches and understand their common features. This program is made natural by the observation that, in spite of their unrelated definitions, the normalisation processes arising in the above mentioned situations share common mechanisms: for instance, in each case, a lengththree word can be normalised in three steps, successively normalising the length-two factors in position 2-3, then in position 1-2, and in position 2-3 again. D. Krammer's ideas had a seminal influence in our approach, in particular for the connection between normalisation and the monoid underlying Subsection 4.3, which he investigated in [START_REF] Krammer | An asymmetric generalisation of Artin monoids[END_REF]. A similar connection was independently discovered by A. Hess and V. Ozornova in [START_REF] Hess | Factorable monoids: resolutions and homology via discrete Morse theory[END_REF][START_REF] Ozornova | Factorability, discrete Morse theory, and a reformulation of K(π, 1)-conjecture[END_REF][START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF], partly building on unpublished work by M. Rodenhausen. Our current approach is close to theirs in the case of graded monoids. In this case, beyond minor terminology discrepancies, the factorability structures of [START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF] correspond to what we call normalisations of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. But, in the general case, the two viewpoints are not directly comparable because of divergent treatment of units and invertible elements: in both approaches a "dummy" element is used, but with different assumptions, resulting in different notions of complexity and different conclusions. It seems that every factorability structure yields a normalisation of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Cain | Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids[END_REF], but understanding which normalisations of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Cain | Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids[END_REF] arise in this way remains open.

Let us present our main results. The central technical notion is that of a normalisation, which is a pair (S, N ) made of a set S and an idempotent length-preserving map N from the free monoid S * to itself: the intuition is that N (w) is the result of normalising w, that is, N (w) is the distinguished element in the equivalence class of w. The normalisation automatically determines the associated monoid via the defining relations w = N (w), and we take it as our basic object of investigation. We call quadratic a normalisation (S, N ) such that a word w is N -normal (meaning N (w) = w) if, and only if, each length-two factor of w is N -normal, and such that one can go from w to N (w) by applying a finite sequence of shifted copies of the restriction N of N to the set S [2] of length-two words. We then introduce, for every quadratic normalisation, a class, which is a pair of positive integers describing the complexity of normalisation for length-three words: by definition, if w is a length-three word, N (w) is equal to N 212...[m] (w) or N 121...[m] (w), meaning a length-m sequence of alternate applications of N in positions 1-2 and 2-3, and we say that the class is (c, c ′ ) if one always reaches the normal form after at most c steps when starting from the left, and c ′ steps from the right. We observe that the class, if not infinite, has the form (c, c ′ ) with |c ′ -c| 1, and that a system of class (c, c ′ ) is of class (d, d ′ ) for all d c and d ′ c ′ . We give a number of examples witnessing possible behaviours for the class and its analogue for the normalisation of longer words. However, most of our general results involve quadratic normalisations of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] or [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF].

The first main result is an axiomatisation of normalisations of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] in terms of the restriction of the normalisation map to length-two words: Theorem A. If (S, N ) is a quadratic normalisation of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF], then the restriction N of N to S [2] is idempotent and satisfies N 212 = N 2121 = N 1212 . Conversely, if φ is an idempotent map on S [2] that satisfies φ 212 = φ 2121 = φ 1212 , there exists a quadratic normalisation (S, N ) of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] satisfying φ = N .

The direct implication is easy and extends to all classes. But the converse direction is more delicate and does not extend: a map on length-two words normalising length-three words needs not normalise words of greater length. The proof of Theorem A involves the monoid M p studied in [START_REF] Krammer | An asymmetric generalisation of Artin monoids[END_REF] and [START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF], which is an asymmetric version of Artin's braid monoids where the relation σ 2 σ 1 σ 2 = σ 1 σ 2 σ 1 is replaced with σ 2 σ 1 σ 2 = σ 1 σ 2 σ 1 σ 2 = σ 2 σ 1 σ 2 σ 1 . Let us mention that [START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF]Th. 3.4] is an analogue of Theorem A for factorability structures.

The second main result involves termination. Every quadratic normalisation (S, N ) gives rise to a quadratic rewriting system, namely the one with rules w → N (w) for w a non-N -normal length-two word. By definition, this rewriting system is confluent and normalising, meaning that, for every initial word, there exists a finite sequence of rewriting steps leading to a unique N -normal word, but its convergence, meaning also that any sequence of rewriting steps is finite, is a different question. We prove Theorem B. If (S, N ) is a quadratic normalisation of class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] or [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF], then the associated rewriting system is convergent, with every rewriting sequence starting from a length-p word having length at most 2 p -p -1.

The result can be compared with the easier result that, in class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF], every rewriting sequence starting from a length-p word has length at most p(p -1)/2, and it is optimal, in the sense that there exists a nonconvergent rewriting system of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF]. The proof of Theorem B is delicate and relies on a diagrammatic tool called the domino rule. Theorem B exhibits a strong difference between the factorability structures of [START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF] and normalisations of class (4, 3), since the former can induce nonterminating rewriting systems, as witnessed by the counterexample of [START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF]Appendix,Prop. 7]. However, there is a connection between Theorem B and [START_REF] Hess | Factorability, string rewriting and discrete Morse theory[END_REF]Th. 7.3], which states termination in the case of a factorability structure that obeys the domino rule, hence, as a normalisation, is of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. The arguments are different, and it is not clear how restrictive it is for a normalisation of class (4, 3) to be associated with a factorability structure.

As mentioned above, Garside normalisation [START_REF] Dehornoy | Foundations of Garside Theory[END_REF] integrates into quadratic normalisations, more precisely normalisations of class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] in the case of a bounded Garside family, and of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] in the general case. It is natural to ask for a characterisation of Garside systems inside the family of all normalisations of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. This is the last one of our main results:

Theorem C. Call a normalisation (S, N ) left-weighted if, for all s, t in S, the element s leftdivides the first entry of N (s|t) in the associated monoid. Then, for every normalisation (S, N ) such that the associated monoid M is left-cancellative and contains no nontrivial invertible element, the family S is a Garside family in M and (S, N ) is the derived normalisation if, and only if, (S, N ) is of class (4, 3) and left-weighted.

The proof relies on nontrivial properties of Garside families and, again, on the domino rule available in class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. A consequence of Theorems B and C is that the rewriting system derived from a Garside family is always convergent, which generalises the case of Artin-Tits monoids with the elements of the corresponding Coxeter group as generators [START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF]Th 3

.1.3,Prop. 3.2.1].
The paper is organised in five sections after this one. Section 2 contains basic definitions about normal forms and normalisations in the general case. We explain how the adjunction of a dummy generator with specific properties extends the use of length-preserving normalisations to non-graded monoids. In Section 3, we introduce quadratic normalisations as those normalisations whose map is determined by its restriction to length-two words, and we establish a bijective correspondence between the latter and a generalisation of convergent rewriting systems (with termination relaxed into normalisation). We also introduce the class, and its generalisation the p-class, as measures of the complexity of normalisation, and establish their basic properties. In particular, we give counterexamples showing the independence of the 3-class and of the p-class for p 4. Section 4 is devoted to the specific case of quadratic normalisations of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. Such systems provide well-behaved normalisation processes; we establish in particular an explicit universal formula for the normalisation of length-p words and, as an application, we show that being of class (4, 3) implies being of p-class (4, 3) for every p. The section ends with Theorem A. In Section 5, we study the relationship between the class of a quadratic normalisation and the termination of the associated rewriting system, proving in particular Theorem B. Finally, Section 6 is devoted to the connection with Garside families and the associated greedy normal forms, establishing Theorem C.

Note that almost all observations in this paper extend from the context of monoids to that of categories, seen as monoids with a partially defined product.

Thanks. The authors warmly thank Viktoriya Ozornova for having sent a number of useful comments about the first version of this paper and shared her view of the subject.

Normalisations and geodesic normal forms

In this introductory section, we define normalisations and connect them with geodesic normal forms of monoids (Subsection 2.1). We explain how to add a "dummy" generator to make the restriction to length-preserving maps innocuous (Subsection 2.2).

2.1.

Normalisations. If S is a set, we denote by S * the free monoid over S and call its elements S-words, or simply words. We write w for the length of an S-word w, and w|w ′ , or simply ww ′ , for the product of two S-words w and w ′ .

Our aim is to investigate normal forms of a monoid M with respect to a generating family S, that is, maps from M to S * that choose, for every element g of M , a distinguished expression of g by an S-word, or, equivalently, maps from S * to itself that choose a distinguished element in each equivalence class. We shall privilege the latter approach, in which the primary object is the word map and the monoid is then derived from it. Definition 2.1.1. A normalisation is a pair (S, N ), where S is a set and N is a map from S * to itself satisfying, for all S-words u, v, w,

N (w) = w , (2.1.2) w = 1 implies N (w) = w, (2.1.3) N (u|N (w)|v) = N (u|w|v). (2.1.4) An S-word w satisfying N (w) = w is called N -normal. If M is a monoid, we say that (S, N ) is a normalisation for M if M admits the presentation (2.1.5) S | {w = N (w) | w ∈ S * } + .
Note that (2.1.4) implies that N is idempotent. The homogeneity condition (2.1.2) is discussed (and partly skirted around) in Subsection 2.2.

Example 2.1.6. Assume that S is a set and < is a linear order on S. For w in S * , define N (w) to be the < * -minimal word obtained by permuting letters in w, where < * is the lexicographic extension of < to S * . So, for instance, assuming a, b, c ∈ S and a < b < c, we find N (bcabac) = aabbcc. Then (S, N ) is a normalisation for the free commutative monoid N (S) over S.

The following fact is a direct consequence of the definition: Lemma 2.1.7. If (S, N ) is a normalisation for a monoid M , then M admits a graduation such that all elements of S have degree one, that is, there exists a morphism d :

M → (N, +) such that s ∈ S implies d(s) = 1.
Proof. For g in M , all the S-words representing g must have the same length by (2.1.2): define d(g) to be this common length.

The following result connects Definition 2.1.1 with the alternative approach in which the monoid is given first. If a monoid M is generated by a set S, we denote by ev the canonical projection from S * to M . Lemma 2.1.8. Assume that M is a monoid and S is a generating subfamily of M . If N is a length-preserving map from S * to itself, then (S, N ) is a normalisation for M if, and only if, for all S-words w, w ′ , the following conditions hold:

ev(N (w)) = ev(w), (2.1.9) ev(w) = ev(w ′ ) implies N (w) = N (w ′ ). (2.1.10)
Proof. Assume that (S, N ) is a normalisation for M . As (2.1.5) is a presentation of M , each relation N (w) = w is valid in M and, therefore, (2.1.9) holds. Next, assume that w, w ′ are S-words satisfying ev(w) = ev(w ′ ). As (2.1.5) is a presentation of M , (2.1.10) follows from N (u|w|v) = N (u|N (w)|v), which is (2.1.4).

Conversely, assume that (2.1.9) and (2.1.10) are satisfied. By assumption on N , (2.1.2) is satisfied and, for s in S, we have N (s) ∈ S, so that S ⊆ M implies ev(s) = s and ev(N (s)) = N (s), whence (2.1.3) by (2.1.9). Then, for S-words u, v, w, we have ev(u|N (w)|v) = ev(u|w|v) by (2.1.9), whence (2.1.4) by (2.1.10). So (S, N ) is a normalisation. Finally, (2.1.5) is a presentation of M because, on the one hand, all relations N (w) = w are valid in M by (2.1.9) and, on the other hand, ev(w) = ev(w ′ ) implies N (w) = N (w ′ ) by (2.1.10), hence (2.1.9) implies that w and w ′ are equivalent to N (w) modulo the relations of (2.1.5).

We now connect normalisations with the usual notion of a normal form. Definition 2.1.11. If M is a monoid and S is a generating subfamily of M , a normal form on (M, S) is a (set-theoretic) section of the canonical projection ev of S * onto M . A normal form nf on (M, S) is called geodesic if, for every g in M , we have nf(g) w for every S-word w representing g.

For graded monoids, normalisations are equivalent to normal forms: Proposition 2.1.12. (i) If (S, N ) is a normalisation for a monoid M , we obtain a normal form on (M, S) by putting (2.1.13) nf(g) = N (w), where w is any representative of g.

(ii) Conversely, assume that M is a graded monoid, S is a generating subfamily of M whose elements have degree 1, and nf is normal form on (M, S). Then we obtain a normalisation (S, N ) for M by putting (iii) The correspondences of (i) and (ii) are inverses of one another.

Proof. (i) First the definition makes sense, since, if w, w ′ are two representatives of g, then (2.1.10) implies N (w) = N (w ′ ). Next, assuming ev(w) = g, we obtain ev(nf(g)) = ev(N (w)) = ev(w) = g using (2.1.9), so nf is a section of ev.

(ii)

The assumption that M is graded implies N (w) = w for every S-word w. Then, (2.1.14) implies ev(N (w)) = ev(nf(ev(w))) = ev(w) because nf is a section of ev, so (2.1.9) holds. Finally, ev(w) = ev(w ′ ) implies nf(ev(w)) = nf(ev(w ′ )), whence (2.1.10). So, by Lemma 2.1.8, (S, N ) is a normalisation for M .

(iii) If (S, N ) is a normalisation for M , and nf is defined by (2.1.13) and N ′ by (2.1.14), then N ′ (w) = nf(ev(w)) = N (w) holds, since w is a representative of ev(w). Conversely, if nf is a normal form on (M, S), and N is defined by (2.1.14) and nf ′ by (2.1.13), then ev(w) = g implies nf ′ (g) = N (w) = nf(g). Hence the correspondences of (i) and (ii) are inverses of one another.

2.2.

The non-graded case. So far, according to Lemma 2.1.7, only graded monoids are eligible. We explain how to adapt our approach to arbitrary monoids.

N (w 0 |e|w 1 | ••• |w ℓ-1 |e|w ℓ ) = N (w 0 | ••• |w ℓ )|e ℓ .
(iii) For every S-word w, we have N (w) = w ′ |e ℓ , where w ′ is an S e -word and ℓ is an upper bound of the number of occurrences of e in w.

Proof. (i) By definition, M is generated by S, hence by S e . Next, for every S e -word w, the relation w = π e (N (w)) is valid in M owing to π e (w) = w. As M admits the presentation (2.2.3), it remains to check that all relations of (2.2.3) can be derived from those of (2.2.5) plus e = 1:

this is because the S-word N (w) is obtained from π e (N (w)) by inserting copies of e thanks to the relation e = 1.

(ii) Use induction on ℓ 0. For ℓ = 0, the result is immediate. For ℓ 1, we find

N (w 0 |e|w 1 | ••• |w ℓ-1 |e|w ℓ ) = N (w 0 |e|w 1 | ••• |w ℓ-1 |N (e|w ℓ )) by (2.1.4) = N (w 0 |e|w 1 | ••• |w ℓ-1 |w ℓ |e) by (2.2.2) = N (w 0 |e|w 1 | ••• |w ℓ-1 |w ℓ )|e by (2.2.2) = N (w 0 | ••• |w ℓ-1 |w ℓ )|e ℓ by induction hypothesis.
(iii) By (ii), we have N (w) = v|e p , where v is N (π e (w)) and p is the number of occurrences of e in w. By the same argument, we find that N (v) is w ′ |e q , where w ′ is N (π e (v)) and q is the number of occurrences of e in v. Since N is idempotent, we have v = N (v) = w ′ |e q . We deduce that w ′ contains no e and that N (w) = w ′ |e p+q holds.

The following variation of Proposition 2.1.12 requires no graduation assumption: the solution is to add a dummy generator to preserve word length. (ii) Conversely, assume that M is a monoid, S is a generating subfamily of M , and nf is a geodesic normal form on (M, S). Put S e = S ∐ {e} and write ev e for the canonical projection of S * onto M extended to (S e ) * by ev e (e) = 1. Then we obtain a normalisation (S e , N ) mod e for M by putting (2.2.9) N (w) = nf(ev e (w))|e m , with m = wnf(ev e (w)) .

(iii) The correspondences of (i) and (ii) are inverses of one another.

Proof. (i) Let w, w ′ be two representatives of g in S * . Then one can be obtained from the other by applying relations

v = v ′ with either v = u 1 |N (u 2 )|u 3 and v ′ = u 1 |u 2 |u 3 , or v = u 1 |e|u 2 and v ′ = u 1 |u 2 .
In the first case, (2.1.4) gives N (v) = N (v ′ ). In the second case, Lemma 2.2.4 (ii) gives N (v) = N (v ′ )|e. Thus we have π e (N (w)) = π e (N (w ′ )) and nf e (g) is well defined. Now, let M e be the monoid presented by (2.1.5), π : M e ։ M and ev e : S * e ։ M be the canonical projections. For g in M and w be a representative of g in S * , the relation π • ev = ev e • π e and (2.1.9) imply ev e (nf(g)) = ev e (π e (N (w)) = π(ev(N (w))) = π(ev(w)) = g, so nf is a normal form on (M, S e ). Moreover, we have π e (N (w))

N (w) = w , so nf is geodesic.

(ii) Since nf is geodesic, we have nf(ev e (w)) w for every S e -word w. So (2.2.9) makes sense and N is length-preserving. Next, for s ∈ S e , we have either s ∈ S and N (s) = nf(s) = s, or s = e and N (e) = nf(1)|e = e. Then, since nf is a section of ev, (2.2.9) gives ev e (N (w)) = ev(nf(ev e (w)) = ev e (w), yielding nf(ev e (u|N (w)|v)) = nf(ev e (u|w|v)) and, since N is length-preserving, N (u|N (w)|v) = N (u|w|v). Thus (S e , N ) is a normalisation. Now, let w be an S e -word, with m = wnf(ev e (w)) . Then we have ev e (w|e) = ev e (e|w) = ev e (w), whence N (w|e) = nf(ev e (w))|e m+1 = N (w)|e, and, similarly, N (e|w) = N (w)|e, so e is N -neutral. Finally, by Lemma 2.2.4(i), the monoid M admits the presentation (S e ) e | {w = π e (N (w)) | w ∈ (S e ) * e } + . Owing to the equalities (S e ) e = S and π e (N (w)) = π e (nf(ev e (w))|e m ) = nf(ev(w)), the monoid M also admits the presentation

S | {w = nf(ev(w)) | w ∈ S * } + .
(iii) Starting from (i), let (S e , N ′ ) be the normalisation mod e derived from nf using (ii). Then we have (S e ) e = S and N ′ (w) = nf(ev(w))|e m = π e (N (w))|e m , whence N ′ (w) = N (w) by Lemma 2.2.4 (iii). Conversely, starting from (ii), let nf ′ be the normal form derived from N using (i). Then we have nf ′ (g) = π e (N (w)) = π e (nf(ev e (w))|e m ) = nf(g) for every g in M with representative S-word w.

Remark. If a monoid M is graded with respect to a generating family S and nf is a normal form on (M, S), then two normalisations come associated with M and S: the one (S, N ) provided by Proposition 2.1.12 (ii), and the one (S e , N e ) provided by Proposition 2.2.7 (ii). The connection between these systems is given, for every S e -word w, by the equality π e (N e (w)) = N (π e (w)).

Quadratic normalisations and their class

We now restrict our study to particular normalisations that are, in a convenient sense, generated by transformations of length-two words. After basic definitions and examples (Subsection 3.1), we relate those normalisations with rewriting systems (Subsection 3.2). Then we introduce the class of such a normalisation as a pair of elements of N ∪ {∞} that gives an upper bound on the complexity of normalisation for length-three words (Subsection 3.3). Finally, we consider the p-class, an analogue involving length-p words (Subsection 3.4).

3.1. Quadratic normalisations. Notation 3.1.1. (i) If S is a set and φ is a map from the set S [p] of length-p S-words to itself, then, for i 1, we denote by φ i the (partial) map of S * to itself that consists in applying φ to the entries in position i, ..., i + p -1.

If u = i 1 | ••• |i n is a finite sequence of positive integers, we write φ u for the composite map φ in • ••• • φ i1 . (ii) If (S, N
) is a normalisation, we denote by N the restriction of N to S [2] .

Here is the main notion investigated in this paper:

Definition 3.1.2. A normalisation (S, N ) is called quadratic if the following conditions hold:
An S-word w is N -normal if, and only if, every length-two factor of w is. (3.1.3) For every S-word w, there exists a finite sequence u of positions, depending on w, such that N (w) is equal to N u (w). (3.1.4) So, a normalisation (S, N ) is quadratic if N -normality only depends on length-two factors and if one can go from an S-word w to the S-word N (w) in finitely many steps, each of which consists in applying N to some length-two factor. Note that, provided S is finite, (3.1.3) implies that the language of all N -normal S-words is regular.

Example 3.1.5. The normalisation (S, N ) of Example 2.1.6 is quadratic. Indeed, an S-word is N -normal if, and only if, all its length-two subfactors are of the form s|t with s t, so (3.1.3) is satisfied. Moreover, (3.1.4) holds, since every S-word w can be transformed into the equivalent N -normal S-word N (w) by switching adjacent letters that are not in the expected order: for instance, if a < b < c, one has N (cbba) = abbc = N 31213 (cbba). Note that the sequence of length-two normalisations is not unique, and depends on the initial word. Definition 3.1.2 gathers two locality conditions, which, taken separately, do not seem to have interesting consequences in our approach: (3.1.3) is a static characterisation of normal words, whereas (3.1.4) is dynamical in that it involves transformations into normal words. As (3.1.4) implies that a length-two word is N -normal if, and only if, it is N -invariant, it induces the right-to-left implication in (3.1.3). The next two counterexamples show that this is the only general connection between (3.1.3) and (3.1.4).

Example 3.1.6. Let S = {a, b, c} and N : S * → S * be defined as follows: starting from w in S * , we first replace every factor aba or aca with a 3 , and then, in the resulting word, we replace every factor ab with ac and every factor ca with ba. Then (S, N ) is a normalisation (for (2.1.4), observe for instance that N (uabv) = N (uacv) holds both when v begins with a and when it does not), it satisfies (3.1.3) since a word is N -normal if and only if it contains no factor ab or ca, but it does not satisfy (3.1.4): neither aba nor aca is N -normal, but the only S-words that can be obtained from aba and aca using N 1 and N 2 are aba and aca themselves. Hence (3.1.3) does not imply (3.1.4). When a normalisation (S, N ) is quadratic, the restriction N of N to S [2] is crucial. Here are first general properties. (iii) If (S, N ) is a quadratic normalisation mod e for a monoid M , then M admits the presentation

(3.1.11) S e | {s|t = π e (N (s|t)) | s, t ∈ S e } + .
Proof. (i) By (2.1.4), N is idempotent, hence so is its restriction N . The monoid M admits the presentation (3.1.9) because it admits the presentation (2.1.5) with the same generators, because the relations (3.1.9) are contained into the ones of (2.

(e|s|w ′ ) = N (N (e|s)|w ′ ) = N (s|e|w ′ ) = N (s|N (e|w ′ )) = N (s|N (w ′ |e)) = N (s|w ′ |e), so e is N -neutral. (iii) By (i), M is presented by S | {s|t = N (s|t) | s, t ∈ S} ∪ {e = 1} + .
Applying the Tietze transformation that collapses e onto 1, we obtain the presentation S e | {π e (s|t) = π e (N (s|t)) | s, t ∈ S} + for M . If at least one of s or t is e, then by (3.1.10), the corresponding relation boils down to s = s, t = t or 1 = 1, so that we can remove it. Otherwise, we have π e (s|t) = s|t, yielding (3.1.11).

3.2.

Quadratic normalisations and rewriting. We recall that a (word) rewriting system is a pair (S, R) consisting of a set S and a binary relation R on S * whose elements (w, w ′ ) are written w → w ′ and called rewriting rules.

Assume that (S, R) is a rewriting system. We denote by → R the closure of R with respect to the product of S * and by

→ * R the reflexive-transitive closure of → R . An S-word w is R-normal if w → * R w ′ implies w ′ = w. If w, w ′ are S-words, w ′ is an R-normal form of w if w → * R w ′ and w ′ is R-normal. One says that (S, R) is quadratic if w → w ′ ∈ R implies w = w ′ = 2; reduced if w → w ′ ∈ R implies that w ′ is R-normal and w is R \ {w → w ′ }-normal;
normalising if every S-word admits at least an R-normal form; and confluent if the conjunction of w → * R w 1 and w → * R w 2 implies w 1 → * R w ′ and w 2 → * R w ′ for some w ′ . As a rewriting rule is a pair of words, there is no ambiguity in speaking of the monoid presented by (S, R). Proposition 3.2.1. (i) If (S, N ) is a quadratic normalisation for a monoid M , then we obtain a quadratic, reduced, normalising and confluent rewriting system (S, R) presenting M by putting

(3.2.2) R = {s|t → N (s|t) | s, t ∈ S, s|t = N (s|t)}.
(ii) Conversely, if (S, R) is a quadratic, reduced, normalising and confluent rewriting system presenting a monoid M , we obtain a quadratic normalisation (S, N ) for M by putting

(3.2.3) N (w) = w ′ where w ′ is the R-normal form of w.
(iii) The correspondences of (i) and (ii) are inverses of one another.

Proof. (i) By definition, (S, R) is quadratic and reduced, and, for all S-words w and w ′ , we have w → * R w ′ if, and only if, w ′ = N u (w) holds for some sequence u of positions. Thus, by (3.1.4), R is normalising. Moreover, the conjunction of w → * R w 1 and w → * R w 2 implies N (w 1 ) = N (w 2 ), hence (S, R) is confluent by (3.1.4). Finally, (S, R) is a presentation of M by (3.1.9).

(ii) Since (S, R) is normalising and confluent, every S-word admits exactly one R-normal form, so (3.2.3) makes sense and implies that M admits the presentation (2.1.5). Next, since R is quadratic, N is length-preserving and preserves generators. Moreover, the R-normal forms of u|w|v and of u|N (w)|v are equal, whence N (u|w|v) = N (u|N (w)|v). So (S, N ) is a normalisation for M . Moreover, the definition of N implies that it satisfies both (3.1.3) and (3.1.4).

(iii) The proof is straightforward.

Note that the rewriting system associated to a quadratic normalisation does not always terminate, meaning that there may exist infinite rewriting sequences

w 0 → R w 1 → R w 2 → R •••, as shown in Section 5.
Example 3.2.4. If (S, N ) is the quadratic normalisation for the free commutative monoid N (S) of Example 2.1.6, the associated quadratic rewriting system (S, R) contains one rule ts → st for all s, t in S with t > s. By Proposition 3.2.1 (i), this rewriting system is normalising and confluent. Proposition 3.2.1(i) can be declined to account for a neutral element and the termination properties of the corresponding rewriting systems are related. Proposition 3.2.5. (i) If (S, N ) is a normalisation mod e for a monoid M , then we obtain a reduced, normalising and confluent rewriting system (S e , R e ) presenting M by putting

(3.2.6) R e = {s|t → π e (N (s|t)) | s, t ∈ S e , s|t = N (s|t)}.
(ii) If the rewriting system (S, R) of (3.2.2) terminates, then so does (S e , R e ).

Proof. (i) Similar to Proposition 3.2.1(i).

(ii) If w → Re w ′ holds for S e -words w, w ′ , then, by definition, there exists a position i satisfying w ′ = π e (N i (w)). Thus, there exists a sequence of positions

u = i 1 | ••• |i p satisfying N u (N i (w)) = w ′ |e m for
some m, and where each N ij acts according to a rule e|s → s|e. Hence, each sequence

w 0 → Re w 1 → Re ••• → Re w ℓ in S * e lifts to a sequence w 0 → R w ′ 0 → * R w 1 |e m1 → R w ′ 1 |e m1 → * R w 2 |e m1+m2 → * R ••• → * R w ℓ |e m1+ ••• +m ℓ in S * . So, if (S e ,
R e ) does not terminate, neither does (S, R).

3.3.

The class of a quadratic normalisation. By definition, if (S, N ) is a quadratic normalisation and w is an S-word, then N (w) is obtained by successively applying the restriction N of N to various length-two factors. We shall now investigate the possibilities and introduce a parameter, called the class, evaluating the complexity of the procedure for length-three S-words.

For such a w, there must exist a finite sequence u of positions 1 and 2, such that, with the convention of Notation 3.1.1, N (w) is equal to N u (w). As N is idempotent, repeating 1 or 2 in the sequence u is useless, and it is enough to consider alternating words u of the form 121... or 212..., omitting the separators to make reading easier. For m 0, we write 121...[m] for the alternating word 121... of length m, and similarly for 212... [m]. So, for instance, N 212... [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] will stand for N 2121 , that is, for the composition of N 2 , N 1 , N 2 , and N 1 with N 2 applied first. According to the above discussion, if (S, N ) is a quadratic normalisation, then, for every length-three S-word w, there exists m such that N (w) is N 121...[m] (w) or N 212...[m] (w). Definition 3.3.1. For c a natural number, we say that a quadratic normalisation (S, N ) is of left-class c if N (w) = N 121...[c] (w) holds for every w in S [3] . Symmetrically, we say that (S, N ) is of right-class c if N (w) = N 212...[c] (w) holds for every w in S [3] . We say that (S, N ) is of class (c, c ′ ) if it is of left-class c and right-class c ′ .

Example 3.3.2. Let (S, N ) be the lexicographic normalisation for N S of Example 2.1.6. For #S = 1, there is only one length-three S-word, which is N -normal, so (S, N ) is of class (0, 0). Assume now #S 2. Then, one checks that, for all r, s, t in S, the words N 121 (r|s|t) and N 212 (r|s|t) are N -normal (and equal), so (S, N ) is of class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. On the other hand, assuming a < b, we find N 12 (bba) = bab and N 21 (baa) = aba, so (S, N ) is neither of left-class 2 nor of right-class 2.

To give another example, consider S = {a, b} and N defined by N (w) = a w if w contains an even number of letters b, and N (w) = a w -1 b otherwise. One checks that (S, N ) is a quadratic normalisation for the monoid a, b | ab = ba, a 2 = b 2 + . Then, a case-by-case checking on S [3] shows that (S, N ) is of class (2, 3), but neither of left-class 1 nor of right-class 2, as shows the worst-case example baa (

N 2 -→ baa ) N 1 -→ aba N 2 -→ aab.
The following observation, already implicit in the above example, will be crucial. (ii) Assume that (S, N ) is of left-class c. Then (i) implies N (w) = N 121...[c+1] (w) for every w in S [3] , so (S, N ) is of left-class c + 1 as well and, from there, it is of left-class c ′ for every c ′ c. For w in S [3] , the assumption and ( 2 The assumption that (S, N ) is quadratic implies, for every w in S [3] , the existence of a smallest finite number c w satisfying N (w) = N 121...[cw] (w). If S is finite, the supremum of all numbers c w for w in S [3] is finite, and Lemma 3.3.3 (i) implies that c is the minimal left-class of (S, N ).

The class of a normalisation (S, N ) can be characterised in terms of algebraic relations exclusively involving the map N . Proof. Assume that (S, N ) is of left-class c. For every w in S [3] , Lemma 3. ) and let w belong to S [3] . If c is odd, we obtain

N 1 (N 121...[c] (w)) = N 1 (N 1 (N 121...[c-1] (w))) = N 121...[c] (w),
since N is idempotent, and, by (3.3.6),

N 2 (N 121...[c] (w)) = N 121...[c+1] (w) = N 121...[c] (w).
If c is even, a symmetric argument gives the same values. So, in all cases, the S-word N 121...[c] (w) is invariant both under N 1 and N 2 , hence it is N -normal. As this holds for every w in S [3] , we conclude that (S, N ) is of left-class c. As this holds for every w in S [3] , (3.3.6) is satisfied, so, by (i), (S, N ) is of left-class c. A symmetric argument implies that (S, N ) is of right-class c.

The following example shows that the minimal left-class of a quadratic normalisation can be an arbitrarily high integer.

Example 3.3.8. For n 2, let S n = {a, b 1 , ..., b n } and R n consist of the rules ab i → ab i+1 for i < n odd and b i a → b i+1 a for i < n even. Then the rewriting system (S n , R n ) is convergent: termination is given by comparison of the number of b 1 , then of b 2 , then of b 3 , etc.; confluence is obtained by observing that, for every minimal overlapping application of rules b i ab j → Rn b i+1 ab j and b i ab j → Rn b i ab j+1 , we have b i+1 ab j → Rn b i+1 ab j+1 and b i ab j → Rn b i+1 ab j+1 . Let (S n , N n ) be the associated quadratic normalisation as defined in Proposition 3.2.1. For n 3, the minimal class of (S n , N n ) is (n -1, n): length-three words that do not begin and finish with a are R n -normal or become R n -normal in one step, and the reduction of ab 1 a looks like

ab 1 a ( N 2 -→ ab 1 a ) N 1 -→ ab 2 a N 2 -→ ab 3 a N 1 -→ ••• N - -→ ab n a,
implying that the minimal left-class is n -1, and the minimal right-class is n.

The next example shows that the minimal left-class can be ∞. (Putting n = ∞ in Example 3.3.8 provides a non-normalising system: ab 1 a has no normal form.) Example 3.3.9. For n 2, let S n = {a 0 , ..., a n } and R n consist of the rules

a i a j → a ⌊ i+j 2 ⌋ a ⌈ i+j 2 ⌉
for i > j.

The rewriting system (S n , R n ) is convergent. Let (S n , N n ) be the associated quadratic normalisation. As in Example 2.1.6, the N n -normal words are the lexicographically non-decreasing ones with respect to a 1 < ••• < a n . Then the minimal class of (S n , N n ) is (3+⌊log 2 n⌋, 3+⌊log 2 n⌋). Indeed, for 2 p n < 2 p+1 , the worst case for the left-class is attained by a 2 p a 2 p a 0 : putting i = ⌊2 p+1 /3⌋, the latter S n -word reduces to a i a i a i+1 (even p) or a i a i+1 a i+1 (odd p) in p + 3 steps. Moreover, if we define S ∞ to be the infinite set {a 0 , a 1 , ...} and N ∞ associated as above, (S ∞ , N ∞ ) is a quadratic normalisation with minimal class (∞, ∞) as, for every p, the reduction of a 2 p a 2 p a 0 requires p + 3 steps.

3.4.

The p-class. We now consider the normalisation of length-p words for p 4. If (S, N ) is a quadratic normalisation, then, by definition, one can transform a length-p word w into N (w) by applying a finite number of elementary maps N i with 1 i < p. Contrary to the case p = 3, there may exist many ways of composing these maps for p 4: for instance, one can consider the left strategy consisting in always normalising the leftmost unreduced length-two factor of the current word, but this choice is arbitrary. Writing N [p] for the restriction of N to S-words of length p, more canonical decompositions arise when one expresses N [4] in terms of N [3] and, more generally, N [p] in terms of N [p-1] . Then the situation is similar to 3 vs. 2, and a natural notion of p-class appears. The N -normality of S-words can be characterised in terms of N -normality of their length-p factors, with a straightforward proof: Lemma 3.4.3. If (S, N ) is a quadratic normalisation, then, for p 2, an S-word w with w p is N -normal if, and only if, every length-p factor of w is.

All properties of the 3-class extend to the p-class for p 3. In particular, when it is not (∞, ∞), the minimal p-class must be a pair of the form (c, c ′ ) with |c -c ′ | 1, and we have the following counterpart of Proposition 3.3.5, with a similar proof:

Quadratic normalisations of class (4, 3)

Example 3.4.7 shows that having left-class or right-class c does not say much about normalisation of words of length four and higher: an upper bound on the complexity of normalisation for length-three words implies no upper bound on the complexity of normalisation for longer words. We observe below that such a phenomenon is impossible when the class is small, namely when the class is [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] or (4, 3). Our proof is based on an argument borrowed from [START_REF] Dehornoy | Foundations of Garside Theory[END_REF], involving a diagrammatic approach called the domino rule. The results for classes [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] and (4, 3) are entirely similar; the latter is chosen here in view of the connection with Garside normalisation in Section 6.

The section comprises three parts. First, the domino rule is introduced in Subsection 4.1. Next, we establish a general formula for normalisation of long words when some domino rule is valid in Subsection 4.2. Finally, we show in Subsection 4.3 how standard braid arguments can be used to provide a complete axiomatisation of class (4, 3) normalisation. We shall now translate these conditions into a diagrammatic rule.

Definition 4.1.2. Assume that S is a set and φ is a map from S [2] to itself. We say that the domino rule is valid for φ if, if, for all s 1 , s 2 , s ′ 1 , s ′ 2 , t 0 , t 1 , t 2 in S satisfying s ′ 1 |t 1 = φ(t 0 , s 1 ) and s ′ 2 |t 2 = φ(t 1 |s 2 ), the assumption that s 1 |s 2 is φ-invariant implies that s ′ 1 |s ′ 2 is φ-invariant as well.

The domino rule of Definition 4.1.2 becomes more understandable when illustrated in a diagram. To this end, we associate with every element s of the considered set S an s-labeled arrow, and use concatenation of arrows for the concatenation of elements (note that this amounts to viewing S * as a category).

Let us indicate that a word s|t of S [2] is φ-invariant-hence N -normal when φ is the map N associated with a normalisation (S, N )-with a small arc, as in s t . Then, in the situation when s ′ |t ′ = φ(s|t) holds, we draw a square diagram as on the right.

s t s ′ t ′
With such conventions, the domino rule for φ corresponds to the diagram on the right: whenever the two squares are commutative and the three pairs of edges connected with small arcs are φ-invariant, then so is the fourth pair indicated with a dotted arc.

s 1 s 2 s ′ 1 s ′ 2 t
) = N 12 (t 0 |s 1 |s 2 ) = N 2 (s ′ 1 |t 1 |s 2 ) = s ′ 1 |s ′ 2 |t 2 . So s ′ 1 |s ′ 2 |t 2 is N -normal, hence so is s ′ 1 |s ′ 2 ,
and the domino rule is valid for N .

Conversely, assume that the domino rule is valid for N . Let t 0 |r 1 |r 2 be an arbitrary word in S [3] . Put

s 1 |s 2 = N (r 1 |r 2 ), s ′ 1 |t 1 = N (t 0 |s 1 ), and s ′ 2 |t 2 = N (t 1 |s 2 ). Then s ′ 2 |t 2 is N -normal by construction, and s ′ 1 |s ′ 2 is N -normal by the domino rule, so s ′ 1 |s ′ 2 |t 2 is N -normal.
Hence we have N (w) = N 212 (w) for every w in S [3] , and (S, N ) is of right-class 3.

4.2.

Normalising long words. We shall now show that, is (S, N ) is a normalisation map of class (4, 3), there exists a simple formula for the normalisation of arbitrarily long words. Notation 4.2.1. Starting from δ 1 = ε (the empty sequence) and using sh for the shift mapping that increases every entry by 1, we inductively define a finite sequence of positive integers δ p by (4.2.2)

δ p = sh(δ p-1 )|1|2| ••• |p -2|p -1 for p 1.
Thus we find, omitting the separation symbol,

δ 2 = 1, δ 3 = 212, δ 4 = 323123, δ 5 = 4342341234, etc.
Proposition 4.2.3. Assume that (S, N ) is a quadratic normalisation of class (4, 3). Then, for every p 1 and every length-p word w, we have

(4.2.4) N (w) = N δp (w).
So there is a universal recipe, prescribed by the sequence of positions δ p , for normalising every word of length p. We begin with a preparatory result. Lemma 4.2.5. If (S, N ) is a quadratic normalisation and the domino rule is valid for N , then, for every t in S and every N -normal S-word s 1 | ••• |s q , we have

(4.2.6) N (t|s 1 | ••• |s q ) = N 12 ••• (q-1)q (t|s 1 | ••• |s q ).
Proof. For q = 1, (4.2.6) reduces to N (t|s 1 ) = N (t|s 1 ). Assume q 2. Put t 0 = t and inductively define s ′ i and t i by s ′ i |t i = N (t i-1 |s i ) for i = 1, ..., q (see Figure 1). Then, by definition, we have

s ′ 1 | ••• |s ′ q |t q = N 12 ••• (q-1)q (t|s 1 | ••• |s q )
, so, in order to establish (4.2.6), it suffices to show that the word s ′ 1 | ••• |s ′ q |t q is N -normal. Now, for i = 1, ..., q -1, the assumption that s i |s i+1 is N -normal and the validity of the domino rule imply that s ′ i |s ′ i+1 is N -normal as well. Finally, s ′ q |t q is N -normal by construction. Hence, every length-two factor of s ′ 1 | ••• |s ′ q |t q is N -normal and, therefore, the latter is N -normal.

s 1 s 2 s q s ′ 1 s ′ 2 s ′ q t q t = t 0 t 1 t 2 t q-1 t q Figure 1.
Left-multiplying a normal word by an element of S: the domino rule guarantees that the upper row is normal whenever the lower row is. The diagram shows, in particular, that the monoid presented by (S, N ) satisfies the 2-Fellow Traveler Property with respect to left-multiplication [START_REF] Hoffmann | A geometric characterization of automatic semigroups[END_REF].

Proof of Proposition 4.2.3. By Lemma 4.1.3, the domino rule is valid for N , hence Lemma 4.2.5 applies. We prove (4.2.4) using induction on p. For p 2 , the result is immediate. Assume p 3 and let w = 2). By induction hypothesis, the word

s 1 |•••|s p belong to S [p] . Put (4.2.7) s ′ 2 |•••|s ′ p := N δp-1 (s 2 |•••|s p ) (see Figure
s ′ 2 |•••|s ′ p is N -normal.
On the other hand, by definition of position shifting, (4.2.7) implies (4.2.8)

s 1 |s ′ 2 |•••|s ′ p = N sh(δp-1) (s 1 |s 2 |•••|s p ). Then, as s ′ 2 |•••|s ′ p-1 is N -normal and s 1 belongs to S, Lemma 4.2.5 implies N (s 1 |s ′ 2 |•••|s ′ p ) = N 12 ••• (p-1) (s 1 |s ′ 2 |•••|s ′ p )
, whence, owing to the inductive definition of δ p , (4.2.9)

N (s 1 |s ′ 2 |•••|s ′ p ) = N 12 ••• (p-1) • N sh(δp-1) (s 1 |s 2 |•••|s p ) = N δp (s 1 |s 2 |•••|s p ). Owing to (2.1.4), (4.2.8) implies that N (s 1 |s 2 |•••|s p ) and N (s 1 |s ′ 2 |•••|s ′ p ) are equal.
Merging with (4.2.9), we deduce N (s

1 |s 2 |•••|s p ) = N δp (s 1 |s 2 |•••|s p ).
The inductive normalisation process described in Proposition 4.2.3 and Figure 2 amounts to using the map N to construct a triangular grid as shown in Figure 3. . We shall show that N (w) is equal to

s 1 s 2 s p s 1 s ′ 2 s ′ p s 1 s ′′ 1 s ′′ p-
|•••|s ′ p into s ′′ 1 |•••|s ′′ p , which is N -normal by Lemma 4.2.5. s ′ 1 s ′ 2 s ′ 3 s ′
N [p-1]
212 (w) by checking that successively applying

N [p-1] 2 , N [p-1] 1
, and

N [p-1] 2 to w leads to an N -normal word. First, let s ′ 2 | ••• |s ′ p = N (s 2 | ••• |s p ). We have (4.2.11) N [p-1] 2 (w) = s 1 |s ′ 2 | ••• |s ′ p . As s ′ 2 | ••• |s ′ p is N -normal, Lemma 4.2.5 implies N (w) = N 12 ••• (p-1) (s 1 |s ′ 2 | ••• |s ′ p ). Now, put t 0 = s 1 and, inductively, s ′′ i |t i = N (t i-1 |s ′ i+1 ) for i = 1, ..., p -1. As s ′ 2 | ••• |s ′ p-1 is N - normal, Lemma 4.2.5 implies that s ′′ 1 | ••• |s ′′ p-2 |t p-1 is N -normal, so we have N (s 1 |s ′ 2 | ••• |s ′ p-1 ) = s ′′ 1 | ••• |s ′′ p-2 |t p-1 , whence (4.2.12) N [p-1] 1 (s 1 |s ′ 2 | ••• |s ′ p ) = s ′′ 1 | ••• |s ′′ p-2 |t p-1 |s ′ p . ≡ p -1| ••• |3|2|1|sh 2 (δ p-2 ))|2| ••• |p -1 by i|1 ≡ 1|i for i = sh 2 (j), = p -1| ••• |3|2|1|sh(sh(δ p-2 ))|1| ••• |p -2) = p -1| ••• |3|2|1|sh(δ p-1 )
by definition of δ p-1 .

Next, for p = 2, (4.3.8) reads 2|1|2|1 ≡ 2|1|2, which is valid. For p 3, we find

p| ••• |2|1|p| ••• |2|1 ≡ p| ••• |2|p| ••• |3|1|2|1 by 1|i ≡ i|1 for i 3, = sh(p -1| ••• |1|p -1| ••• |2)|1|2|1 ≡ sh(p -1| ••• |1|p -1| ••• |2|1)|1|2|1 by induction hypothesis, = p| ••• |2|p| ••• |3|2|1|2|1 ≡ p| ••• |2|p| ••• |3|2|1|2 by definition of ≡, = sh(p -1| ••• |1|p -1| ••• |2|1)|1|2 ≡ sh(p -1| ••• |1|p -1| ••• |2)|1|2 by induction hypothesis, = p| ••• |2|p| ••• |3|1|2 ≡ p| ••• |2|1|p| ••• |3|2 by i|1 ≡ 1|i for i 3.
The argument for (4.3.9) is symmetric.

Lemma 4.3.10. The following relations are valid for every p 2 and 1 i < p:

(4.3.11) δ p ≡ δ p |i ≡ i|δ p .
Proof. We use induction on p 2. For p = 2, the only case to consider is i = 1, and (4.

δ p |1 ≡ p -1| ••• |2|1|p -1| ••• |2|sh 2 (δ p-2 )|1 by (4.3.7) twice, ≡ p -1| ••• |2|1|p -1| ••• |2|1|sh 2 (δ p-2 ) by i|1 ≡ 1|i for i 3, ≡ p -1| ••• |2|1|p -1| ••• |2|sh 2 (δ p-2 ) by (4.3.8), ≡ p -1| ••• |2|1|sh(δ p-1 ) ≡ δ p by (4.3.7) twice,
and, for 2 i < p, using (4.3.7) and the induction hypothesis, we find

δ p |i ≡ p -1| ••• |1|sh(δ p-1 )|i = p -1| ••• |1|sh(δ p-1 |i -1) ≡ p -1| ••• |1|sh(δ p-1 ) ≡ δ p .
The argument for i|δ p ≡ δ p is symmetric, with the definition of δ p and (4.3.9) replacing (4.3.7) and (4.3.8).

Proof of Proposition 4.3.1. Assume that φ is idempotent and satisfies (4.3.2). Lemmas 4.3.5 and 4.3.11 imply, for all p 3 and every w in S [p] , the equalities

(4.3.12) φ * (φ i (w)) = φ * (w) and φ i (φ * (w)) = φ * (w) for i with 1 i < p.
Let u, v, w be S-words with respective lengths m, n, p. Then we find

φ * (u|φ * (w)|v) = φ δm+n+p (u|φ δp (w)|v) = φ δm+n+p (φ sh m (δp) (u|w|v)).
The map φ sh m (δp) is a composite of maps φ i with m + 1 i m + p -1, so Lemma 4.3.10 implies φ * (u|φ * (w)|v) = φ δm+n+p (u|w|v) = φ * (u|w|v), and we deduce that (S, φ * ) satisfies (2.1.4). As it also satisfies (2.1.2) and (2.1.3) by the definition of φ * , it is a normalisation.

The following example shows that the axiomatisation of class (4, 3) normalisations provided by Proposition 4.3.1 does not extend to higher classes. ∞ satisfies the relation φ 12121 = φ 21212 , but no quadratic normalisation (S ∞ , N ) satisfies φ = N . Indeed, no S ∞ -word that can be reached from ab 1 c 1 a by successive applications of φ on length-two factors is normal.

Class and termination

By Proposition 3.2.1, a quadratic normalisation (S, N ) yields a reduced quadratic rewriting system (S, R) that is normalising and confluent. This however does not rule out the possible existence of infinite rewriting sequences, which we investigate here.

The section comprises three parts. We first consider the case of class (3, 3) and prove an easy convergence result (Subsection 5.1). Next, the case of classes [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] and (4, 3) is investigated in Subsection 5.2, where the not-so-easy convergence result stated as Theorem B is established. Finally, we show in Subsection 5.3 that the previous result is optimal by constructing a nonconvergent example in class (4, 4). [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. We first consider the case of quadratic normalisations of class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF], and we use an argument of finiteness on symmetric groups to prove: [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF], then the associated rewriting system (S, R) is convergent, and so is (S e , R e ) if e is an N -neutral element of S. More precisely, every rewriting sequence from a length-p word has length at most p(p -1)/2.

Termination in class

Proposition 5.1.1. If (S, N ) is a quadratic normalisation of class
Proof. Assume that w 0 , ..., w ℓ are S-words satisfying w k → R w k+1 for 0 k < ℓ. Let p be the common length of the S-words w k . By assumption, for every k 1, we have

w k = N i k (w k-1 ) for some 1 i k < p, with w k = w k-1 .
Let us observe, by induction on k, that u = i 1 | ••• |i k is reduced in the sense of Coxeter theory, that is, it is a minimal-length representative of the associated element of the symmetric group S p . For k = 0, the result is true as the empty word is reduced. Assume k 1, and write u = u ′ |i. By induction hypothesis, u ′ is reduced. If u ′ |i is not reduced, then, by the exchange lemma for S p , see [START_REF] Bjorner | Combinatorics of Coxeter Groups[END_REF], there exists a sequence of positions u ′′ such that u ′ is equivalent to u ′′ |i modulo the braid relations. Now, by Proposition 3.3.5, the assumption that (S, N ) is of class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] implies N 121 = N 212 and, from there, the equivalence of u ′ and u ′′ |i modulo the braid relations implies

N u ′ = N u ′′ |i . Putting w ′ = N u ′′ (w 0 ), we obtain w k-1 = N i (w ′ ) and, since N is idempotent, w k = N i (N i (w ′ )) = N i (w ′ ) = w k-1 , which contradicts w k-1 → R w k . So u must be reduced.
Now, it is well-known that the length ℓ of a reduced word representing an element of S p is bounded above by p(p -1)/2, for instance because ℓ is the number of inversions of the permutation represented by u. So (S, R) terminates and, by Proposition 3.2.5, so does (S e , R e ) if e is an N -neutral element in S.

Remark. The bound p(p -1)/2 in Proposition 5.1.1 is sharp, since, for the lexicographic normalisation (S,

N ) of Example 2.1.6, normalising a p | ••• |a 1 with a 1 < ••• < a p actually requires p(p -1)/2 steps.
Proposition 5.1.1 applies to the example of plactic monoids, described thereafter. Those monoids have known normalisations that fit into our setting of quadratic normalisations, and were among the original motivations for extending the framework of Garside normalisation to the current one.

Example 5.1.2. If X is a totally ordered finite set, the plactic monoid over X is the monoid P X generated by X and subject to xzy = zxy, for x y < z, and yxz = yzx, for x < y z. We refer to [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF] for a recent reference on the following facts. The monoid P X is also generated by the family S of columns over X (the strictly decreasing products of elements of X). A pair c|c ′ of columns is normal if c c ′ holds and, for every 1 k c ′ , the kth element of c is at most the one of c ′ . Every equivalence class of X-words contains a unique tableau (a product c 1 •••c n of columns such that each c i |c i+1 is normal), with minimal length in terms of columns: thus, mapping a S-word to the unique corresponding tableau defines a geodesic normal form nf on (P X , S e ), where e denotes the empty column. We consider the normalisation (S e , N ) associated to nf, which satisfies (3.1.3) by the definition of tableaux. Moreover, for every S-word w, the tableau nf(w) can be computed from any S-word w by Schensted's insertion algorithm, progressively replacing each pair c|c ′ of subsequent columns of w by nf(c|c ′ ), which is a tableau with one or two columns. So, the normalisation (S e , N ) also satisfies (3.1.4), so that it is quadratic, and, when X contains at least two elements, it is of minimal class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] as testified by the computations of [3, § §4.2-4.4]. By Proposition 5.1.1, we recover [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF]Th. 3.4]: the rewriting system (S, R) with R = {c|c ′ → nf(c|c ′ ) | c, c ′ ∈ S} is finite, convergent and it presents P X . A similar argument leads to a (nonfinite) convergent quadratic presentation of P X in terms of rows, which are nondecreasing products of elements of X. The proof that the class is [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. We now consider the case of class (4, 3) and establish the general termination result stated as Theorem B: Proposition 5.2.1. If (S, N ) is a quadratic normalisation of class (4, 3), then the associated rewriting system (S, R) is convergent, and so is (S e , R e ) if e is an N -neutral element of S. More precisely, every rewriting sequence from a length-p word has length at most 2 p -p -1.

is given in [3, § §3.2-3.4].

Termination in class

Proposition 5.2.1 subsumes Proposition 5.1.1. But its proof resorts to different arguments, since Krammer's monoid M p , see [START_REF] Krammer | An asymmetric generalisation of Artin monoids[END_REF], which should replace here the finite quotient-monoid B + p /{σ 2 i = σ i | 1 i < p}, with 121 = 212 substituted with 121 = 2121, is infinite. Instead, we analyse N -normalisation directly to show that no infinite rewriting sequence may exist because one inevitably proceeds to the normal form.

Proof. Let F (p) denote the maximal length of sequences w 0 → R w 1 → R ••• → R w ℓ of S-words of length p, possibly ∞. We prove the inequality F (p) 2 p -p -1 using induction on p 2. For p = 2, the inequality F (p) 1 holds, since N is idempotent. We now assume p 3 and consider a sequence -→ w = (w 0 , ..., w ℓ ) of length-p words satisfying w k → R w k+1 for 0 k < ℓ. We shall distinguish several types of rewriting steps in the sequence -→ w , in connection with Proposition 4.2.3 and the triangular grid diagram of Figure 3. The latter corresponds to an optimal strategy, which needs not be the case for -→ w , but we shall explain how to enrich each word w k into a word w k by attaching with each letter of w a direction, either horizontal or vertical. We define S as S ∐ S, where S is a copy of S with an element s for each s in S, and we take the convention that s means "vertical s" and s means "horizontal s": this associates with every S-word w a path in a triangular grid by starting from the top-left corner and attaching to the successive letters of w horizontal left-to-right edges and vertical top-to-down edges.

We construct the S-words w k inductively, in such a way that (5.2.2) for every length-two factor s|t or s|t of w k , the S-word s|t is N -normal.

First, for

w 0 = s 1 | ••• |s p , we put w 0 = s 1 | ••• |s p-1 |s p .
Then w 0 satisfies (5.2.2) by default, and (the path associated with) w 0 consists of w 0 drawn vertically, except the last letter, which is drawn horizontally. Assume that w k-1 has been defined, it satisfies (5.2.2), and w k = N i (w k-1 ) holds. Let s and t be the letters of w k-1 in positions i and i+1, and s ′ |t ′ = N (s|t). We look at the directions of the letters of w k-1 in positions i and i + 1. The assumption w k-1 → R w k implies that s|t is not N -normal. By (5.2.2), this excludes the directions s|t and s|t. So only two cases are possible.

In the case of a VH-step, meaning a vertical letter followed by a horizontal one, we define w k to be obtained from w k-1 by replacing, at position i, the factor s|t with s ′ |t ′ when t is not the last letter of w k-1 , and by s ′ |t ′ otherwise, which corresponds to replacing s t with s ′ t ′ or s ′ t ′ respectively. In both cases, the length-two factor of w k starting at position i is thus N -normal, so (5.2.2) is satisfied at this position. The only other position where (5.2.2) might fail is i -1, when the corresponding letter of w k is horizontal, since, otherwise, (5.2.2) requires nothing on the factor. Now, going from w k-1 to w k replaces with .

But, by construction, the pattern necessarily comes from an earlier diagram , in which the pairs indicated with small arcs are N -normal by induction hypothesis. Hence, going to w k means going to and the domino rule precisely implies that the top two horizontal edges form an N -normal word. So w k satisfies (5.2.2).

In the case of a VV-step (two vertical letters), we define w k to be obtained from w k-1 by replacing, at position i, the factor s|t with s ′ |t ′ . As the shape of w k is the same as the one of w k-1 , we only have to check (5.2.2) for the length-two factor at position i -1, and only when its first letter is horizontal, that is, one goes from r s t to r s ′ t ′ . But, by construction, the original pattern in w k-1 arises from an earlier pattern r s t , so that, when s|t is replaced by

s ′ |t ′ , the domino rule implies that r|s ′ is N -normal, as the diagram r s t s ′ t ′ witnesses.
The construction of w 0 , ..., w ℓ is complete, and we now count how many VH-steps and VVsteps can occur in -→ w . First, each S-word w k is associated with a path in the triangular grid diagram of Figure 3 and each VH-step causes this path to cross one square in the grid. As the latter contains p(p -1)/2 squares, we deduce that there are at most p(p -1)/2 VH-steps in -→ w .

We turn to VV-steps, partitioning them into several subtypes according to where they occur: we say that a VV-step is a VV j -step if it is located on the jth column, that is, it replaces a vertical factor s|t of w k that is preceded by j -1 horizontal letters. Now we fix j with 1 j < p and count the VV j -steps that can occur in -→ w . For 1 i p -j, let s i,k be the letter that vertically occurs at the ith position in the jth column in w k , if it exists. For a given value of i, define s i,+ to be s i,k where k is minimal such that s i,k exists (if any) and, symmetrically, let s i,-be s i,k where k is maximal such that s i,k exists (if any). For each k, if s i,+ is defined for a i, if s i,k is defined for b i c, and if s i,-is defined for i d, we put

v k = s a,+ | ••• |s b-1,+ |s b,k | ••• |s c,k |s c+1,-| ••• |s d,-.
So v k is the factor of w k forming the jth column of w k , preceded by the letters that are the first to appear in positions a, ..., b -1 in column j in w k+1 , ..., w ℓ , and followed by the last letters to appear in positions c+1, ..., d in column j in w 0 , ..., w k-1 . If one goes from w k-1 to w k by a VHstep or a VV j ′ -step with j ′ = j, then we have v k = v k-1 : indeed, either the jth columns of w k-1 and w k are equal, or a VH-step normalises the last letter s c,k-1 of the jth column of w k-1 with the subsequent horizontal letter, or the first letter s b,k-1 of the jth column of w k-1 with the previous horizontal letter; and, in the case of the last letter (the other one being symmetric), v k is v k-1 with s c,k replaced by s c,-, hence unchanged by definition of s c,-. Otherwise, if one goes from w k-1 to w k by a VV j -step, then v k-1 → R v k holds. As, by construction, the length of the S-word v k is at most p -j, we conclude that the number of VV j -steps in -→ w is at most possible. For instance, we find D(ab ′ db ′′ cdb ′ ab ′ ) = ab ′ |d|b ′′ cd|b ′ |ab ′ . Now, we observe that π is compatible with all rules of R and, moreover, every rule acts inside a special factor. Hence, if we have D(w) = w 1 | ••• |w m , then the words w ′ for which w → R w ′ holds are those words w

′ satisfying D(w ′ ) = w ′ 1 | ••• |w ′ m with w i → R w ′ i for each i.
Consequently, in order to prove that (S, R) is normalising and confluent, it suffices to prove it for the factors of the D-decomposition, that is, for special words. We review the ten types. First, an S-word w of type a, b, c, d, ab, bc, or cd is R-normal form, or we have w → R w ′ for some R-normal S-word w ′ . Next, there are nine S-words of type abc, and the corresponding restriction of → R is (where framed S-words are the R-normal ones)

abc ′ ab ′ c ′ abc ab ′ c ab ′′ c ′′ abc ′′ ab ′ c ′′ ab ′′ c ab ′′ c ′
The graph for bcd is entirely similar. Finally, for the type abcd, we find:

abcd ab ′ cd abc ′ d ab ′′ c ′′ d ab ′ c ′ d ab ′′ cd ab ′′ c ′ d abc ′′ d ab ′ c ′′ d
Thus, for each type, the corresponding connected component of the relation → R contains exactly one R-normal S-word, which is reachable from any other S-word of the component. It follows that (S, R) is normalising and confluent. Moreover, the inspection of the normalisation of length-three S-words shows that the normalisation (S, N ) associated with R is of minimal class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF].

By contrast, the following example shows that terminating rewriting systems may also arise when the minimal class is at least (4, 4).

Example 5.3.2. For a totally ordered finite set X, the Chinese monoid over X is the monoid C X generated by X and submitted to the relations zyx = zxy = yzx, for x y z [START_REF] Cassaigne | The Chinese monoid[END_REF]. Assume that X has three elements and denote by S the eight-element set obtained from X by adjoining the empty word e, the three words yx for x < y, and yy if y is the middle element of X (neither the minimal one nor the maximal one). The following twelve rules are derivable from the defining relations of C X : the nine rules y|x → yx, y|yx → yx|y, yx|x → x|yx for x < y; the two rules y|zx → zx|y and z|yx → zx|y for x < y < z; and y|y → yy if y is the middle element of X. This reduced rewriting system terminates (using the weighted right-lexicographic order generated by x < yx for x y and zx < y for x < y) and, after application of Knuth-Bendix completion, it yields a convergent rewriting system (S e , R e ) with 22 rules presenting C X . After homogenisation, we obtain a reduced, quadratic and convergent rewriting system (S, R), whose corresponding quadratic normalisation is of class (4, 4), the worst case being reached on z|yy|y if y is the middle element and z > y holds. Similar convergent quadratic presentations also exist when X has four or five elements (to be compared with the nonquadratic ones of [START_REF] Cain | Rewriting systems and biautomatic structures for Chinese, hypoplactic, and sylvester monoids[END_REF]Th. 3.3]), the class being (5, 4) in both cases.

Garside normalisation

In this last section, we investigate the connection between our current general framework and Garside families. It turns out that the latter provide natural examples of quadratic normalisations of class (4, 3) and that, conversely, a normalisation of class (4, 3) comes from a Garside family if, and only if, it satisfies some explicit additional condition called left-weightedness.

The section is organised as follows. In Subsection 6.1, we briefly recall the basic definitions involving Garside families and the associated normal forms. In Subsection 6.2, we introduce the notion of a left-weighted normalisation and establish the above mentioned connection, which is Theorem C of the introduction. Finally, in Subsection 6.3, we mention a few further consequences.

6.1. Greedy decompositions. Hereafter, if M is a left-cancellative monoid, we denote by the associated left-divisibility relation, defined by f g if f g ′ = g holds in M for some g ′ . The starting point is the notion of an S-normal word. ∀s∈S ∀f ∈M (s f s 1 s 2 ⇒ s f s 1 ).

An S-word s

1 | ••• |s p is called S-normal if s i |s i+1 is S-normal for every i.
The intuition underlying condition (6.1.2) is that s 1 already contains as much of S as it can, a greediness condition; note that we do not only consider the left-divisors of s 1 s 2 that lie in S, but, more generally, all elements of S that left-divide f s 1 s 2 .

Then the notion of a Garside family arises naturally. Here we state the definition in a restricted case fitting our current framework (see [START_REF] Dehornoy | Foundations of Garside Theory[END_REF] for the general case): Definition 6.1.3. Assume that M is a monoid with no nontrivial invertible elements and S is a subset of M that contains 1. We say that S is a Garside family in M if every element g of M has an S-normal decomposition, that is, there exists an S-normal S-word s

1 | ••• |s p satisfying s 1 •••s p = g.
Example 6.1.4. The seminal example of a Garside family is the family of all simple braids. Let B n be Artin's n-strand braid group and B + n be the submonoid of B n consisting of all braids that can be represented by a diagram in which all crossings have a positive orientation (see for instance [START_REF] Garside | The braid group and other groups[END_REF] or [10, Section I.1]). Then the subfamily S n of B + n consisting of those positive braids that can be represented by a diagram in which any two strands cross at most once is a Garside family in B + n . More generally, if M is an Artin-Tits monoid, that is, a monoid defined by relations of the form stst... = tsts... where both terms have the same length, and if W is the Coxeter group obtained by adding the torsion relations s 2 = 1 to the above relations, then M admits a Garside family that is a copy of W [START_REF] Dehornoy | Garside families in Artin-Tits monoids and low elements in Coxeter groups[END_REF]. When W is finite, this Garside family (which consists of the divisors of some element ∆ connected with the longest element of W ) is minimal. When W is infinite, it is not minimal, but there exists in every case a finite Garside family [START_REF] Dehornoy | Garside families in Artin-Tits monoids and low elements in Coxeter groups[END_REF]. For instance, if M is the Artin-Tits monoid of (affine) type A 2 , that is, M admits a presentation with three generators σ 1 , σ 2 , σ 3 and three relations σ i σ j σ i = σ j σ i σ j , then the associated Coxeter group is infinite, but M admits a finite Garside family S consisting of the sixteen right-divisors of the elements σ 1 σ 2 σ 3 σ 2 , σ 2 σ 3 σ 1 σ 3 , and σ 3 σ 1 σ 3 σ 1 .

It turns out that a large number of monoids admit interesting Garside families, and many results involving such families, including various practical characterisations, and the derived normalisations are now known [START_REF] Dehornoy | Foundations of Garside Theory[END_REF].

For our current approach, what counts is that Garside normalisation enters the framework of Sections 2 to 4. First, a mild discussion is in order, because the S-normal form as introduced in Definition 6.1.3 is not readily unique. Lemma 6.1.5. Assume that M is a left-cancellative monoid with no nontrivial invertible elements and S is a Garside family in M .

(i) [10, Prop. III.1.25] Call two S-words ≃-equivalent if they only differ by appending final entries 1. Then every S-word that is ≃-equivalent to an S-normal word is S-normal; conversely, any two S-normal decompositions of the same element of M are ≃-equivalent.

(ii) [10, Prop. III.1.30] Every element of M with a representative in S [p] admits an S-normal decomposition of length at most p.

Building on Lemma 6.1.5, we immediately obtain Proposition 6.1.6. Assume that M is a left-cancellative monoid with no nontrivial invertible elements and S is a Garside family of M . Then every element g of M admits a unique Snormal decomposition of minimal length, and the corresponding map is a geodesic normal form on (M, S \ {1}).

We can then apply Proposition 2.2.7, and associate with the Garside family S a normalisation (S, N ). The latter involves the generating set S \ {1} enriched with one letter representing the unit, and it is then natural to use 1 for that letter so that we simply recover S. We shall then say that (S, N ) is derived from the Garside family S. In this case, 1 is an N -neutral element by Proposition 2.2.7, and M admits the presentation (2.2.3). Here is the main observation: Proposition 6.1.7. Assume that M is a left-cancellative monoid with no nontrivial invertible elements and S is a Garside family of M . Then the normalisation (S, N ) derived from S is quadratic of class (4, 3).

Proof. That N satisfies (3.1.3) directly follows from Definition 6.1.1, since S-greedy words are defined by a condition that only involves length-two factors. For (3.1.4) The result of Proposition 6.1.7 is optimal: as the example below shows, (4, 3) is in general the minimal class. Let us mention that there is a particular class of Garside families, called bounded [START_REF] Dehornoy | Foundations of Garside Theory[END_REF]chapter VI], for which the class drops to [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF] or less. Garside monoids [START_REF] Dehornoy | Groupes de Garside[END_REF] are typical examples of the latter situation. Example 6.1.8. The normalisation derived from the finite Garside family mentioned in Example 6.1.4 for the Artin-Tits monoid of type A 2 is not of class [START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]: for instance, one finds N 121 (σ 1 |σ 1 σ 2 |σ 1 σ 3 ) = σ 1 σ 2 σ 1 |σ 2 |σ 3 , in which σ 2 |σ 3 is not normal.

6.2. Left-weighted normalisation. Definition 6.1.1 is highly non-symmetric, so we can expect that the normalisations derived from Garside families satisfy some relations capturing the specific role of the left-hand side. Definition 6.2.1. Assume that (S, N ) is a (quadratic) normalisation for a monoid M . We say that (S, N ) is left-weighted if, for all s, t, s ′ , t ′ in S, the equality s ′ |t ′ = N (s|t) implies s s ′ in M .

In other words, a normalisation (S, N ) is left-weighted if, for every s in S, the first entry of any length-two S-word N (s|t) is always a right-multiple of s in the associated monoid: normalising s|t amounts to adding something in the left entry. Lemma 6.2.2. The normalisation derived from a Garside family in a left-cancellative monoid with no nontrivial invertible element is left-weighted.

Proof. Assume that (S, N ) derives from a Garside family S. If s ′ |t ′ = N (s|t) holds, s is an element of S, and we have st = s ′ t ′ , whence s s ′ t ′ . By assumption, s ′ |t ′ is S-normal, so (6.1.2) implies s s ′ . Thus N is left-weighted.

We shall now establish that left-weightedness characterises Garside normalisation, as stated in Theorem C: Corollary 6.3.4. Every Artin-Tits monoid admits a finite quadratic convergent presentation. Example 6.3.5. In the case of a spherical Artin-Tits monoid, the elements of the corresponding Coxeter group form a finite Garside family, and Corollary 6.3.4 corresponds to [START_REF] Gaussent | Coherent presentations of Artin monoids[END_REF]Th. 3.1.3,Prop. 3.2.1]. In the nonspherical case, Corollary 6.3.4 is an improvement of the latter results, which only give an infinite convergent presentation. For instance, in type A 2 , the 16-element Garside family described in Example 6.1.4 yields a convergent rewriting system for A 2 with 15 generators and 87 relations.

( 2 .

 2 1.14) N (w) = nf(ev(w)).

Example 3 . 1 . 7 .

 317 Let S = {a, b} and N : S * → S * be defined by N (w) = w for w 1, and N (w) = a w -1 b for w 2. Then (S, N ) is a normalisation for the monoid S | ab = ba = b 2 = a 2 + . Now (3.1.3) fails, since aab, which is N -normal, contains the non N -normal factor aa. But (3.1.4) is satisfied, since a straightforward induction gives N (w) = N 1| ••• |p-1 (w) for w of length p 2. Hence (3.1.4) does not imply (3.1.3).

Proposition 3 . 1 . 8 .

 318 (i) If (S, N ) is a quadratic normalisation for a monoid M , then N is idempotent and M admits the presentation(3.1.9) S | {s|t = N (s|t) | s, t ∈ S} + ; (ii) If (S,N ) is a quadratic normalisation, then an element e of S is N -neutral if, and only if, it satisfies (3.1.10) N (e|s) = N (s|e) = s|e for every s in S.

  1.5), and because(3.1.4) implies that every relation of (2.1.5) is a consequence of finitely many relations of(3.1.4).(ii) The relations (3.1.10) are particular instances of (2.2.2), so they hold if e is N -neutral. Conversely, assume (3.1.10) and let w be an S-word.We first prove N (w|e) = N (w)|e. We have N (w|e) = N (N (w)|e) by (2.1.4). Moreover, every length-two factor of N (w)|e is N -normal. Indeed, for w 1, writing N (w) = w ′ |s with w ′ ∈ S * and s ∈ S, the length-two factors of N (w)|e are those of N (w), which are N -normal by (3.1.3), and s|e, which is N -normal by (3.1.10). Hence N (w)|e is N -normal by (3.1.3), which implies N (w|e) = N (w)|e. Now, we prove N (e|w) = N (w|e) by induction on w . The result is immediate for w = 0. Otherwise, write w = s|w ′ , with s in S and w ′ satisfying N (e|w ′ ) = N (w ′ |e). Using (2.1.4), (3.1.10) and the induction hypothesis on w ′ , we find N

Lemma 3 . 3 . 3 .

 333 Assume that (S, N ) is a quadratic normalisation. (i) If w is in S[3] , then N (w) = N 121...[c] (w) implies N (w) = N 121...[c+1] (w). (ii) If (S, N ) is of left-class c, then it is of left-class c ′ for every c ′ with c ′ c, and of right-class c ′′ for every c ′′ with c ′′ c + 1. Proof. (i) Assume N (w) = N 121...[c] (w). By (3.1.3), N (w) is invariant both under N 1 and N 2 , since it is N -normal. Hence we have N 121...[c+1] (w) = N 121...[c] (w).

  .1.4) give N (w) = N 121...[c] (N 2 (w)) = N 212...[c+1] (w). Hence (S, N ) is of right-class c + 1 and, from there, of right-class c ′′ for every c ′′ with c ′′ c + 1. Define the minimal left-class of a quadratic normalisation (S, N ) to be the smallest integer c such that (S, N ) is of left-class c, if such an integer exists, and ∞ otherwise. We introduce the symmetric notion of minimal right-class, and define the minimal class to be the pair made of the minimal left-class and the minimal right-class. Lemma 3.3.4. The minimal class of a quadratic normalisation (S, N ) is either of the form (c, c ′ ) with |c ′ -c| 1, or (∞, ∞). If S is finite, the value (∞, ∞) is excluded. Proof. If the minimal left-class of (S, N ) is a finite number c, then Lemma 3.3.3 implies that (S, N ) is of right-class c + 1; hence the minimal right-class c ′ satisfies c ′ c + 1 and, for symmetric reasons, we have c c ′ + 1, whence |c ′ -c| 1.

Proposition 3 . 3 . 5 .

 335 A quadratic normalisation (S, N ) is of left-class c if, and only if, N satisfies (3.3.6) N 121...[c] = N 121...[c+1] = N 212...[c+1] , and of class (c, c) if, and only if, N satisfies (3.3.7) N 121...[c] = N 212...[c] .

  3.3 gives N (w) = N 121...[c] (w) = N 121...[c+1] (w) = N 212...[c+1] (w), whence (3.3.6). Conversely, assume (3.3.6

  Assume that (S, N ) is of class (c, c). By (i), we have N 121...[c] = N 121...[c+1] = N 212...[c+1] and, by the symmetric counterpart of (i), we have N 212...[c] = N 212...[c+1] = N 121...[c+1] , whence (3.3.7) by merging the values. Conversely, assume (3.3.7) and let w belong to S [3] . Applying (3.3.7) to N 1 (w) gives N 121...[c] (N 1 (w)) = N 212...[c] (N 1 (w)), reducing to N 121...[c] (w) = N 121...[c+1] (w), since N 1 is idempotent. Similarly, applying (3.3.7) to N 2 (w) leads to N 212...[c+1] (w) = N 212...[c] (w). Merging the results and applying (3.3.7) to w, we deduce N 121...[c+1] (w) = N 121...[c] (w) = N 212...[c] (w) = N 212...[c+1] (w).

Definition 3 . 4 . 1 .

 341 For p 3, we say that a quadratic normalisation (S, N ) is of left-p-class c if, for every w in S[p] , we haveN (w) = N [p-1] 121...[c] . Symmetrically, we say that (S, N ) is of rightp-class c if, for every w in S [p] , we have N (w) = N [p-1] 212...[c] . We say that (S, N ) is of p-class (c, c ′ ) if it is of left-p-class c and right-p-class c ′ .Thus the left-class of Subsection 3.3 is the left-3-class, and similarly for the right-class and the class.Example 3.4.2. Consider the lexicographic normalisation (S, N ) of Example 3.3.2. We saw that, for #S 2, the minimal (3)-class is[START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF]. An easy induction shows that, for every p 4 and for every w in S[p] , the words N [p-1] 212 (w) and N [p-1] 121 (w) are lexicographically nondecreasing, hence N -normal. Thus (S, N ) is of p-class (3, 3). Then, assuming #S 2 and a < b, we find N [p-1] 12 (b p-1 a) = bab p-2 and N [p-1] 21 (ba p-1 ) = a p-2 ba, which are not N -normal. So (S, N ) is neither of left-p-class 2 nor of right-p-class 2.

Proposition 3 . 4 . 4 .Example 3 . 4 . 5 . 7 .

 3443457 A quadratic normalisation (S, N ) is of left-p-class c if, and only if, the map N[p-1] satisfies N .[c+1] , and of p-class (c, c) if, and only if, the mapN [p-1] satisfies N [p-1] 121...[c] = N [p-1] 212...[c] .The following examples show that the behaviour of the 4-class is independent from that of the 3-class: the 4-class may be larger, equal, or smaller. The normalisation (S n , N n ) of Example 3.3.8 has minimal 3-class is (n, n). However, for p 4, its minimal p-class is (2, 2). Example 3.4.6. Let S n = {a, b 1 , ..., b n } and N n be given by the rules ab i →ab i+1 for i odd and b i a→b i+1 a for i even (as in Example 3.3.8), completed with b i+1 b i → b i+1 b i+1 for i odd and b i b i+1 →b i+1 b i+1 for i even. For p 3, the minimal p-class of (S n , N n ) is (n -1, n), with the worst case realised for ab p-2 Let S n = {a, b 1 , ..., b n , c 1 , ..., c n } and N n be given by the rules ab i →ab i+1 and b i+1 c i →b i+1 c i+1 for i odd, and c i a→c i+1 a and b i c i+1 →b i+1 c i+1 for i even. Here it turns out that the minimal 3-class is (5, 5), whereas the minimal 4-class is (n -1, n). For instance, for n = 10, the worst cases are realised by N 12121 (b 4 c 2 a) = b 5 c 5 a, and N [3] 2121212121 (ab 1 c 1 a) = ab 10 c 10 a. One also observes that the minimal p-class for p 5 is (2, 2) for every n 5.

4. 1 .

 1 The domino rule. By Proposition 3.3.5, if a quadratic normalisation (S, N ) has class (4, 3), the map N satisfies (3.3.6), which, in the current case, is (4.1.1) N 212 = N 2121 = N 1212 .

3 Figure 3 .

 33 Figure 3. Normalising a length-p word in p(p -1)/2 steps, here with p = 4: according to (4.2.4), the six steps correspond to applying N δ 4 , that is, N323123. An important consequence of Proposition 4.2.3 is that, contrary to the situation of Example 3.4.7, it is impossible to have a large 4-class in class (4, 3).

Corollary 4 . 2 . 10 .

 4210 If (S, N ) is a quadratic normalisation of class (4, 3), then (S, N ) is of p-class (4, 3) for every p 3. Proof. Assume p 3, and let w = s 1 | ••• |s p lie in S [p]

3 . 11 ) then to 1 ≡

 3111 1|1, which is true by definition. Assume p = 3. For i = 1, (4.3.11) reduces to 2|1|2 ≡ 2|1|2|1 ≡ 1|2|1|2 and, for i = 2, to 2|1|2 ≡ 2|1|2|2 and 2|1|2 ≡ 2|2|1|2, which are true by the definition of ≡.Assume now p 4. For i = 1, we find

Example 4 . 3 . 13 .

 4313 Let us consider the rewriting system of Example 3.4.7 with n = ∞, that is, S ∞ = {a, b 1 , b 2 , ..., c 1 , c 2 , ...} with the rules ab i →ab i+1 and b i+1 c i →b i+1 c i+1 for i odd and c i a→c i+1 a and b i c i+1 →b i+1 c i+1 for i even. The associated map φ on S[START_REF] Bjorner | Combinatorics of Coxeter Groups[END_REF]

Definition 6 . 1 . 1 (

 611 [START_REF] Dehornoy | Foundations of Garside Theory[END_REF] Def. III.1.1]). If M is a left-cancellative monoid and S is included in M , an S-word s 1 |s 2 is called S-normal if the following condition holds: (6.1.2)

  We then put S e = S \ {e}, and write ev e for the canonical projection of S * e onto M . If (S, N ) is a normalisation for a monoid M , (2.2.2) implies that there exists at most one N -neutral element in S. Then, if e is such an element, (S, N ) is a normalisation mod e for the monoid obtained by collapsing e in M .

	Definition 2.2.1. If (S, N ) is a normalisation, an element e of S is called N -neutral if
	(2.2.2)	N (w|e) = N (e|w) = N (w)|e
	hold for every S-word w. If M is a monoid, we say that (S, N ) is a normalisation mod e for M
	if e is an N -neutral element of S and M admits the presentation
	(2.2.3)	S | {w = N (w) | w ∈ S * } ∪ {e = 1} + .
	Lemma 2.2.4. Assume that (S, N ) is a normalisation mod e for a monoid M , and let π e be
	the canonical projection from S * onto S * e .
	(i) The monoid M admits the presentation
	(2.2.5)	S e | {w = π e (N (w)) | w ∈ S * e } + .
	(ii) For all S-words w 0 , ..., w ℓ , we have
	(2.2.6)

  Assume that (S, N ) is of right-class 3, and let s 1 , ..., t 2 be elements of S satisfying the assumptions of the domino rule. By definition of the right-class, we have N (t 0 |s 1 |s 2 ) = N

	0	t 1	t 2
	Lemma 4.1.3. A quadratic normalisation (S, N ) is of class (4, 3) if, and only if, the domino
	rule is valid for N .
	Proof.

212 (t 0 |s 1 |s 2 ). As, by assumption, s 1 |s 2 is N -normal, we obtain N (t 0 |s 1 |s 2

  and the more precise result about the class, it follows from [10, Prop. III.1.45] which states that the domino rule is valid for N . As the current statement is different from [10, Prop. III.1.45], we recall the argument. So assume that s 1 , s 2 , s ′ 1 , s ′ 2 , t 0 , t 1 , t 2 lie in S, that s 1 |s 2 is Snormal, and that we have s ′ 1 |t 1 = N (t 0 |s 1 ) and s ′ 2 |t 2 = N (t 1 |s 2 ). Assume s ∈ S and s f s ′ 1 s ′ 2 . A fortiori we have s f s ′ 1 s ′ 2 t 2 , hence s f t 0 s 1 s 2 , since the diagram on the right is commutative. As s 1 |s 2 is S-normal, we deduce s f t 0 s 1 , whence s f s ′ 1 t 1 . As s ′ 1 |t 1 is S-normal, we deduce s f s ′ 1 . This shows that s ′ 1 |s ′ 2 is S-normal.

		s
	f	s ′ 1	2 s ′
	t 0	t 1	t 2
		s 1	s 2

 (w), witnessing that (S, N ) is of right-p-class 3. 4.3. Axiomatisation. By Proposition 3.3.5, if a quadratic normalisation (S, N ) is not of minimal left-class ∞, the restriction N of N to S [2] satisfies (3.3.6) and its symmetric counterpart for c large enough. In particular, if (S, N ) has class (4, 3), then N satisfies (4.1.1), that is, N 212 = N 2121 = N 1212 . We now go in the other direction, and prove that any idempotent map φ on S [2] satisfying the above relation necessarily stems from a quadratic normalisation of class [START_REF] Cain | Finite Gröbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids[END_REF][START_REF] Bokut | New approaches to plactic monoid via Gröbner-Shirshov bases[END_REF], thus completing a proof of Theorem A. Proposition 4.3.1. If S is a set and φ is a map from S [2] to itself satisfying The problem is to extend φ into a map φ * on S * such that (S, φ * ) is a quadratic normalisation of class (4, 3). Proposition 4.2.3 leads us into introducing the following extension of φ. Definition 4.3.3. For φ a map from S [2] to itself, we write φ * for the extension of φ to S * defined by φ * (s) = s for s in S and φ * (w) = φ δp (w) for w in S [p] .

We will prove that, when (4.3.2) is satisfied, (S, φ * ) is a quadratic normalisation of class (4, 3). We begin with preparatory formulas of the form φ u = φ v when u and v are sequences of positions connected by a specific equivalence relation. Note that the corresponding quotient monoid is a variant with infinitely many generators of the monoid M n of [START_REF] Krammer | An asymmetric generalisation of Artin monoids[END_REF]. Lemmas 4.3.6 and 4.3.10 below are essentially equivalent to [START_REF] Krammer | An asymmetric generalisation of Artin monoids[END_REF]Prop. 67] but we include a short self-contained proof as our framework and notation are different. Proof. As φ * is idempotent, φ i| i coincides with φ i . For |i -j| 2, φ i and φ j act on disjoint factors, so they commute. Finally, the relations for 2|1|2 and their shifted copies directly reflect (4.3.2). Lemma 4.3.6. The following relations are valid for every p 2:

Proof. We use induction on p 2. For p = 2, (4.3.7) reads 1 ≡ 1|sh(ε), which is valid. Assume p 3. Then we find

Summing up, we deduce (5.2.3)

which solves into F (p) 2 p + p -1 owing to F (q) 2 q -q -1 that holds for every 2 q < p by induction hypothesis. Finally, as in the case of class (3, 3), Proposition 3.2.5 implies that, if (S, R) terminates and e is an N -neutral element in S, then so does (S e , R e ).

Types of the successive steps in the computation of N12123212323 (w) for w of length 4: in addition to the six VH-steps, which inexorably approach N (w), we find four VV1-steps and one VV2-steps; this turns out to be the only possible length-11 sequence for length-4 words.

Remark. In the previous proof, one can observe that the number of VV-steps between two VH-steps is bounded above by F (p -1), since columns in the grid have length at most p -1, and deduce

, which is coarser than (5.2.3) but sufficient to inductively prove termination.

The following result, formulated purely in terms of rewriting systems, is an immediate consequence of Proposition 5.2.1.

Corollary 5.2.4. Assume that (S, R) is a reduced quadratic rewriting system. Define φ : S [2] → S [2] by φ(w) = w ′ for w → w ′ in R and φ(w) = w otherwise.

(i) Assume that, for all r, s, t in S, with r|s not R-normal, if s|t is R-normal then φ 12 (r|s|t) is R-normal, and if s|t is not R-normal then φ 1212 (r|s|t) = φ 212 (r|s|t). Then (S, R) is convergent.

(ii) If S contains a φ-neutral element e and the conditions of (i) are satisfied for all r, s, t in S e , then (S, R) and (S e , R e ) are convergent, where R e consists of one rule w → π e (w ′ ) for each w → w ′ in R with w ∈ S * e . 5.3. Termination in higher classes. We show that Proposition 5.2.1 is optimal: from class (4, 4) onwards, no general termination result can be established, since both nonterminating and terminating rewriting systems may arise. Proposition 5.3.1. There exists a quadratic normalisation of class (4, 4) such that the associated rewriting system is not convergent.

and cd → c ′ d. We claim that the rewriting system (S, R), which is quadratic by definition, is normalising and confluent. However (S, R) is not terminating, as it admits the length-3 cycle abcd → ab ′ cd → ab ′ c ′ d → abcd. We prove that (S, R) is normalising using an exhaustive description of the rewriting sequences starting from an arbitrary S-word. According to Proposition 6.1.7 and Lemma 6.2.2, the implication (i)⇒(ii) holds and we are left with the converse direction. So, until the end of the subsection, we assume that (S, N ) is a left-weighted quadratic normalisation mod 1 of class (4, 3) for a monoid M that is leftcancellative and contains no nontrivial invertible element. Our aim is to show that S is a Garside family in M and that N derives from it. We decompose the argument into several steps. Lemma 6.2.4. The family S is closed under right-divisor in M . Proof. Assume s ∈ S. An element g of M is a right-divisor of s if there exists f in M satisfying s = f g. We prove g ∈ S by induction on the minimal length f of the S-words representing f . For f = 0, we have s = g, whence g ∈ S.

Assume f 1. Then we can write f = f ′ t for some f ′ satisfying f ′ = f -1 and some t in S. Then we have s = f ′ tg, so the induction hypothesis implies tg ∈ S and, therefore, the S-normal decompositions of tg are the S-words tg|1|

. Now, we prove using induction on k decreasing from p to 2 that t k-1 and s k equal 1. For k = p, we have s ′ p = t p = 1; by construction, we have t p-1 s p = s ′ p t p , whence t p-1 s p = 1, and t p-1 = s p = 1, since M contains no nontrivial invertible element. For 2 k < p, we have s ′ k = 1 by assumption and t k = 1 by induction hypothesis, so that the same argument gives t k-1 = s k = 1. Thus g admits an N -normal decomposition of the form s 1 |1| ••• |1 and, therefore, it belongs to S. Lemma 6.2.5. For g in M , define H(g) to be 1 for g = 1, and to be the first entry in the N -normal decomposition of g otherwise. Then H(g) is an element of S that left-divides g, and every element of S that left-divides g in M left-divides H(g).

Proof. By definition, H(g) belongs to S, and it left-divides g in M , since we have g = H(g)ev(w) if H(g)|w is the N -normal decomposition of g. Now assume that t is an element of S that left-divides g, say g = th. Let s 1 | ••• |s p be the N -normal decomposition of h. As N is quadratic of class (4, 3), the domino rule is valid for N , so the N -normal decomposition of g is s

But the fact that (S, N ) is left-weighted implies that t 0 left-divides the first entry in N (t 0 |s 1 ), which is s ′ 1 |t 1 , so t H(g) holds.

Lemma 6.2.6. The family S is a Garside family in the monoid M . Proof. By assumption, S contains 1 and, by Lemma 6.2.4, it is closed under right-divisor. So S is what is called solid in [START_REF] Dehornoy | Foundations of Garside Theory[END_REF]Section IV.2]. Moreover, by definition, S is a generating family in M . Then, by [10, Prop. IV.2.7], we know that a solid generating family is a Garside family in M if, and only if, for every element g of M , there exists an element H(g) of S with the properties of Lemma 6.2.5. Thus the latter lemma implies that S is a Garside family in M .

We can now complete the argument.

Proof of Proposition 6.2.3. Owing to the previous results, it only remains to show that, in the implication (ii)⇒(i), the given normalisation (S, N ) coincides with the one, say (S, N ′ ), derived from the Garside family S. As both normalisations are quadratic, it is sufficient to prove N (s 1 |s 2 ) = N ′ (s 1 |s 2 ) for all s 1 , s 2 ∈ S, and, to this end, it is sufficient to prove that N (s 1 |s 2 ) is S-normal (in the sense of Definition 6.1.1). Now assume s ′ 1 |s ′ 2 = N (s 1 |s 2 ). Since S is a Garside family in M , we can appeal to [10, If t ′ = e holds, we have s ′ = st in M , so the result is true. Otherwise, the assumption that (S, N ) is left-weighted implies that there exists r in M satisfying sr = s ′ . By construction, r is a right-divisor of s ′ in M so, by Lemma 6.2.4, r must lie in S. Then, in M , we have s ′ = sr, whence st = srt ′ . The assumption that M is left-cancellative implies t = rt ′ . Hence the relation s|t = s ′ |t ′ is the consequence of s|r = s ′ and rt ′ = t.

Note that the existence of the presentation of Proposition 6.3.1 is only possible in a nongraded context, except for the free monoid S * with its presentation S | + . Example 6.3.2. Consider the braid monoid B + 3 , that is, the monoid presented by a, b | aba = bab + . Then B + 3 has a Garside family consisting of the six elements 1, a, b, ab, ba, and aba. Proposition 6.3.1 provides a presentation of B + 3 whose generators are the five nontrivial elements of the Garside family, and with the six relations a|b = ab, b|a = ba, and a|ba = b|ab = ab|a = ba|b = aba. This presentation is much smaller than the one provided by (3.1.11), that has the same five generators and 5 2 = 25 relations, such as ab|ab = aba|b or a|a = a|a.

Another subsequent development is that Garside families give rise to convergent rewriting system. Indeed, Propositions 5.2.1 and 6.2.3 directly imply Proposition 6.3.3. Assume that M is a left-cancellative monoid with no nontrivial invertible elements and S is a Garside family in M . Let R consist of all rules s|t → w with s, t in S \ {1} and w the minimal length S-normal decomposition of s|t. Then the rewriting system (S \{1}, R) is convergent.

As mentioned in Example 6.1.4, every finitely generated Artin-Tits monoid admits a finite Garside family. Being also left-cancellative with no nontrivial invertible element, Artin-Tits monoids are thus eligible to Proposition 6.3.3.