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

DOI10.1016/S0304-3975(02)00570-4zbMath1053.68055MaRDI QIDQ1399980

Yuji Kobayashi, Masashi Katsura, Friedrich Otto

Publication date: 30 July 2003

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

zbMATH Keywords

finite string-rewriting systemssingle-tape Turing machines

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subrekursive Komplexität bei Gruppen. I: Gruppen mit vorgeschriebener Komplexität
• Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
• A finiteness condition for rewriting systems
• Undecidable properties of monoids with word problem solvable in linear time.
• Automatic semigroups
• 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
• Church-Rooser property and homology of monoids
• String rewriting and homology of monoids
• Diagram groups
• New undecidability results for finitely presented monoids
• THE PROPERTY FDT IS UNDECIDABLE FOR FINITELY PRESENTED MONOIDS THAT HAVE POLYNOMIAL-TIME DECIDABLE WORD PROBLEMS
• SECOND ORDER DEHN FUNCTIONS OF GROUPS AND MONOIDS
• ON HOMOTOPICAL AND HOMOLOGICAL FINITENESS CONDITIONS FOR FINITELY PRESENTED MONOIDS
• SOME EXACT SEQUENCES FOR THE HOMOTOPY (BI-)MODULE OF A MONOID
• LOW-DIMENSIONAL HOMOTOPY THEORY FOR MONOIDS