Back to Search
Start Over
DECIDABILITY AND COMPLEXITY IN AUTOMATIC MONOIDS.
- Source :
-
International Journal of Foundations of Computer Science . Aug2005, Vol. 16 Issue 4, p707-722. 16p. - Publication Year :
- 2005
-
Abstract
- 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]. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 16
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 17535026
- Full Text :
- https://doi.org/10.1142/S0129054105003248