Bounds for the Quantifier Depth in Finite-Variable Logics
Bounds for the Quantifier Depth in Finite-Variable Logics
复制标题
有限变量逻辑中量词深度的界限
DOI：
10.1145/2732409
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
O. Verbitsky
中科院分区：
文献类型：
--
作者：
C. Berkholz;A. Krebs;O. Verbitsky
给定FOk（k变量一阶逻辑）中两个可区分的结构GandH，设Ak（G，H）表示FOk公式从G到H的最小交错深度.设Ak（n）是Ak（G，H）在n元结构上的最大值。我们证明了FO 2的量词交替谱系在强数量形式下的严格性，即A2（n）>n/8 − 2，它紧到常数因子。对于每个k = 2，它甚至在着色树上也成立Ak（n）> logk+1 n − 2，这也是紧的，直到一个常数因子ifk = 3。Fork 103，最后一个下界也适用于未着色的树，而FO 2的交替层次甚至在所有未着色的图上都崩溃了。我们还展示了着色图GandHonn顶点的例子，如果交替数仅增加1，则可以在FO 2中更简洁地区分这些顶点：而在FO 2中，可以用有界量词深度从H中提取G，在FO 2中，这需要量词深度Ω（n2）。二次下界在这里是最可能的，因为如果GandH可以在FOk中用i个量词替换来区分，那么这可以用量词深度2k − 2+ 1和相同数量的替换来完成。
Given two structuresGandHdistinguishable in FOk(first-order logic withkvariables), let Ak(G,H) denote the minimum alternation depth of a FOkformula distinguishingGfromH. Let Ak(n) be the maximum value of Ak(G,H) overn-element structures. We prove the strictness of the quantifier alternation hierarchy of FO2in a strong quantitative form, namely A2(n) >n/8 − 2, which is tight up to a constant factor. For eachk⩾ 2, it holds that Ak(n) > logk+ 1n− 2 even over colored trees, which is also tight up to a constant factor ifk⩾ 3. Fork⩾ 3, the last lower bound holds also over uncolored trees, whereas the alternation hierarchy of FO2collapses even over all uncolored graphs. We also show examples of colored graphsGandHonnvertices that can be distinguished in FO2much more succinctly if the alternation number is increased just by one: Whereas in Σiit is possible to distinguishGfromHwith bounded quantifier depth, in Πithis requires quantifier depth Ω(n2). The quadratic lower bound is best possible here because, ifGandHcan be distinguished in FOkwithiquantifier alternations, this can be done with quantifier depthn2k− 2+ 1 and the same number of alternations.
登录
查看更多内容
一种为约束满足问题生成启发式的问题简化方法
DOI：
--
发表时间：
1988
期刊：
影响因子：
--
作者：
R. Dechter;J. Pearl
通讯作者：
J. Pearl
词上 FO2 的结构定理和严格交替层次
DOI：
--
发表时间：
2007
期刊：
Annual Conference for Computer Science Logic
影响因子：
--
作者：
Philipp Weis;N. Immerman
通讯作者：
N. Immerman
DOI：
--
发表时间：
1990
期刊：
影响因子：
--
作者：
N. Immerman;E. Lander
通讯作者：
E. Lander
有限变量逻辑中的等价性对于多项式时间是完全的
影响因子：
1.1
作者：
Martin Grohe
通讯作者：
Martin Grohe
DOI：
--
发表时间：
1981
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
N. Immerman
通讯作者：
N. Immerman