Undecidable properties of monoids with word problem solvable in linear time. Part II— cross sections and homological and homotopical finiteness conditions
✍ Scribed by Masashi Katsura; Yuji Kobayashi; Friedrich Otto
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 337 KB
- Volume
- 301
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
Using a particular simulation of single-tape Turing machines by ÿnite string-rewriting systems the ÿrst two authors have shown that all linear Markov properties are undecidable for the class of ÿnitely presented monoids with linear-time decidable word problem. Expanding on this construction it is shown here that also many properties that are not known to be linear Markov properties are undecidable for this class of monoids. These properties include the existence of context-free or regular cross-sections, the existence of ÿnite convergent presentations, the property of being automatic, and the homological and homotopical ÿniteness properties left-and right-FPn (n ¿ 3), FHT, and FDT.