Yves Guiraud -Philippe Malbos

M.S.C 2000 -18c10

HIGHER-DIMENSIONAL NORMALISATION STRATEGIES FOR ACYCLICITY

Keywords: rewriting, polygraphic resolution, homology of small categories, identities among relations

We introduce acyclic polygraphs, a notion of complete categorical cellular model for (small) categories, containing generators, relations and higher-dimensional globular syzygies. We give a rewriting method to construct explicit acyclic polygraphs from convergent presentations. For that, we introduce higher-dimensional normalisation strategies, defined as homotopically coherent ways to relate each cell of a polygraph to its normal form, then we prove that acyclicity is equivalent to the existence of a normalisation strategy. Using acyclic polygraphs, we define a higher-dimensional homotopical finiteness condition for higher categories which extends Squier's finite derivation type for monoids. We relate this homotopical property to a new homological finiteness condition that we introduce here.

INTRODUCTION

An overview of Squier's theory

In the eighties, Squier has established a link between some computational, homological and homotopical properties of monoids, [START_REF] Craig | Word problems and a homological finiteness condition for monoids[END_REF][START_REF] Squier | A finiteness condition for rewriting systems[END_REF]. This allowed him to answer an open question: does a finitely generated monoid with a decidable word problem always admit a finite convergent presentation?

1.1.1. The word problem and rewriting theory. Given a monoid M, a generating set Σ 1 for M provides a way to represent the elements of M in the free monoid Σ * 1 , i.e., as finite words written with the elements of Σ 1 . But, if M is not free, there is no reason for an element of M to have a single representative in Σ * 1 . The word problem for M consists in finding a generating set Σ 1 and an algorithm that can determine whether or not any two elements of Σ * 1 represent the same element of M. One way to solve the word problem is to exhibit a finite presentation (Σ 1 , Σ 2 ) of M with a good computational property, called convergence in rewriting theory. There, one studies presentations where the relations in Σ 2 are not seen as equalities between the words in Σ * 1 , such as u = v, but, instead, as rewriting rules that can only be applied in one direction, like u ⇒ v, simulating a non-reversible computational process. Convergence is defined as the conjunction of the following two conditions:

• termination, i.e., all the computations end eventually,

• confluence, i.e., different computations on the same input lead to the same result.

A finite convergent presentation (Σ 1 , Σ 2 ) of M gives a solution to the word problem: the normal form algorithm. Given an element u in Σ * 1 , convergence ensures that all the applications of directed relations to u, in any possible manner, will eventually produce a unique result: an element u of Σ * 1 where no directed relation applies anymore, called the normal form of u. And, by construction, two elements u and v of Σ * 1 represent the same element of M if, and only if, their normal forms are equal in Σ * 1 . Finally, finiteness ensures that one can determine if an element of Σ * 1 is a normal form, by examining all the relations. (As far as rewriting is concerned, this article is self-contained, but this wider mathematical field is covered in more details by Book and Otto, [START_REF] Book | String-rewriting systems[END_REF], Baader and Nipkow, [START_REF] Baader | Term rewriting and all that[END_REF], and the group Terese, [START_REF]Term rewriting systems[END_REF].) Thus, if a monoid admits a finite convergent presentation, it has a decidable word problem. In the middle of the eighties, it was still unknown if the converse implication held. In [START_REF] Kapur | A finite Thue system with decidable word problem and without equivalent finite canonical system[END_REF], Kapur and Narendran had exhibited a monoid that admits a finite generating set for which the word problem was solvable, but that do not admit a finite convergent presentation with the same generators. However, this did not answer the original question, the generating set having been fixed.

1.1.2. From computational to homological properties. At that time, Squier linked the existence of a finite convergent presentation to a homological invariant of the monoid, the homological type left-FP 3 , that is independent of the choice of a presentation of M and, in particular, of a generating set. A monoid M has homological type left-FP 3 when there exists an exact sequence

P 3
/ / P 2 / / P 1 / / P 0 / / Z / / 0 of (left) modules over M, where Z denotes the trivial M-module and each P i is projective and finitely generated.

An overview of Squier's theory

From a presentation (Σ 1 , Σ 2 ) of M, one can build an exact sequence of free M-modules

ZM[Σ 2 ] J / / ZM[Σ 1 ] / / ZM / / Z / / 0, (1)
where ZM[Σ 1 ] and ZM[Σ 2 ] are the free M-modules over Σ 1 and Σ 2 , respectively. The differential J, called the Fox Jacobian after [START_REF] Fox | Free differential calculus. I. Derivation in the free group ring[END_REF], is defined on a directed relation α :

u ⇒ v by J(α) = [u] -[v],
where [ • ] is the unique derivation of Σ * 1 with values in ZM[Σ 1 ] that extends the canonical inclusion of

Σ 1 into ZM[Σ 1 ].
In [START_REF] Craig | Word problems and a homological finiteness condition for monoids[END_REF], Squier proved that, when (Σ 1 , Σ 2 ) is a convergent presentation, its critical branchings form a generating set of the kernel of the Fox Jacobian. A critical branching of (Σ 1 , Σ 2 ) is an overlapping application of two different directed relations on the same word u of Σ * 1 , where u has minimal size. For example, the relations α : Squier proves that the set Σ 3 of critical branchings of (Σ 1 , Σ 2 ) and the boundary J extend the exact sequence (1) by one step:

ZM[Σ 3 ] J / / ZM[Σ 2 ] J / / ZM[Σ 1 ] / / ZM / / Z / / 0. (2)
Moreover, when (Σ 1 , Σ 2 ) is finite, then Σ 3 is finite, proving that, if a monoid has a finite convergent presentation, then it is of homological type left-FP 3 . Finally, Squier exhibited a finitely generated monoid, with a decidable word problem, but that is not of homological type left-FP 3 . This gave a negative answer to the aforementioned open question: there exist finitely generated monoids with a decidable word problem that do not admit a finite convergent presentation (for any possible finite set of generators).

Introduction

To define this invariant, for a monoid M with a presentation (Σ 1 , Σ 2 ), Squier constructs a cellular complex S(Σ 1 , Σ 2 ) with one 0-cell, whose 1-cells are the elements of the free monoid Σ * 1 and whose 2-cells are generated by the relations of Σ 2 . More precisely, there is a 2-cell between every pair of words with shape wuw and wvw such that u = v is a relation in Σ 2 . Then, to get S(Σ 1 , Σ 2 ), one fills with 3-cells all the squares formed by independent applications of relations, such as the following one, where (u 1 , v 1 ) and (u 2 , v 2 ) are relations in Σ 2 :

wv 1 w u 2 w u 2 = v 2 wu 1 w u 2 w u 1 = v 1 u 2 = v 2 wv 1 w v 2 w wu 1 w v 2 w u 1 = v 1
If Σ 3 is a set of 3-cells over S(Σ 1 , Σ 2 ), then the set Σ * 1 Σ 3 Σ * 1 is the set of 3-cells uβv, with β in Σ 3 and u and v in Σ * 1 , and whose boundary is the one of β multiplied by u on the left and v on the right. A homotopy basis of (Σ 1 , Σ 2 ) is a set Σ 3 of 3-cells such that Σ * 1 Σ 3 Σ * 1 makes the complex S(Σ 1 , Σ 2 ) contractible. A monoid is of finite derivation type (FDT 3 ) if it admits a finite presentation whose associated complex admits a finite homotopy basis or, in other words, whose "relations among the relations" are finitely generated.

Squier proves that, given a convergent presentation (Σ 1 , Σ 2 ), it is sufficient to attach one 3-cell to each 3-dimensional sphere corresponding to a critical branching to get a homotopy basis of (Σ 1 , Σ 2 ). Moreover, if Σ 2 is finite, the presentation (Σ 1 , Σ 2 ) has finitely many critical branchings proving that, if a monoid admits a finite convergent presentation, then it is FDT 3 . Squier used this result to give another proof that there exist finitely generated monoids with a decidable word problem that do not admit a finite convergent presentation.

1.1.4. Refinements of Squier's conditions. By his results, Squier has opened two different directions, one homological and one homotopical, to explore in the quest for a complete characterisation of the existence of finite convergent presentations in the case of monoids. The corresponding invariants are related: FDT 3 implies left-FP 3 , as proved by several authors, [START_REF] Cremanns | Finite derivation type implies the homological finiteness condition FP 3[END_REF][START_REF] Stephen | Low-dimensional homotopy theory for monoids[END_REF][START_REF] Lafont | A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)[END_REF]. The converse implication is false in general, as already noted by Squier in [START_REF] Squier | A finiteness condition for rewriting systems[END_REF], yet it is true in the special case of groups, [START_REF]For groups the property of having finite derivation type is equivalent to the homological finiteness condition FP 3[END_REF], the latter result being based on the Brown-Huebschmann isomorphism between homotopical and homological syzygies, [START_REF] Brown | Identities among relations, Low-dimensional topology[END_REF].

However, the invariants left-FP 3 and FDT 3 are not complete characterisations of the property to admit a finite convergent presentation: they are necessary, but not sufficient conditions, as already proved by Squier in [START_REF] Squier | A finiteness condition for rewriting systems[END_REF]. Following this observation, various refinements of both invariants have been explored.

In the homological direction, thanks to the notion of Abelian resolution, one defines the more restrictive conditions left-FP n , for every natural number n > 3, and left-FP ∞ : a monoid M has homological type left-FP ∞ when there exists a resolution of the trivial M-module by finitely generated and projective M-modules. In [START_REF] Kobayashi | Complete rewriting systems and homology of monoid algebras[END_REF], a notion of n-fold critical branching is used to complete the exact sequence (2) into a resolution, obtaining the following implication: if a monoid admits a finite convergent presentation, then it is of homological type left-FP ∞ , the converse implication still being false in general. The same results are also known for associative algebras, [START_REF] Anick | On the homology of associative algebras[END_REF], and for groups, [START_REF] Daniel | A monoid which is right-FP ∞ but not left-FP 1[END_REF][START_REF] Brown | The geometry of rewriting systems: a proof of the Anick-Groves-Squier theorem, Algorithms and classification in combinatorial group theory[END_REF][START_REF] John | Rewriting systems and homology of groups, Groups-Canberra[END_REF]. One can obtain similar 1.2. Organisation and main results of the article implications with the properties right-FP ∞ and bi-FP ∞ , defined with resolutions by right modules and bimodules, respectively.

In the homotopical direction, the condition FDT 3 has been refined into FDT 4 , a property about the existence of a finite presentation with a finite homotopy basis, itself satisfying a homotopical finiteness property, [START_REF] Mcglashan | Pride, Finiteness conditions for rewriting systems[END_REF]. The condition FDT 4 is also necessary for a monoid to admit a finite convergent presentation and it is sufficient, but not necessary, for the conditions left/right/bi-FP 4 .

1.2. Organisation and main results of the article 1.2.1. Polygraphic resolutions. In Section 2, we introduce a notion of homotopical resolution that generalises Squier's complex, in order to define the homotopical finiteness conditions FDT n and FDT ∞ . Squier's complex appears as the first two dimensions of a free (∞, 1)-category, i.e., a free ∞-category whose cells of dimension 2 and higher are invertible. Then, homotopy bases and higher homotopy bases generate the higher dimensions of this (∞, 1)-category, in such a way that the latter is homotopically equivalent to the starting monoid. Moreover, these resolutions further generalise from monoids to pcategories, yielding free (∞, p)-categories.

More explicitly, let (Σ 1 , Σ 2 ) be a presentation of a monoid M. Such a presentation of a monoid, or more generally of a (small) category, is called a (2, 1)-polygraph in this article. The terminology comes from Burroni's polygraphs, [START_REF] Burroni | Higher-dimensional word problems with applications to equational logic[END_REF], also known as Street's computads, [START_REF] Street | Limits indexed by category-valued 2-functors[END_REF][START_REF]The algebra of oriented simplexes[END_REF]. From the (2, 1)-polygraph (Σ 1 , Σ 2 ), we generate a free (2, 1)-category Σ 2 by taking all the formal composites of 2-cells, modulo exchange relations that correspond exactly to the 2-cells of Squier's complex associated to (Σ 1 , Σ 2 ). Informally, the (2, 1)-category Σ 2 is homotopically equivalent to Squier's complex: this allows us to see a homotopy basis as a set Σ 3 of 3-cells, attached to Σ 2 , such that the quotient (2, 1)-category Σ 2 /Σ 3 is homotopically equivalent to the original monoid or, equivalently, such that any parallel 2-cells of Σ 2 are identified in the quotient by Σ 3 .

Then, one considers the free (3, 1)-category Σ 3 generated by the (3, 1)-polygraph (Σ 1 , Σ 2 , Σ 3 ). One defines a homotopy basis of Σ 3 as a set of 4-cells over Σ 3 that relate every parallel 3-cells. The same idea is used to define homotopy bases in every dimension, yielding our notion of polygraphic resolution of the monoid M: this is an acyclic (∞, 1)-polygraph Σ = (Σ n ) n≥1 such that (Σ 1 , Σ 2 ) is a presentation of M, where acyclic means that each Σ n+1 is a homotopy basis of the free (n, 1)-category Σ n , for n ≥ 3.

The notion we get is close to Métayer's polygraphic resolutions, introduced in [START_REF] Métayer | Resolutions by polygraphs[END_REF]: these are ∞polygraphs that produce cofibrant approximations (free objects that are homotopically equivalent to the original one) in the canonical model structure on ∞-categories, described in [START_REF] Lafont | A folk model structure on omega-cat[END_REF]. Our resolutions, called (∞, p)-polygraphs, have the same good homotopical properties, with respect to the canonical model structure on (∞, p)-categories, obtained by Ara and Métayer, [START_REF] Ara | The Brown-Golasiński model structure on strict ∞-groupoids revisited[END_REF]. We say that a monoid and, more generally, a p-category is of finite ∞-derivation type (FDT ∞ ) when it admits a polygraphic resolution with finitely many cells in every dimension. This generalises to higher categories and in every dimension the two previously known homotopical finiteness conditions, FDT 3 introduced by Squier for monoids and its refinement FDT 4 .

1. Introduction 1.2.2. Normalisation strategies for polygraphs. In Section 3, we give a constructive characterisation of the acyclicity of an (∞, 1)-polygraph. Let Σ be a polygraphic resolution of a monoid M. In particular, if π : Σ * 1 M denotes the canonical projection, one can choose a (non-functorial) section ι of π. Moreover, the 2-cells of Σ 2 are generating relations for M: for every element u of Σ * 1 , one can choose a 2-cell σ u : u ⇒ ιπ(u) in Σ 2 . Then, we use that Σ 3 is a homotopy basis: for every 2-cell f : u ⇒ v of Σ 2 , one can choose a 3-cell σ f in Σ 3 with shape

u f 2 4 σ u 1 3 v σ v k ιπ(u) = ιπ(v) σ f

Õ

From the acyclicity of Σ, we deduce that similar choices can be made in every dimension, in a coherent way: if π : Σ M and ι : M Σ are now seen as (weak) ∞-functors, then σ is a (weak) natural isomorphism from the identity of Σ to the composite (weak) ∞-functor ιπ.

We call σ a normalisation strategy. It generalises to every dimension the notion of strategy appearing in rewriting theory: a canonical way, among all the computations generated by the directed relations, to reduce a word into a normal form. An (∞, 1)-polygraph with a normalisation strategy is normalising. Theorem 3.3.6. An (n, 1)-polygraph is acyclic if, and only if, it is normalising.

Moreover, a normalisation strategy can always be assumed to commute with the monoid product in a sensible way: it can always "reduce" a word by starting on the left or on the right. This leads to the left-normalising and right-normalising properties for (∞, 1)-polygraphs, which are also equivalent to acyclicity.

1.2.3. Polygraphic resolutions from convergent presentations. In Section 4, we use normalisation strategies to build, by induction on the dimension, an explicit polygraphic resolution from a convergent presentation. Given a convergent (2, 1)-polygraph Σ, the first dimensions of the polygraphic resolution c ∞ (Σ) we get are similar to the ones of Squier's complex: generators in dimension 1, generating relations in dimension 2, critical branchings in dimension 3. Then, we build the 4-cells from the critical triple branchings, i.e., the minimal overlappings of three 2-cells on the same 1-cell: for such a (f, g, h), we use a normalisation strategy σ to build the corresponding 4-cell

v σ v # A Õ v σ v # C Õ u f E A g 7 9 h ( 0 w B Õ σ w 7 9 u 1 ? u f E A h ( 0 u x σ x P x σ x P
where A, B and C are 3-cells built by using the critical branchings and the normalisation strategy σ.

In higher dimensions, we proceed similarly to build the (n + 1)-cells of the resolution from the critical n-fold branchings.

1.3. Acknowledgements Theorem 4.5.3. If Σ is a convergent presentation of a category C, then the (∞, 1)- polygraph c ∞ (Σ) is a polygraphic resolution of C.
Since a finite convergent (2, 1)-polygraph has finitely many n-fold critical branchings, a category with a finite convergent presentation is FDT ∞ .

1.2.4. Abelianisation of polygraphic resolutions. In Section 5, we relate the homotopical finiteness condition FDT ∞ to a new homological finiteness condition, called FP ∞ . For that, from a polygraphic resolution Σ of a category C, we deduce a free Abelian resolution

• • • δ n+1 / / F C [Σ n ] δ n / / F C [Σ n-1 ] δ n-1 / / • • • δ 2 / / F C [Σ 1 ] δ 1 / / F C [Σ 0 ] ε / / Z / / 0
in the category of natural systems on C, a generalisation of bimodules due to Baues, see [START_REF] Baues | Combinatorial homotopy and 4-dimensional complexes[END_REF]. This complex, denoted by F C [Σ], is called the Reidemeister-Fox-Squier complex of Σ and extends Squier's exact sequence [START_REF] Ara | The Brown-Golasiński model structure on strict ∞-groupoids revisited[END_REF]. The acyclicity of F C [Σ] is proved by using a contracting homotopy induced by a normalisation strategy.

Theorem 5.4.3. If Σ is a polygraphic resolution of a category C, then the Reidemeister-Fox-Squier complex F C [Σ] is a free resolution of the constant natural system Z on C.

We define the homological properties FP n , for any n, and FP ∞ as the refined versions of left/right/bi-FP n and left/right/bi-FP ∞ with natural systems instead of left/right/bi-modules. We get that, for categories, the property FDT n implies FP n and, as a consequence, that a category with a finite convergent presentation is of homological type FP ∞ . Finally, we relate the homological 2-syzygies of a presentation Σ to its identities among relations, defined by the authors in [START_REF]Identities among relations for higher-dimensional rewriting systems[END_REF].

Theorem 5.6.5. For every 2-polygraph Σ, the natural systems of homological 2-syzygies and of identities among relations of Σ are isomorphic.

As a consequence, for finitely presented categories, the homological finiteness condition FP 3 is equivalent to the homotopical finiteness condition FDT ab , characterising the existence of a finite homotopy basis of an Abelianised version of a presentation of the category, see Theorem 5.7.3.

Examples.

Throughout this article, we apply our constructions to the example of the reduced standard presentation of a category, yielding, at the end, an Abelian resolution that is similar to the bar construction. In Section 6, we give two more examples: the monoid with one non-unit and idempotent element and the subcategory of the simplicial category whose morphisms are the monotone surjections only. They give rise to resolutions where the higher-dimensional cells have the shapes of associahedra and permutohedra, respectively.

Polygraphic resolutions

POLYGRAPHIC RESOLUTIONS

Throughout this section, we denote by n either a natural number or ∞.

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 when 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 or f : u v a 1-cell, a 2-cell or a 3-cell f with source u and target v.

If f and g are i-composable k-cells, that is when t i (f) = s i (g), we denote by f i g their i-composite; we simply use fg when i = 0. The compositions satisfy the exchange relations given, for every i = j and every 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. When 1 f is composed with cells of dimension k + 1 or higher, we simply denote it by f. 2.1.1. (n, p)-categories. A k-cell f of an n-category C, with i-source u and i-target v, is i-invertible when there exists a (necessarily unique) k-cell g in C, with i-source v and i-target u in C, called the i-inverse of f, that satisfies f i g = 1 u and g i f = 1 v .

When i = k-1, we just say that f is invertible and we denote by f -its inverse. As in higher-dimensional groupoids, if a k-cell f is invertible and if its i-source u and i-target v are invertible, then f is (i -1)invertible, with (i -1)-inverse given by

v - i-1 f - i-1 u -.
For a natural number p ≤ n, or for p = n = ∞, an (n, p)-category is an n-category whose k-cells are invertible for every k > p. When n < ∞, this is a p-category enriched in (n -p)-groupoids and, when n = ∞, a p-category enriched in ∞-groupoids. In particular, an (n, n)-category is an n-category, an (n, 0)-category is an n-groupoid and, when n < ∞, an (n, n -1)-category is a track (n -1)-category, as defined in [START_REF] Guiraud | Higher-dimensional categories with finite derivation type[END_REF] after Baues, [START_REF] Baues | Combinatorial homotopy and 4-dimensional complexes[END_REF][START_REF] Baues | Track extensions of categories and cohomology[END_REF]. If n < ∞, any (n, p)-category can be seen as an (∞, p)-category with only identity k-cells for k > n.

2.1.2. Spheres and asphericity. 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. 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)). If n < ∞, the n-category C is aspherical when the source and the target of each n-sphere of C coincide, i.e., when every n-sphere of C has shape (f, f) for some (n -1)-cell f of C.

2.1. Higher-dimensional categories 2.1.3. The canonical model structure on (∞, p)-categories. In [START_REF] Ara | The Brown-Golasiński model structure on strict ∞-groupoids revisited[END_REF], Ara and Métayer have proved that the canonical model structure on ∞-categories from [START_REF] Lafont | A folk model structure on omega-cat[END_REF] transfers to (∞, p)-categories through the adjunction

(∞, p)Cat U ) ) ∞Cat ( • ) i i
where U is the forgetful functor and its left adjoint adds to an ∞-category all the missing inverses for cells of dimension p + 1 and above. The proof in [START_REF] Ara | The Brown-Golasiński model structure on strict ∞-groupoids revisited[END_REF] is detailed for the specific case p = 0, i.e., for ∞groupoids, but it works equally well in the general case. Here we are interested in cofibrant replacements in the model structure on (∞, p)-categories, so let us examine the classes of weak equivalences and cofibrations.

From [START_REF] Lafont | A folk model structure on omega-cat[END_REF], we recall that an ∞-functor F : C → D is a weak equivalence in the model structure on ∞-categories if, and only if, it satisfies the following properties:

• for every 0-cell x of D, there exists a 0-cell x of C such that F( x) is ω-equivalent to x,

• for every 0-cells x and y of C and every 1-cell u :

F(x) → F(y) of D, there exists a 1-cell u : x → y in C such that F( u) is ω-equivalent to u,
• for every parallel n-cells u and v of C, with n ≥ 1, and every (n + 1)-cell f : u → v of D, there exists an

(n + 1)-cell f : u → v of C such that F( f) is ω-equivalent to f.
The ω-equivalence relation is defined together with the notion of reversible cells, by mutual coinduction:

• two n-cells u and v of an ω-category C are ω-equivalent when there exists a reversible (n+1)-cell

f : u → v in C,
• an (n + 1)-cell f : u → v of an ω-category C is reversible when there exists an (n + 1)-cell g : v → u in C such that g n f and f n g are ω-equivalent to 1 x and 1 y , respectively.

From the result of [START_REF] Ara | The Brown-Golasiński model structure on strict ∞-groupoids revisited[END_REF], the weak equivalences for (∞, p)-categories are the images through the forgetful functor U of the weak equivalences for ∞-categories, i.e., the ∞-functors between (∞, p)-categories that are weak equivalences for ∞-categories.

In the canonical model structure on ∞-categories, the cofibrations are the retracts of transfinite compositions of pushouts of the ∞-functors

i n : ∂E n → E n ,
for n ≥ 0, where E n is the n-globe and ∂E n its boundary:

• the n-globe E n is the n-category with exactly one n-cell together with its distinct k-source and k-target for every 0 ≤ k < n,

• the boundary ∂E n of the n-globe is the same n-category as E n but with the n-cell removed.

By the result of [START_REF] Ara | The Brown-Golasiński model structure on strict ∞-groupoids revisited[END_REF], we get that the cofibrations for (∞, p)-categories are the retracts of transfinite compositions of pushouts of the ∞-functors

i n : ∂E n → E n ,
for n ≥ 0, where E n and ∂E n are obtained from E n and ∂E n by formal adjunction of inverses for every k-cell, with 1 < k ≤ n. The quotient of C by Γ , denoted by C/Γ , is 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, p)-category and Γ is a cellular extension of C, then the free (n + 1, p)-category generated by Γ over C is denoted by C(Γ ) and defined as follows:

C(Γ ) = C Γ, Γ -Inv(Γ )
where Γ -contains the same (n + 1)-cells as Γ , with source and target reversed, and Inv(Γ ) is the cellular extension made of two (n + 2)-cells

γ n+1 γ -→ 1 f and γ - n+1 γ → 1 g
for each (n + 1)-cell γ from f to g in Γ .

2.2.2. Homotopy bases. Let C be an (n, p)-category, for p < n < ∞. A homotopy basis of C is a cellular extension Γ of C such that the (n, p)-category C/Γ is aspherical, i.e., such that, for every nsphere γ of C, there exists an (n + 1)-cell with boundary γ in the (n + 1, p)-category C(Γ ). For example, the n-spheres of C form a cellular extension which is a homotopy basis of C.

2.2.3.

(n, p)-polygraphs. An n-polygraph is a data Σ made of a set Σ 0 and, for every 0 ≤ k < n, a cellular extension Σ k+1 of the free k-category

Σ * k = Σ 0 [Σ 1 ] • • • [Σ k ].
For p ≤ n, an (n, p)-polygraph is a data Σ made of:

• a p-polygraph (Σ 0 , . . . , Σ p ),

• for every p ≤ k < n, a cellular extension Σ k+1 of the free (k, p)-category

Σ k = Σ * p (Σ p+1 ) • • • (Σ k ).

Polygraphs

Note that (n, n)-polygraphs coincide with n-polygraphs, so that any notion defined on (n, p)-polygraphs also covers the case of n-polygraphs.

For an (n, p)-polygraph Σ, an element of Σ k is a called k-cell of Σ and Σ is finite when it has finitely many cells in every dimension. An (n, p)-polygraph Σ is aspherical when the free (n, p)-category Σ is aspherical. An (n, p)-polygraph Σ is acyclic when, for every p < k < n, the cellular extension Σ k+1 is a homotopy basis of the (k, p)-category Σ k .

Remark. An (n, p)-polygraph yields a diagram which is similar to the one given in the original definition of n-polygraphs by Burroni, [START_REF] Burroni | Higher-dimensional word problems with applications to equational logic[END_REF], drawn for the case n < ∞ as follows:

Σ * 0 (• • • ) o o o o Σ * p o o o o Σ p+1 o o o o (• • • ) o o o o Σ n-1 o o o o Σ 0 (• • • ) d d d d Σ p d d d d O O O O Σ p+1 d d d d O O O O (• • • ) d d d d Σ n-1 d d d d O O O O Σ n d d d d
This diagram contains the source and target attachment maps of generating (k + 1)-cells on composite k-cells, their extension to composite (k + 1)-cells and the inclusion of generating k-cells into composite k-cells.

2.2.4. Proposition. Every free (∞, p)-category on an (∞, p)-polygraph is a cofibrant object for the canonical model structure on (∞, p)-categories.

Proof. Let Σ be an (∞, p)-polygraph. The unique ∞-functor from the initial (∞, p)-category ∅ to Σ is obtained as the following countable composition of inclusions:

∅ Σ 0 Σ * 1 • • • Σ * p Σ p+1 • • • Σ n • • •
The generating cofibration i 0 is the inclusion of ∂E 0 = ∅ into the singleton E 0 . Thus, for any set X, seen as a 0-polygraph, the inclusion ∅ X is equal to

∅ x∈X ∂E 0 x∈X i 0 / / x∈X E 0 X. Then, for 0 < k ≤ p, the inclusion of Σ * k-1 into Σ * k is a particular case of an inclusion ι : C C[Γ ]
for C a (k -1)-category and Γ a cellular extension of C. By seeing each (k -1)-sphere γ of Γ as an ∞-functor from ∂E k to C, the inclusion ι is given by the following pushout:

γ∈Γ ∂E k γ∈Γ i k / / Γ γ∈Γ E k C / / ι / / C[Γ ].
Finally, the inclusion of Σ * p into Σ p+1 and, for n > p, the inclusion of Σ n into Σ n+1 are particular cases of an inclusion ι : C C(Γ ), for C an (n, p)-category and Γ a cellular extension of C. By seeing each n-sphere γ of Γ as an ∞-functor from ∂E n+1 to C, the inclusion ι is given by the following pushout:

γ∈Γ ∂E n+1 γ∈Γ i n+1 / / Γ γ∈Γ E n+1 C / / ι / / C(Γ ).
As a conclusion, we get that the inclusion ∅ Σ is a countable composition of pushouts of the generating cofibrations (i n ) n≥0 and, as such, it is a cofibration.

Resolutions by (n, p)-polygraphs

2.3.1. Polygraphic presentations. If p < n, given an (n, p)-polygraph Σ, the p-category Σ presented by Σ is defined by Σ = Σ * p /Σ p+1 .
We usually denote by f the image of a p-cell of Σ * p through the canonical projection Σ * p Σ. If f is a k-cell of Σ , with p < k ≤ n, we also denote by f the common image in Σ of the p-cells s p (f) and t p (f) by the canonical projection. An (m, p)-polygraph Σ and an (n, p)-polygraph Υ are Tietze-equivalent when the p-categories Σ and Υ they present are isomorphic.

Example.

Every category C admits a presentation, called the standard presentation of C, defined as the 2-polygraph whose cells are the following ones:

• one 0-cell for each 0-cell of C, • one 1-cell u : x → y for every 1-cell u : x → y of C,
• one 2-cell µ u,v : u v ⇒ uv for every 1-cells u : x → y and v : y → z of C and one 2-cell η x : 1 x ⇒ 1 x for every 0-cell x of C:

y v x u 7 7 uv 3 3 z µ u,v Õ x 1 x 1 x > > x. η x Õ
In the free category generated by the 1-cells of the standard presentation of C, we get, for every 0-cell x, the identity 1 x of x and the generating 1-cell 1 x associated to the identity of x in C. By removing this last superfluous generator, together with the corresponding 2-cell η x , we get another presentation of C, namely the 2-polygraph called the reduced standard presentation of C, with the following cells:

Resolutions by (n, p)-polygraphs

• one 0-cell for each 0-cell of C,

• one 1-cell u : x → y for every non-identity 1-cell u : x → y of C,

• one 2-cell y v x u 7 7 uv 3 3 z µ u,v Õ
for every non-identity 1-cells u : x → y and v : y → z of C such that uv is not an identity,

• one 2-cell y v x u 7 7
1 x x µ u,v Õ for every non-identity 1-cells u : x → y and v : y → x of C such that uv = 1 x . 2.3.3. Polygraphic resolutions. Let C be a p-category. A polygraphic resolution of C is an acyclic (∞, p)-polygraph Σ such that the p-category Σ is isomorphic to C. If p < n < ∞, a partial polygraphic resolution of length n of C is an acyclic (n, p)-polygraph Σ such that Σ is isomorphic to C.
Explicitly, the first dimensions of a polygraphic resolution Σ of C are given as follows:

• For k < p, the k-cells of Σ are the ones of C. In particular, polygraphic resolutions concern the cofibrant p-categories only, i.e., the p-categories that are free up to dimension p -1, which is always the case for p = 1.

• The p-cells of Σ are generators for the ones of C, i.e., the p-category C is a quotient of the free p-category Σ * p .

• The (p + 1)-cells of Σ are relations, i.e., the (p + 1)-polygraph Σ p+1 is a presentation of C.

• The (p + 2)-cells of Σ form a homotopy basis of Σ p+1 , i.e., they are generators of the relations between relations of the presentation Σ p+1 of C.

As previously mentioned, Métayer introduced a notion of polygraphic resolution of a p-category C, with 0 ≤ p ≤ ∞, in [START_REF] Métayer | Resolutions by polygraphs[END_REF]: this is an ∞-polygraph Σ such that the free ∞-category Σ * is a cofibrant replacement of C in the canonical model structure on ∞-categories. The notion we use here is similar, using (∞, p)-polygraphs to produce cofibrant approximations of p-categories in the canonical model structure on (∞, p)-categories:

2.3.4. Theorem.
Let Σ be a polygraphic resolution of a p-category C. The canonical projection Σ C is a cofibrant approximation of C in the canonical model structure on (∞, p)-categories.

Polygraphic resolutions

Proof. From Proposition 2.2.4, we already know that Σ is cofibrant. There remains to check that the canonical projection Σ C is a weak equivalence. Since, by hypothesis, the p-categories C and Σ are isomorphic, it is sufficient to prove that the canonical projection Σ Σ is a weak equivalence. First, we note that the ω-equivalence relation is reflexive: hence, proving that two k-cells of Σ are equal implies that they are ω-equivalent.

By definition, the (∞, p)-categories Σ and Σ have the same cells up to dimension p -1. Thus, if x is a 0-cell of Σ, we take x = x. Moreover, if x and y are parallel k-cells of Σ , for 0 < k < p -1, and if u : x → y is a (k + 1)-cell of Σ, then we take u = u. Now, let x and y be parallel (p -1)-cells of Σ and let u : x → y be a p-cell of Σ. By definition, the p-category Σ is a quotient of the p-category underlying Σ . Hence, there exists a p-cell u in Σ sent to u by the canonical projection.

Then, let u and v be parallel p-cells of Σ and let f : u → v be a (p + 1)-cell of Σ. Since Σ is a p-category, we must have u = v and f = 1 u . By definition of Σ, there exists a (p + 1)-cell f in Σ from u to v, which is sent to 1 u by the canonical projection.

Finally, let f and g be parallel n-cells of Σ , for n > p. Both f and g must be sent to the same n-cell of Σ, so that the only possible (n + 1)-cell of Σ between their images is an identity. Since Σ is acyclic, there exists an (n + 1)-cell from f to g in Σ , and this (n + 1)-cell must be sent to this same identity (n + 1)-cell of Σ.

Polygraphic dimension.

Let us note that every cofibrant p-category C admits a presentation, i.e., a partial polygraphic resolution of length p + 1. Indeed, we can take:

• for k < p, any choice of generating k-cells of C,

• the same p-cells as C,

• one (p + 1)-cell from u to v, when u and v are p-cells of the free p-category C * that are identified by the projection C * C, i.e., that yield the same p-cell of C by composition.

Furthermore, every partial polygraphic resolution Σ of length n of a p-category C can be extended into a partial polygraphic resolution of length n + 1 of C by adjunction of the homotopy basis of the n-spheres of Σ . By iterating this process, we can extend any partial polygraphic resolution into a polygraphic resolution of the same p-category. Applied to the generic presentation of a cofibrant p-category, we get that any cofibrant p-category admits a polygraphic resolution.

If C is a cofibrant p-category, the polygraphic dimension of C is the element d pol (C) of N {∞} defined as follows: if there exists a natural number n such that C admits an aspherical partial polygraphic resolution of length n, then d pol (C) is the smallest of those natural numbers; otherwise d pol (C) = ∞.

2.3.6. Higher-dimensional finite derivation type. For n ≥ p, a p-category is of finite n-derivation type (FDT n ) when it admits a finite partial polygraphic resolution of length n. A p-category is of finite ∞-derivation type (FDT ∞ ) when it admits a finite polygraphic resolution, i.e., when it is FDT n for every n ≥ p. By extension, for n < p, a p-category is of finite n-derivation type when it admits finitely many generating n-cells.

In particular, a p-category is FDT p when it is finitely generated, it is FDT p+1 when it is finitely presented and it is FDT p+2 when it has finite derivation type, a condition introduced by the authors in [START_REF] Guiraud | Higher-dimensional categories with finite derivation type[END_REF]. When p = 1 and for monoids, seen as categories with one 0-cell, the property FDT 3 corresponds to the finite derivation type condition originally defined by Squier, [START_REF] Craig | Word problems and a homological finiteness condition for monoids[END_REF], while the property FDT 4 was introduced in [START_REF] Mcglashan | Pride, Finiteness conditions for rewriting systems[END_REF].

Let us note that FDT n+1 is harder to fulfil than FDT n , because of the finiteness condition on (n + 1)cells, leading to the following chain of implications:

FDT ∞ ⇒ (• • • ) ⇒ FDT p+2 ⇒ FDT p+1 ⇒ FDT p ⇒ (• • • ) ⇒ FDT 0 .

NORMALISATION STRATEGIES FOR POLYGRAPHS

Strategies in rewriting theory

A rewriting system specifies a set of rules that describe valid replacements of subformulas by other ones, [START_REF] Thue | Probleme über Veränderungen von Zeichenreihen nach gegebenen Regeln[END_REF][START_REF] Herman | On theories with a combinatorial definition of "equivalence[END_REF]. On some formulas, the rewriting rules may produce conflicts, when two or more rules can be applied. For this reason, to transform a rewriting system into a genuine computation algorithm, one specifies a way to apply the rules in a deterministic way by a strategy.

For example, in a word rewriting system, formulas are elements of a free monoid. There are two canonical strategies to reduce words where several rewriting rules apply: the leftmost one and the rightmost one, using first the rewriting rule that can be applied on the leftmost or the rightmost subformula:

u u v v w left i Y right Õ
In term rewriting, formulas are morphisms with target the terminal object in a free Lawvere algebraic theory, [START_REF] William | Functorial semantics of algebraic theories[END_REF]. Formulas can be represented by trees and rewriting rules replace subtrees by other subtrees. There exist many possible strategies for term rewriting systems. Among them, outermost and innermost strategies are families of strategies that first use rules that apply closer to the root or closer to the leaves of the term, respectively: inner e y outer 7 9 In programming languages based on rewriting mechanisms, such as Caml, [START_REF] Leroy | The Objective Caml system[END_REF], and Haskell, [START_REF]Haskell 2010 language report[END_REF], strategies are implicitly used by compilers to transform rewriting systems into deterministic algorithms. In that setting, innermost strategies include the call-by-value evaluation, while outermost strategies contain the call-by-need evaluation. Some programming languages, like Tom, [START_REF] Bach | [END_REF], include a dedicated grammar to explicitly construct user-defined strategies.

Several models have been introduced to study the computational properties of strategies. In abstract rewriting, a strategy is defined as a subgraph of the ambient abstract rewriting system. This definition allows the introduction of some properties: for example, a normalisation strategy is a strategy that reaches normal forms, [START_REF]Term rewriting systems[END_REF]. Strategies in functional programming languages are usually classified by corresponding notions of strategies in the λ-calculus, [START_REF] Lévy | Réductions correctes et optimales dans le λ-calcul[END_REF]. This has led to the axiomatic setting of standardisation theory, where strategies are seen as standardisation systems of rewriting paths, [START_REF] Melliès | A diagrammatic standardization theorem, Processes, Terms and Cycles: Steps on the Road to Infinity[END_REF].

In this work, we introduce a notion of normalisation strategy for higher-dimensional rewriting systems that, in turn, induces a notion of normal forms in every dimension, together with a homotopically coherent reduction of every cell to its normal form.

Normalisation strategies

Before a formal definition of normalisation strategy, let us give the idea underlying this notion. If Σ is an (∞, p)-polygraph, the p-category Σ it presents can be seen as an (∞, p)-category with identity cells only in dimensions p + 1 and higher. This way, the canonical projection π : Σ * p Σ can be extended into an (∞, p)-functor π : Σ Σ. Given a (non-functorial) section ι : Σ Σ * p of the canonical projection, a normalisation strategy corresponds to an extension of this section into a (∞, p)-functor ι : Σ Σ , in a suitably weak sense, that satisfies πι = Id Σ and ιπ Id Σ , with an explicitly chosen natural isomorphism witnessing this last fact: it follows that Σ is a polygraphic resolution of Σ. Let us fix n and p with 0 ≤ p ≤ n ≤ ∞.

Sections.

Let Σ be an (n, p)-polygraph. A section of Σ is a choice of a representative p-cell u : x → y in Σ , for every p-cell u : x → y of Σ, such that

1 x = 1 x
holds for every (p -1)-cell x of Σ. Such an assignment u → u is not assumed to be functorial with respect to the compositions: in general, such a property can only be required for a (p, p)-polygraph, i.e., when Σ is a free p-category.

Since, by hypothesis, the assignment u → u is compatible with the quotient map, it extends to a mapping of each p-cell u in Σ * to a parallel p-cell in Σ * , still denoted by u, in such a way that the equality u = v holds in Σ if, and only if, we have u = v in Σ * . Thereafter, we assume that every (n, p)-polygraph comes with an implicitly chosen section.

3.2.2. Normalisation strategies. Let Σ be an (n, p)-polygraph. A normalisation strategy for Σ is a mapping σ of every k-cell f of Σ , with p ≤ k < n, to a (k + 1)-cell f σ f / / f
where, for k > p, the notation f stands for the k-cell f = σ s(f) k-1 σ - t(f) , such that the following properties are satisfied:

• for every k-cell f, with p ≤ k < n, σ f = 1 f • for every pair (f, g) of i-composable k-cells, with p ≤ i < k < n, σ f i g = σ f i σ g .

The case of (n, 1)-polygraphs

An (n, p)-polygraph is normalising when it admits a normalisation strategy. This property is independent of the chosen section. Indeed, let us consider an (n, p)-polygraph Σ with two sections f → f and f → f of Σ and let us assume that σ is a normalisation strategy for Σ, equipped with the section f → f. Then, one checks that we get a normalisation strategy τ for the other section by defining τ f as the following composite:

f σ f / / f (σ f ) - / / f . 3.2.3. Lemma.
Let Σ be an (n, p)-polygraph and let σ be a normalisation strategy for Σ.

i) For every k-cell f, with p -1 ≤ k < n -1, we have

σ 1 f = 1 1 f .
ii) For every k-cell f, with p ≤ k < n -1, we have

σ σ f = 1 σ f .
iii) For every k-cell f, with p < k < n, we have

σ f -= f - k-1 σ - f k-1 f -. Proof. For i), if x is a (p -1)-cell, we have 1 x = 1 x by definition. If f is a k-cell, with p ≤ k < n -1,
then we have, by definition of 1 f :

1 f = σ s(1 f ) k σ - t(1 f ) = σ f k σ - f = 1 f . In either case, if f is a k-cell, with p -1 ≤ k ≤ n, we get σ 1 f = 1 1 f by definition of σ. For ii), if f is a k-cell, with p ≤ k < n -1
, then the definition of σ f gives:

σ f = σ s(σ f ) k σ - t(σ f ) = σ f k σ - f = σ f k 1 - f = σ f .
As a consequence, we get σ σ f = 1 σ f . Finally, for iii), if f is a k-cell, with p < k < n, we have:

σ f k-1 σ f -= σ f k-1 f -= σ 1 s(f) = 1 1 s(f) .
Thus, σ f -is the (k -1)-inverse of σ f , yielding:

σ f -= s(σ f ) - k-1 σ - f k-1 t(σ f ) -= f - k-1 σ - f k-1 f -.

The case of (n, 1)-polygraphs

Let Σ be an (n, 1)-polygraph. In the lower dimensions, a normalisation strategy σ for Σ specifies the following assignments:

• For every 1-cell u of Σ , a 2-cell u σ u 7 9 u
of Σ that satisfies σ u = 1 u and thus, in particular, σ 1x = 1 1x for every 0-cell x of Σ.

• For every 2-cell f : u ⇒ v of Σ , a 3-cell u f 3 5 σ u ) 1 v u σ - v b R σ f Õ
of Σ that satisfies σ f = 1 f and the following relations:

-If u is a 1-cell of Σ , then σ 1u = 1 1u : u 1 u 3 5 σ u ) 1 u u σ - u a Q σ 1u Õ = u 1 u ! ) 1 u S I 1 1u Õ u -If f : u ⇒ v and g : v ⇒ w are 2-cells in Σ , then σ f 1 g = σ f 1 σ g : u f 1 g 3 5 σ u ) 1 w u σ - w a Q σ f 1 g Õ = u f 3 5 σ u ) 1 v g 3 5 σ v ! ) w u σ - v S I σ f Õ c u σ - w a Q σ g Õ -If f : u ⇒ v is a 2-cell in Σ , then f -= σ v 1 σ - u and σ f -= f - 1 σ - f 1 f -: v f - 3 5 σ v ) 1 u u σ - u a Q σ f - Õ = u σ - v v f - 7 9 u σ u E A f A = v σ - f Õ σ v 7 9 u σ - u u • For every 3-cell A : f g : u ⇒ v of Σ , a 4-cell u f ! ) g S I v A Õ σ A 1 ? u f $ g X N σ u 7 9 u σ - v 7 9 σ f Õ σ - g Õ v
of Σ with σ A = 1 A and such that the following relations hold:

3.3. The case of (n, 1)-polygraphs

-If f is a 2-cell of Σ , then σ 1 f = 1 1 f : u f ! ) f S I v 1 f Õ 1 1 f 1 ? u f $ f X N σ u 7 9 u σ - v 7 9 σ f Õ σ - f Õ v -If A : f f : u ⇒ v and B : g g : v ⇒ w are 3-cells of Σ , then σ A 1 B = σ A 1 σ B : u f ! ) f S I A Õ v g ! ) g S I B Õ w σ A 1 σ B 1 ? u f $ f X N σ u 7 9 u σ - v 7 9 σ f Õ σ - f Õ v g $ g X N σ v 7 9 u σ - w 7 9 σ g Õ σ - g Õ w -If A : f g : u ⇒ v and B : g h : u ⇒ v are 3-cells of Σ , then σ A 2 B = σ A 2 σ B : u f # g 7 9 h Y O A Õ B Õ v σ A 2 σ B 1 ? u f $ h X N σ u 7 9 u σ - v 7 9 σ f Õ σ - h Õ v -If A : f g : u ⇒ v is a 3-cell of Σ , then A = σ f 2 σ - g and σ A -= A - 2 σ - A 2 A -: u g f % - g I E f c S v A - Õ A Õ A - Õ A - 2 σ - A 2 A - 1 ? u g f % - g I E f c S v A - Õ A Õ A - Õ 3.3.1. Lemma.
Let Σ be an (n, 1)-polygraph. Normalisation strategies for Σ are in bijective correspondence with data made of:

• a family with one 2-cell σ u : u ⇒ u for every 1-cell u of Σ such that u = u,

• a family with one (k + 1)-cell σ uϕv : uϕv → uϕv for every 1 < k < n, every k-cell ϕ of Σ and every pair (u, v) of 1-cells of Σ such that the composite k-cell uϕv is defined.

Proof. We proceed by induction on the size of cells of Σ . We already know that a normalisation strategy σ has fixed values on normal forms, identities, inverses and i-composites for i ≥ 1. As a consequence, using the exchange relations, we get that the values of σ are entirely and uniquely determined by its values on 1-cells that are not normal forms and, for every k ≥ 2, on k-cells with shape uϕv, where ϕ is a k-cell of Σ and u and v are 1-cells of Σ .

3.3.2.

From normalisation strategies to natural transformations. Let σ be a normalisation strategy for an (n, 1)-polygraph Σ. We define, for every 1-cell u of Σ , the 1-cell u * as u and, by induction on the dimension, for every k-cell f in Σ , with 1 < k ≤ n, the k-cell f * in Σ is given by

f * = ((f 1 σ t 1 (f) * ) 2 • • • ) k-1 σ * t k-1 (f) * .
For example, for a 2-cell f

: u ⇒ v, the 2-cell f * is u f 7 9 v σ v 7 9 u
and, for a 3-cell A :

f g : u ⇒ v, the 3-cell A * is v σ v $ , u f 1 3 g Q G σ u 9 ; u . A " σ g * Õ
One checks that, for any k-cell f, with k > 1, the k-cell f * has source s(f) * and target t(f) *

. Moreover, we have ( f) * = f * , which implies σ f * = σ * f . Since every k-cell of Σ is invertible for k ≥ 2, one can recover σ from σ * , in a unique way, so that the normalisation strategy σ is uniquely and entirely determined by the values

σ * u = σ u : u ⇒ u
for every 1-cell u with u = u and σ * uϕv : (uϕv) * → uϕv * for every 1 < k < n, every k-cell ϕ of Σ and every 1-cells u and v of Σ such that the k-cell uϕv is defined. In the lowest dimensions, the natural transformation form σ * of the strategy σ consists of the following data:

• For every 1-cell u of Σ , a 2-cell σ * u = σ u from u to u.

• For every 2-cell f : u ⇒ v of Σ , a 3-cell σ * f of Σ corresponding to a (weak) naturality condition:

v σ v ' u f @ < σ u 3 5 u u σ * f Õ
To simplify subsequent diagrams, we draw the 3-cell σ * f in a more compact shape, as follows:

v σ v ! u f E A σ u A = u σ * f Õ
This 3-cell must satisfy the following relations:

-if u is a 1-cell of Σ , then σ * 1u = 1 σu holds: u σ u " u 1 u E A σ u A = u σ * 1u Õ = u σ u # + σ u Q G 1 σu Õ u -if f : u ⇒ v and g : v ⇒ w are 2-cells of Σ , then σ * f 1 g = (f 1 σ * g ) 2 σ * f holds: w σ w " u f 1 g E A σ u A = u σ * f 1 g Õ = w σ w Ù v g D @ σ v ) 1 u f E A σ u @ < u σ * g Õ σ * f Õ -if f : u ⇒ v is a 2-cell of Σ , then σ * f -= f - 1 (σ * f ) -holds: u σ u " v f - E A σ v A = u σ * f - Õ = u σ u 3 5 f ! ) u v f - E A c v σ v e U (σ * f ) - Õ • For every 3-cell A : f g : u ⇒ v of Σ , a 4-cell v σ v " * u f 1 3 g Q G σ u @ < u A " σ * g Õ σ * A 1 ? v σ v ! u f E A σ u A = u σ * f Õ
of Σ such that the following relations are satisfied:

-if f is a 2-cell of Σ , then σ * 1 f = 1 σ * f holds: v σ v ! u f E A σ u A = u σ * f Õ 1 σ * f 1 ? v σ v ! u f E A σ u A = u σ * f Õ -if A : f f : u ⇒ v and B : g g : v ⇒ w are 3-cells of Σ , then σ * A 1 B = (f 1 σ * B ) 2 σ * A holds: w σ w Ñ v σ v ( 0 g 1 3 g P F u f 1 3 f Q G σ u @ < u A " B ! σ * f Õ σ * g Õ (f 1 σ * B ) 2 σ * A 1 ? w σ w Ñ v σ v ( 0 g A = u f A = σ u @ < u σ * f Õ σ * g Õ -if A : f g : u ⇒ v and B : g h : u ⇒ v are 3-cells of Σ , then σ * A 2 B = ((A 1 σ v ) 2 σ * B ) 3 σ * A holds: v σ v " * u f ( 0 g 6 8 h Q G σ u @ < u A # B " σ * h Õ (A 1 σ * v ) 2 σ * B 1 ? v σ v " * u f 1 3 g Q G σ u @ < u A " σ * g Õ σ * A 1 ? v σ v ! u f E A σ u A = u σ * f Õ -if A : f g : u ⇒ v is a 3-cell of Σ , then σ * A -= (A - 1 σ * v ) 2 (σ * A ) -holds: v σ v " * u g 1 3 f Q G σ u @ < u A - " σ * f Õ (A - 1 σ * v ) 2 (σ * A ) - 1 ? v σ v ! u g E A σ u A = u σ * g Õ 3.
3. The case of (n, 1)-polygraphs 3.3.3. Left and right normalisation strategies. Let Σ be an (n, 1)-polygraph. A normalisation strategy σ for Σ is a left one when it satisfies the following properties:

• For every pair (u, v) of 0-composable 1-cells of Σ , we have σ uv = σ u v 1 σ uv , i.e., uv σ uv

4 6 σ u v ) 1 uv uv σ uv P c • For every pair (f, g) of 0-composable k-cells of Σ , with 2 ≤ k ≤ p, t 1 (f) = u and s 1 (g) = v, we have σ fg = σ f v 1 σ u g .
In particular, when f : u ⇒ u and g : v ⇒ v are 0-composable 2-cells of Σ :

uv fg 4 6 σ uv ) 1 u v uv σ - u v Y O σ fg Õ = u v u g $ , σ u v # + uv fv 6 8 σ u v 7 9 σ uv Q G uv σ - u v Q G σ uv 7 9 uv σ - u v 7 9 u v σ f v Õ σ u g Õ c c
In a symmetric way, a normalisation strategy σ is a right one when it satisfies:

σ uv = uσ v 1 σ u v
and σ fg = uσ g 1 σ fv .

An (n, 1)-polygraph is left (resp. right) normalising when it admits a left (resp. right) normalisation strategy.

3.3.4. Lemma. Let Σ be an (n, 1)-polygraph, let f be a k-cell of Σ , for 1 < k < n, with 1-source u and 1-target v, and let w and w be 1-cells of Σ such that wfw is defined. Then, if σ is a left normalisation strategy for Σ, we have:

σ wfw = σ w uw 1 σ wf w 1 σ - w vw and σ * wfw = σ w uw 1 σ * wf w 1 σ wuw .
Symmetrically, if σ is a right normalisation strategy, then we have:

σ wfw = wuσ w 1 wσ f w 1 wvσ - w and σ * wfw = wuσ w 1 wσ * f w 1 σ w uw .

Proof. In the case of a left normalisation strategy, the proof for right normalisation strategies being symmetric, we have:

σ fw = σ f w 1 σ 1 wvw = σ f w 1 1 1 wvw = σ f w .
Then, we use the exchange relation to get:

σ σwf = σ wf 1 σwv = σ wf 1 σ σwv = σ wf 1 1 σw v = σ wf 1 σ w v.
Moreover, the definition of left normalisation strategy implies:

σ σwf = σ σw u 1 σ wf = σ w u 1 σ wf .
From the last two computations, we deduce:

σ wf = σ w u 1 σ wf 1 σ - w v.
Combining all the results, we get the required equality:

σ wfw = σ wf w = σ w uw 1 σ wf w 1 σ - w vw .
For σ * wfw , we proceed as follows: 3.3.6. Theorem. Let Σ be an (n, 1)-polygraph. The following assertions are equivalent:

σ * wfw = σ (wfw ) * = σ wf * w 1 σ wvw = σ w uw 1 σ wf * w 1 σ - w vw 1 σ wvw = σ w uw 1 σ wf * w 1 σ wv w 1 σ wuw = σ * w uw 1 σ * wfw 1 σ * wuw . 3
i) Σ is acyclic, ii) Σ is normalising, iii) Σ is left normalising, iv) Σ is right normalising.
Proof. Let us assume that there exists a normalisation strategy σ for Σ. We consider a k-cell f in Σ , for some 1 < k < n. By definition of a normalisation strategy, the (k + 1)-cell σ f has source f and target f. Thus, if g is a k-cell which is parallel to f, the (k + 1)-cell σ f k σ - g of Σ has source f and target g, proving that Σ k+1 forms a homotopy basis of Σ k . Hence Σ is acyclic.

Conversely, let us assume that Σ is acyclic and let us define a right normalisation strategy σ, the case of a left one being symmetric. By definition of the category Σ, we can choose a 2-cell σ x u : x u ⇒ xu for every 1-cell x in Σ and every 1-cell u in Σ such that x u is defined. Then, for 1 < k < n, we use the fact that Σ k+1 is a homotopy basis of Σ k to choose an arbitrary (k + 1)-cell σ ϕ u : ϕ u -→ ϕu for every k-cell ϕ in Σ and every 1-cell u in Σ with ϕ u is defined. We use Corollary 3.3.5 to conclude.

3.3.7. Corollary. Let C be a category and let n be a non-zero natural number. Then C is FDT n if, and only if, there exists a finite, (left, right) normalising (n, 1)-polygraph presenting C.

POLYGRAPHIC RESOLUTIONS FROM CONVERGENT PRESENTATIONS

Convergent 2-polygraphs

Let us recall notions and results from rewriting theory for 2-polygraphs, [START_REF] Guiraud | Termination orders for 3-dimensional rewriting[END_REF][START_REF] Guiraud | Higher-dimensional categories with finite derivation type[END_REF][START_REF] Mimram | Computing critical pairs in 2-dimensional rewriting systems[END_REF]. Let Σ be a fixed 2-polygraph.

Rewriting and normal forms.

A rewriting step of Σ 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 rewriting sequence of Σ is a finite or infinite sequence

u 1 f 1 7 9 u 2 f 2 7 9 (• • • ) f n-1 7 9 u n f n 7 9 (• • • )
of rewriting steps. If Σ has a non-empty rewriting sequence from u to v, we say that u rewrites into v.

Let us note that every 2-cell f of Σ * decomposes into a finite rewriting sequence of Σ, this decomposition being unique up to exchange relations. A 1-cell u of Σ * is a normal form when Σ has no rewriting step with source u. A normal form of u is a 1-cell v that is a normal form and such that u rewrites into v. A 1-cell is reducible if it is not a normal form.

Branchings.

A branching of Σ is a pair (f, g) of 2-cells of Σ * with a common source, as in the diagram v u f 8 :

g 5 7 w
The 1-cell u is the source of this branching and the pair (v, w) is its target, written (f, g) : u ⇒ (v, w).

We do not distinguish the branchings (f, g) and (g, f).

A branching (f, g) is local when f and g are rewriting steps. Local branchings belong to one of the three following families:

• aspherical branchings have shape v u f 8 :

f 6 8 v with f : u ⇒ v a rewriting step of Σ,
• Peiffer branchings have shape u v uv fv @ < ug 4 6 uv with f : u ⇒ v and g : u ⇒ v rewriting steps of Σ,

• overlapping branchings are the remaining local branchings.

The terms "aspherical" and "Peiffer" come from the corresponding notions for spherical diagrams in Cayley complexes associated to presentations of groups, [START_REF] Lyndon | Combinatorial group theory[END_REF], while the term "critical" comes from rewriting theory, [START_REF] Book | String-rewriting systems[END_REF][START_REF] Baader | Term rewriting and all that[END_REF].

Local branchings are compared by the order generated by the relations

(f, g) ufv, ugv)
given for any local branching (f, g) and any 1-cells u and v of Σ * such that ufv exists (and, thus, so does ugv). An overlapping local branching that is minimal for the order is called a critical branching.

A branching (f, g) is confluent when there exists a pair (f , g ) of 2-cells of Σ * with the following shape: v f

( u f @ < g 4 6 u w g V L 4.1. Convergent 2-polygraphs 4.1.3.
Termination, confluence and convergence. We say that Σ terminates when it has no infinite rewriting sequence. In that case, every 1-cell has at least one normal form. Moreover, Noetherian induction allows definitions and proofs of properties of 1-cells by induction on the maximum size of the 2-cells leading to normal forms. We say that Σ is confluent (resp. locally confluent) when all of its branchings (resp. local branching) are confluent. In a confluent 2-polygraph, every 1-cell has at most one normal form. A fundamental result of rewriting theory is that local confluence is equivalent to confluence of critical branchings. For terminating 2-polygraphs, Newman's Lemma ensures that local confluence and confluence are equivalent properties, [START_REF] Herman | On theories with a combinatorial definition of "equivalence[END_REF].

We say that Σ is convergent when it terminates and it is confluent. In that case, every 1-cell u has a unique normal form. Such a Σ is called a convergent presentation of Σ and has a canonical section sending u to its normal form u, so that u = v holds in Σ * if, and only if, we have u = v in Σ. As a consequence, a finite and convergent 2-polygraph Σ yields generators for the 1-cells of the category Σ, together with a decision procedure for the corresponding word problem (finiteness is used to effectively check that a given 1-cell is a normal form).

4.1.4. Reduced 2-polygraphs. A 2-polygraph Σ is reduced when, for every 2-cell ϕ : u ⇒ v in Σ, the 1-cell u is a normal form for Σ 2 \ {ϕ} and v is a normal form for Σ 2 . Let us note that, in that case, for every 1-cell u of Σ * , there exist finitely many rewriting steps with source u in Σ * : indeed, we have exactly one such 2-cell for every decomposition u = vwv such that w is the source of a 2-cell of Σ and the number of decompositions u = vwv is finite in a free category. 4.1.5. Lemma. For every (finite) convergent 2-polygraph, there exists a (finite) Tietze-equivalent, reduced and convergent 2-polygraph.

Proof. Let Σ be a (finite) convergent 2-polygraph Σ. We successively transform Σ as follows. First, we replace every 2-cell ϕ : u ⇒ v in Σ with ϕ : u ⇒ u. Then, if there exist several 2-cells in Σ with the same source, we drop all of them but one. Finally, we drop all the remaining 2-cells whose source is reducible by another 2-cell. After each step, we check that the (finite) 2-polygraph we get is convergent and that it is Tietze-equivalent to the former one. Moreover, by construction, the result is a reduced 2-polygraph.

Remark. This result was proved by Métivier for term rewriting systems, [START_REF] Métivier | About the rewriting systems produced by the knuth-bendix completion algorithm[END_REF], and by Squier for word rewriting systems, [START_REF] Craig | Word problems and a homological finiteness condition for monoids[END_REF]. The proof works for any type of rewriting systems, including n-polygraphs for any n.

4.1.6. Example. Let C be a category and let N C be the reduced standard polygraphic presentation of C, i.e., the 2-polygraph with the following cells:

• one 0-cell for each 0-cell of C,

• one 1-cell u : x → y for every non-identity 1-cell u : x → y of C,

• one 2-cell µ u,v : u v ⇒ uv for every non-identity 1-cells u : x → y and v : y → z of C such that uv is not an identity,

• one 2-cell µ u,v : u v ⇒ 1 x for every non-identity 1-cells u : x → y and v : y → x of C such that uv = 1 x .

The 2-polygraph N C is reduced. Let us prove that it is convergent. For termination, one checks that each 2-cell µ u,v of N C has source of size 2 and target of size 1 or 0. As a consequence, for every non-identity 2-cell f : u ⇒ v of the free 2-category N C * , the size of u is strictly greater than the size of v.

For confluence, we check that N C has one critical branching for every triple (u, v, w) of non-identity composable 1-cells in C: µ u,v w , uµ v,w .

Each of these critical branchings is confluent, with four possible cases, depending on whether uv or vw is an identity or not:

• if neither uv nor vw is an identity: We define the relation on rewriting steps with source u as follows. If ϕ and ψ are 2-cells of Σ and if f = vϕv and g = wψw have source u, then we write f g when v is smaller than w, i.e., informally, when the part of u on which f acts is more at the left than the part on which g acts. By convention, we denote branchings of Σ in increasing order, i.e., (f, g) when f g, which is always possible thanks to the following result.

uv w γ uv,w & . u v w γ u,v w @ < uγ v,w 4

Lemma.

Let Σ be a reduced 2-polygraph and u be a 1-cell of Σ * . Then the relation induces a total ordering on the rewriting steps of Σ with source u.

Proof. From its definition, we already know that the relation is reflexive, transitive and total. For antisymmetry, we assume that f = vϕv and g = wψw are rewriting steps with source u, such that f g and g f, i.e., such that v and w have the same size. Then, using the fact that Σ * 1 is free, we have v = w and either s(ϕ) = s(ψ) or s(ϕ) = s(ψ)a or s(ϕ)a = s(ψ): the latter two cases cannot occur, because Σ is reduced and, from that same hypothesis we get, in the first case, that ϕ = ψ, hence that f = g.

The leftmost and rightmost normalisation strategies.

Let Σ be a reduced 2-polygraph and let u be a reducible 1-cell of Σ * that is not a normal form. The leftmost and the rightmost rewriting steps on u are denoted by λ u and ρ u and defined as the minimum and the maximum elements for of the (finite, non-empty) set of rewriting steps of Σ with source u. We note that, if u and v are reducible and composable 1-cells of Σ * , then we have:

λ uv = λ u v and ρ uv = uρ v .
When Σ terminates, the leftmost normalisation strategy of Σ is the normalisation strategy σ defined by Noetherian induction as follows. On normal forms, it is given by

σ u = 1 u
and, on reducible 1-cells, by σ u = λ u 1 σ t(λu) .

One defines the rightmost normal form of Σ in a similar way by replacing the leftmost rewriting step by the rightmost one in the case of reducible 1-cells.

4.2.4. Lemma. The leftmost (resp. rightmost) normalisation strategy σ is a left (resp. right) normalisation strategy for Σ, seen as a (2, 1)-polygraph, with the property that, for every 1-cell u, the 2-cell σ u lives in Σ * ⊆ Σ .

Proof. Let us assume that σ is the leftmost normalisation strategy, the proof in the rightmost case being symmetric. We must prove that, for every composable 1-cells u and v of Σ * , the following relation holds:

σ uv = σ u v 1 σ uv .
We proceed by Noetherian induction on the 1-cell u. If u is a normal form, then σ u = 1 u and σ uv = σ uv , so that the relation is satisfied. Otherwise, we have, using the definition of σ and the properties of λ:

σ uv = λ uv 1 σ t(λuv) = λ u v 1 σ t(λu)v .
We apply the induction hypothesis to t(λ u )v to get:

σ uv = λ u v 1 σ t(λu) v 1 σ uv = σ u v 1 σ uv .
The fact that σ u is in Σ * is also proved by Noetherian induction on u, using the definition of σ and the facts that both 1 u and λ u are 2-cells of Σ * . Thus, if σ is a normalisation strategy, the 2-cell σ aabb can be either aaβ 1 αc or aaβ 1 aγ. Since the 1-cells a, aa and aab are normal forms, assuming that σ is a left strategy still leaves us with the same choice. Hence, we can define a left normalisation strategy σ for Σ as the leftmost normalisation strategy on every 1-cell of Σ * , except for aabb where it is given by σ aabb = aaβ 1 aγ.

Remark

Thus, we have a left normalisation strategy for Σ, distinct from the leftmost normalisation strategy: indeed, the latter would send aabb to aaβ 1 αc.

Let us note that this phenomenon does not come from the fact that Σ is not confluent, since we can add the 2-cell δ : bcc ⇒ ccb to Σ to get a reduced, convergent 2-polygraph which still has at least two different left normalisation strategies. From Σ, we can build a symmetric (for 0 ) 2-polygraph that admits at least two different right normalisation strategies.

However, we can ensure that, if σ is a left (resp. right) normalisation strategy for a reduced and terminating 2-polygraph Σ with the property that, for every 1-cell u of Σ * , the 2-cell σ u is in Σ * , then this same 2-cell admits a decomposition

σ u = λ u 1 g u (resp. σ u = ρ u 1 g u )
with g u a 2-cell of Σ * . Indeed, if σ is a left strategy, we consider the decomposition λ u = vϕw. By definition of λ u , the 1-cell vs(ϕ) is the source of only one rewriting step of Σ, namely vϕ. Hence, since σ vs(ϕ) is a 2-cell of Σ * with source vs(ϕ), it admits a decomposition σ vs(ϕ) = λ vs(ϕ) 1 h u Peiffer. Moreover, if u 1 (resp. v) was an identity, then the source of ψ (resp. ϕ) would be reducible by ϕ (resp. ψ).

Finally, if we write u = u 1 u 2 , the definitions of λ uv and of ρ uv imply that we have:

λ uv = ϕv and ρ uv = u 1 ψ.
From all those observations, we conclude that every critical branching b of Σ must have shape

b = ϕ v, ρ u v
where u and v are composable 1-cells of Σ * and where ϕ is a 2-cell of Σ with source u. Proof. From Corollary 3.3.5, we know that it is sufficient to define a 3-cell σ * ϕ w : (ϕ w) * ϕw * of c 2 (Σ) for every 2-cell ϕ : v ⇒ v of Σ and every 1-cell w in Σ such that u = v w exists. We note that, by definition, we have:

(ϕ w) * = ϕ w 1 σ v w and ϕw * = σ u = ρ u 1 σ t(ρu) .
Let us proceed by case analysis on the type of the local branching b = (ϕ w, ρ u ).

• If b is aspherical, then ρ u = ϕ w. In that case, we define σ * ϕ w = 1 (ϕ w) * .

• By hypothesis, the branching b cannot be a Peiffer branching. Indeed, the source of ρ u cannot be entirely contained in the normal form w.

• Otherwise, we have w = w 1 w 2 and b 1 = (ϕ w 1 , ρ v w 1 ) is a critical branching of Σ. In that case, we define σ * ϕ w as the composite 3-cell Remark. This result is already contained in [START_REF] Guiraud | Higher-dimensional categories with finite derivation type[END_REF], with a different proof and in a more general form: the generating confluences of a convergent n-polygraph Σ form a homotopy basis of the (n, n -1)category Σ .

v w σ v w 1 w 2 & . ω b 1 w 2 Õ σ v w ( 0 u ϕ w E A ρ u ' / vw 1 w 2 σ vw 1 w 2 7 9 u u w 2 σ u w 2 H D σ u w 2 G C (σ * σ v w 1 w 2 ) - Õ σ * σ u w 2 Õ of c 2 (Σ) .

Corollary.

A category with a finite convergent presentation is FDT 3 .

In particular, we recover Squier's result: a monoid with a finite convergent presentation has finite derivation type, [START_REF] Squier | A finiteness condition for rewriting systems[END_REF].

4.3.6. Example. Let C be a category. We consider the reduced standard presentation N C of C, equipped with the rightmost normalisation strategy. The basis of generating confluences of N C has one 3-cell µ u,v,w for every composable non-identity 1-cells u, v and w of C. The shape of this 3-cell depends on whether uv or vw is an identity or not:

• if neither uv nor vw is an identity: • if uv is not an identity, but vw is:

uv w γ uv,w & . γ u,v,w Õ u v w γ u,v w @ < uγ v,w 4
uv w γ uv,w w γ u,v,w Õ u v w γ u,v w 9 ; uγ v,w 6 8 u
• if uv and vw are identities, and thus u = uvw = w:

u v w γ u,v w ' / uγ v,w I E u = w γ u,v,w

Õ

The basis of generating confluences in the case of the leftmost normalisation strategy has the same 3cells, with source and target reversed.

The acyclic (4, 1)-polygraph of generating triple confluences

Let Σ be a reduced and convergent 2-polygraph.

Triple branchings of 2-polygraphs.

A triple branching of Σ is a triple (f, g, h) of 2-cells of Σ * with the same source and such that f g h. The triple branching (f, g, h) is local when f, g and h are rewriting steps. A local triple branching (f, g, h) is:

• aspherical when either (f, g) or (g, h) is aspherical,

• Peiffer when either (f, g) or (g, h) is Peiffer,

• overlapping, otherwise.

Triple branchings are ordered by inclusion, similarly to branchings. A critical triple branching is a minimal overlapping triple branching. Such a triple branching can have two different shapes, where ϕ, ψ and χ are generating 2-cells :

u 1 / / u 2 / / B B u 3 / / u 4 / / v / / ϕ i Y ψ Õ χ i Y or u 1 / / u 2 / / B B u 3 / / u 4 / / v / / ϕ i Y ψ Õ χ i Y
Those two shapes of critical triple branchings are sufficient for a reduced 2-polygraph but, in a general situation, the other possible type of critical branchings (with an inclusion of one source into the other one) generates several other possibilities. Either way, if Σ is finite, then it has a finite number of critical triple branchings.

The acyclic (4, 1)-polygraph of generating triple confluences

For both possible shapes, the corresponding critical triple branching b can be written

b = c v, ρ u v = f v, ρ u v, ρ u v
where c = (f, ρ u ) is a critical branching of Σ with source u = u 1 u 2 u 3 u 4 and where ρ u = u 1 ψ. Indeed, we note that v must be a normal form for Σ to be reduced. Moreover, in the first case, we have f = ϕu 4 and ρ u v = u 1 u 2 χ and, in the second case, we have f = ϕu 3 u 4 and ρ u v = u 1 u 2 u 3 χ.

u v σ u v $ , u v f * v 2 4 σ * u v P F σ u v 9 ; uv ω c v # σ * σ * u v Õ ω b 1 ? u v σ u v # u v f * v E A σ u v @ < uv σ * f * v Õ for every critical triple branching b = (f v, ρ u v, ρ u v ) of Σ, where c = (f, ρ u ) is a critical branching of Σ.
Using the notations ( • ) * and • for 2-cells and 3-cells, the 4-cell ω b can also be written • If b is aspherical, then ρ v w = ρ v w. In that case, we define σ * ω b w = 1 (ω b w) * .

u v (f * v) * # + ( fv) * R H uv ω b 1 ? u v (f * v) * # + ( fv) * R H uv. (ω c v) * Õ ω c v *
• By hypothesis, the triple branching b cannot be a Peiffer one.

• Otherwise, we have w = w 1 w 2 and b 1 = (f w 1 , ρ v w 1 , ρ v w 1 ) is a critical triple branching of Σ.

We define the 4-cell σ * ωc w as the following composite in c 3 (Σ) :

v w σ v w 1 w 2 1 3 σ v w ( 0 v w f w A = ρ v w 1 w 2 3 5 vw 1 w 2 σ vw 1 w 2 7 9 vw w w 2 σ w w 2 C ? σ w w 2 G C (σ * σ v w 1 w 2 ) - Õ σ * σ w w 2 Õ (ω c w 1 ) * w 2 Õ ω c w * 1 w 2 Õ ω b 1 w 2 1 ?
We apply Corollary 3.3.5 to extend the family of 4-cells we have defined to a right normalisation strategy of c 3 (Σ). 4.4.6. Example. In the case of the reduced standard presentation N C of a category C, the basis of generating triple confluences (for the rightmost normalisation strategy) has one 4-cell µ u,v,w,x for every composable non-identity 1-cells u, v, w and x of C. The shape of the 4-cell µ u,v,w,x depends on whether uv, vw, wx, uvw and vwx are identities or not. In the case where neither of these 1-cells is an identity, the corresponding 4-cell is the following one:

# + u v w x µ u,v w x R H uµ v,w x 7 9 u vµ w,x " * u vw x µ u,vw x R H uµ vw,x " * µ u,vw,x uvwx µ u,v,w,x 1 ? u v w x µ u,v w x R H u vµ w,x
" * c uv wx µ uv,wx 7 9 µ uv,w,x µ u,v,wx uvwx.

u v wx uµv, wx

7 9 uµ v,w,x u vwx µ u,vwx R H u v wx µ u,v wx R H uµv, wx 7 9 u vwx µ u,vwx Q G

The polygraphic resolution generated by a convergent 2-polygraph

Let Σ be a reduced and convergent 2-polygraph and let us extend it into an acyclic (∞, 1)-polygraph, i.e., a polygraphic resolution of the category Σ. This (∞, 1)-polygraph is denoted by c ∞ (Σ) and its generating (n + 1)-cells, for n ≥ 2, are (indexed by) the n-fold critical branchings of Σ. We proceed by induction on n, having already seen the base cases, for n = 2 and n = 3. The induction case follows the construction of the acyclic (4, 1)-polygraph c 3 (Σ), so we go faster here.

4.5.1. Higher branchings of 2-polygraphs. An n-fold branching of Σ is a family (f 1 , . . . , f n ) of rewriting steps of Σ with the same source and such that f 1 • • • f n . We define local, aspherical, Peiffer, overlapping, minimal and critical n-fold branchings in a similar way to the cases n = 2 and n = 3. As where c is a critical (n-1)-fold branching of Σ with source u. Moreover, if Σ is finite, then it has finitely many n-fold critical branchings. of Σ such that w = w 1 w 2 and such that b 1 = (c w 1 , ρ v w 1 ) is a critical n-fold branching of Σ. As in the case n = 3, we define the (n + 1)-cell σ * ωc w as the following composite, where f is the first 2-cell of the critical n-fold branching c:

v w σ v w 1 w 2 & . ω b 1 w 2 σ v w ( 0 v w f w E A ρ v w 1 w 2 ( 0 vw 1 w 2 σ vw 1 w 2 7 9 vw w w 2 σ w w 2 H D σ w w 2 F B (σ * σ v w 1 w 2 ) - Õ σ * σ w w 2 Õ
As a conclusion of this construction, we get that the (n + 1, 1)-polygraph c n (Σ) is acyclic. As a consequence, we get: 4.5.4. Corollary. A category with a finite convergent presentation is FDT ∞ . Moreover, if C is a category with a convergent presentation with no critical n-fold branching, for some n ≥ 2, then d pol (C) ≤ n. More generally, the (∞, 1)-polygraph c ∞ (N C) has, for every natural number n ≥ 2, one n-cell µ u 1 ,...,un for every family (u 1 , . . . , u n ) of non-identity composable 1-cells of C. The shape of this cell depends on the partial compositions of the 1-cells u 1 , . . . , u n .

In the case where no such partial composition is an identity, we get an n-cell with the same shape as an n-simplex, representing all the possible ways to transform

u 1 • • • u n into u 1 • • • u n ,
all the homotopies between these different ways, all homotopies between these homotopies, and so on. Indeed, we have seen that each 2-cell µ u,v : u v ⇒ uv is represented by a triangle, each 3-cell µ u,v,w is pictured as a tetrahedron and each 4-cell µ u,v,w,x as a 4-simplex. More generally, the source and the target of this n-cell are (n -1)-composites of the following (n -1)-cells:

d i (u 1 , . . . , u n ) =      u 1 µ u 2 ,...,un if i = 0 µ u 1 ,...,u i u i+1 ,...,un if 1 ≤ i ≤ n -1 µ u 1 ,...,u n-1 u n if i = n.
More precisely, the n-cell µ u 1 ,...,un has the same shape as an n-oriental, the higher-categorical equivalent of an n-simplex, see [START_REF]The algebra of oriented simplexes[END_REF].

ABELIANISATION OF POLYGRAPHIC RESOLUTIONS

Let us fix a category C.

Resolutions of finite type

5.1.1. Modules over a category, [START_REF] Mitchell | Rings with several objects[END_REF]. A C-module is a functor from C to the category of Abelian groups Ab. The C-modules and natural transformations between them form an Abelian category with enough projectives, denoted by Mod(C). Equivalently, Mod(C) can be described as the category of additive functors from ZC to Ab, where ZC is the free Z-category over C: its 0-cells are the ones of C and each hom-set ZC(x, y) is the free Abelian group generated by C(x, y). A C-module M is free when it is a coproduct of representable functors ZC(x, -) and it is finitely generated if there exists an epimorphism of C-modules F M, with F free. Let M be a C o -module and N be a C-module. The tensor product of M and N over C is the Abelian group M ⊗ C N defined as the coend

M ⊗ C N = x∈C 0 M(x) ⊗ Z N(x).
In a more explicit way, we have:

M ⊗ C N =   x∈C 0 M(x) ⊗ Z N(x)   Q where Q is the subgroup of x∈C 0 M(x) ⊗ Z N(x) generated by the elements M(u)(a) ⊗ b -a ⊗ N(u)(b),
for any possible 1-cell u : x → y of C and any elements a of M(y) and b of N(x).

Categories of finite homological type

5.2.1. Natural systems of Abelian groups. The category of factorisations of C is the category, denoted by FC, whose 0-cells are the 1-cells of C and whose 1-cells from w to w are pairs (u, v) of 1-cells of C such that the following diagram commutes in C:

• w / / • v • u @ @ w / / • c
In such a situation, the triple (u, w, v) is called a factorisation of w . Composition in FC is defined by pasting, i.e., if (u, v) : w → w and (u , v ) : w → w are 1-cells of FC, then the composite

(u, v)(u , v ) is (u u, vv ): • w / / • v • u @ @ w / / • v • u @ @ w / / • c c
The identity of w is (1 s(w) , 1 t(w) ):

• w / / • 1 t(w) • 1 s(w) @ @ w / / • c
A natural system (of Abelian groups) on C is an FC-module D, i.e., a functor D : FC → Ab. As in [START_REF] Baues | Cohomology of small categories[END_REF], we denote by D w the Abelian group which is the image of w by D. If there is no confusion, we denote by uav the image of a ∈ D w through the morphism of groups D(u, v) : D w → D w . The category of natural systems on C is denoted by Nat(C).

5.2.2. Free natural systems. Given a family X of 1-cells of C, we denote by F C [X] the free natural system on C generated by X, which is defined by

F C [X] = x∈X FC(x, -).
In particular, if Σ is an (n, 1)-polygraph such that Σ C, we consider:

• The free natural system F C [Σ 0 ] generated by the 1-cells 1 x , for x ∈ Σ 0 : if w is a 1-cell in C, then F C [Σ 0 ] w is the free Abelian group generated by the pairs (u, v) of 1-cells of C such that uv = w.

• For every 1 ≤ k ≤ p, the free natural system F C [Σ k ] generated by a copy of the 1-cell ϕ for each k-cell ϕ of Σ k : if w is a 1-cell in C, then F C [Σ k ] w is the free Abelian group generated by the triples (u, ϕ, v), thereafter denoted by u[ϕ]v, made of a k-cell ϕ of Σ k and 1-cells u, v of C such that uϕv = w.

Categories of finite homological type.

The property for a category C to be of homological type FP n is defined according to a category of modules over one of the categories in the following diagram

C o + + q 1 FC π / / / / C o × C p 1 2 2 2 2 p 2 ---- C C 2 2 q 2 B B
where C is the groupoid generated by C, π is the projection u → (s(u), t(u)), p 1 and p 2 are the projections of the cartesian product, q 1 and q 2 are the injections u o → u -and u → u.

Let us denote by Z the constant natural system on C given, for any 1-cell u of C, by

Z u = Z and Z(u, 1) = Z(1, u) = Id Z .
Let Proof. We have the following left Kan extensions:

Lan π (Z) = ZC Lan p i (Z) = Z Lan q i (Z) = Z.
Hence the implications are consequences of Lemma 5.1.4.

Converse implications.

The converse of the implications bi-FP n ⇒ left/right-FP n and left/right-FP n ⇒ top-FP n of Proposition 5.2.4 does not hold in general. Indeed, Cohen constructed a right-FP ∞ monoid which is not left-FP 1 : thus, the properties top-FP n , left-FP n and right-FP n are not equivalent in general, [START_REF] Daniel | A monoid which is right-FP ∞ but not left-FP 1[END_REF]. Moreover, monoids with a finite convergent presentation are of types left-FP ∞ and right-FP ∞ , [START_REF] Craig | Word problems and a homological finiteness condition for monoids[END_REF][START_REF] Anick | On the homology of associative algebras[END_REF][START_REF] Kobayashi | Complete rewriting systems and homology of monoid algebras[END_REF], but there exists a finitely presented monoid, of types left-FP ∞ and right-FP ∞ , which does not satisfy the homological finiteness condition FHT, introduced by Pride and Wang, [START_REF] Kobayashi | On homotopical and homological finiteness conditions for finitely presented monoids[END_REF]; since the properties FHT and bi-FP 3 are equivalent, [START_REF]For finitely presented monoids the homological finiteness conditions FHT and bi-FP 3 coincide[END_REF], it follows that the properties left-FP n and right-FP n do not imply the property bi-FP n in general. We conjecture that the converse of the first implication is not true either, but this is still an open problem. However, in the special case of groupoids, all the implications are equivalences. Given a G-module M, we denote by M the natural system of G defined, on a 1-cell w : x → y of G, by M w = M(y) and, on a factorisation w = uwv with w : x → y and w : x → y in G, by M(u, v) = M(v) : M(y) → M(y ). Let us assume that M is a projective G-module, i.e., there exists a family X of 1-cells of G and a surjective morphism of groups x∈X ZG(x, y) π y / / / / M(y)

that is natural in y. Let us denote by L the natural system on G defined, on a 1-cell u with target y, by

L u = x∈X ZFG(1 x , 1 y ).
For fixed 0-cells x and y of G, the set FG(1 x , 1 y ) is the one of pairs (u, v) of 1-cells of G such that u1 x v = 1 y . Because G is a groupoid, this is exactly the set of pairs (v -, v) where v : x → y is a 1-cell of G. Hence, we have a bijection between G(x, y) and FG(1 x , 1 y ) that is natural in y. This gives, for any 1-cell u with target y in G, a surjective morphism of groups

L u = x∈X ZG(x, y) π t(u) / / / / M(y) = M(u).
Moreover, one checks that this is natural in u, yielding an epimorphism π t(-) : L M of natural systems on G, proving that M is projective. Moreover, by construction, if M is finitely generated, then we can choose the family X to be finite, so that M is finitely generated too.

As a conclusion, from a partial resolution P * Z of length n by projective and finitely generated G-modules, we can build a partial resolution P * Z of length n by projective and finitely generated natural systems on G. Thus, the property left-FP n implies the property FP n for groupoids. 5.2.7. Finite homological type and homology. The cohomology of categories with values in natural systems was defined in [START_REF] Wells | Extension theories for categories[END_REF] and [START_REF] Baues | Cohomology of small categories[END_REF]. One can also define the homology of a category C with values in a contravariant natural system D on C, that is an (FC) o -module, and relate its finiteness properties to the fact that C is FP n . Note that this is independent of the rest of this article.

dι s = ι d 0 (s) u 1 * + n-1 i=1 (-1) i ι d i (s) + (-1) n ι dn(s) u * n ,
with s = (u 1 , . . . , u n ) and where u 1 * and u * n respectively denote D(u 1 , 1) and D(1, u n ). The homology of C with coefficients in D is defined as the homology of the complex (C * (C, D), d * ):

H * (C, D) = H * (C * (C, D), d * ).
We denote by Tor FC * (D, -) the left derived functor from the functor D ⊗ FC -. One proves that there is an isomorphism which is natural in D:

H * (C, D)
Tor FC * (D, Z). As a consequence, using Lemma 5.1.3, we get: 5.2.8. Proposition. If a category C is of homological type FP n , for a natural number n, then the Abelian group H k (C, Z) is finitely generated for every 0 ≤ k ≤ n.

The Reidemeister-Fox-Squier complex

Let Σ be an (n, 1)-polygraph. The mapping of every 1-cell x of Σ to the element [x] of F Σ [Σ 1 ] x is extended to associate to every 1-cell u of Σ * 1 the element [u] of F Σ [Σ 1 ] u , defined by induction on the size of u as follows:

[1 x ] = 0 and [uv] = [u]v + u[v].
This is well-defined since the given relations are compatible with the associativity and identity relations of Σ * 1 . Note that the mapping [•] is a special case of the notion of derivation of the category Σ * 1 into the natural system F Σ [Σ 1 ] on Σ, seen as a natural system on Σ * 1 by composition with the canonical projection Σ * 1 Σ, see [START_REF] Baues | Cohomology of small categories[END_REF]. Then, for 1 < k ≤ n, the mapping of every k-cell α of Σ to the element

[α] of F Σ [Σ k ] α is extended to associate to every k-cell f of Σ k the element [f] of F Σ [Σ k ] f ,
defined by induction on the size of f as follows:

[1 u ] = 0 [f -] = -[f] [f i g] = [f]g + g[f] if i = 0 [f] + [g] otherwise.
Here, to check that this is well-defined, we also have to show that this definition is compatible with exchange relations, for every 0 ≤ i < j ≤ k:

[(f i g) j (h i k)] = [(f j h) i (g j k)] = [f]g + f[g] + [h]k + h[k] if i = 0 [f] + [g] + [h] + [k] otherwise.
5.3.1. The Reidemeister-Fox-Squier complex. Let Σ be an (n, 1)-polygraph. For 1 ≤ k ≤ n, the k-th Reidemeister-Fox-Squier boundary map of Σ is the morphism of natural systems

δ k : F Σ [Σ k ] -→ F Σ [Σ k-1 ]
defined, on the generator [α] corresponding to a k-cell α of Σ, by:

δ k [α] = (α, 1) -(1, α) if k = 1 [s(α)] -[t(α)] otherwise.
The augmentation map of Σ is the morphism of natural systems ε : F Σ [Σ 0 ] → Z defined, for every pair (u, v) of composable 1-cells of Σ, by: ε(u, v) = 1.

By induction on the size of cells of Σ , one proves that, for every k-cell f in Σ , with k ≥ 1, the following holds:

δ k [f] = (f, 1) -(1, f) if k = 1 [s(f)] -[t(f)] otherwise.
As a consequence, we have εδ 1 = 0 and δ k δ k+1 = 0, for every 1 ≤ k < n. Thus, we get the following chain complex of natural systems on Σ, called the Reidemeister-Fox-Squier complex of Σ and denoted by F Σ [Σ]:

F Σ [Σ n ] δ n / / F Σ [Σ n-1 ] δ n-1 / / • • • δ 2 / / F Σ [Σ 1 ] δ 1 / / F Σ [Σ 0 ] ε / / Z / / 0.
The terminology is due to the fact that this complex is inspired by constructions by Reidemeister, Fox and Squier, see [START_REF] Reidemeister | Über Identitäten von Relationen[END_REF][START_REF] Fox | Free differential calculus. I. Derivation in the free group ring[END_REF][START_REF] Craig | Word problems and a homological finiteness condition for monoids[END_REF]. In particular, the Fox Jacobian used by Squier is the boundary map δ 2 , sending every 2-cell f : u ⇒ v, i.e., every relation u = v of the presentation Σ 2 , to the element

[u] -[v] of F Σ [Σ 1 ] u .

Abelianisation of polygraphic resolutions

Let us fix a partial polygraphic resolution Σ of length n ≥ 1 of the category C.

Contracting homotopies.

Since Σ is acyclic, it admits a left normalisation strategy σ. We denote by σ k , for -1 ≤ k ≤ p, the following families of morphisms of groups, indexed by a 1-cell w of C:

(σ -1 ) w : Z -→ F C [Σ 0 ] w 1 -→ (1, w) (σ 0 ) w : F C [Σ 0 ] w -→ F C [Σ 1 ] w (u, v) -→ [ u]v (σ k ) w : F C [Σ k ] w -→ F C [Σ k+1 ] w u[x]v -→ [σ ux ]v 5
.4.2. Lemma. For every k ∈ {1, . . . , n -1}, every k-cell f of Σ and every 1-cells u and v of C such that ufv exists, we have:

σ k (u[f]v) = [σ uf ]v.
Proof. We proceed by induction on the size of f. If f = 1 w , for some (k -1)-cell w of Σ , then we have, on the one hand,

σ k (u[1 w ]v) = σ k (0) = 0
and, on the other hand,

[σ 1 uw ]v = [1 1 uw ]v = 0.
If f has size 1, then the result holds by definition of σ k . Let us assume that f = gh, where g and h are non-identity k-cells of Σ . Then we use the induction hypothesis on g and h to get, on the one hand:

σ k (u[gh]v) = σ k (u[g]hv) + σ k (ug[h]v) = [σ ug ]hv + [σ ugh ]v.
On the other hand, since σ is a left normalisation strategy, we have:

[σ ugh ]v = σ ug s 1 (h) 1 σ ugh v = [σ ug ]hv + [σ ugh ]v.
Finally, let us assume that f = g i h, where g and h are non-identity k-cells of Σ and i ≥ 1. Then we get:

σ k (u[g i h]v) = σ k (u[g]v) + σ k (u[h]v) = [σ ug ]v + [σ uh ]v.
And we also have:

[σ u(g i h) ]v = [σ ug i uh ]v = [σ ug i σ uh ]v = [σ ug ]v + [σ uh ]v. 5.4.3. Theorem. If Σ is a (partial) polygraphic resolution (of length n) of a category C, then the Reidemeister-Fox-Squier complex F C [Σ] is a free (partial) resolution (of length n) of the constant natural system Z on C.
Proof. Let us prove that σ * is a contracting homotopy. Each (σ -1 ) w is a section of ε w , hence ε is an epimorphism of natural systems. By linearity of the boundary and section maps, it is sufficient to check the relation

δ 1 σ 0 (u, v) = (u, v) -(1, uv) = (u, v) -σ -1 ε(u, v), on a generator (u, v) of F C [Σ 0 ] w to get the exactness of F C [Σ] at F C [Σ 0 ]. Then, on a generator u[x]v of F C [Σ 1 ] w , we compute δ 2 σ 1 (u[x]v) = δ 2 ([σ ux ])v = [ ux]v -[ ux]v = [ u]xv + u[x]v -[ ux]v. and σ 0 δ 1 (u[x]v) = σ 0 (ux, v) -σ 0 (u, xv) = [ ux]v -[ u]xv.
Hence, using the linearity of the boundary and section maps, we get

δ 2 σ 1 + σ 0 δ 1 = 1 F C [Σ 1 ] , proving exactness at F C [Σ 1 ]. Finally, for k ∈ {2, . . . , p -1} and a generator u[α]v of F C [Σ k ] w , we have: δ k+1 σ k (u[α]v) = δ k+1 [σ uα ]v = [ uα]v -[σ us(α) k-1 σ - ut(α) ]v = u[α]v -[σ us(α) ]v + [σ ut(α) ]v = u[α]v -σ k-1 (u[sα]v) + σ k-1 (u[tα]v) = u[α]v -σ k-1 δ k (u[α]v).
Thus, by linearity of the boundary and section maps, we get

δ k+1 σ k + σ k-1 δ k = 1 F C [Σ k ] , proving exact- ness at F C [Σ k ]
and concluding the proof. By construction, if Σ is a finite (n, 1)-polygraph, then each F Σ [Σ k ] is finitely generated. In particular, every category with a finite number of 0-cells is of homological type FP 0 and every category that is finitely generated (resp. presented) is of homological type FP 1 (resp. FP 2 ). More generally, we have the following result, generalising the fact that a finite derivation type monoid is of homological type FP 3 , see [START_REF] Cremanns | Finite derivation type implies the homological finiteness condition FP 3[END_REF][START_REF] Stephen | Low-dimensional homotopy theory for monoids[END_REF]: 5.4.4. Corollary. For categories, the property FDT n implies the property FP n , for every 0 ≤ n ≤ ∞.

Finally, as a consequence of Theorem 4.5.3, we get: 5.4.5. Corollary. If a category admits a finite and convergent presentation, then it is of homological type FP ∞ . 5.4.6. Example. Let C be a category. The Reidemeister-Fox-Squier complex corresponding to the reduced standard polygraphic resolution c ∞ (N C) of C is (isomorphic to) the following one

• • • δ n+1 / / F C [C n ] δ n / / F C [C n-1 ] δ n-1 / / • • • δ 2 / / F C [C 1 ] δ 1 / / F C [C 0 ] ε / / Z / / 0
where C n is the set of composable non-identity 1-cells u 1 , . . . , u n of C. The differential map is given, on a generator [u 1 , . . . , u n ], by:

δ[u 1 , . . . , u n ] = n i=0 (-1) n-i [d i (u 1 , . . . , u n )] = (-1) n u 1 [u 2 , . . . , u n ] + n-1 i=1
(-1) n-i [u 1 , . . . , u i u i+1 , . . . , u n ] + [u 1 , . . . , u n-1 ]u n .

5.5. Homological syzygies and cohomological dimension 5.5.1. Homological syzygies. For every k in {1, . . . , p + 1}, the kernel of δ k is denoted by h k (Σ) and called the natural system of homological k-syzygies of Σ. The kernel of ε is denoted by h 0 (Σ) and called the augmentation ideal of Σ. When Σ 0 is finite, then the natural system h 0 (Σ) is finitely generated if, and only if, the category Σ has homological type FP 1 . If Σ is a generating 1-polygraph for a category C, one checks that h 0 (C) is generated by the set {(x, 1) -(1, x) | x ∈ Σ 1 }. Thus a category has homological type FP 1 if, and only if, it is finitely generated.

From Theorem 5.4.3, we get a characterisation of the homological properties FP n in terms of polygraphic resolutions: 5.5.2. Proposition. Let C be a category and Σ be a partial finite polygraphic resolution of C of length n. If the natural system h n (Σ) of homological n-syzygies of Σ is finitely generated, then C is of homological type FP n+1 .

Theorem 5.4.3 also gives a description of homological n-syzygies in terms of critical n-fold branchings of a convergent presentation: 5.5.3. Proposition. Let C be a category with a convergent presentation Σ. Then, for every n ≥ 2, the natural system h n (Σ) of homological n-syzygies of Σ is generated by the elements

δ n+1 [ω b ] = [(ω c v) * ] -[ ω c v * ]
where b = (c v, ρ u v ) ranges over the critical n-fold branchings of Σ. 5.5.4. Cohomological dimension. Finally, Theorem 5.4.3 gives the following bounds for the cohomological dimension of a category. We recall that the cohomological dimension of a category C, is defined, when it exists as the lowest 0 ≤ n ≤ ∞ such that the constant natural system Z on C admits a projective resolution 0

/ / P n / / • • • / / P 1 / / P 0 / / Z / / 0.
In that case, the cohomological dimension of C is denoted by cd(C). In particular, when C is free, then we have cd(F) ≤ 1, see [START_REF] Baues | Cohomology of small categories[END_REF].

5.5.5. Proposition. The cohomological dimension of a category C admits the following upper bounds:

i) The inequality cd(C) ≤ d pol (C) holds.

ii) If C admits an aspherical partial polygraphic resolution of length n, then cd(C) ≤ n.

iii) If C admits a convergent presentation with no critical n-fold branching, then cd(C) ≤ n.

Homological syzygies and identities among relations

In [START_REF]Identities among relations for higher-dimensional rewriting systems[END_REF], the authors have introduced the natural system of identities among relations of an n-polygraph Σ.

If Σ is a convergent 2-polygraph, this natural system on Σ is generated by the critical branchings of Σ. In Proposition 5.5.3, we have seen that this is also the case of the natural system of homological 2-syzygies of Σ. In this section, we prove that, more generally, the natural systems of homological 2-syzygies and of identities among relations of any 2-polygraph are isomorphic.

5.6.1. Natural systems on n-categories. We recall from [START_REF] Guiraud | Higher-dimensional categories with finite derivation type[END_REF], that a context of an n-category C is an n-cell C of the n-category C[x], where x is an (n -1)-sphere of C, and such that C contains exactly one occurrence of the n-cell x of C[x]. Such a context admits a (generally non-unique) decomposition If Γ is a cellular extension of C, then every non-identity

C = f n n-1 (f n-1 n-2 (• • • 1 f 1 x g 1 1 • • • ) n-2 g n-1 ) n-1 g n , where
(n + 1)-cell f of C[Γ ] has a decomposition f = C 1 [ϕ 1 ] n • • • n C k [ϕ k ],
with k ≥ 1 and, for every i in {1, . . . , k}, ϕ i in Γ and C i a whisker of C[Γ ].

The category of contexts of C is denoted by Ct(C), its objects are the n-cells of C and its morphisms from f to g are the contexts C of C such that C[f] = g holds. When C is a category, the category Ct(C) of contexts of C is isomorphic to the category FC of factorisations of C. A natural system on C is a Ct(C)-module, i.e., a functor D from Ct(C) to the category Ab of Abelian groups; we denote by D u and by D C the images of an n-cell u and of a context C of C through the functor D. 5.6.2. Identities among relations. Let Σ be an n-polygraph, seen as an (n, n -1)-polygraph. An ncell f of Σ is closed when its source and target coincide. The natural system Π(Σ) on Σ of identities among relations of Σ is defined as follows:

• If u is an (n -1)-cell of Σ, the Abelian group Π(Σ) u is generated by one element f , for each n-cell f : v ⇒ v of Σ such that v = u, submitted to the following relations:

if f : v → v and g : v → v are n-cells of Σ , with v = u, then f n-1 g = f + g ;

if f : v → w and g : w → v are n-cells of Σ , with v = w = u, then f n-1 g = g n-1 f .

• If g = C[f] is a factorisation in Σ, then the morphism Π(Σ) C : Π(Σ) f → Π(Σ) g of groups is defined by

Π(Σ) C ( f ) = C[f] ,
where C is any representative context for C in Σ * . We recall from [START_REF]Identities among relations for higher-dimensional rewriting systems[END_REF] that the value of Π(Σ) does not depend on the choice of C, proving that Π(Σ) is a natural system on Σ and allowing one to denote this element of Π(Σ) g by C f .

As consequences of the defining relations of each group Π(Σ) u , we get the following equalities:

1 u = 0 f -= -f g n-1 f n-1 g -= f
for every n -1-cell u and every n-cells f : u → u and g : v → u of Σ . Conversely, let us consider a 2-cell f : w ⇒ w in Σ such that [f] = 0 holds. We decompose f into:

f = u 1 ϕ ε 1 1 v 1 1 • • • 1 u p ϕ εp p v p
where ϕ i is a 2-cell of Σ, u i and v i are 1-cells of Σ , ε i is an element of {-, +}. Then we get:

0 = [f] = p i=1 ε i u i [ϕ i ]v i Since F C [Σ 2
] is freely generated, as an FC-module, by the elements [ϕ] of F C [Σ 2 ] ϕ , for ϕ a 2-cell of Σ, this implies the existence of a self-inverse permutation τ of {1, . . . , p} such that the following relations are satisfied: with, for every 1 ≤ i ≤ p, α i in Σ 3 , u i and v i in Σ and ε i in {-, +} such that u i α i v i = w holds. We fix a section • of Σ and we choose 2-cells g i : w ⇒ u i s 1 (α ε i i ) v i and h i :

ϕ i = ϕ τ(i) u i = u τ(i) v i = v τ(i) ε i = -ε τ(i) .
u i t 1 (α ε i i ) v i ⇒ w.
Let A be the following 3-cell of Σ 3 :

A = g 1 1 u 1 α ε 1 1 v 1 1 h 1 1 • • • 1 g k 1 u k α ε k k v k 1 h k .
By definition of [•] on 3-cells, we have 5.6.5. Theorem. For every 2-polygraph Σ, the natural systems of homological 2-syzygies and of identities among relations of Σ are isomorphic.

[A] = p i=1 g i 1 u i α ε i i v i 1 h i = p i=1 [1 g i ] + ε i u i [α i ]v i + [1 h i ] = b.
Proof. We define a morphism of natural systems Φ : Π(Σ) → h 2 (Σ) by

Φ f = [f] .
This definition is correct, since the defining relations of Π(Σ) also hold in F C [Σ 2 ], hence in h 2 (Σ). Let us check that Φ is a morphism of natural systems. Indeed, we have

Φ(u f v) = Φ( uf v ) = [ uf v] = u[f]v = uΦ( f )v
for every 2-cell f : w ⇒ w in Σ and 1-cells u, v in Σ such that uf v is defined. Now, let us define a morphism of natural systems Ψ : h 2 (Σ) → Π(Σ). Let a be an element of h 2 (Σ) w . Then there exists a closed 2-cell f : u ⇒ u such that a = [f] and w = u. We define Ψ(a) = f .

Examples

i) the category C is of homological type FP 3 , ii) the natural system h 2 (Σ) on C is finitely generated, iii) the natural system Π(Σ) on C is finitely generated, iv) the category C is FDT ab .

Proof. The equivalence between i) and ii) comes from the definition of the property FP 3 . The equivalence between ii) and iii) is a consequence of Theorem 5.6.5. The last equivalence is given by Proposition 5.7.2.

In Corollary 5.4.4, we have seen that FDT 3 implies FP 3 . We expect that the reverse implication is false in general, which is equivalent to proving that FDT ab does not imply FDT 3 , since FP 3 is equivalent to FDT ab for finitely presented categories.

EXAMPLES

A concrete example of reduced standard polygraphic resolution

Let us denote by A the monoid with one non-unit element, a, and with product given by aa = a. The standard presentation of A, seen as a category, is the reduced and convergent 2-polygraph, denoted by As, with one 0-cell (for 1), one 1-cell (for a) and one 2-cell aa ⇒ a. Here we use diagrammatic notations, where a is denoted by a vertical string and the 2-cell aa ⇒ a is pictured as . The 2-polygraph As has one critical branching:

, .

The corresponding generating confluence (for the rightmost normalisation strategy) is the 3-cell:

7 9
By extending As with that 3-cell, one gets a finite, acyclic (3, 1)-polygraph, still denoted by As and which is a partial polygraphic resolution of A of length 3. We conclude that the monoid A has the property FDT 3 and, thus, is of homological type FP 3 . In particular, the natural system h 2 (As) of homological 2-syzygies of As is generated by the following element: This triple critical branching b has shape (f a, g a, ρ u a ) with f = and g = .

δ 3 [ ] = - = + - - = a -a .

Examples

The corresponding generator of the natural system h 4 (As) of homological 4-syzygies of As is:

δ 5 [ω b ] = + + - - - = [ ] a -a [ ] .

The category Epi

We denote by Epi the subcategory of the simplicial category whose 0-cells are the natural numbers and whose morphisms from n to p are the monotone surjections from {0, . . . , n} to {0, . . . , p}. This category is studied in [START_REF] Livernet | An interpretation of E n -homology as functor homology[END_REF], where it is denoted by ∆ epi . The category Epi admits a presentation by the (infinite) 2-polygraph Σ with the natural numbers as 0-cells, with 1-cells

n + 1 s i / / n 0 ≤ i ≤ n,
where s i represents the map Let us prove that this 2-polygraph is convergent. For termination, given a 1-cell u = s i 1 . . . s i k of Σ * , we define the natural number ν(u) as the number of pairs (i p , i q ) such that i p ≤ i q , with 1 ≤ p < q ≤ k.

s i (j) = j if 0 ≤ j ≤ i, j -1 if i + 1 ≤ j ≤ n + 1,
In particular, we have ν(s i s j ) = 1 and ν(s j+1 s i ) = 0 when i ≤ j, i.e., when s i s j is the source and s j+1 s i is the target of a 2-cell of Σ. Moreover, we have ν(wuw ) > ν(wvw ) when ν(u) > ν(v) holds. Thus, for every non-identity 2-cell f : u ⇒ v in Σ * , the strict inequality ν(u) > ν(v) is satisfied, yielding termination of Σ. The 2-polygraph Σ has one critical branching (s i,j s k , s i s j,k ) for every possible 0 ≤ i ≤ j ≤ k ≤ n+2 and it is confluent, so that we get a partial resolution of Epi by the acyclic (3, 1)-polygraph c 2 (Σ) obtained by extending Σ with all the 3-cells filling the confluence diagrams associated to the critical branchings: s j+1 s i s k s j+1 s i,k 7 9 s j+1 s k+1 s i s j+1,k+1 s i & .

s i s j s k s i,j s k C ?

s i s j,k 2 4
s k+2 s j+1 s i .

s i s k+1 s j s i,k+1 s j 7 9 s k+2 s i s j s k+2 s i,j G C s i,j,k Õ

The category Epi

To simplify notations, we draw each 1-cell s i as a vertical string i , each 2-cell s i,j as i,j , so that each 3-cell s i,j,k has the same shape as the Yang-Baxter relation, or permutohedron of order 3: i,j,k i,j,k 7 9

i,j,k

Using those notations, the natural system h 2 (Σ) of homological 2-syzygies of Σ is generated by the elements

δ 3 i,j,k = i,j,k - i,j,k =        [ i,j ]s k -s k+2 [ i,j ] + s j+1 [ i,k ] -[ i,k+1 ]s j + [ j+1,k+1 ]s i -s i [ j,k ] .
The 2-polygraph Σ has one critical triple branching s i,j s k s l , s i s j,k s l , s i s j s k,l for every possible 0 ≤ i ≤ j ≤ k ≤ l ≤ n + 3. This yields a partial resolution of Epi by the acyclic (4, 1)-polygraph c 3 (Σ) with one 4-cell s i,j,k,l for every possible 0 ≤ i ≤ j ≤ k ≤ l ≤ n + 3. In string diagrams, omitting the subscripts, each critical triple branching is written , , .

With the same conventions, the corresponding 4-cell has the shape of the permutohedron of order 4: As usual, the elements δ 4 i,j,k,l , for 0 ≤ i ≤ j ≤ k ≤ k ≤ n + 3, form a generating set for the natural system h 3 (Σ) of homological 3-syzygies of Σ.

More generally, this construction extends to a polygraphic resolution of Epi where, for every natural number n, the generating n-cell has the shape of a permutohedron of order n.

  xy ⇒ v and β : yz ⇒ w generate a critical branching (αz, xβ) on u = xyz: Convergence of the presentation (Σ 1 , Σ 2 ) ensures that any critical branching (f, g) can be completed as in the following diagram: The boundary of such a branching is defined as the element J (f, g) = [f] -[g] + [f ] -[g ], where [ • ] extends the canonical inclusion of Σ 2 into ZM[Σ 2 ].

Theorem 2 . 3 . 4 .

 234 Let Σ be a polygraphic resolution of a p-category C. The canonical projection ΣC is a cofibrant approximation of C in the canonical model structure on (∞, p)-categories.

. 3 . 5 .

 35 Corollary. Let Σ be an (n, 1)-polygraph. Left (resp. right) normalisation strategies on Σ are in bijective correspondence with the families σ uϕ : uϕ → uϕ ( resp. σ ϕ u : ϕ u → ϕu ) and with the families σ * uϕ : ( uϕ) * → ϕu * ( resp. σ * ϕ u : (ϕ u) * → ϕu * ) of (k + 1)-cells, indexed by k-cells ϕ of Σ, for 1 ≤ k < n, and by 1-cells u of Σ such that the composite k-cell uϕ (resp. ϕ u) exists. Proof. Let us assume, for example, that σ is a left normalisation strategy. The property satisfied by σ on 1-cells of Σ gives, by induction on the size of 1-cells, that the values of σ on 1-cells of Σ are determined by the 2-cells σ ux , for x a 1-cell of Σ and u a 1-cell of Σ such that ux is defined. Then, Lemma 3.3.1 tells us that the values of σ on higher-dimensional cells of Σ are determined by the values of σ or of σ * on k-cells uϕv of Σ , where ϕ is a k-cell of Σ and u and v are 1-cells of Σ . We use Lemma 3.3.4 to conclude.

•••

  if uv is an identity, but not vw: if uv is not an identity, but vw is: if uv and vw are identities, and thus u = uvw = w:As a conclusion, the reduced standard presentation N C of the category C is a reduced convergent presentation of C.

4. 2 .

 2 Normalisation strategies for convergent 2-polygraphs 4.2.1. The order relation on branchings. Let Σ be a reduced 2-polygraph and let u be a 1-cell in Σ * .

  . A reduced and terminating 2-polygraph can have several left or right strategies, beside the leftmost and the rightmost ones. Indeed, let us consider the reduced and terminating 2-polygraph Σ with one 0-cell, three 1-cells a, b and c and the following three 2-cells: aac α 7 9 a bb β 7 9 cc acc γ 7 9 c.Let us prove that Σ admits at least two different left normalisation strategies. For that, we examine the 1-cell aabb and all the 2-cells of Σ * from aabb to its normal form ac:

4. 3 . 2 .

 32 The basis of generating confluences. The basis of generating confluences of Σ is the cellular extension c 2 (Σ) of Σ made of one 3-cellu v σ u v ( branching b = (ϕ v, ρ u v ) of Σ.Alternatively, since, for a 2-cell f, we have defined f * as the 2-cell f 1 σ t(f) , the 3-cell ω b can be pictured in the following, more compact way: .3. Lemma. The rightmost normalisation strategy of Σ extends to a right normalisation strategy of c 2 (Σ).

4. 3 . 4 .

 34 Proposition. The (3, 1)-polygraph c 2 (Σ) is acyclic.

•

  if uv is an identity, but not vw:

4. 4 . 2 .

 42 The basis of generating triple confluences. The basis of generating triple confluences of Σ is the cellular extension c 3 (Σ) of c 2 (Σ) made of one 4-cell

Õ 4 . 4 . 3 .

 443 Lemma. The rightmost normalisation strategy of Σ extends to a right normalisation strategy of c 3 (Σ). Proof. Let us define a 4-cell σ * ωc w : (ω c w) * 1 ? ω c w * of c 3 (Σ) for every 3-cell ω c of c 2 (Σ) and every 1-cell w in Σ such that ω c w exists. Let us denote by v the source of the critical branching c of Σ and by f the rewriting step of Σ with source v such that the critical branching c is (f, ρ v ). We proceed by case analysis on the type of the local triple branching b = (f w, ρ v w, ρ v w ).

4. 4 . 4 .

 44 Proposition. The (4, 1)-polygraph c 3 (Σ) is acyclic. 4.4.5. Corollary. A category with a finite convergent presentation is FDT 4 .

4. 5 .

 5 The polygraphic resolution generated by a convergent 2-polygraph before, we study the possible shapes of an n-fold critical branching b of Σ and we conclude that it must have shape b = c v, ρ u v

4. 5 . 2 .

 52 The basis of generating n-fold confluences. The basis of generating n-fold confluences of Σ is the cellular extension c n (Σ) of c n-1 (Σ) made of one (n + 1)-cell ω b : ω c v * -→ ω c v * for every critical n-fold branching b = (c v, ρ u v ) of Σ. The extension of the right normalisation strategy to c n (Σ) is made in the same way as in the case n = 3. It relies on a Corollary 3.3.5 and a case analysis, whose main point is to define an (n + 1)-cell σ * ωc w : (ω c w) * -→ ω c w * in c n (Σ) for every local n-fold branching b = c w, ρ v w

4. 5 . 3 .

 53 Theorem. Every convergent 2-polygraph Σ extends to a Tietze-equivalent, acyclic (∞, 1)-polygraph c ∞ (Σ), whose generating n-cells, for every n ≥ 3, are (indexed by) the critical (n -1)-fold branchings of Σ.

4. 5 . 5 .

 55 Example. If N C is the reduced standard presentation of a category C, we have already built the dimensions 3 and 4 of the (∞, 1)-polygraph c ∞ (N C), called the reduced standard polygraphic resolution of C.

  ZC denote the C o × C-module ZC whose component at (x, y) is the free Z-module ZC(x, y) generated by C(x, y).A category C is of homological typei) FP n when the constant natural system Z is of type FP n , ii) bi-FP n when the C o × C-module ZC is of type FP n , iii) left-FP n when the constant C-module Z is of type FP n , iv) right-FP n when the constant C o -module Z is of type FP n , v) top-FP n when the constant C -module Z is of type FP n .5.2.4. Proposition. For categories, we have the following implications:right-FP n

5. 3 .

 3 The Reidemeister-Fox-Squier complexWe consider the nerve N * (C) of C, with boundary mapsd i : N n (C) → N n-1 (C), for 0 ≤ i ≤ n. For s = (u 1 , . . . , u n ) in N n (C), we denote by s the composite 1-cell u 1 • • • u n of C.For every natural number n, the n-th chain group C n (C, D) is defined as the Abelian group C n (C, D) = s∈Nn(C) D s . We denote by ι s the embedding of D s into C n (C, D). The boundary map d : C n (C, D) → C n-1 (C, D) is defined, on the component D s of C n (C, D), by:

  , for every k in {1, . . . , n}, f k and g k are k-cells of C. The context C is a whisker of C if the n-cells f n and g n are identities. If f is an n-cell of C with boundary x, one denotes by C[f] the n-cell of C obtained by replacing x with f in C.

5. 6 . 3 .

 63 Lemma. Let Σ be a 2-polygraph. For every closed 2-cell f of Σ , we have [f] = 0 in F C [Σ 2 ] if, and only if, f = 0 holds in Π(Σ). Proof. To prove that f = 0 implies [f] = 0, we check that the relations defining Π(Σ) are also satisfied in F C [Σ 2 ]. The first relation is given by the definition of the map [•]. The second relation is checked as follows: [f 1 g] = [f] + [g] = [g] + [f] = [g 1 f].

5. 6 . 4 .

 64 Lemma. Let Σ be a 2-polygraph. For every element a in h 2 (Σ), there exists a closed 2-cell f in Σ such that a = [f] holds.Proof. Let w be the 1-cell of Σ such that a belongs to F Σ [Σ 2 ] w and let Σ 3 be a homotopy basis of the (2, 1)-category Σ . Since δ 2 (a) = 0, Theorem 5.4.3 implies the existence of an element b in F Σ [Σ 3 ] w such that a = δ 3 (b) holds. By definition of F Σ [Σ 3 ] w , we can write b = p i=1 ε i u i [α i ]v i

Finally, we get: a = δ 3 [

 3 A] = [s(A)] -[t(A)] = [s(A) 1 t(A) -]. Hence f = s(A) 1 t(A) -is a closed 2-cell of Σ that satisfies a = [f].

The 2 -

 2 polygraph As has exactly one critical triple branching:

  Let us assume that n < ∞ and 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. 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 size of an (n + 1)-cell f of C[Γ ] is the number of (n + 1)-cells of Γ it contains.

	2.2. Polygraphs
	2.2.1. Cellular extensions.

  5.2.6. Proposition. For groupoids, the properties FP n , bi-FP n , left-FP n , right-FP n and top-FP n are equivalent.Proof. If G is a groupoid, then the groupoid G generated by G is G itself. Hence, the properties left-FP n and top-FP n are equivalent. As a consequence, it is sufficient to prove that left-FP n implies FP n to conclude the proof.

Acknowledgements

The authors wish to thank François Métayer, Timothy Porter and the anonymous referee for their comments and suggestions that helped to produce an improved version of this work.

with h u a 2-cell of Σ * . The 2-cell g u of Σ * is given by g u = h u w 1 σ vs(ϕ)w and use the hypothesis on σ to get: σ u = σ vs(ϕ) w 1 σ vs(ϕ)w = λ vs(ϕ) w 1 g u = λ u 1 g u .

The case of a right normalisation strategy is symmetric. 4.2.5. Example. Let C be a category and let N C be its reduced standard presentation. A generic 1-cell of N C is a composite u 1 • • • u n of non-identity 1-cells of C. In the case where no partial composition u i u i+1 • • • u j is an identity in C, the leftmost reduction strategy σ of C is given on u 1 • • • u n by:

If some partial composition is an identity in C, we get σ u 1 ••• un by removing the corresponding 2-cell µ. For example, in the case n = 4, u 1 u 2 = 1 and u 3 u 4 = 1, we have:

The rightmost normalisation strategy of N C is given in a symmetric way.

The acyclic (3, 1)-polygraph of generating confluences

We fix a reduced convergent 2-polygraph Σ equipped with its rightmost normalisation strategy σ.

4.

3.1. Critical branchings of 2-polygraphs. By case analysis on the source of critical branchings of Σ, we can conclude that they must have one of the following two shapes

We note that, if Σ is finite, then it has finitely many critical branchings: indeed, in that case there are finitely many pairs of 2-cells of Σ and, for ϕ and ψ fixed, there are finitely many ways to make their sources (which are 1-cells of a free category) overlap as in one of the two diagrams.

In fact, the 2-polygraph Σ being reduced, the first case cannot occur since, otherwise, the source of ϕ would be reducible by ψ. Thus, every critical branching of Σ must have shape (ϕv, u 1 ψ). We write the branching in that order since, by definition of , we have ϕv u 1 ψ.

We also note that the 1-cells u 1 , u 2 and v are normal forms and cannot be identities. Indeed, they are normal forms since, otherwise, at least one of the sources of ϕ and of ψ would be reducible by another 2-cell, preventing Σ from being reduced. If u 2 was an identity, then the branching would be i) The C-module M is of homological type FP n .

ii) There exists a free, finitely generated partial resolution of M of length n:

iii) The C-module M is finitely generated and, for every 0 ≤ k < n and every projective, finitely generated partial resolution of M of length k

Proof. Let us assume that M is a C-module of type FP n . Then there exists a projective, finitely generated partial resolution P * → M of length n. If x is a 0-cell in D, then we have:

Since each C-module P i is finitely generated and projective, then so is the D-module Lan F (P i ). Moreover, the functor Lan F is right-exact: it follows that Lan F (P * ) → Lan F (M) is a projective, finitely generated partial resolution of length n. This proves that Lan F (M) is of type FP n .

Let us denote, for every 1 ≤ i ≤ p, the source and target of ϕ ε i i by w i and w i respectively. They satisfy w i = w i . We also fix a section • and a left strategy σ for the 2-polygraph Σ. In particular, the section satisfies u = v for every 1-cells u and v such that u = v.

For every 1 ≤ i ≤ p, we denote by f i the following 2-cell of Σ :

Using the facts that w is equal to both u 1 w 1 v 1 and u p w p v p and that u i w i v i is equal to u i+1 w i+1 v i+1 for every 1 ≤ i < p, we can write the 2-cell f of the (2, 1)-category Σ as the following composite:

As a consequence, we get:

In order to conclude this proof, it is sufficient to check that, for every 1 ≤ i ≤ p, we have the equality f τ(i) = -f i . Let us fix an i in {1, . . . , p} and let us compute f i . Since σ is a left normalisation strategy, we have

and, using the fact that u i w i = u i w i ,

This gives:

We can remove the final 2-cell σ u i w i v i and its inverse at the beginning of the composition, to get:

Then, we use exchange relations to get:

Now, let us compute f τ(i) . We already know that ϕ τ(i) = ϕ i and ε τ(i) = -ε i . As a consequence, we get w τ(i) = w i and w τ(i) = w i . Moreover, we have u τ(i) = u i , so that we have:

We remove the 2-cell σ u i w i v τ(i) and its inverse and, then, we use exchange relations and v τ(i) = v i , in order to get:

This implies f = 0, thus concluding the proof.

Abelian finite derivation type

This definition does not depend on the choice of f. Indeed, let us assume that g : v ⇒ v is a closed 2-cell such that a = [g] holds. It follows that v = w = u. Hence, we can choose a 2-cell h : u ⇒ v in Σ .

Then we have:

As a consequence, we get:

The relations ΨΦ = 1 Π(Σ) and ΦΨ = 1 h 2 (Σ) are direct consequences of the definitions of Φ and Ψ.

Abelian finite derivation type

An (n, n -1)-category C is Abelian if, for every (n -1)-cell u of C, the group Aut C u of closed n-cells of C with source u is Abelian. The Abelian (n, n -1)-category generated by C is the (n, n -1)-category, denoted by C ab and defined as the quotient of C by the cellular extension that contains one n-sphere f n-1 g -→ g n-1 f for every closed n-cells f and g of C with the same source.

One says that an n-polygraph Σ is of Abelian finite derivation type, FDT ab for short, when the Abelian (n, n -1)-category Σ ab admits a finite homotopy basis. In this section, we prove that an n-polygraph is FDT ab if, and only if, the natural system Π(Σ) of identities among relations of Σ is finitely generated.

In [START_REF]Identities among relations for higher-dimensional rewriting systems[END_REF], it is proved that, given an n-polygraph Σ, there exists an isomorphism of natural systems on the free (n -1)-category Σ * n-1 :

In fact, this property characterises the natural system Π(Σ) on the (n -1)-category Σ up to isomorphism.

In [START_REF]Identities among relations for higher-dimensional rewriting systems[END_REF], we also proved the following result.

Lemma ([19]

). Let C be an (n, n -1)-category and let B be a family of closed n-cells of C. The following assertions are equivalent:

with, for every 1 ≤ i ≤ p, β i in B, ε i in {-, +}, C i a whisker of C and g i an n-cell of C.

5.7.2.

Proposition. An n-polygraph Σ is FDT ab if, and only if, the natural system Π(Σ) on Σ is finitely generated.

Proof. Let us assume that the n-polygraph Σ is FDT ab . Then the Abelian (n, n -1)-category Σ ab has a finite homotopy basis B. Let ∂B be the set of closed n-cells of Σ ab defined by:

By Lemma 5.7.1, any closed n-cell f in Σ ab can be written

with, for every 1 ≤ i ≤ p, β i in B, ε i in {-, +}, C i a whisker of Σ and g i an n-cell of Σ . As a consequence, for any identity among relations f in Π(Σ), we have:

Thus, the elements of ∂B form a generating set for the natural system Π(Σ). Hence Π(Σ) is finitely generated.

Conversely, suppose that the natural system Π(Σ) is finitely generated. This means that there exists a finite set B of closed n-cells of Σ ab such that the following property is satisfied: for every (n -1)-cell u of Σ and every closed n-cell f with source v of Σ ab such that v = u, one can write

with, for every 1 ≤ i ≤ p, β i in B, C i a whisker of Σ and ε i an integer; moreover, each whisker C i is such that, for every representative C i of C i in Σ ab , C i [β i ] is a closed n-cell of Σ ab whose source v i satisfies v i = v. We fix, for every i, an n-cell g i : v ⇒ v i in Σ . Then, the properties of Π(Σ) imply:

We use the isomorphism between Π(Σ) u and Aut Σ ab v and Lemma 5.7.1 to deduce that the cellular extension B = β : β → 1 sβ , β ∈ B of Σ ab is a homotopy basis. Thus Σ is FDT ab .

In [START_REF]Identities among relations for higher-dimensional rewriting systems[END_REF], the authors have proved that the property to be finitely generated for Π(Σ) is Tietze-invariant for finite polygraphs: if Σ and Υ are two Tietze-equivalent finite n-polygraphs, then the natural system Π(Σ) is finitely generated if, and only if, the natural system Π(Υ) is finitely generated. By Proposition 5.7.2, we deduce that the property FDT ab is Tietze-invariant for finite polygraphs, so that one can say that an n-category is FDT ab when it admits a presentation by a finite (n + 1)polygraph which is FDT ab . In this way, the following result relates the homological property FP 3 and the homotopical property FDT ab . 5.7.3. Theorem. Let C be a category with a finite presentation Σ. The following conditions are equivalent:

Examples

We compute the 3-cells ω f,g , σ * f a and σ * g a , using their definitions and the properties of the rightmost normalisation strategy σ, to get:

We fill the diagram defining ω b = , obtaining:

Contracting one dimension, we see that the 4-cell is, in fact, Mac Lane's pentagon, or Stasheff's polytope K 4 :

We get a finite, acyclic (4, 1)-polygraph c 3 (As) which is a partial polygraphic resolution of A of length 4, proving that A has the property FDT 4 and, as a consequence, that it is of homological type FP 4 . In particular, the natural system h 3 (As) of homological 3-syzygies of As is generated by the following element:

Iterating the process, we get a resolution of A by an acyclic (∞, 1)-polygraph c ∞ (As). For every natural number, c ∞ (As) has exactly one n-cell, whose shape is Stasheff's polytope K n . For example, in dimension 5, the generating 5-cell ω b is associated to the following critical quadruple branching: b = , , , .

To compute the source and target of the corresponding 4-cell ω b , we use the inductive construction of the rightmost strategy σ. Alternatively, one can also start from the 2-dimensional source and target of ω b , which are obtained as the 2-cells associated to the source aaaaa of the critical quadruple branching b by the leftmost and the rightmost strategies, respectively: