FO Model Checking on Nested Pushdown Trees
FO Model Checking on Nested Pushdown Trees
复制标题
嵌套下推树的 FO 模型检查
DOI：
10.1007/978-3-642-03816-7_39
复制
发表时间：
2009
影响因子：
--
通讯作者：
Alexander Kartzow
中科院分区：
文献类型：
--
作者：
Alexander Kartzow
嵌套下推树是下推图的一种具有额外跳关系的开折。这些图与可折叠下推图密切相关。他们喜欢可判定的μ演算模型检查，而一元二阶逻辑在这个类上是不可判定的。我们表明，嵌套的下推树是树自动结构，因此一阶模型检测是可判定的。此外，我们证明了它是在2-EXPSPACE使用泵参数的运行下推系统。对于这些参数，我们还开发了一个Gaifman风格的小直径图的参数。
Nested Pushdown Trees are unfoldings of pushdown graphs with an additional jump-relation. These graphs are closely related to collapsible pushdown graphs. They enjoy decidable μ-calculus model checking while monadic second-order logic is undecidable on this class. We show that nested pushdown trees are tree-automatic structures, whence first-order model checking is decidable. Furthermore, we prove that it is in 2-EXPSPACE using pumping arguments on runs of pushdown systems. For these arguments we also develop a Gaifman style argument for graphs of small diameter.
关于 Caucal 层次结构中的图结构
DOI：
10.1016/j.tcs.2008.01.053
发表时间：
2008
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Achim Blumensath
通讯作者：
Achim Blumensath