Back to Search
Start Over
Logical aspects of Cayley-graphs: the group case
- Source :
-
Annals of Pure & Applied Logic . Jan2005, Vol. 131 Issue 1-3, p263-286. 24p. - Publication Year :
- 2005
-
Abstract
- We prove that a finitely generated group is context-free whenever its Cayley-graph has a decidable monadic second-order theory. Hence, by the seminal work of Muller and Schupp, our result gives a logical characterization of context-free groups and also proves a conjecture of Schupp. To derive this result, we investigate general graphs and show that a graph of bounded degree with a high degree of symmetry is context-free whenever its monadic second-order theory is decidable. Further, it is shown that the word problem of a finitely generated group is decidable if and only if the first-order theory of its Cayley-graph is decidable. [Copyright &y& Elsevier]
- Subjects :
- *CAYLEY graphs
*THEORY
*GRAPH theory
Subjects
Details
- Language :
- English
- ISSN :
- 01680072
- Volume :
- 131
- Issue :
- 1-3
- Database :
- Academic Search Index
- Journal :
- Annals of Pure & Applied Logic
- Publication Type :
- Academic Journal
- Accession number :
- 14785535
- Full Text :
- https://doi.org/10.1016/j.apal.2004.06.002