THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS

DOI10.1142/S0218196700000108zbMATH Open1029.20028OpenAlexW2049964808MaRDI QIDQ4786249FDOQ4786249

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

zbMATH Keywords

undecidabilityword problemfinite derivation typefinitely presented monoids

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Free semigroups, generators and relations, word problems (20M05)

Cites Work

• Complete rewriting systems and homology of monoid algebras
• Word problems and a homological finiteness condition for monoids
• Finite derivation type implies the homological finiteness condition \(FP_ 3\)
• LOW-DIMENSIONAL HOMOTOPY THEORY FOR MONOIDS
• A finiteness condition for rewriting systems
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
• For groups the property of having finite derivation type is equivalent to the homological finiteness condition \(FP_ 3\)
• Termination for direct sums of left-linear complete term rewriting systems
• Confluent and Other Types of Thue Systems
• Infinite regular Thue systems

Cited In (2)

• Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
• Finite derivation type for Rees matrix semigroups

This page was built for publication: THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4786249)