In the general context of presentations of monoids, we study normalisation processes that are determined by their restriction to length-two words. Garsides greedy normal forms and quadratic convergent rewriting systems, in particular those associated
with the plactic monoids, are typical examples. Having introduced a parameter, called the class and measuring the complexity of the normalisation of length-three words, we analyse the normalisation of longer words and describe a number of possible behaviours. We fully axiomatise normalisations of class (4, 3), show the convergence of the associated rewriting systems, and characterise those deriving from a Garside family.
Several constructive homological methods based on noncommutative Grobner bases are known to compute free resolutions of associative algebras. In particular, these methods relate the Koszul property for an associative algebra to the existence of a qua
dratic Grobner basis of its ideal of relations. In this article, using a higher-dimensional rewriting theory approach, we give several improvements of these methods. We define polygraphs for associative algebras as higher-dimensional linear rewriting systems that generalise the notion of noncommutative Grobner bases, and allow more possibilities of termination orders than those associated to monomial orders. We introduce polygraphic resolutions of associative algebras, giving a categorical description of higher-dimensional syzygies for presentations of algebras. We show how to compute polygraphic resolutions starting from a convergent presentation, and how these resolutions can be linked with the Koszul property.
Craig Squier proved that, if a monoid can be presented by a finite convergent string rewriting system, then it satisfies the homological finiteness condition left-FP3. Using this result, he constructed finitely presentable monoids with a decidable wo
rd problem, but that cannot be presented by finite convergent rewriting systems. Later, he introduced the condition of finite derivation type, which is a homotopical finiteness property on the presentation complex associated to a monoid presentation. He showed that this condition is an invariant of finite presentations and he gave a constructive way to prove this finiteness property based on the computation of the critical branchings: being of finite derivation type is a necessary condition for a finitely presented monoid to admit a finite convergent presentation. This survey presents Squiers results in the contemporary language of polygraphs and higher-dimensional categories, with new proofs and relations between them.
We compute coherent presentations of Artin monoids, that is presentations by generators, relations, and relations between the relations. For that, we use methods of higher-dimensional rewriting that extend Squiers and Knuth-Bendixs completions into a
homotopical completion-reduction, applied to Artins and Garsides presentations. The main result of the paper states that the so-called Tits-Zamolodchikov 3-cells extend Artins presentation into a coherent presentation. As a byproduct, we give a new constructive proof of a theorem of Deligne on the actions of an Artin monoid on a category.
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 fr
om 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 Squiers finite derivation type for monoids. We relate this homotopical property to a new homological finiteness condition that we introduce here.
We introduce homotopical methods based on rewriting on higher-dimensional categories to prove coherence results in categories with an algebraic structure. We express the coherence problem for (symmetric) monoidal categories as an asphericity problem
for a track category and we use rewriting methods on polygraphs to solve it. The setting is extended to more general coherence problems, seen as 3-dimensional word problems in a track category, including the case of braided monoidal categories.
We generalize the notion of identities among relations, well known for presentations of groups, to presentations of n-categories by polygraphs. To each polygraph, we associate a track n-category, generalizing the notion of crossed module for groups,
in order to define the natural system of identities among relations. We relate the facts that this natural system is finitely generated and that the polygraph has finite derivation type.
We study convergent (terminating and confluent) presentations of n-categories. Using the notion of polygraph (or computad), we introduce the homotopical property of finite derivation type for n-categories, generalizing the one introduced by Squier fo
r word rewriting systems. We characterize this property by using the notion of critical branching. In particular, we define sufficient conditions for an n-category to have finite derivation type. Through examples, we present several techniques based on derivations of 2-categories to study convergent presentations by 3-polygraphs.
