Paper Info
Title
Undecidability Results for Monoids with Linear-Time Decidable Word Problems
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 Clin of finitely presented monoids with linear-time decidable word problems. Expanding on this construction it is then shown that also many other properties are undecidable for Clin, 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 ≥ 3), left- and right-FP∞, FDT and FHT.
Year
DOI
Venue
2000
10.1007/3-540-40996-3_24
ISAAC
Keywords
Field
DocType
strong markov property,homotopical finiteness condition,turing machine,linear-time decidable word problem,linear-time decidable word problems,class clin,undecidability results,finite string-rewriting system,finite convergent presentation,linear time,markov property,word problem,cross section
Discrete mathematics,Word problem (mathematics education),Markov chain,Decidability,Monoid,Turing machine,Time complexity,Mathematics,Undecidable problem
Conference
Volume
ISSN
ISBN
1969
0302-9743
3-540-41255-7
Citations 
PageRank 
References 
0
0.34
9
Authors
3
Name
Order
Citations
PageRank
M. Katsura15810.49
Yuji Kobayashi2182.82
Friedrich Otto328134.60