Logical aspects of Cayley-graphs: the group case
Logical aspects of Cayley-graphs: the group case
复制标题
凯莱图的逻辑方面：群案例
DOI：
10.1016/j.apal.2004.06.002
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Markus Lohrey
中科院分区：
文献类型：
--
作者：
D. Kuske;Markus Lohrey
我们证明了当有限生成群的Cayley-图具有可判定的单二阶理论时，它是上下文无关的。因此，通过Muller和Schupp的开创性工作，我们的结果给出了上下文无关群的一个逻辑刻画，并证明了Schupp的一个猜想。为了得到这一结果，我们研究了一般图，并证明了具有高度对称度的有界度图是上下文无关的，只要它的一元二阶理论是可判定的。进一步证明了有限生成群的字问题是可判定的当且仅当它的Cayley图的一阶理论是可判定的。
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.