Stéphane Gaussent

Yves Guiraud

Philippe Malbos

Pierre-Louis Curien

Kenji Iohara

François Métayer

Samuel Mimram

Timothy Porter

COHERENT PRESENTATIONS OF ARTIN MONOIDS

Keywords: categories

We compute coherent presentations of Artin monoids, that is presentations by generators, relations, and relations between the relations. For that, we use methods of higher-dimensional rewriting that extend Squier's and Knuth-Bendix's completions into a homotopical completion-reduction, applied to Artin's and Garside's presentations. The main result of the paper states that the so-called Tits-Zamolodchikov 3-cells extend Artin's presentation into a coherent presentation. As a byproduct, we give a new constructive proof of a theorem of Deligne on the actions of an Artin monoid on a category.

INTRODUCTION

A Coxeter system (W, S) is a group W together with a presentation by a finite set of involutions S satisfying some (generalised) braid relations that we recall in Section 3. Forgetting about the involutive character of the generators and keeping only the braid relations, one gets Artin's presentation of the Artin monoid B + (W). For example, if W = S 4 , the group of permutations of {1, 2, 3, 4}, then S consists of the elementary transpositions r = (1 2), s = (2 3) and t = (3 4), and the associated Artin monoid is the monoid B + 4 of positive braids on four strands, with generators r, s, t satisfying the relations rsr = srs, rt = tr and sts = tst.

The aim of this article is to push further Artin's presentation and study the relations between the braid relations. A coherent presentation of a monoid (or more generally of a category) consists of a set of generators, a set of generating relations and some coherence conditions. These coherence conditions can be thought of as elements of a homotopy basis of a 2-dimensional CW-complex associated to the presentation. In the case of the braid monoid B + 4 on 4 strands, Deligne [START_REF]Action du groupe des tresses sur une catégorie[END_REF] notes that the homotopy basis associated to Artin's presentation contains only one element whose boundary consists of the reduced expressions graph of the element of maximal length in S 4 (this graph can be seen in Subsection 4.3).

Such a graph can be considered for any element w in W. The vertices are the reduced expressions of w and two such are linked by an edge if one is obtained from the other by a braid relation. In [START_REF] Tits | A local approach to buildings, The geometric vein[END_REF], Tits proves that the fundamental group of the reduced expressions graph is generated by two types of loops in the graph, the most interesting ones are associated to finite parabolic subgroups of rank 3 of W. Actually, for the purpose of finding generators for the homotopy basis of B + (W) associated to Artin's presentation, the generators of the first type are degenerate and part of the generators of the second type are superfluous. The main result of our paper, Theorem 4.1.1, states that there exists exactly one nondegenerate generator of the homotopy basis for every finite parabolic subgroup of rank 3 of W.

We now give some more details on the techniques we are using. The notion of coherent presentation is formalised in terms of polygraphs, which are presentations of higher-dimensional categories introduced by Burroni in [START_REF] Burroni | Higher-dimensional word problems with applications to equational logic[END_REF], and by Street in [START_REF] Street | Limits indexed by category-valued 2-functors[END_REF] under the name of computad. A 2-polygraph corresponds to a presentation of a monoid by a rewriting system, that is a presentation by generators (1-cells) and oriented relations (2-cells). For example, Artin's presentation of B + 4 has three generating 1-cells r, s, t and three generating 2-cells rsr ⇒ srs, rt ⇒ tr and sts ⇒ tst.

In [START_REF]Higher-dimensional normalisation strategies for acyclicity[END_REF], the last two authors have introduced the notion of (3, 1)-polygraph as a presentation extended by 3-cells on the 2-category defined by the congruence generated by the presentation. A coherent presentation is then a (3, 1)-polygraph such that the extension is a homotopy basis. We recall all these notions in Section 1.

To obtain coherent presentations for monoids, in Section 2, we develop a homotopical completionreduction method that is based on Squier's and Knuth-Bendix's completions. The completion-reduction is given in terms of Tietze transformations, known for presentations of groups [START_REF] Tietze | Über die topologischen Invarianten mehrdimensionaler Mannigfaltigkeiten[END_REF][START_REF] Lyndon | Combinatorial group theory[END_REF], here defined for (3, 1)-polygraphs. More precisely, we extend Squier's completion to terminating 2-polygraphs thanks to Knuth-Bendix's completion [START_REF] Knuth | Simple word problems in universal algebras[END_REF]. This is a classical construction of rewriting theory, similar to Buchberger's algorithm for computing Gröbner bases [START_REF] Buchberger | Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal (An Algorithm for Finding the Basis Elements in the Residue Class Ring Modulo a Zero Dimensional Polynomial Ideal[END_REF]. The procedure transforms a terminating 2polygraph Σ into a convergent one by adding to Σ a potentially infinite number of 2-cells so that every critical branching is confluent. Confluence of a 2-polygraph means that every time two 2-cells share the same source but two different targets, there exist two 2-cells having those different 1-cells as source and the same target. So, we end up with a (3, 1)-polygraph S(Σ) where every critical branching has given a 3-cell in the homotopy basis. Since the 2-polygraph we started with presents the monoid, S(Σ) is a coherent presentation of this monoid. Next, we introduce homotopical reduction as a general construction to coherently eliminate unnecessary cells in a coherent presentation. The (3, 1)-polygraph S(Σ) has usually more cells than one could expect. For example, one can eliminate the pairs of redundant 2-cells and collapsible 3-cells adjoined by homotopical completion for nonconfluent critical branchings. Some of the remaining 3-cells may also be redundant: one way to detect them is to compute the 3-spheres associated to the triple critical branchings of the presentation. Let us mention that the two last authors and Mimram have applied those methods to compute coherent presentations of plactic and Chinese monoids in [START_REF] Guiraud | A homotopical completion procedure with applications to coherence of monoids[END_REF].

In Section 3, we use the homotopical completion-reduction method to get a coherent presentation Gar 3 (W) of the Artin monoid B + (W). The starting presentation is Garside's presentation, denoted by Gar 2 (W). It has the elements of W \ {1} as generators and the relations are

u|v = uv if l(uv) = l(u) + l(v).
The notation •|• stands for the product in the free monoid over W \ {1} and l(u) is the length of u in W. The resulting coherent presentation Gar 3 (W), that we obtain in Theorem 3.1.3, corresponds to the coherence data given by Deligne in [START_REF]Action du groupe des tresses sur une catégorie[END_REF]Theorem 1.5]. We generalise our construction to Garside monoids, so that we are able to associate to every Garside monoid M a coherent presentation Gar 3 (M) (see Theorem 3.3.3).

In Section 4, we homotopically reduce Garside's coherent presentation Gar 3 (W) into the smaller coherent presentation Art 3 (W) associated with Artin's presentation of the monoid B + (W). The homotopy basis of Gar 3 (W) boils down to one 3-cell Z r,s,t for all elements t > s > r of S such that the subgroup of W they span is finite. To sum up, Theorem 4.1.1 says that the coherent presentation Art 3 (W) has exactly one k-cell, 0 ≤ k ≤ 3, for every subset I of S of rank k such that the subgroup W I is finite. The precise shape of the 3-cells is given in 4. [START_REF] Bourbaki | Groupes et algèbres de Lie. Chapitre IV : Groupes de Coxeter et systèmes de Tits. Chapitre V : Groupes engendrés par des réflexions. Chapitre VI : systèmes de racines[END_REF].

As an application, in Theorem 5.1.6, we prove that if Σ is a coherent presentation of a monoid M, then the category Act(M) of actions of M on categories is equivalent to the category of 2-functors from the associated (2, 1)-category Σ to Cat that send the elements of the homotopy basis to commutative diagrams. In [13, Theorem 1.5], Deligne already observes that this equivalence holds for Garside's presentation of spherical Artin monoids. The constructions are described in the homotopical setting of the canonical model structure on 2-categories given by Lack [START_REF] Lack | A Quillen model structure for 2-categories[END_REF][START_REF]A Quillen model structure for bicategories[END_REF]. In this spirit, as a byproduct of our main theorem, to determine the action of an Artin monoid on a category, it suffices to attach to any generating 1-cell s ∈ S an endofunctor T (s) and to any generating 2-cell a natural isomorphism, such that these satisfy coherence relations given by the Tits-Zamolodchikov 3-cells.

Finally, let us remark that, in [START_REF]Higher-dimensional normalisation strategies for acyclicity[END_REF]Theorem 4.5.3], Squier's completion is extended in higher dimensions to produce polygraphic resolutions of monoids, of which coherent presentations form the first three dimensions. From that point of view, the present work is a first step towards the construction of polygraphic resolutions Gar * (W) and Art * (W) of Artin monoids, extending the coherent presentations

COHERENT PRESENTATIONS OF CATEGORIES

Higher-dimensional categories

If C is an n-category (we always consider strict, globular n-categories), we denote by C k the set (and the k-category) of k-cells of C. If f is a k-cell of C, then s i (f) and t i (f) respectively denote the i-source and i-target of f; we drop the suffix i if i = k -1. The source and target maps satisfy the globular relations:

s i • s i+1 = s i • t i+1 and t i • s i+1 = t i • t i+1 .
We respectively denote by f :

u → v, f : u ⇒ v, f : u v and f : u 1 c v a 1-cell, a 2-cell, a 3
-cell and a 4-cell f with source u and target v. If f and g are i-composable k-cells, that is if t i (f) = s i (g), we denote by f i g their i-composite; we simply write fg if i = 0. The compositions satisfy the exchange relations given, for every i = j and all possible cells f, g, h and k, by

(f i g) j (h i k) = (f j h) i (g j k).
If f is a k-cell, we denote by 1 f its identity (k + 1)-cell. If 1 f is composed with cells of dimension k + 1 or higher, we simply denote it by f; for example, we write ufv and ufvgw instead of 1 u 0 f 0 1 v and 1 u 0 f 0 1 v 0 g 0 1 w for 1-cells u, v and w and 2-cells f and g.

1.1.1. (n, p)-categories. In an n-category C, a k-cell f, with source x and target y, is invertible if there exists a k-cell f -in C, with source y and target x in C, called the inverse of f, such that

f k-1 f -= 1 x and f - k-1 f = 1 y .
An (n, p)-category is an n-category whose k-cells are invertible for every k > p. In particular, an (n, n)-category is an ordinary n-category and an (n, 0)-category is an n-groupoid.

1.1.2. Spheres. Let C be an n-category. A 0-sphere of C is a pair γ = (f, g) of 0-cells of C and, for 1 ≤ k ≤ n, a k-sphere of C is a pair γ = (f, g) of parallel k-cells of C, i.e.
, with s(f) = s(g) and t(f) = t(g). We call f the source of γ and g its target and we write s(γ) = f and t(γ the n-category one gets from C by identification of the n-cells s(γ) and t(γ), for every n-sphere γ of Γ . If C is an (n, 1)-category and Γ is a cellular extension of C, then the free (n + 1, 1)-category generated by Γ over C is denoted by C(Γ ) and defined as follows:

) = g. If f is a k-cell of C, for 1 ≤ k ≤ n, the boundary of f is the (k -1)-sphere (s(f), t(f)).
C(Γ ) = C[Γ, Γ ] Inv(Γ )
where Γ contains the same (n + 1)-cells as Γ , with source and target reversed, and Inv(Γ ) is the cellular extension of C[Γ, Γ ] made of two (n + 2)-cells

x n x λ x / / 1 t(x) and x n x ρ x / / 1 s(x)
for each (n + 1)-cell x of Γ .

1.1.4. Homotopy bases. Let C be an n-category. A homotopy basis of C is a cellular extension Γ of C such that, for every n-sphere γ of C, there exists an (n+1)-cell with boundary γ in C(Γ ) or, equivalently, if the quotient n-category C/Γ has n-spheres of shape (f, f) only. For example, the n-spheres of C form a homotopy basis of C.

Coherent presentations of categories

1.2.1. Polygraphs. A 1-polygraph is a pair Σ = (Σ 0 , Σ 1 ) made of a set Σ 0 and a cellular extension Σ 1 of Σ 0 . The free category Σ * over Σ is Σ * = Σ 0 [Σ 1 ]. A 2-polygraph is a triple Σ = (Σ 0 , Σ 1 , Σ 2 )
where (Σ 0 , Σ 1 ) is a 1-polygraph and Σ 2 is a cellular extension of the free category Σ * 1 . The free 2-category Σ * over Σ, the free (2, 1)-category Σ over Σ and the category Σ presented by Σ are respectively defined by

Σ * = Σ * 1 [Σ 2 ] , Σ = Σ * 1 (Σ 2 ) and Σ = Σ * 1 /Σ 2 .
A (3, 1)-polygraph is a pair Σ = (Σ 2 , Σ 3 ) made of a 2-polygraph Σ 2 and a cellular extension Σ 3 of the free (2, 1)-category Σ 2 . The free (3, 1)-category Σ over Σ and the (2, 1)-category presented by Σ are defined by

Σ = Σ 2 (Σ 3 ) and Σ = Σ 2 /Σ 3 .
The category presented by a (3, 1)-polygraph Σ is the one presented by its underlying 2-polygraph, namely Σ 2 . If Σ is a polygraph, we identify its underlying k-polygraph Σ k and the set of k-cells of the corresponding cellular extension. We say that Σ is finite if it has finitely many cells in every dimension. A (3, 1)-polygraph Σ can be summarised by a diagram representing the cells and the source and target maps of the free (3, 1)-category Σ it generates:

Σ 0 Σ * 1 t 0 o o s 0 o o Σ 2 t 1 o o s 1 o o Σ 3 . t 2 o o s 2 o o 1.2.2.
Coherent presentations of categories. Let C be a category. A presentation of C is a 2-polygraph Σ whose presented category Σ is isomorphic to C. We usually commit the abuse to identify C and Σ and we denote by u the image of a 1-cell u of Σ * through the canonical projection onto C. An extended presentation of C is a (3, 1)-polygraph Σ whose presented category is isomorphic to C. A coherent presentation of C is an extended presentation Σ of C such that the cellular extension Σ 3 of Σ 2 is a homotopy basis.

& F u v w γ u,v w @ ` uγ v,w 4 T uvw u vw γ u,vw P p α u,v,w Õ % 1 x u γ 1x,u 4 u ι x u F f u λ u Õ % u 1 y γ u,1y 4

Cofibrant approximations of 2-categories

Let us recall the model structure for 2-categories given by Lack in [START_REF] Lack | A Quillen model structure for 2-categories[END_REF] and [START_REF]A Quillen model structure for bicategories[END_REF]. A 2-category is cofibrant if its underlying 1-category is free. A 2-functor F : C → D is a weak equivalence if it satisfies the following two conditions:

every 0-cell y of D is equivalent to a 0-cell F(x) for x in C, i.e., there exist 1-cells u : F(x) → y and v : y → F(x) and invertible 2-cells f :

u 1 v ⇒ 1 F(x) and g : v 1 u ⇒ 1 y in D;
for all 0-cells x and x in C, the induced functor F(x, x ) : C(x, x ) → D(F(x), F(x )) is an equivalence of categories.

In particular, an equivalence of

i) the (3, 1)-polygraph Σ is a coherent presentation of C; ii) the (2, 1)-category Σ presented by Σ is a cofibrant approximation of C.
Proof. Let us assume that Σ 3 is a homotopy basis of Σ 2 . By definition, the 2-category Σ is cofibrant. Let us check that it is weakly equivalent to C. We consider the canonical projection π : Σ C that sends every 0-cell to itself, every 1-cell to its equivalence class and every 2-cell and 3-cell to the corresponding 1.3. Cofibrant approximations of 2-categories identity. This is well defined since two 1-cells of Σ 2 have the same equivalence class in C if, and only if, there exists a 2-cell between them in Σ 2 and since parallel 2-cells of Σ are sent to the same (identity) 2-cell of C.

Since π is the identity on 0-cells, it is sufficient to check that it induces an equivalence of categories between Σ(x, y) and C(x, y) for all 0-cells x and y in C. We define a quasi-inverse ι by choosing, for each 1-cell u : x → y of C, an arbitrary representative 1-cell ι(u) in Σ. By construction, we have that πι is the identity of C(x, y). Moreover, for every 1-cell u : x → y of Σ, the 1-cell ιπ(u) is a 1-cell of Σ from x to y that has the same equivalence class as u: we choose an arbitrary 2-cell α u : u ⇒ ιπ(u) in Σ. Since all the parallel 2-cells of Σ are equal, we get the following commutative diagram for every 2-cell f of Σ:

ιπ(u) ιπ(f) u α u A a f 5 U = ιπ(v) v α v I i
This proves that α is a natural isomorphism between ιπ and the identity of Σ(x, y), yielding that π is a weak equivalence and, as a consequence, that Σ is a cofibrant approximation of C.

Conversely, let us assume that Σ is a cofibrant approximation of C. Let F : Σ → C be a weak equivalence and let f, g : u ⇒ v : x → y be parallel 2-cells of Σ . Since F is a 2-functor and C has identity 2-cells only, we must have F(u) = F(v) and F(f) = F(g) = 1 F(u) . By hypothesis, the 2-functor F induces an equivalence of categories between Σ(x, y) and C(x, y): we choose a quasi-inverse G and a natural isomorphism α between GF and the identity of Σ(x, y). We write the naturality conditions for f and g and, using GF(f) = GF(g) = 1 GF(u) , we conclude that f and g are equal in Σ:

GF(u) GF(f) u α u A a f 5 U = GF(v) v α v H h GF(u) GF(g) u α u A a g 5 U = GF(v) v α v H h
Thus Σ is a coherent presentation of C.

1.3.2. Remark. The cofibrant approximations of a category C form, in general, a strictly larger class than the 2-categories presented by coherent presentations of C. Indeed, let C be the terminal category: it contains one 0-cell and the corresponding identity 1-cell only. Then C is cofibrant and, as a consequence, it is a cofibrant approximation of itself: this corresponds to the coherent presentation of C given by the (3, 1)-polygraph with one 0-cell and no higher-dimensional cells. But C also admits, as a cofibrant approximation, the "equivalence" 2-category with two 0-cells x and y, two 1-cells u : x → y and v : y → x and two invertible 2-cells f : uv ⇒ 1 x and g : vu ⇒ 1 y , and this 2-category is not presented by a coherent presentation of C, since it does not have the same 0-cells as C.

1.3.3. Example (The standard cofibrant approximation [START_REF] Lack | A Quillen model structure for 2-categories[END_REF]). For any 2-category C, we denote by C the cofibrant 2-category with the same 0-cells as C and the following higher cells:

the 1-cells of C are freely generated by the ones of C, with u in C denoted by u when seen as a generator of C;

Homotopical completion and homotopical reduction

-the 2-cells from u 1 • • • u m to v 1 • • • v n in C are the 2-cells from u 1 • • • u m to v 1 • • • v n in C, with the same compositions as in C.
The canonical projection C C is the identity on 0-cells and maps each generating 1-cell u to u and each 2-cell to itself: this is a weak equivalence whose quasi-inverse lifts a 2-cell f : u ⇒ v to its distinguished representative f : u ⇒ v. Hence, the 2-category C is a cofibrant approximation of C, called the standard cofibrant approximation of C.

When C = C is a category, the 2-category C has exactly one 2-cell from

u 1 • • • u m to v 1 • • • v n if, and only if, the relation u 1 • • • u m = v 1 • • • v n holds in C:
this is a representative of an identity and, thus, it is invertible. As a consequence, the standard cofibrant approximation C of C is exactly the (2, 1)-category presented by the standard coherent presentation Std 3 (C) of C.

HOMOTOPICAL COMPLETION AND HOMOTOPICAL REDUCTION

Tietze transformations of (3, 1)-polygraphs

An equivalence of 2-categories F : C → D is a Tietze equivalence if the quotient categories C 1 /C 2 and D 1 /D 2 are isomorphic. Two (3, 1)-polygraphs are Tietze-equivalent if the 2-categories they present are Tietze-equivalent. In that case, they have the same 0-cells (up to a bijection). In particular, two coherent presentations of the same category are Tietze-equivalent.

2.1.1. Tietze transformations. Let Σ be a (3, 1)-polygraph. Following the terminology of [START_REF] Brown | The geometry of rewriting systems: a proof of the Anick-Groves-Squier theorem[END_REF], a 2-cell (resp. 3-cell, resp. 3-sphere) γ of Σ is called collapsible if it satisfies the following:

the target of γ is a 1-cell (resp. 2-cell, resp. 3-cell) of the (3, 1)-polygraph Σ, the source of γ is a 1-cell (resp. 2-cell, resp. 3-cell) of the free (3, 1)-category over Σ \ {t(γ)}.

If γ is collapsible, then its target is called a redundant cell. A collapsible cell and its redundant target can be coherently adjoined or removed from a (3, 1)-polygraph, without changing the presented 2-category, up to Tietze equivalence. These operations are formalised by Tietze transformations.

An elementary Tietze transformation of a (3, 1)-polygraph Σ is a 3-functor with domain Σ that belongs to one of the following six operations:

1. Coherent adjunction or elimination of a redundant 1-cell with its collapsible 2-cell:

• u / / • ι u / / π α o o • u # # x ; ; α Õ % • The coherent adjunction ι u : Σ Σ (x)(α)
is the canonical inclusion. The coherent elimination π α : Σ Σ /α maps x to u and α to 1 u , leaving the other cells unchanged. The (3, 1)-category Σ /α is freely generated by the following (3, 1)-polygraph Σ/α:

Σ 0 (Σ 1 \ {x}) * t 0 o o s 0 o o (Σ 2 \ {α}) π α • t 1 o o π α • s 1 o o Σ 3 . π α • t 2 o o π α • s 2 o o 2.
1. Tietze transformations of (3, 1)-polygraphs 2. Coherent adjunction or elimination of a redundant 2-cell with its collapsible 3-cell:

• C C f Õ % • ι f / / π γ o o • C C f Õ % α Õ % γ 7 W

•

The coherent adjunction ι f : Σ Σ (α)(γ) is the canonical inclusion. The coherent elimination π γ : Σ Σ /γ maps α to f and γ to 1 f , leaving the other cells unchanged. The (3, 1)-category Σ /γ is freely generated by the following (3, 1)-polygraph Σ/γ:

Σ 0 Σ * 1 t 0 o o s 0 o o (Σ 2 \ {α}) t 1 o o s 1 o o (Σ 3 \ {γ}) . π γ • t 2 o o π γ • s 2 o o 3.
Coherent adjunction or elimination of a redundant 3-cell:

• C C Õ % Õ % A 7 W • ι A / / π (A,γ) o o • C C Õ % Õ % A 7 W γ 7 W

•

The coherent adjunction ι A : Σ Σ (γ) is the canonical inclusion. The coherent elimination π (A,γ) : Σ Σ /(A, γ) maps γ to A, leaving the other cells unchanged. The (3, 1)-category Σ /(A, γ) is freely generated by the following (3, 1)-polygraph Σ/(A, γ):

Σ 0 Σ * 1 t 0 o o s 0 o o Σ 2 t 1 o o s 1 o o (Σ 3 \ {γ}) . t 2 o o s 2 o o
If Σ and Υ are (3, 1)-polygraphs, a (finite) Tietze transformation from Σ to Υ is a 3-functor F : Σ → Υ that decomposes into a (finite) sequence of elementary Tietze transformations. the 3-cells α 1x,u,v , α u,1y,v and α u,v,1z , since they are parallel to composites of λs and ρs, the 2-cells γ 1x,u and the 3-cells λ u , the 2-cells γ u,1x and the 3-cells ρ u , the 1-cells 1 x and the 2-cells ι x .

2.1.3. Theorem. Two (finite) (3, 1)-polygraphs Σ and Υ are Tietze equivalent if, and only if, there exists a (finite) Tietze transformation between them. As a consequence, if Σ is a coherent presentation of a category C and if there exists a Tietze transformation from Σ to Υ, then Υ is a coherent presentation of C.

Proof. Let us prove that, if two (3, 1)-polygraphs are related by a Tietze transformation, then they are Tietze-equivalent. Since isomorphisms of categories and equivalence of 2-categories compose, it is sufficient to check the result for each one of the six types of elementary Tietze transformations on a fixed (3, 1)-polygraph Σ. By definition, the 3-functors π • ι are all equal to the identity of Σ and the 3-functors ι • π induce identities on the presented category. Moreover, the latter induce the following 2-functors on the presented 2-category Σ:

ι u • π α 1 Σ , ι f • π A = 1 Σ , ι A • π (A,γ) = 1 Σ .
Indeed, the first isomorphism is the identity on every cell, except on x which is mapped to α. The second and third isomorphisms are, in fact, identities since they do not change the equivalence classes of 2-cells modulo 3-cells.

Conversely, let Σ and Υ be Tietze-equivalent (3, 1)-polygraphs. We fix an equivalence F : Σ → Υ of 2-categories that induces an isomorphism on the presented categories. We choose a weak inverse G : Υ → Σ and pseudonatural isomorphisms σ : GF ⇒ 1 Σ and τ : FG ⇒ 1 Υ , in such a way that the quadruple (F, G, σ, τ) is an adjoint equivalence, which is always feasible [32, Chap. IV, § 4, Theorem 1]. This means that the following "triangle identities" hold:

FGF Fσ $ D τF P p F = GFG Gτ % E σG I i G =
Let us lift the 2-functor F to a 3-functor F : Σ → Υ , defined as F on the 0-cells and 1-cells. For every 2-cell α : u ⇒ v of Σ, we choose a representative F(α) : F(u) ⇒ F(v) of F(α) in Υ and, then, we extend F by functoriality to every 2-cell of Σ . For a 3-cell γ : f g of Σ, we have f = g by definition of Σ, so that F(f) = F(g) holds in Υ, meaning that there exists a 3-cell in Υ from F(f) to F(g): we take it as a value for F(γ) and we extend F to every 3-cell of Σ by functoriality. We proceed similarly with G to get a 3-functor G : Υ → Σ .

Then, for a 1-cell x of Σ, we choose a representative σ x : GF(x) ⇒ x of σ x in Σ and we extend it to every 1-cell by functoriality. If α : u ⇒ v is a 2-cell of Σ, the naturality condition satisfied by σ on α lifts to an arbitrarily chosen

3-cell of Σ GF(v) σ v " B σ α Õ % GF(u) G F(α) B b σ u 5 U v u α P p
We proceed similarly with τ. The conditions for the adjoint equivalence also lift to a 3-cell λ x of Υ for every 1-cell x of Σ and to a 3-cell ρ y of Σ for every 1-cell y of Υ:

FGF(x) F( σ x ) $ D τ F(x) P p F(x) λ x Õ % GFG(y) G( τ y ) $ D σ G(y) P p G(y) ρ y Õ %
Now, let us build a Tietze transformation from Σ to Υ. We start by constructing a (3, 1)-polygraph Ξ that contains both Σ and Υ, together with coherence cells that correspond to the Tietze equivalence. The (3, 1)-polygraph Ξ has the same 0-cells as Σ (and as Υ) and it contains the 1-cells, 2-cells and 3-cells of Σ and Υ, plus the following cells:

-Two 2-cells ϕ x : F(x) ⇒ x and ψ y : G(y) ⇒ y, for all 1-cells x of Σ and y of Υ. Using the fact that F is a functor that preserves the 0-cells, we extend ϕ to every 1-cell u of Σ by functoriality, i.e. by ϕ 1p = 1 1p and ϕ uu = ϕ u ϕ u , to get a 2-cell ϕ u : F(u) ⇒ u for every 1-cell u of Σ . We proceed similarly with

ψ to define a 2-cell ψ v : G(v) ⇒ v of Ξ for every 1-cell v of Υ .
-Two 3-cells ϕ α and ψ β , for all 2-cells α : u ⇒ u and β : v ⇒ v , with the following shapes:

F(u) F(α) 7 W F(u ) ϕ u 9 u ϕ - u D d α 9 Y ϕ α Õ % u G(v) G(β) 7 W G(v ) ψ v 9 v ψ - v D d β 9 Y ψ β Õ % v
We use the 2-functoriality of the sources and targets of ϕ α and ψ β to extend ϕ and ψ to every 2-cells f of Σ and g of Υ , respectively.

-Two 3-cells ξ x and η y , for all 1-cells x of Σ and y of Υ, with the following shapes:

GF(x) σ x ! A ξ x Õ % F(x) ψ - F(x) C c ϕ x @ `x FG(y) τ y @ η y Õ % G(y) ϕ - G(y) C c ψ y @ `y
We then extend ε and η to all 1-cells u of Σ and v of Υ , respectively.

We construct a Tietze transformation Φ from Σ to Ξ step-by-step, as follows.

-Adjunction of the cells of Υ. For every 1-cell y of Υ, we apply ι G(y) to coherently add y and ψ y : G(y) ⇒ y. Then, for every

2-cell β : v ⇒ v of Υ, we apply ι ψ - v 1 G(β) 1 ψ v
to coherently add β and ψ β . Then, we add every 3-cell δ : g g of Υ with ι B , where B is the 3-cell of Ξ defined by B = ψ - g 2 ψ - v 1 G(δ) 1 ψ v 2 ψ g and pictured as follows:

v g 9 ψ - v 7 W g U u G(v) G(g) # C G(g ) R r G(v ) ψ v 7 W v ψ - g Õ % G(δ) Õ % ψ g Õ %
-Adjunction of the coherence cells for Σ. For every 1-cell x, we apply ι ψ - F(x) 1 σx to coherently add the 2-cell ϕ x and the 3-cell ξ x . Then, for every 2-cell α : u ⇒ u of Σ, we add the 3-cell ϕ α with ι A , where A is the 3-cell of ξ defined by

A = ϕ - u 1 ξ u 1 σ - u 1 ψ F(u) 1 ψ - F(α) 1 ξ - u 2 σ - u 1 σ α
and pictured as follows, where we abusively simplify the labels of 3-cells for readability:

F(u) F(α) 7 W ψ F(α) F(u ) ϕ u 6 ψ - F(u ) Õ % u ϕ - u 8 X σ - u 7 W α I i GF(u) ψ F(u) i G F(α) 7 W GF(u ) σ u 7 W u ξ u ξ u σ α
-Adjunction of the last coherence cells for Υ. For every 1-cell y of Υ, we add the 3-cell η y with ι C , where C is the 3-cell of Ξ defined by

C = ϕ - G(y) 1 ξ G(y) 1 σ - G(y) 1 ψ FG(y) 1 ψ - τy 2 σ - G (
y) 1 ρ y 1 ψ y and pictured, in a simplified way, as follows

FG(y) τ y 6 G(y) ϕ - G(y) 9 Y σ - G(y) 7 W GFG(y) ψ FG(y) i G( τ y ) Õ % ψ τy y G(y) ψ y X x ξ G(y) ρ y
As a result, we get a Tietze transformation Φ from Σ to Ξ. Since the construction and the result are totally symmetric in Σ and Υ, and since the Tietze transformation Φ contains coherent adjunctions only, we also get a Tietze transformation Ψ from Ξ to Υ. By composition, we get a Tietze transformation from Σ to Υ.

To conclude, we note that both Φ and Ψ are finite when both Σ and Υ are. Finally, if Σ is a coherent presentation of a category C, then the 2-category it presents is a cofibrant approximation of C by Theorem 1.3.1. Moreover, if there exists a Tietze transformation from Σ to Υ, they are Tietze-equivalent by the first part of the proof. Thus, the categories presented by Σ and Υ are isomorphic (to C), and the 2-categories they present are equivalent, hence weakly equivalent. As a consequence, the 2-category presented by Υ is also a cofibrant approximation of C so that, by Theorem 1.3.1, we conclude that Υ is a coherent presentation of C.

2.1.4. Higher Nielsen transformations. We introduce higher-dimensional analogues of Nielsen transformations to perform replacement of cells in (3, 1)-polygraphs. The elementary Nielsen transformations on a (3, 1)-polygraph Σ are the following operations:

1. The replacement of a 2-cell by a formal inverse (including in the source and target of every 3-cell).

2. The replacement of a 3-cell by a formal inverse.

3. The replacement of a 3-cell γ : f g by a 3-cell γ : h 1 f 1 k h 1 g 1 k, where h and k are 2-cells of Σ . Each one of those three elementary Nielsen transformations is a Tietze transformation. For example, the last one is the composition of the following elementary Tietze transformations:

-the coherent adjunction ι h 1 γ 1 k of the 3-cell γ : h 1 f 1 k h 1 g 1 k, -the coherent elimination π h -1 γ 1 k -of γ.
The replacement of a 2-cell α : u ⇒ v by a formal inverse α : v ⇒ u is the composition of:

the coherent adjunction ι α -of the 2-cell α : v ⇒ u and a 3-cell γ : α - α,

the Nielsen transformation that replaces γ with γ : α - α by composition with α on one side and by α -on the other side, the coherent elimination π γ of α and γ.

In what follows, we perform coherent eliminations of cells that are collapsible only up to a Nielsen transformation (a composition of elementary ones). If f is Nielsen-equivalent to a collapsible cell f, we abusively denote by π f the corresponding coherent elimination, with a precision about the eliminated cell t( f) when it is not clear from the context. In a similar way, if (A, B) is a noncollapsible 3-sphere of Σ , we denote by π (A,B) the potential coherent elimination corresponding to a collapsible 3-sphere Σ obtained from (A, B) by composition with 2-cells and 3-cells of Σ .

Homotopical completion

In this section, we recall notions of rewriting theory for 2-polygraphs from [21, 4.1] and [22, 4.1], together with Squier's completion to compute coherent presentations from convergent presentations. Then we extend Squier's completion to terminating 2-polygraphs thanks to Knuth-Bendix's completion [START_REF] Knuth | Simple word problems in universal algebras[END_REF].

2. Homotopical completion and homotopical reduction 2.2.1. Rewriting properties of 2-polygraphs. A rewriting step of a 2-polygraph Σ is a 2-cell of the free 2-category Σ * with shape

y w / / x u # # v < < α Õ % x w / / y
where α : u ⇒ v is a 2-cell of Σ and w and w are 1-cells of Σ * . A normal form is a 1-cell that is the source of no rewriting step. We say that Σ terminates if it has no infinite rewriting sequence (no infinite sequence of composable rewriting steps). In that case, the relations s(f) > t(f) for f a rewriting step define a termination order: this is a well-founded order relation on the 1-cells that is compatible with the composition. Another example of termination order is the deglex order that first compares the length and, then, uses a lexicographic order on the words of same length. In fact, the existence of a termination order is sufficient to prove termination.

A branching of Σ is a (non-ordered) pair (f, g) of 2-cells of Σ * with a common source, also called the source of the branching. We say that Σ is confluent if all of its branchings are confluent, that is, for every branching (f, g), there exist 2-cells f and g in Σ * , as in the following diagram:

v f # C u f 9 Y g 5 U u w g S s
A branching (f, g) is local if f and g are rewriting steps. The local branchings are classified as follows:

aspherical branchings have shape (f, f),

-Peiffer branchings have shape (fv, ug), where u = s(f) and v = s(g),

overlap branchings are all the other cases.

Local branchings are ordered by inclusion of their sources, and a minimal overlap branching is called critical. Under the termination hypothesis, confluence is equivalent to confluence of critical branchings. We say that Σ is convergent if it terminates and is confluent. Such a Σ is called a convergent presentation of the category Σ, and of any category that is isomorphic to Σ. In that case, every 1-cell u of Σ * has a unique normal form, denoted by u, so that we have u = v in Σ if, and only if, u = v holds in Σ * . This extends to a section Σ Σ * of the canonical projection, sending a 1-cell u of Σ to the unique normal form of its representative 1-cells in Σ * , still denoted by u. A (3, 1)-polygraph is convergent if its underlying 2-polygraph is.

Squier's completion for convergent polygraphs.

Let us assume that Σ is convergent. A family of generating confluences of Σ is a cellular extension of Σ that contains exactly one 3-cell v f

$ D Õ % u f 9 Y g 5 U u w g Q q
for every critical branching (f, g) of Σ. Such a family always exists by confluence but it is not necessarily unique. Indeed, the 3-cell can be directed in the reverse way and, for a given branching (f, g), one can have several possible 2-cells f and g with the required shape (see [22, 4. One considers each critical branching (f, g) of Σ. There are two possible situations, shown below, depending on whether (f, g) is confluent or not:

v f & F γ Õ % u f 9 Y g 5 U v = w w g I i v f 7 W γ Õ % v i α Õ % u f 9 Y g 5 U w g 7 W w
If (f, g) is confluent, the left case occurs and one adds the dotted 3-cell γ to Σ. Otherwise, one performs a Tietze transformation on Σ to coherently add the 2-cell α and the 3-cell γ. To preserve termination, the 2cell α is directed from v to w if v > w and in the reverse direction otherwise. To be formal, the coherent adjunction would add a 3-cell γ with target α, but we implicitly perform a Nielsen transformation for convenience.

The potential adjunction of additional 2-cells α can create new critical branchings, whose confluence must also be examined, possibly generating the adjunction of additional 2-cells and 3-cells. This defines an increasing sequence of (3, 1)-polygraphs, where Σ n+1 is obtained by completion of the critical branchings of Σ n :

(Σ, ∅) = Σ 0 ⊆ Σ 1 ⊆ • • • ⊆ Σ n ⊆ Σ n+1 ⊆ • • •
The (3, 1)-polygraph S(Σ) is defined as the union of this increasing sequence. If the 2-polygraph Σ is already confluent, the homotopical completion is exactly Squier's completion. As a consequence of Theorem 2.2.3, we get that the potentially infinite (3, 1)-polygraph S(Σ) satisfies the following properties. every γ of every Γ k is collapsible (potentially up to a Nielsen transformation),

no γ of any Γ k is redundant for some element of Γ k+1 , there exists well-founded order relations on the 1-cells, 2-cells and 3-cells of Σ such that, for every γ in every Γ k , the target of γ is strictly greater than every generating (k -1)-cell that occurs in the source of γ.

In that case, the recursive assignment Local triple branchings are ordered by inclusion of their sources and a minimal overlap triple branching is called critical.

π Γ (x) =      π Γ (s(γ)) if x = t(γ) for γ in Γ 1 π Γ (s(γ)) if x = γ is in Γ x otherwise
If Σ is a coherent and convergent (3, 1)-polygraph, a triple generating confluence of Σ is a 3-sphere

v f 1 3 S A x h 2 v f 1 3 S f 2 @ x h 2 u f F f g 7 W h ( H w g 1 T t g 2 @ C u ω 1 c u f F f C h ( H w g 7 W B A u x h 2 A a B v f b x h 1 T t h 2 A a v f b
where (f, g, h) is a triple critical branching of Σ and the other cells are obtained as follows. First, we consider the branching (f, g): we use confluence to get f 1 and g 1 and coherence to get the 3-cell A. We proceed similarly with the branchings (g, h) and (f, h). Then, we consider the branching (f 1 , f 2 ) and we use convergence to get g and h with u as common target, plus the 3-cell B by coherence. We do the same operation with (h 1 , h 2 ) to get A . Finally, we build the 3-cell C to relate the parallel 2-cells g 1 1 h and g 2 1 f .

Homotopical completion-reduction.

In the applications we consider, homotopical reduction is applied to the homotopical completion S(Σ) of a terminating 2-polygraph Σ. This induces a collapsible part Γ of S(Σ) made of some of the generating triple confluences of S(Σ),

the 3-cells coherently adjoined with a 2-cell by homotopical completion to reach confluence, some collapsible 2-cells or 3-cells already present in the initial presentation Σ.

If Σ is a terminating 2-polygraph, the homotopical completion-reduction of Σ is the (3, 1)-polygraph

R(Σ) = π Γ (S(Σ))
obtained from the homotopical completion of Σ by homotopical reduction with respect to some collapsible part Γ of S(Σ). The definition and the notation should depend on Γ , and we make them precise in each application we consider. We conclude that Γ is collapsible with the orders

D > C > B > A, δ > γ > β > α, a > t > s.
Thus the homotopical reduction of S(Σ) with respect to Γ is the (3, 1)-polygraph

R(Σ) = s, t ; tst ⇒ sts ; ∅ .
By Theorem 2.3.4, we recover that the monoid B + 3 admits a coherent presentation made of Artin's presentation and no 3-cell.

GARSIDE'S COHERENT PRESENTATION OF ARTIN MONOIDS

Recall that a Coxeter group is a group W that admits a presentation with a finite set S of generators and with one relation

(st) m st = 1, with m st ∈ N {∞}, (1)
for every s and t in S, with the following requirements and conventions:

Garside's presentation of Artin monoids

-m st = ∞ means that there is, in fact, no relation between s and t,

-m st = 1 if, and only if, s = t.

The last requirement implies that s 2 = 1 holds in W for every s in S. As a consequence, the group W can also be seen as the monoid with the same presentation. Let us note that a given Coxeter group can have several generating sets that fit the given scheme, but we always assume that such a set S has been fixed and comes equipped with a total order. Following [4, (1.1)], we denote by st n the element of length n in the free monoid S * , obtained by multiplication of alternating copies of s and t. Formally, this element is defined by induction on n as follows:

st 0 = 1 and st n+1 = s ts n .

When s = t and m st < ∞, we use this notation and the relations s 2 = t 2 = 1 to write (1) as a braid relation:

st m st = ts m st . (2)
A reduced expression of an element u of W is a representative of minimal length of u in the free monoid S * . The length of u is denoted by l(u) and defined as the length of any of its reduced expressions. The Coxeter group W is finite if, and only if, it admits an element of maximal length, [4, Theorem 5.6]; in that case, this element is unique, it is called the longest element of W and is denoted by w 0 (S). For I ⊆ S, the subgroup of W spanned by the elements of I is denoted by W I . It is a Coxeter group with generating set I. If W I is finite, we denote by w 0 (I) its longest element.

We recall that the Artin monoid associated to W is the monoid denoted by B + (W), generated by S and subject to the braid relations (2). This presentation, seen as a 2-polygraph, is denoted by Art 2 (W) and called Artin's presentation: this is the same as the one of W, except for the relations s 2 = 1.

In this section, we fix a Coxeter group W and we apply the homotopical completion-reduction method to get a coherent presentation for the Artin monoid B + (W).

Garside's presentation of Artin monoids

We recall some arithmetic properties on Artin monoids, observed by Garside for braid monoids in [START_REF] Garside | The braid group and other groups[END_REF] and generalised by Brieskorn and Saito in [START_REF] Brieskorn | Artin-Gruppen und Coxeter-Gruppen[END_REF]. Garside's presentation is explicitly given in [13, 1.4.5] for spherical Artin monoids and in [34, Proposition 1.1] for any Artin monoid. We refer to [START_REF] Geck | Characters of finite Coxeter groups and Iwahori-Hecke algebras[END_REF] for proofs.

Length notation and divisibility.

For every u and v in W, we have l(uv) ≤ l(u) + l(v) and we use distinct graphical notations depending on whether the equality holds or not:

u v ⇔ l(uv) = l(u) + l(v), u v × ⇔ l(uv) < l(u) + l(v).
When w = uv holds in W with u v, we write w . = uv. We generalise the notation for a greater number of elements of W. For example, in the case of three elements u, v and w of W, we write u v w when both equalities l(uv) = l(u) + l(v) and l(vw) = l(v) + l(w) hold. This case splits in the following two mutually exclusive subcases:

u v w ⇔ u v w l(uvw) = l(u) + l(v) + l(w), u v w × ⇔ u v w l(uvw) < l(u) + l(v) + l(w).
If u and v are two elements of B + (W), we say that u is a divisor of v and that v is a multiple of u if there exists an element u in B + (W) such that uu = v. In that case, the element u is uniquely defined and called the complement of for every u, v and w of W \ {1} with u v w.

u in v [4,
3.1.3. Theorem. For every Coxeter group W, the Artin monoid B + (W) admits Gar 3 (W) as a coherent presentation.

The (3, 1)-polygraph Gar 3 (W) is called the Garside's coherent presentation of the Artin monoid B + (W). Theorem 3.1.3 is proved in the following section by homotopical completion-reduction of Gar 2 (W).

Homotopical completion-reduction of Garside's presentation

Let us define a termination order on the 2-polygraph Gar 2 (W). Let < denote the strict order on the elements of the free monoid W * that first compares their length as elements of W * , and then the length of their components, starting from the right. For example, we have that u 1 |u 2 < v 1 |v 2 |v 3 (first condition) and uv|w < u|vw if u v w (second condition). The order relation ≤ generated by < by adding reflexivity is a termination order on Gar 2 (W): for every 2-cell α u,v of Gar 2 (W), we have u|v > uv.

Hence the 2-polygraph Gar 2 (W) terminates, so that its homotopical completion is defined. , and the nine families of 3-cells A, B, C, D, E, F, G, H, I given in Figure 1. .

uv|w α uv,w @ A u,v,w Õ % u|v|w α u,v |w C c u|α v,w 1 Q uvw u|vw α u,vw T t u|v|w α u,v |w 1 Q u|α v,w ) I uv|w u|vw β u,v,w U u B u,v,w Õ % uv|wx β uv,w,x # C C u,v,w,x Õ % u|v|wx α u,v |wx B b u|β v,w,x 1 Q uvw|x u|vw|x α u,vw |x Q q u|v|wx α u,v |wx 3 S u|β v,w,x 1 Q uv|wx u|vw|x β u,v,w |x 7 W uv|w|x uv|α w,x Q q D u,v,w,x Õ % uv|w|x uv|α w,x # C E u,v,w,x Õ % u|vw|x β u,v,w |x C c
C c uvx|y H u,v,x,y Õ % uv 1 |w 1 = uv 1 |x 1 y β uv 1 ,x 1 ,y ! A I u,v 1 ,w 1 ,v 2 ,w 2 Õ % u|v 1 w 1 = u|v 2 w 2 β u,v 1 ,w 1 D d β u,v 2 ,w 2 0 P uv 1 x 1 |y = uv 2 x 2 |y uv 2 |w 2 = uv 2 |x 2 y β uv 2 ,x 2 ,y S s
Proof. The 2-polygraph Gar 2 (W) has exactly one critical branching for every u, v and w of W \ {1} such that u v w:

uv|w u|v|w α u,v |w 6 V u|α v,w 8 X u|vw
Then there are two possibilities. If u v w , the branching is confluent, adjoining the 3-cell A u,v,w .

Otherwise, we have u v w × and the branching is not confluent, thus homotopical completion coherently adjoins the 2-cell β u,v,w and the 3-cell B u,v,w . The family β of 2-cells creates new critical branchings, each one being confluent and conducting to the adjunction of one or several 3-cells. The sources of all the 2-cells α and β have size 2 in the free monoid over W \ {1}. As a consequence, there are two main cases for the critical branchings that involve at least one 2-cell β.

The first case occurs when the sources of the 2-cells of Gar 2 (W) that generate the branching overlap on one element of W \ {1}. The source of such a branching has size 3, with one 2-cell of the branching reducing the leftmost two generating 1-cells and the other one reducing the rightmost two. This leaves three main cases of branchings: , respectively corresponding to the 3-cells F u,v,w,x,y and G u,v,w,x,y .

The second main case occurs when the 2-cells of Gar 2 (W) that generate the branching have the same source. Since one of those 2-cells must be a β, the source must have shape u|v 1 w 1 with u v 1 w 1 preventing the other 2-cell to be an α. The only remaining possibility is to have a different decomposition

Homotopical completion-reduction of Garside's presentation

v 1 w 1 = v 2 w 2 , with u v 2 w 2 ×
, so that the branching is as follows:

uv 1 |w 1 u|v 1 w 1 = u|v 2 w 2 β u,v 1 ,w 1 5 U β u,v 2 ,w 2 9 Y uv 2 |w 2
The properties of Artin monoids ensure that we have the following relations in B + (W):

• w 1 $ $ x 1 = • v 1 7 7 v 2 ' ' = • y / / • • x 2 A A w 2
: :

= Indeed, we note that the elements v 1 and v 2 have a common multiple since v 1 w 1 = v 2 w 2 . Hence, they admit an lcm. The elements x 1 and x 2 are respectively defined as the complements of v 1 and v 2 in their lcm. The element y is the complement of the lcm v 1 x 1 = v 2 x 2 of v 1 and v 2 in their common multiple v 1 w 1 = v 2 w 2 . By uniqueness of the complements of v 1 and v 2 in v 1 w 1 = v 2 w 2 , we get w 1 = x 1 y and w 2 = x 2 y. Moreover, we have v 1 x 1 y and v 2 x 2 y . Finally, from the hypothesis u v 1 w 1 we get that y = 1. Then, there are two possible subcases for the confluence diagram, depending on x 1 and x 2 .

The first subcase is when we have either x 1 = 1 or x 2 = 1. We note that both cannot happen at the same time, otherwise v 1 = v 2 and w 1 = w 2 , so that the branching would be aspherical and not critical. We get the 3-cell H u,v,x,y if x 2 = 1, inducing v 2 = v 1 x 1 , w 1 = x 1 y and w 2 = y, with v = v 1 and x = x 1 .

The second subcase, when x 1 = 1 and x 2 = 1 gives the 3-cell I u,v 1 ,w 1 ,v 2 ,w 2 .

Homotopical reduction of S(Gar 2 (W))

. We consider the following generating triple confluences, associated to some of the triple critical branchings of S(Gar 2 (W)):

-The 3-sphere ω C u,v,w,x in the case u v w x with v 1 w 1 = v 2 w 2 :

uv 1 |w 1 βuv 1 ,x 1 ,y " B I u,v 1 ,w 1 ,v 2 ,w 2 u|v 1 w 1 βu,v 1 ,w 1 A a βu,v 2 ,w 2 7 W βu,v 1 x 1 ,y Q q uv 2 |w 2 βuv 2 ,x 2 ,y 7 W H u,v 2 ,x 2 ,y uv 1 x 1 |y 1 c uv 1 |w 1 βuv 1 ,x 1 ,y # C u|v 1 w 1 βu,v 1 ,w 1 B b βu,v 1 x 1 ,y S s uv 1 x 1 |y H u,v 1 ,x 1 ,y
We consider the collapsible part Γ of S(Gar 2 (W)) made of each of those 3-spheres and all the 3-cells B u,v,w , with the order

I > H > • • • > C.
The homotopical reduction of S(Gar 2 (W)) with respect to Γ is exactly Garside's coherent presentation Gar 3 (W), ending the proof of Theorem 3.1.3.

Garside's coherent presentation for Garside monoids

Garside monoids have been introduced as a generalisation of spherical Artin monoids by Dehornoy and Paris [START_REF] Dehornoy | Gaussian groups and Garside groups, two generalisations of Artin groups[END_REF][START_REF] Dehornoy | Groupes de Garside[END_REF] to abstract the arithmetic properties observed by Garside on braid monoids [START_REF] Garside | The braid group and other groups[END_REF] and by Brieskorn-Saito and Deligne on spherical Artin monoids [START_REF] Brieskorn | Artin-Gruppen und Coxeter-Gruppen[END_REF][START_REF] Deligne | Les immeubles des groupes de tresses généralisés[END_REF]. We refer the reader to [START_REF] Dehornoy | Foundations of Garside theory[END_REF] for a unified treatment of Garside structure. We fix a Garside monoid M and we follow [START_REF] Gebhardt | The cyclic sliding operation in Garside groups[END_REF] for most of the terminology and notation.

Recollections on Garside monoids.

In the monoid M, all elements u and v admit a greatest common divisor u ∧ v. Moreover, the monoid M has a Garside element, denoted by w 0 , such that the set W of its divisors generates M. The complement of an element u of W in w 0 is denoted by

∂(u). A pair (u, v) of elements of W is left-weighted if we have ∂(u) ∧ v = 1.
For each pair (u, v) of elements of W, there exists a unique left-weighted pair (u , v ) of elements of W such that uv = u v holds in M: we take u = u(∂(u)∧v) and v to be the complement of ∂(u)∧v in v. The operation transforming (u, v) into (u , v ) is called local sliding. It induces a computational process that transforms any element u of W * into its (left) normal form by a finite sequence of local slidings, thereafter represented by dashed arrows:

u / / (• • • ) / / u.
Moreover, two elements u and v of W * represent the same element of M if, and only if, they have the same normal form, so that they are linked by a finite sequence of local slidings and their inverses:

u / / u v. o o 3.3.2.
Garside's presentation. First, let us note that, since the set W of divisors of w 0 generates M, then so does W \ {1}. Given two elements u and v of W \ {1}, we use the notations u v and u v

× to mean u v ⇔ ∂(u) ∧ v = 1, u v × ⇔ ∂(u) ∧ v = 1.
We define Garside's presentation of M as the 2-polygraph Gar 2 (M) with one 0-cell, one 1-cells for every element of W \ {1} and one 2-cell u|v α u,v 7 W uv for every u and v in W \ {1} such that u v holds. Let us check that Garside's presentation is, indeed, a presentation of the monoid M. If u v holds, transforming u|v into uv is a local sliding since uv is the normal form of u|v, so that each 2-cell α u,v is an instance of local sliding. Conversely, if u|vw is transformed into uv|w by local sliding, this implies, in particular, that both u v and v w hold. Thus, the composite 2-cell u|v|w α u,v |w

! A u|vw u|α - v,w D d
/ / uv|w corresponds to the local sliding transformation applied to u|vw. We define Garside's coherent presentation Gar 3 (M) as done in 3.1.2 for Artin monoids. The proof of Theorem 3.1.3 adapts in a straightforward way to this case.

3.3.3. Theorem. Every Garside monoid M admits Gar 3 (M) as a coherent presentation.

ARTIN'S COHERENT PRESENTATION OF ARTIN MONOIDS

Let W be a Coxeter group with a totally ordered set S of generators. In this section, we use the homotopical reduction method on Garside's coherent presentation Gar 3 (W) to contract it into a smaller coherent presentation associated to Artin's presentation.

Artin's coherent presentation

We call Artin's presentation of the Artin monoid B + (W) the 2-polygraph Art 2 (W) with one 0-cell, the elements of S as 1-cell and one 2-cell γ s,t : ts m st ⇒ st m st for every t > s in S such that m st is finite. We recall that, if I is a subset of S, then I has an lcm if, and only if, the subgroup W I of W spanned by I is finite. In that case, the lcm of I is the longest element w 0 (I) of W I . This implies that, if an element u of W admits reduced expressions s 1 u 1 , . . . , s n u n where s 1 , . . . , s n are in S, then the subgroup W {s 1 ,...,sn} is finite and its longest element w 0 (s 1 , . . . , s n ) is a divisor of u. As a consequence, the element u has a unique reduced expression of the shape w 0 (s 1 , . . . , s n )u .

The main theorem of this section extends Art 2 (W) into Artin's coherent presentation of the Artin monoid B + (W).

4.1.1. Theorem. For every Coxeter group W, the Artin monoid B + (W) admits the coherent presentation Art 3 (W) made of Artin's presentation Art 2 (W) and one 3-cell Z r,s,t for all elements t > s > r of S such that the subgroup W {r,s,t} is finite.

We note that Artin's coherent presentation has exactly one k-cell, 0 ≤ k ≤ 3, for every subset I of S of rank k such that the subgroup W I is finite. In 4.2, we use homotopical reduction on Garside's coherent presentation Gar 3 (W) to get a homotopy basis of Artin's presentation. The precise shape of the 3-cells is given in 4.3.

Homotopical reduction of Garside's coherent presentation

We consider Garside's coherent presentation Gar 3 (W) of B + (W). The homotopical reduction in the proof of Theorem 3.1.3 has coherently eliminated some redundant 3-cells, thanks to generating triple confluences of S(Gar 2 (W)). This convergent (3, 1)-polygraph has other triple critical branchings. In particular, the critical triple branchings created by three 2-cells α, whose sources are the u|v|w|x with u v w x, generate the following family Gar 4 (W) of 4-spheres ω u,v,w,x of Gar 3 (W) : To construct a collapsible part of Gar 3 (W), we use the indexing families of the cells of Gar 3 (W) and the 3-spheres of Gar 4 (W) to classify and compare them.

The classification.

If u is an element of W \ {1}, the smallest divisor of u is denoted by d u and defined as the smallest element of S that is a divisor of u. Let (u 1 , . . . , u n ) be a family of elements of

W \ {1} such that l(u 1 • • • u n ) = l(u 1 ) + • • • + l(u n ).
For every k ∈ {1, . . . , n}, we write We check that each redundant 2-cell is strictly greater than the other 2-cells appearing in the source and target of A s,u,v . For both cases (a) and (b), we observe that α su,v and α s,uv are always strictly greater than α s,u and α u,v since l(suv) > l(su) and l(suv) > l(uv). Then, we proceed by case analysis:

s k = d u 1 •••u k . We note that s 1 ≥ s 2 ≥ • • • ≥ s n since each s k divides u 1 • • • u l for l ≥ k.
(a) α su,v > α s,uv since s = d su and l(su) > l(s)

(b) α s,uv > α su,v since s > d su .
Finally, the 3-spheres of Γ are the ω s,u,v,w su|v|w αsu,v|w Those 3-cells are collapsible up to a Nielsen transformation, and the corresponding redundant 3-cells are (a) A su,v,w , (b) A s,uv,w or (c) A s,u,vw . By hypothesis, the indexing triples (su, v, w), (s, uv, w) and (s, u, vw) are redundant, so that none of those 3-cells is in Γ . We observe that A su,v,w , A s,uv,w and A s,u,vw are always strictly greater than A s,u,v and A u,v,w since l(suvw) > l(suv) and l(suvw) > l(uvw). Then, we proceed by case analysis:

(a) A su,v,w > A s,uv,w and A su,v,w > A s,u,vw since s = d su and l(su) > l(s).

(b) A s,uv,w > A su,v,w since s > d su and A s,uv,w > A s,u,vw since d suv = d su and l(suv) > l(su).

(c) A s,u,vw > A su,v,w since s > d su and A s,u,vw > A s,uv,w since d su > d suv .

4.2.4. The homotopical reduction. The homotopical reduction of Gar 3 (W) with respect to Γ is the Tietze transformation π = π Γ that coherently eliminates all the collapsible cells of Γ with their corresponding redundant cell. According to the partition of the cells of Gar 3 (W), this only leaves the essential cells, i.e., those whose indexing family is essential, with source and target replaced by their image through π.

In particular, the essential 1-cells are the elements of S. By definition of Γ , the 3-functor π maps a 1-cell u of Gar 3 (W) to the element sπ(v) of S * if u . = sv and s = d u . This gives, by induction,

π(u) = s 1 • • • s n for s 1 , . . . , s n in S such that u . = s 1 • • • s n and s i = d s i •••sn
. This is sufficient to conclude that the underlying 2-polygraph of Gar 3 (W)/Γ is (isomorphic to) Artin's presentation of B + (W).

The essential 2-cells are the α s,u such that s > d su and su = w 0 (s, d su ). Hence, there is one such 2-cell for every t > s in S such that W {s,t} is finite, i.e., such that m st is finite, and its image through π has shape ts m st ⇒ st m st .

Finally, the essential 3-cells are the A s,u,v such that s > d su > d suv , su = w 0 (s, d su ) and suv = w 0 (s, d su , d suv ). Hence, there is one such 3-cell for every t > s > r in S such that W {r,s,t} is finite. If we denote by Z r,s,t the image of the corresponding 3-cell A s,u,v through π, this concludes the proof of Theorem 4.1.1.

The 3-cells of Artin's coherent presentation

Let us compute the sources and targets of the 3-cells Z r,s,t of Artin's coherent presentation. The 3-cell Z r,s,t is the image through the Tietze transformation π of the corresponding essential 3-cell A t,u,v , with u the complement of t in w 0 (s, t) and v the complement of w 0 (s, t) in w 0 (r, s, t). Since the 3-cell A t,u,v is entirely determined by its source, the shape of the 3-cell Z r,s,t is determined by the Coxeter type of the parabolic subgroup W {r,s,t} . According to the classification of finite Coxeter groups [3, Chap. VI, § 4, Theorem 1], there are five cases, shown below:

r s t A 3 r s t 4 B 3 r s t 5 H 3 r s t A 1 × A 1 × A 1 r s t p I 2 (p) × A 1 3≤p<∞
Note that we use the numbering conventions of [START_REF] Geck | Characters of finite Coxeter groups and Iwahori-Hecke algebras[END_REF]Theorem 1.1]. The resulting 3-cells are given in Figures 2 and3. The rest of this section explains their computation, mainly based on the images of the 2-cells of Gar 3 (W) through π. We detail the cases of the Coxeter types A 1 × A 1 × A 1 and A 3 . A Python script, based on the PyCox library [START_REF] Geck | PyCox: computing with (finite) Coxeter groups and Iwahori-Hecke algebras[END_REF], can be used to compute Garside's and Artin's coherent presentations for spherical Artin monoids 1 . The 3-cells Z r,s,t are also given, in "string diagrams", in [

π(α su,v ) 4 T π(α - s,u )π(v) 2 R π(suv) π(s)π(u)π(v) π(s)π(α u,v ) 7 W π(s)π(uv) π(α s,uv ) H h = (b) s > d su = d suv π(s)π(uv) π(α s,uv ) 4 T π(s)π(α - u,v ) 2 R π(suv) π(s)π(u)π(v) π(α s,u )π(v) 7 W π(su)π(v) π(α su,v ) H h = 4.3.2. The Coxeter type A 1 × A 1 × A 1 . For t > s > r in S such that W {r,s,t} is of type A 1 × A 1 × A 1 , the corresponding essential 3-cell of Gar 3 (W) is as follows: st|r α st,r 8 A t,s,r Õ % t|s|r α t,s |r C c t|α s,r 1 Q rst t|rs α t,rs V v
The image Z r,s,t of A t,s,r through π is given by the inductive application of π to the 2-cells of its source and target. For the source of Z r,s,t , we get π(α t,s |r) = γ st r and π(α st,r ) = sπ(α t,r ) 1 π(α s,rt )

= sγ rt 1 γ rs t 1 π(α rs,t )

= sγ rt 1 γ rs t.

For the target of Z r,s,t , we get π(t|α s,r ) = tγ rs and π(α t,rs ) = γ rt s 1 π(α rt,s ) = γ rt s 1 rγ st 1 π(α r,st ) = γ rt s 1 rγ st .

Hence Z r,s,t is the permutohedron, displayed as the third 3-cell of Figure 2. For the source of Z r,s,t = π(A t,st,rst ), we have π(α t,st |rst) = γ st rst and π(α sts,rst ) = stπ(α s,rst ) 1 sπ(α t,rsrt ) 1 π(α s,rstsr ).

Then, we have stπ(α s,rst ) = stγ rs t and π(α s,rstsr ) = γ rs tsr, together with sπ(α t,rsrt ) = sγ rt srt 1 srπ(α t,srt ) 1 sπ(α r,stsr ).

Finally, we get sπ(α r,stsr ) = 1 srstsr and srπ(α t,srt ) = srtπ(α st,r ) - 1 srγ st r 1 srπ(α sts,r ) = srtsγ - rt 1 srγ st r.

Wrapping up all those computations, we get the source of Z r,s,t as displayed at the top of Figure 2, where an exchange relation has been applied to contract sγ rt srt 1 srtsγ - rt into sγ rt sγ - rt . The target of Z r,s,t is obtained by similar computations.

Let us note that we can have W {r,s,t} of type A 3 , but with another ordering on the elements r, s, t. For example, if s > r > t, the 3-cell Z s,r,t is the image of A t,rt,srt through π, obtained, up to a Nielsen equivalence, as follows: one considers the 3-cell of the case r > s > t with r and s exchanged, then one replaces every occurrence of the 2-cell γ r,s , that is not in Art 2 (W) since s < r, by γ - s,r .

COHERENT PRESENTATIONS AND ACTIONS ON CATEGORIES

In this section, we establish the relationship between our results on coherent presentations of monoids and Deligne's notion of an action on a category. In particular, we obtain that Deligne's Theorem [13, Theorem 1.5] is equivalent to Theorem 3.1.3. We prove that, up to equivalence, the actions of a monoid M on categories are the same as the 2-functors from Σ to Cat, where Σ is any coherent presentation of M. for every 0-cell x of C, a 0-cell F(x) of D,

-for every 1-cell u : x → y of C, a 1-cell F(u) : F(x) → F(y) of D, -for every 2-cell f : u ⇒ v of C, a 2-cell F(f) : F(u) ⇒ F(v) of D.
As for 2-functors, the data are required to be compatible with vertical composition, in a strict way:

for all 2-cells f : u ⇒ v : x → y and g : v ⇒ w : x → y of C, we have F(f 1 g) = F(f) 1 F(g),

for every 1-cell u of C, we have F(1 u ) = 1 F(u) .

The data are also compatible with horizontal composition, but only up to coherent isomorphisms:

for all 1-cells u : x → y and v :

y → z of C, an invertible 2-cell F u,v : F(u)F(v) ⇒ F(uv) of D, natural in u and v, -for every 0-cell x of C, an invertible 2-cell F x : 1 F(x) ⇒ F(1 x ) of D.
Finally, these 2-cells are required to satisfy the following monoidal coherence relations in D:

for all 1-cells u : x → y, v : y → z and w : z → t of C,

F(y) F(v) / / F u,v Õ % F(z) F(w) F uv,w Õ % F(x) F(u) 7 7 F(uv) B B F(uvw) 5 5 F(t) = F(y) F(v) / / F(vw) 0 0 F u,vw Õ % F(z) F(w) F v,w Õ % F(x) F(u) 7 7 F(uvw) 5 5 F(t) -for every 1-cell u : x → y of C, F(x) F(u) F(x) 1 F(x) + + F(1x) E E F x @ F(u) 2 2 F 1x,u Õ % F(y) = F(x) F(u) ! ! F(u) < < 1 F(u) Õ % F(y) = F(y) 1 F(y) F(1y) ' ' F y u Ù F(x) F(u) 7 7 F(u) 2 2 F u,1y Õ % F(y)
As usual with monoidal coherence relations, this implies that, for every sequence (u 1 , . . . , u n ) of pairwise composable 1-cells in C, there exists a unique invertible 2-cell

F u 1 ,...,un : F(u 1 ) • • • F(u n ) =⇒ F(u 1 • • • u n )
in D built from the coherence isomorphisms of F. A 2-functor is just a pseudofunctor whose coherence 2-cells are identities: it can be seen as a strict 2-representation.

The notion of 2-representation has been introduced by Elgueta for 2-groups in [START_REF] Elgueta | Representation theory of 2-groups on Kapranov and Voevodsky's 2-vector spaces[END_REF]. It is also studied by Ganter and Kapranov in [START_REF] Ganter | Representation and character theory in 2-categories[END_REF] in the special case of groups. In [START_REF] Rouquier | 2-Kac-Moody algebras[END_REF], Rouquier considers the more general case of 2-representations of bicategories. Among concrete target 2-categories for 2-representations, natural choices are the 2-categories of 2-vector spaces, either from Kapranov and Voevodsky [START_REF] Kapranov | 2-categories and Zamolodchikov tetrahedra equations, Algebraic groups and their generalizations: quantum and infinite-dimensional methods[END_REF] or from Baez and Crans [START_REF] Baez | Higher-dimensional algebra. VI. Lie 2-algebras[END_REF], of 2-Hilbert spaces [START_REF] Baez | Higher-dimensional algebra. II. 2-Hilbert spaces[END_REF] or of categories [START_REF]Action du groupe des tresses sur une catégorie[END_REF].

-if x is a 0-cell of C, the 1-cell (α β) x : F(x) → H(x) of D is the composite F(x) α x / / G(x) β x / / H(x) -if u : x → y is a 1-cell of C, the invertible 2-cell (α β) u of D is defined by F(y) (α β)y F(x) F(u) 4
(α β)x * * H(y) H(x) H(u) A A (α β) u Õ % = F(y) αy F(x) F(u) 4
3 αx + + G(y) βy G(x) G(u) 8 8 βx + + α u Õ % H(y) H(x) H(u) > > β u Õ % 3
The category of 2-representations of C into D is denoted by 2Rep(C, D) and its full subcategory whose objects are the 2-functors is denoted by 2Cat(C, D). for every triple (u, v, w) of elements of M, the following diagram commutes:

T (uv)T (w) T uv,w % E = T (u)T (v)T (w) T u,v T (w) @ T (u)T v,w 4 T T (uvw) T (u)T (vw) T u,vw I i
for every element u of M, the following two diagrams commute:

T (1)T (u) T 1,u 7
T (u)

T • T (u) B b T (u) = T (u)T (1) T u,1 7
T (u)

T (u)T • B b T (u) =
This definition corresponds to the notion of unital action of M on C that Deligne considers in [START_REF]Action du groupe des tresses sur une catégorie[END_REF]. For semigroups, he proves that unital actions are equivalent to nonunital actions. For any monoid M, this fact is a consequence of the Tietze equivalence of the standard coherent presentation Std 3 (M) and the reduced standard coherent presentation Std 3 (M), given in Example 2.1.2, together with Theorem 5.1.6.

5.1.5. Remark. If S is an action of M on a category C and T is an action of M on a category D, by expanding the definition, we get that a morphism of actions α from S to T is specified by a functor F : C → D, corresponding to the component of α at the unique 0-cell of M, and, for every element u of M, a natural isomorphism α u : S(u)F ⇒ FT (u). These data must satisfy the coherence conditions of a pseudonatural transformation. Those morphisms of actions of monoids on categories differ from the ones of Deligne in [START_REF]Action du groupe des tresses sur une catégorie[END_REF]. Indeed, he considers morphisms between actions of M on the same category C, such that the functor F is the identity of C, but where the natural transformation α u is not necessarily an isomorphism: those are the icons between the corresponding pseudofunctors, as introduced by Lack in [START_REF]Icons[END_REF] as a special case of oplax natural transformations (defined as pseudonatural transformations whose component 2-cells are not necessarily invertible). Here we follow Elgueta and consider pseudonatural transformations, but the results and proofs can be adapted to icons or generalised to oplax natural transformations.

The main theorem of this section relates the coherent presentations and the 2-representations of a category. It is a direct consequence of Theorem 1.3.1 and of Proposition 5.3.2, whose proof is the objective of the rest of this section.

2-representations of cofibrant 2-categories

Let us fix 2-categories C and D, with C cofibrant. Our objective is to define a "strictification" functor

• : 2Rep(C, D) -→ 2Cat(C, D)
and to prove that it is a quasi-inverse for the canonical inclusion functor of 2Cat(C, D) into 2Rep(C, D). is an equivalence of categories that is natural in D, with quasi-inverse given by the strictification functor.

Proof. It is sufficient to check that, for every 2-representation F : C → D, there exists a pseudonatural isomorphism ϕ F : F ⇒ F that is itself natural in F. We define ϕ F as follows:

if x is a 0-cell of C, then F(x) = F(x) and we take (ϕ F ) x = 1 x , if u : x → y is a 1-cell of C, then (ϕ F ) u : F(u) ⇒ F(u) is defined as the invertible coherence 2-cell F u : F(u) ⇒ F(u).

These data satisfy the required coherence properties: the compatibility with the 2-cells of C is exactly the definition of F and the compatibility with horizontal composition and identities comes from the monoidal coherence relations of F, as already checked. Moreover, if α : F ⇒ G is a morphism of 2-representations, the naturality condition F α

! A F ϕ F @ ` α 4 T = G G ϕ G U u
corresponds, on each 1-cell u of C, to the definition of α.

2-representations and cofibrant approximations

Let us recall that, for a 2-category C, we denote by C its standard cofibrant replacement. We note that the definition of a 2-functor from C to a 2-category D is exactly the same as the one of a pseudofunctor from C to D, yielding the following isomorphism of categories:

2Rep(C, D) 2Cat( C, D).

In particular, for every monoid M, we get an isomorphism of categories:

Act(M) 2Cat( M, Cat).
In what follows, we prove that weak versions of these isomorphisms exist for all cofibrant approximations. More precisely, the category of 2-representations of a 2-category C into a 2-category D is equivalent to the one of 2-functors from any cofibrant approximation C of C into D. the functors that constitute the equivalence. This means that, for all pseudofunctors H : C → E and K : D → E, we have the following isomorphisms:

Ψ E Φ E (H) H and Φ E Ψ E (K) K.
The naturality of the equivalence means that, for all 2-categories E and E and every pseudofunctor H : E → E , the following diagrams commute: We define the pseudofunctors F : C → D and G : D → C as follows:

F = Ψ D (1 D ) and G = Φ C (1 C ).
We consider the naturality condition on Φ with E = C, E = D and H = F. This gives an equality

F • Φ C (K) = Φ D (F • K)
for every pseudofunctor K : C → C. Thus, in the special case K = 1 C , we get

FG = Φ D (F) = Φ D • Ψ D (1 D ) 1 D .
In a symmetric way, the naturality condition on Ψ gives GF 1 C , thus concluding the proof.

A combination of Proposition 5.2.3 and of Lemma 5.3.1 gives the following result. that is natural in D.

Finally, an application of Theorem 1.3.1 concludes the proof of Theorem 5.1.6. In the particular case of Artin monoids, we thus get Deligne's Theorem 1.5 of [START_REF]Action du groupe des tresses sur une catégorie[END_REF] for any Artin monoid as a consequence of Theorem 3.1.3. Moreover, Theorem 4.1.1 gives a similar result in terms of Artin's coherent presentation, formalising the paragraph 1.3 of [START_REF]Action du groupe des tresses sur une catégorie[END_REF] on the actions of B + 4 .

1. 1 . 3 .

 13 Cellular extensions. Let C be an n-category. A cellular extension of C is a set Γ equipped with a map from Γ to the set of n-spheres of C, whose value on γ is denoted by (s(γ), t(γ)). By considering all the formal compositions of elements of Γ , seen as (n+1)-cells with source and target in C, one builds the free (n + 1)-category generated by Γ over C, denoted by C[Γ ]. The quotient of C by Γ , denoted by C/Γ , is

1 .

 1 Coherent presentations of categories 1.2.3. Example (The standard coherent presentation). The standard presentation Std 2 (C) of a category C is the 2-polygraph whose cells are the 0-cells of C and a 1-cell u : x → y for every 1-cell u : x → y of C, a 2-cell γ u,v : u v ⇒ uv for all composable 1-cells u and v of C, a 2-cell ι x : 1 x ⇒ 1 x for every 0-cell x of C. The standard coherent presentation Std 3 (C) of C is Std 2 (C) extended with the following 3-cells uv w γ uv,w

  u : x → y, v : y → z and w : z → t range over the 1-cells of C. It is well known that those 3-cells form a homotopy basis of Std 2 (C) , see [32, Chap. VII, § 2, Corollary].

2. 1 . 2 .

 12 Example (The reduced standard coherent presentation). Let C be a category. One can reduce the standard coherent presentation Std 3 (C) of C, given in Example 1.2.3 into the smaller reduced standard coherent presentation Std 3 (C) of C. It is obtained from Std 3 (C) by a Tietze transformation that performs the following coherent eliminations, the resulting coherent presentation of the category C being detailed in [22, 4.1.6]:

2. 2 . 5 . 1 .

 251 Theorem. For every terminating presentation Σ of a category C, the homotopical completion S(Σ) of Σ is a coherent convergent presentation of C. 2.2.6. Example. From[START_REF] Kapur | A finite Thue system with decidable word problem and without equivalent finite canonical system[END_REF], we consider the presentation Σ = s, t, a ; ta α 7 W as , st β 7 W a ofB + 3 = B + (S3), obtained from Artin's presentation by coherent adjunction of the Coxeter element st and the 2-cell β. The deglex order generated by t > s > a proves the termination of Σ. The homotopical completion of Σ is the (3, 1)-polygraph S(Σ) = s, t, a ; ta α 7 W as , st β 7 W a , sas γ 7 W aa , saa δ 7 W aat ; A, B, C, D where A, B, C and D are the following 3-cells, induced by completion of critical pairs (βa, sα) and (γt, saβ): Generic homotopical reduction. Let Σ be a (3, 1)-polygraph. A collapsible part of Σ is a triple Γ = (Γ 2 , Γ 3 , Γ 4 ) made of a family Γ 2 of 2-cells of Σ, a family Γ 3 of 3-cells of Σ and a family Γ 4 of 3-spheres of Σ , such that the following conditions are satisfied:

  defines a Tietze transformation π Γ : Σ → Σ /Γ by well-founded induction, called the homotopical reduction of Σ with respect to Γ . The target (3, 1)-category is freely generated by the (3, 1)-polygraph Σ/Γ obtained from Σ by removing the cells of Γ and of the corresponding redundant cells, and by replacement of the source and target maps of Σ by their compositions with π Γ . Moreover, by construction, the (3, 1)-polygraph Σ/Γ is Tietze-equivalent to Σ.

2. 3 . Homotopical reduction 2 . 3 . 2 .

 3232 Generating triple confluences. The coherent elimination of 3-cells of a (3, 1)-polygraph Σ by homotopical reduction requires a collapsible set of 3-spheres of Σ . When Σ is convergent and coherent, its triple critical branchings generate a convenient way to build such a set.We recall from[START_REF]Higher-dimensional normalisation strategies for acyclicity[END_REF] that a local triple branching is a triple (f, g, h) of rewriting steps with a common source. Like branchings, local triple branchings are classified into three families:aspherical triple branchings have two of their 2-cells equal, -Peiffer triple branchings have at least one of their 2-cells that form a Peiffer branching with the other two,overlap triple branchings are the remaining local triple branchings.

2. 3 . 4 .

 34 Theorem. For every terminating presentation Σ of a category C, the homotopical completionreduction R(Σ) of Σ is a coherent presentation of C. 2.3.5. Example. In Example 2.2.6, we have obtained a coherent convergent presentation S(Σ) of B + 3 by homotopical completion. We consider the collapsible part Γ of S(Σ) consisting of the two generating triple confluences 3-cells A and B coherently adjoined with the 2-cell γ and δ during homotopical completion and the 2-cell β : st ⇒ a that defines the redundant generator a. We have that ω 1 , ω 2 , A, B and β are collapsible (up to a Nielsen transformation), with respective redundant cells C, D, γ, δ and a.

  2 (W) whose 1-cells are the elements of W \ {1} and with one 2-cell α u,v : u|v ⇒ uv whenever l(uv) = l(u) + l(v) holds. Here, we write uv for the product in W and u|v for the product in the free monoid over W. We denote by Gar 3 (W) the extended presentation of B + (W) obtained from Gar 2 (W) by adjunction of one 3

3. 2 . 1 .

 21 Proposition. For every Coxeter group W, the Artin monoid B + (W) admits, as a coherent convergent presentation, the (3, 1)-polygraph S(Gar 2 (W)) with one 0-cell, one 1-cell for every element of W \ {1}, the 2-cells u|v α u,v 7 W uv and u|vw β u,v,w 7 W uv|w, respectively for every u, v of W \ {1} with u v and every u, v, w of W \ {1} with u v w ×

Figure 1 :

 1 Figure 1: The 3-cells of the homotopical completion of Garside's presentation

7 W

 7 u|β vw,x,y 7 W u|vwx|y The first branching occurs when u v w x × , splitting into the two disjoint possibilities u v w x × and u v w x × × , respectively corresponding to the 3-cells C u,v,w,x and D u,v,w,x . The second branching appears when u v w x × and corresponds to the 3-cell E u,v,w,x . The third branching happens when u v w x y × , with the extra condition that l(vwxy) < l(vw) + l(xy) since vw|xy is the source of the 2-cell β vw,x,y : this situation splits into the two disjoint possibilities u v w x y

3 .---|y 3 . 3 .- 1 × and u v 2 w 2 ×

 33312 Garside's coherent presentation of Artin monoids-The 3-sphere ω D u,v,w,x in the case u v w x The 3-sphere ω E u,v,w,x in the case u v w x The 3-sphere ω F u,v,w,x,y in the case u v w x y The 3-sphere ω G u,v,w,x,y in the case u v w x y Garside's coherent presentation for Garside monoids -The 3-sphere ω H u,v,w,x in the case u v w x The 3-sphere ω I u,v 1 ,w 1 ,v 2 ,w 2 in the case u v 1 w

  Moreover, the elements s 1 ,. . . , s k have u 1 • • • u k as common multiple, so that their with either (a) s = d su or (b) s > d su = d suv and su = w 0 (s, d su ). Those 3-cells are collapsible up to a Nielsen transformation, and the corresponding redundant 2-cells are: (a) α su,v ; or (b) α s,uv . By hypothesis, the indexing pairs (su, v) and (s, uv) are redundant, so that none of those 2-cells is in Γ .

  s = d su , (b) s > d su = d suv and su = w 0 (s, d su ), (c) s > d su > d suv = d suvw and suv = w 0 (s, d su , d suv ).

Figure 3 :

 3 Figure 3: The 3-cells Z r,s,t for Coxeter type H 3 and I 2 (p) × A 1 , p ≥ 3

5. 1 . 2 -

 12 representations of 2-categories 5.1.1. 2-representations. We recall from[START_REF] Elgueta | Representation theory of 2-groups on Kapranov and Voevodsky's 2-vector spaces[END_REF] that, given 2-categories C and D, a 2-representation of C in D is a pseudofunctor F : C → D. This is a weakened notion of 2-functor, specified by:

5. 1 . 3 .

 13 Categories of 2-representations. If F, G, H : C → D are 2-representations and if α : F ⇒ G and β : G ⇒ H are morphisms of 2-representations, the composite morphism α β : F ⇒ H is defined by:

5. 1 . 4 .

 14 Actions of monoids on categories. If M is a monoid, we see it as a 2-category with exactly one 0-cell •, with the elements of M as 1-cells and with identity 2-cells only. We define the category of actions of M on categories as the category Act(M) = 2Rep(M, Cat) of 2-representations of M in Cat. Expanding the definition, an action T of M is specified by a category C = T (•), an endofunctor T (u) : C → C for every element u of M, a natural isomorphism T u,v : T (u)T (v) ⇒ T (uv) for every pair (u, v) of elements of M and a natural isomorphism T • : 1 C ⇒ T (1) such that:

5. 1 . 6 .

 16 Theorem. Let C be a category, let Σ be an extended presentation of C. The following assertions are equivalent: i) the (3, 1)-polygraph Σ is a coherent presentation of C; ii) for every 2-category C, there is an equivalence of categories 2Rep(C, C) ≈ 2Cat(Σ, C) that is natural in C.

5. 2 . 1 .

 21 Strictification of 2-representations. Let F : C → D be a 2-representation. Let us define the 2-functor F : C → D, dimension after dimension. On 0-cells, F takes the same values as F. Since C is cofibrant, its underlying 1-category is free: on generating 1-cells, F is equal to F and, then, it is extended by functoriality on every 1-cell. Hence, if u = a 1 • • • a n is a 1-cell of C, where the a i s are generating 1-cells, we haveF(u) = F(a 1 ) • • • F(a n ).From the monoidal coherence relations satisfied by F, there is a unique invertible 2-cell in DF(u) = F(a 1 ) • • • F(a n ) F a 1 ,...,an 7 W F(a 1 • • • a n ) = F(u)5.3. 2-representations and cofibrant approximations 5.2.3. Proposition. Let C be a cofibrant 2-category. For every 2-category D, the canonical inclusion 2Cat(C, D) -→ 2Rep(C, D)

5. 3 . 1 .

 31 Lemma. Let C and D be 2-categories. The following assertions are equivalent: i) the 2-categories C and D are pseudoequivalent, i.e., there exist pseudofunctors F : C → D and G : D → C such that GF 1 C and FG 1 D ;ii) for every 2-category E, there is an equivalence of categories2Rep(C, E) ≈ 2Rep(D, E)that is natural in E.Proof. Let us assume that C and D are pseudoequivalent. As a consequence, for all pseudofunctors H : C → E and K : D → E, we have: Thus the functors 2Rep(F, E) and 2Rep(G, E), respectively sending a pseudofunctor K : D → E to KF and a pseudofunctor H : C → E to HG, form the required equivalence of categories. Conversely, let us assume that, for every 2-category E, we have 2Rep(C, E) ≈ 2Rep(D, E) natural in E. We denote by Φ E : 2Rep(C, E) → 2Rep(D, E) and Ψ E : 2Rep(D, E) → 2Rep(C, E)

  , E ) Ψ E / / 2Rep(C, E ).

5. 3 . 2 .

 32 Proposition. Let C and C be 2-categories, with C cofibrant. The following assertions are equivalent: i) the 2-category C is a cofibrant approximation of C; ii) for every 2-category D, there is an equivalence of categories 2Rep(C, D) ≈ 2Cat( C, D)

  Proposition 2.3]. Moreover, if v is in W, seen as an element of B If two elements u and v of B + (W) have a common multiple, then they have a least common multiple, lcm for short [4, Proposition 4.1]. 3.1.2. Garside's coherent presentation. Let W be a Coxeter group. We call Garside's presentation of B + (W) the 2-polygraph Gar

+ (W) by the canonical embedding (given by Matsumoto's theorem, see [20, Theorem 1.2.2]), then we also have u and u in W and uu . = v.

  Projection of the 2-cells of Garside's presentation. By construction, the image of a 2-cell α u,v of Gar 3 (W) through π is given by induction, depending on whether it is essential, collapsible or redundant.The essential 2-cells are the α t,u such that t > s and u is the complement of t in w 0 (s, t), where s = d tu . The image of α t,u is the corresponding braid relation:

	4. Artin's coherent presentation of Artin monoids
		srstrsrsrtsrsrt @ `srsrtstrsrtsrst 7 W srsrtsrstrsrsrt 7 W srsrtsrstsrsrst 7 W srsrtsrtstrsrst
	srstsrsrstsrsrt i	stγ rs t	strsrt @ `rsrtsr sγ rt sγ -rt 7 W srtstr srγ st r 7 W srstsr γ rs tsr	# C
	i stsrst i srtstrsrtstrsrt				8 i	Õ % Õ % srsrstsrsrtsrst
	γ st rst srtsrtstrsrtstr i					rsγ rt sr rsrsrtsrsrtsrst i
	tstrst i srtsrstsrsrstsr tsγ rt st Õ % tsrtst srtsrstrsrsrtsr i			Z r,s,t Õ %	rstrsr i V v rstsrs rstγ rs rsrstrsrsrtsrst i rsrstsrsrstsrst i
	strsrsrtsrsrtsr i					rsrtstrsrtstrst i
	tsrγ st i stsrsrstsrsrtsr	4 T tsrsts tγ rs ts	7 W trsrts	γ rt sγ -rt s 7 W rtstrs	rγ st rs	rsrtsrtstrsrtst i
	srtsrtstr srtsγ -rt str 7 W srtstrstr srγ st rsγ rt 7 W srstsrsrt srstγrst 7 W srstrsrst 9 Y srsγ rt srst 7 W srsrtsrst Õ % sγ rt srγ -st r tsrtsrstsrstrsr tstrsrstsrsrtsr Z r,s,t Õ %	γrstsrst rsrtsrstrsrsrts i rsrtsrstsrsrsts i
	Õ % strsrstsr stγrstsr i tsrtsrtstrstrsr Õ % tsrtstrsrtstrsr					8 rsrstsrst rstrsrsrtsrsrts i i rsrγ st rst rstsrsrstsrsrts i
	stsrsrtsr γ st rsrtsr i Õ % tsrstsrsrstsrsr					rsrtstrst i rsrtsγ -rt st rtstrsrtstrsrts i
	tstrsrtsr tsγ rt sγ -Õ % tsrstrsrsrtsrsr rt sr Õ % tsrtstrsr tsrγ st rsr Õ % tsrstsrsr Õ % tsrsrtsrstrsrsr Õ % tsrsrtsrstsrsrs				Z r,s,t Õ %	rsrtsrtst rsγ rt srγ -st i rtsrtstrsrtstrs i rstrsrsts rstsrsrts i rtsrstsrsrstsrs i rstγrsts V v rtsrstrsrsrtsrs Q q
	tsrstγrs	5 U tsrstrsrs tsrsγ rt srs 7 W tsrsrtsrs tγrstsrs 7 W trsrstsrs γ rt srγ -st rs 7 W rtsrtstrs rtsγ -rt strs 7 W rtstrstrs 4 T tsrsrtsrtstrsrs 7 W tsrsrtstrsrtsrs 7 W tsrsrstsrsrtsrs 7 W trsrsrtsrsrtsrs	rγ st rsγ rt s
	Definition 4.3]. γ st rs p-1	str @ tγ sγ rt 7 W srt st rs p-1 sγ rt rs p-2 γ st r 7 W (• • • ) 9 Y	γ rs t 7 W	sr p t	γ rs t	15,
	Figure 2: The 3-cells Z r,s,t for Coxeter types A 3 , B 3 and A 1 × A 1 × A 1 tγ rs 6 V t rs p γ rt sr p-1 7 W rt sr p-1 rγ st sr p-2 7 W (• • • ) 4.3.1. π(α t,u ) = γ s,t . 4 tsr rs 4 T rst trs γ rt s 7 W rts rγ st Z r,s,t Õ % Z r,s,t Õ % t sr p	9 rs p t U u

  4.3.3. The Coxeter type A 3 . If W {r,s,t} is of type A 3 with t > s > r, the corresponding essential 3-cell of Gar 3 (W) is as follows:

	sts|rst α t,st |rst B b	α sts,rst
	t|st|rst	A t,st,rst Õ %	# C rst R r
	t|α st,rst 2 R t|rsrts	α t,rsrts

http://www.pps.univ-paris-diderot.fr/~guiraud/cox/cox.zip

fruitful exchanges and meaningful suggestions. This work has been partially supported by the project Cathre, ANR-13-BS02-0005-02.

lcm w 0 (s 1 , . . . , s k ) exists and divides u 1 • • • u k , and each subgroup W s 1 ,...,s k is finite. Thus, we have the following diagram, where each arrow u → v means that u is a divisor of v: w 0 (s 1 ) / / w 0 (s 1 , s 2 ) / / (• • • ) / / w 0 (s 1 , . . . , s n-1 ) / / w 0 (s 1 , . . . , s n )

If every vertical arrow is an equality, we say that (u 1 , . . . , u n ) is essential. Since each u k is different from 1, this implies that no horizontal arrow is an equality, so that s 1 > • • • > s n holds. Moreover, we have u 1 = s 1 and, by uniqueness of the complement, we get that each u k+1 is the complement of w 0 (s 1 , . . . , s k ) in w 0 (s 1 , . . . , s k+1 ). Thus, the family (u 1 , . . . , u n ) is uniquely determined by the elements s 1 , . . . , s n of S such that

Otherwise, there exists a minimal k in {1, . . . , n} such that (u 1 , . . . , u k ) is not essential, i.e., such that

there are two possibilities, depending on whether w 0 (s 1 , . . . , s k-1 ) and w 0 (s 1 , . . . , s k ) are equal or not, which is equivalent to the equality

= vw (i.e., u k = vw and v w ), with v and w in W \ {1} such that (u 1 , . . . , u k-1 , v) is essential: we say that (u 1 , . . . , u n ) is redundant.

Finally, if k = 1 and (u 1 ) is not essential, we have u 1 = s 1 w with w in W \ {1} and we say that (u 1 ) is redundant.

By construction, the family (u 1 , . . . , u n ) is either essential, collapsible or redundant. This induces a partition of the cells of Gar 3 (W) and the spheres of Gar 4 (W) in three parts. 4.2.2. The well-founded order. Finally, we define a mapping

. We equip the target set with the well-founded lexicographic order generated by the natural order on N and the fixed order on S. We compare families (u 1 , . .

The cells of Gar 3 (W) are then compared according to their indices.

The collapsible part of Gar 3 (W).

We define Γ as the collection of all the 2-cells and 3-cells of Gar 3 (W) and all the 3-spheres of Gar 4 (W) whose indexing family is collapsible. Let us check that Γ is a collapsible part of Gar 3 (W).

The 2-cells of Γ are the α s,u : s|u ⇒ su with s = d su . Each one is collapsible, the corresponding redundant 1-cell is su and we have su > s and su > u because l(su) > l(s) and l(su) > u.

The for every 0-cell x of C, a 1-cell α x :

for every 1-cell u : x → y of C, an invertible 2-cell of D as follows

These data must satisfy several coherence relations:

) )

for all 1-cells u : x → y and v : y → z of C,

2-representations of cofibrant 2-categories

from F(u) to F(u), built from the coherence 2-cells of F. Since the decomposition of u in generators is unique, we simply denote this 2-cell by F u . Let f : u ⇒ v : x → y be a 2-cell of C. We define F(f) as the following composite 2-cell of D, where the double arrows, which always go from top to bottom, have been omitted for readability:

As a direct consequence, we get that F is compatible with vertical composition and identities of 1-cells. Hence, we have defined a 2-functor F from C to D. We note that the monoidal coherence relations satisfied by F imply that, if u : x → y and v : y → z are 1-cells of C, we have

and, if x is a 0-cell of C, we have F 1x = F x .

Strictification of morphisms of 2-representations.

Let F, G : C → D be 2-representations and let α : F ⇒ G be a morphism between them. Let us define a pseudonatural transformation α : F ⇒ G. For a 0-cell x of C, we take α x = α x . If u : x → y is a 1-cell of C, we define α u as the following invertible 2-cell of D:

This defines a pseudonatural transformation α : F ⇒ G. Indeed, if x is a 0-cell of C, we have:

Then, if u : x → y and v : y → z are 1-cells of C, we get: With similar computations, we check that strictification is compatible with the composition of morphisms of 2-representations and with identities, so that it is a functor from 2Rep(C, D) to 2Cat(C, D).