Extensions of MSO and the monadic counting hierarchy
Extensions of MSO and the monadic counting hierarchy
复制标题
MSO 和单子计数层次结构的扩展
DOI：
10.1016/j.ic.2010.09.002
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
H. Niemistö
中科院分区：
文献类型：
--
作者：
J. Kontinen;H. Niemistö
本文研究了一元二阶多数量词Most 1对一阶逻辑的扩充的表达能力。在1中，它被证明是FO的扩展的二阶多数量词的所有arities准确地描述了计数层次中的问题。我们首先考虑某些子逻辑的FO（Most 1）的一元词汇。我们证明了在一元词汇表上，逻辑MSO（R），其中MSO是一元二阶逻辑，R是一阶Rescher量词，可以用Presburger算术来表征，而逻辑[公式：见正文]，其中Rnis R的第n个向量化，对应于算术的Δ0-片段。然后我们证明了[公式：见正文]，并且在一元词汇表上，FO（Most 1）坍缩为uniform-TC 0。使用这种崩溃，我们表明，一阶逻辑与二进制二阶多数量词是严格的表达比FO（Most 1）的空词汇。另一方面，在字符串上，FO（Most 1）被示为捕获计数层次的线性片段。最后，我们表明，在非一元词汇表，FO（Most 1）可以表示通过一阶减少计数层次的每个级别完成的问题。
In this paper, we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most1. In 1 it was shown that the extension of FO by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We consider first certain sublogics of FO(Most1) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic [Formula: see text] , where Rnis the nth vectorization of R, corresponds to the Δ0-fragment of arithmetic. Then we show that [Formula: see text] and that, on unary vocabularies, FO(Most1) collapses to uniform-TC0. Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most1) over the empty vocabulary. On the other hand, over strings, FO(Most1) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most1) can express problems complete via first-order reductions for each level of the counting hierarchy.