Undecidability results for monoids with linear-time decidable word problems

DOI10.1007/3-540-40996-3_24MaRDI QIDQ4472500zbMATH OpenFDO

Authors Friedrich Otto, Masashi Katsura, Yuji Kobayashi

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/1969/19690278.htm

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
• Undecidable properties of monoids with word problem solvable in linear time.
• New undecidability results for finitely presented monoids
• 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

Cited in

(6)

• Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
• Undecidable properties of monoids with word problem solvable in linear time.
• Decidable sentences for context-free groups
• New undecidability results for finitely presented monoids
• THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
• Mathematical Foundations of Computer Science 2003

This page was built for publication: Undecidability results for monoids with linear-time decidable word problems

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