Conference proceedings article
Undecidability results for monoids with linear-time decidable word problem
Publication Details
Authors: | Katsura, M.; Kobayashi, Y.; Otto, F. |
Editor: | D.T. Lee, Sh. Teng |
Publisher: | Springer |
Place: | Berlin |
Publication year: | 2000 |
Pages range : | 278-289 |
Book title: | Algorithms and Computation, Proceedings ISAAC'2000 |
Title of series: | Lecture Notes in Computer Science 1969 |
Abstract
Using a particularly adopted simulation of Turing machines by finite string-rewriting systems we show that all strong Markov properties are undecidable for the class C-lin of finitely presented monoids with linear-time, decidable word problems. Expanding on this construction it is then shown that also many other properties axe undecidable for C-lin, among them the property of having a context-free (or a regular) cross-section, the existence of a finite convergent presentation, and the homological and homotopical finiteness conditions left- and right-FPn (n greater than or equal to 3), left- and right-FPinfinity, FDT and FHT.
Using a particularly adopted simulation of Turing machines by finite string-rewriting systems we show that all strong Markov properties are undecidable for the class C-lin of finitely presented monoids with linear-time, decidable word problems. Expanding on this construction it is then shown that also many other properties axe undecidable for C-lin, among them the property of having a context-free (or a regular) cross-section, the existence of a finite convergent presentation, and the homological and homotopical finiteness conditions left- and right-FPn (n greater than or equal to 3), left- and right-FPinfinity, FDT and FHT.
