The Theory of Ends, Pushdown Automata, and Second-Order Logic
The Theory of Ends, Pushdown Automata, and Second-Order Logic
复制标题
DOI：
10.1016/0304-3975(85)90087-8
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
D. E. Muller;P. Schupp
中科院分区：
文献类型：
--
作者：
D. E. Muller;P. Schupp
一类称为上下文无关的边缘标记图是根据它们在无穷远处的行为来定义的。这些图是上下文无关群的凯莱图的概括。它们还被证明可以在下推自动机方面以非常自然的方式定义。使用关于有限二叉树的一元二阶理论的拉宾定理，这些图也被证明具有可判定的一元二阶理论。当系统在二维网格上运行时，关于在这些图上运行的平铺系统和元胞自动机的问题是可判定的，即使类似的问题不是可判定的。
A class of edge-labeled graphs calledcontext-freeare defined according to their behavior at infinity. Such graphs are generalizations of Cayley graphs of context-free groups. They are also shown to be definable in a very natural way in terms of push-down automata. Using Rabin's theorem on the monadic second-order theory of the finite binary tree, these graphs are also shown to have a decidable monadic second-order theory. Questions about tiling systems and cellular automata operating on these graphs are decidable even when the analogous questions are not, when the systems operate on a two-dimensional grid.