THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
From MaRDI portal
Publication:4786249
DOI10.1142/S0218196700000108zbMath1029.20028OpenAlexW2049964808MaRDI QIDQ4786249
Andrea Sattler-Klein, Friedrich Otto
Publication date: 15 December 2002
Published in: International Journal of Algebra and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0218196700000108
Free semigroups, generators and relations, word problems (20M05) Grammars and rewriting systems (68Q42)
Related Items (2)
Finite derivation type for Rees matrix semigroups ⋮ Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
Cites Work
- For groups the property of having finite derivation type is equivalent to the homological finiteness condition \(FP_ 3\)
- Complete rewriting systems and homology of monoid algebras
- Word problems and a homological finiteness condition for monoids
- A finiteness condition for rewriting systems
- Finite derivation type implies the homological finiteness condition \(FP_ 3\)
- Infinite regular Thue systems
- A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
- Confluent and Other Types of Thue Systems
- Termination for direct sums of left-linear complete term rewriting systems
- LOW-DIMENSIONAL HOMOTOPY THEORY FOR MONOIDS
This page was built for publication: THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS