Polygraphs of finite derivation type
From MaRDI portal
2-categoryfinite derivation typehomological typehomotopy basesmonoidpolygraphstring rewritingword problem
Finite generation, finite presentability, normal forms (diamond lemma, term-rewriting) (16S15) Groupoids, semigroupoids, semigroups, groups (viewed as categories) (18B40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Grammars and rewriting systems (68Q42)
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.
Recommendations
- Finite derivation type implies the homological finiteness condition \(FP_ 3\)
- Low dimensional homotopy for monoids II: groups
- Higher-dimensional categories with finite derivation type
- Homological Finite Derivation Type
- A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
Cites work
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- A finiteness condition for rewriting systems
- A Monoid which is Right FP ∞ but not Left FP 1
- A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
- A note on a special one-rule semi-Thue system
- About the rewriting systems produced by the Knuth-Bendix completion algorithm
- Algebra and geometry of rewriting
- Church-Rooser property and homology of monoids
- Cofibrant objects among higher-dimensional categories
- Coherence in monoidal track categories
- Coherent presentations of Artin monoids
- Combinatorial group theory.
- Complete rewriting systems and homology of monoid algebras
- Computing critical pairs in 2-dimensional rewriting systems
- Finite derivation type implies the homological finiteness condition \(FP_ 3\)
- FINITENESS CONDITIONS FOR REWRITING SYSTEMS
- For groups the property of having finite derivation type is equivalent to the homological finiteness condition \(FP_ 3\)
- Higher-dimensional categories with finite derivation type
- Higher-dimensional normalisation strategies for acyclicity
- Higher-dimensional word problems with applications to equational logic
- scientific article; zbMATH DE number 6679826 (Why is no real title available?)
- scientific article; zbMATH DE number 4210420 (Why is no real title available?)
- scientific article; zbMATH DE number 3762893 (Why is no real title available?)
- scientific article; zbMATH DE number 46995 (Why is no real title available?)
- scientific article; zbMATH DE number 67429 (Why is no real title available?)
- scientific article; zbMATH DE number 1216133 (Why is no real title available?)
- scientific article; zbMATH DE number 1924513 (Why is no real title available?)
- scientific article; zbMATH DE number 1889386 (Why is no real title available?)
- scientific article; zbMATH DE number 789389 (Why is no real title available?)
- scientific article; zbMATH DE number 3299786 (Why is no real title available?)
- scientific article; zbMATH DE number 3045417 (Why is no real title available?)
- scientific article; zbMATH DE number 3047078 (Why is no real title available?)
- Identities among relations for higher-dimensional rewriting systems
- Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
- Limits indexed by category-valued 2-functors
- LOW-DIMENSIONAL HOMOTOPY THEORY FOR MONOIDS
- On the Homology of Associative Algebras
- On theories with a combinatorial definition of 'equivalence'
- Recursive unsolvability of a problem of Thue
- Term Rewriting and All That
- Termination orders for three-dimensional rewriting
- The algebra of oriented simplexes
- Word problems and a homological finiteness condition for monoids
Cited in
(40)- Polygraphic resolutions and homology of monoids
- The matching polynomial of a polygraph
- Finite derivation type implies the homological finiteness condition \(FP_ 3\)
- Knuth's coherent presentations of plactic monoids of type A
- A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
- Chinese syzygies by insertions
- Rewriting modulo isotopies in pivotal linear (2,2)-categories
- Coherent confluence modulo relations and double groupoids
- A combinatorial-topological shape category for polygraphs
- Rewriting modulo isotopies in Khovanov-Lauda-Rouquier's categorification of quantum groups
- Convergent presentations and polygraphic resolutions of associative algebras
- Topological rewriting systems applied to standard bases and syntactic algebras
- Categorified cyclic operads
- Coherent presentations of monoids with a right-Noetherian Garside family
- A categorical characterization of strong Steiner \(\omega\)-categories
- r-multisemigroups, modal quantales and the origin of locality
- Abstract strategies and coherence
- On the first Zagreb index of polygraphs
- Identities among relations for higher-dimensional rewriting systems
- Intensional properties of polygraphs
- scientific article; zbMATH DE number 988811 (Why is no real title available?)
- From Analytical Mechanics Problems to Rewriting Theory Through M. Janet’s Work
- Noncommutative Gröbner bases: applications and generalizations
- scientific article; zbMATH DE number 517043 (Why is no real title available?)
- scientific article; zbMATH DE number 1008515 (Why is no real title available?)
- Higher-dimensional normalisation strategies for acyclicity
- FINITENESS CONDITIONS FOR REWRITING SYSTEMS
- scientific article; zbMATH DE number 7471699 (Why is no real title available?)
- Algebraic coherent confluence and higher globular Kleene algebras
- A cubical Squier's theorem
- Confluence of algebraic rewriting systems
- Shuffle polygraphic resolutions for operads
- Coherence for plactic monoids via rewriting theory and crystal structures
- Pregeometric spaces from Wolfram model rewriting systems as homotopy types
- Single-set cubical categories and their formalisation with a proof assistant
- Super rewriting theory and nondegeneracy of odd categorified \(\mathfrak{sl}_2\)
- Rewriting techniques for relative coherence
- Higher catoids, higher quantales and their correspondences
- Topological closure of formal powers series ideals and application to topological rewriting theory
- Termination orders for 3-polygraphs
This page was built for publication: Polygraphs of finite derivation type
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3130298)
