Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
复制标题
词上 FO2 的结构定理和严格交替层次
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
N. Immerman
中科院分区：
文献类型：
--
作者：
Philipp Weis;N. Immerman
众所周知，使用三个变量，只有两个变量表达的属性都可以表达单词上的每个一阶属性。在单词上具有两个变量的一阶逻辑。线性排序在字符串位置上。
对于两种语言，我们的结构定理使用给定的量词深度，N和使用M≤N的M≤N的M块显示出什么表达式。这两种语言的替代量化者。一般来说，一旦我们仅考虑一个有界尺寸的字母，fo2 [<]通常是NEXP完整的。
It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and well-studied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to FO2[<] and FO2[<, Suc], the latter of which includes the binary successor relation in addition to the linear ordering on string positions.
For both languages, our structure theorems show exactly whatis expressible using a given quantifier depth, n, and using m blocks of alternating quantifiers, for any m ≤ n. Using these characterizations, we prove, among other results, that there is a strict hierarchy of alternating quantifiers for both languages. The question whether there was such a hierarchy had been completely open. As another consequence of our structural results, we show that satisfiability for FO2[<], which is NEXP-complete in general, becomes NP-complete once we only consider alphabets of a bounded size.