Polygraphs of finite derivation type
arXiv:1402.2587 · doi:10.1017/S0960129516000220
Abstract
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 word 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 Squier's results in the contemporary language of polygraphs and higher-dimensional categories, with new proofs and relations between them.
References in corpus (3)
Cited by in corpus (12)
- Convergent presentations and polygraphic resolutions of associative algebras
- Normalization for planar string diagrams and a quadratic equivalence algorithm
- Coherent Presentations of Monoidal Categories
- Chinese syzygies by insertions
- Diagrammatic sets and rewriting in weak higher categories
- Coherence for braided and symmetric pseudomonoids
- Representable diagrammatic sets as a model of weak higher categories
- Topological closure of formal power series ideals and application to topological rewriting theory
- Rewriting techniques for relative coherence
- Strategies for linear rewriting systems: link with parallel rewriting and involutive divisions
- C-trees and a coherent presentation for the plactic monoid of type C
- Higher Catoids, Higher Quantales and their Correspondences