Undecidable properties of monoids with word problem solvable in linear time. II: Cross sections and homological and homotopical finiteness conditions.
From MaRDI portal
Publication:1399980
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)
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
