Undecidable properties of monoids with word problem solvable in linear time. Part II - cross sections and homological and homotopical finiteness conditions

摘要

Using a particular simulation of single-tape Turing machines by finite string-rewriting systems the first two authors have shown that all linear Markov properties are undecidable for the class of finitely 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 proper-ties are undecidable for this class of monoids. These properties include the existence of context-free or regular cross-sections, the existence of finite convergent presentations, the property of being automatic, and the homological and homotopical finiteness properties left- and right-FPn (n greater than or equal to 3), FHT, and FDT. (C) 2002 Elsevier Science B.V. All rights reserved. [References: 30]