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.


Authors/Editors

Last updated on 2019-25-07 at 14:06