DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS
Markus Lohrey · International Journal of Foundations of Computer Science · 2005
Several complexity and decidability results for automatic monoids are shown: (i) there exists an automatic monoid with a P-complete word problem, (ii) there exists an automatic monoid such that the first-order theory of the corresponding Cayley-graph is not elementary decidable, and (iii) there exists an automatic monoid such that reachability in the corresponding Cayley-graph is undecidable. Moreover, it is shown that for every hyperbolic group the word problem belongs to LOGCFL, which improves a result of Cai [8].