Logics with Rank Operators
Logics with Rank Operators
复制标题
具有排序运算符的逻辑
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Bastian Laubner
中科院分区：
文献类型：
--
作者：
A. Dawar;Martin Grohe;Bjarki Holm;Bastian Laubner
引入了一阶逻辑（FO）和不动点逻辑（FP）的扩展，并引入了计算可定义矩阵秩的算子。这些运算符是FP+C中计数运算（即带计数的定点逻辑）的推广，它们允许我们计算可定义向量空间的维数，而不仅仅是计算可定义集合的基数。我们定义的逻辑具有包含在多项式时间内的数据复杂度，并且所有已知的多项式时间查询在FP+C中不可定义的示例都可以在FP+rk中定义，FP+rk是FP的扩展与秩运算符。对于每一个素数p和每一个正整数n，我们有秩算子rk_p来确定一个矩阵在有限域GF_p上的秩，这个有限域GF_p是由一个n元组上的公式定义的。我们比较了通过改变p和n可以取的值而得到的逻辑的表达能力。特别是，我们证明了增加运算符的数量会产生无限层次的表达能力。即使在没有定点运算符的情况下，秩运算符的表现力也令人惊讶。证明了FO+rk_p可以定义确定性和对称传递闭包。这允许我们证明，在有序结构上，FO+rk_p捕获了复杂度类MOD_pL，对于p的所有素数值。
We introduce extensions of first-order logic (FO) and fixed-point logic (FP) with operators that compute the rank of a definable matrix. These operators are generalizations of the counting operations in FP+C (i.e. fixed-point logic with counting) that allow us to count the dimension of a definable vector space, rather than just count the cardinality of a definable set. The logics we define have data complexity contained in polynomial time and all known examples of polynomial time queries that are not definable in FP+C are definable in FP+rk, the extension of FP with rank operators. For each prime number p and each positive integer n, we have rank operators rk_p for determining the rank of a matrix over the finite field GF_p defined by a formula over n-tuples. We compare the expressive power of the logics obtained by varying the values p and n can take. In particular, we show that increasing the arity of the operators yields an infinite hierarchy of expressive power. The rank operators are surprisingly expressive, even in the absence of fixed-point operators. We show that FO+rk_p can define deterministic and symmetric transitive closure. This allows us to show that, on ordered structures, FO+rk_p captures the complexity class MOD_pL, for all prime values of p.