Undecidable properties of monoids with word problem solvable in linear time.

DOI10.1016/S0304-3975(01)00275-4zbMath1044.68078OpenAlexW2079333248MaRDI QIDQ1401160

Masashi Katsura, Yuji Kobayashi

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00275-4

zbMATH Keywords

finitely presented monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (1)

Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Undecidable questions related to Church-Rosser Thue systems
• The Knuth-Bendix Completion Procedure and Thue Systems
• Fast Pattern Matching in Strings
• New undecidability results for finitely presented monoids
• Divergence phenomena during completion

This page was built for publication: Undecidable properties of monoids with word problem solvable in linear time.