FDT is undecidable for finitely presented monoids with solvable word problems

DOI10.1007/BFB0036200MaRDI QIDQ5055951zbMATH OpenOpenAlexFDO

Authors Friedrich Otto, Andrea Sattler-Klein

Publication date 9 December 2022

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0036200

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05)

Recommendations

• THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
• scientific article; zbMATH DE number 4014693
• New undecidability results for finitely presented monoids
• Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
• Uniform decision problems for certain restricted classes of finite monoid presentations -- a survey on recent undecidability results

Cites work

• A finiteness condition for rewriting systems
• A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
• Complete rewriting systems and homology of monoid algebras
• Divergence phenomena during completion
• FDT is undecidable for finitely presented monoids with solvable word problems
• Finite derivation type implies the homological finiteness condition \(FP_ 3\)
• For groups the property of having finite derivation type is equivalent to the homological finiteness condition \(FP_ 3\)
• scientific article; zbMATH DE number 1008515 (Why is no real title available?)
• scientific article; zbMATH DE number 1972807 (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?)
• LOW-DIMENSIONAL HOMOTOPY THEORY FOR MONOIDS
• New undecidability results for finitely presented monoids
• Termination for direct sums of left-linear complete term rewriting systems
• Word problems and a homological finiteness condition for monoids

Cited in

(4)

• Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
• scientific article; zbMATH DE number 2080253 (Why is no real title available?)
• THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
• FDT is undecidable for finitely presented monoids with solvable word problems

This page was built for publication: FDT is undecidable for finitely presented monoids with solvable word problems

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