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

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

zbMATH Keywords

undecidabilityword problemfinitely presented monoidsfinite derivation type

Mathematics Subject Classification ID

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