Beitrag in einem Tagungsband
Undecidability results for monoids with linear-time decidable word problem
Details zur Publikation
Autor(inn)en: | Katsura, M.; Kobayashi, Y.; Otto, F. |
Herausgeber: | D.T. Lee, Sh. Teng |
Verlag: | Springer |
Verlagsort / Veröffentlichungsort: | Berlin |
Publikationsjahr: | 2000 |
Seitenbereich: | 278-289 |
Buchtitel: | Algorithms and Computation, Proceedings ISAAC'2000 |
Titel der Buchreihe: | Lecture Notes in Computer Science 1969 |
Zusammenfassung, 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.
