RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!
RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!
复制标题
等级逻辑已死，等级逻辑万岁！
DOI：
10.1017/jsl.2018.33
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Wied Pakusa
中科院分区：
文献类型：
--
作者：
Grädel;Wied Pakusa
受寻找多项式时间逻辑的启发，我们研究了秩逻辑(FPR)，它通过确定有限域上矩阵的秩算子来扩展带计数的不动点逻辑(FPC)。在我们的第一个主要结果中，我们证明了不同素数域上秩算子对FPC的扩张是不可比拟的。这解决了Dawar和Holm提出的一个悬而未决的问题，也意味着排名逻辑在其原始定义中对每个字段都有不同的排名运算符，无法捕获多项式时间。证明中的一个重要步骤是考虑可解性逻辑FPS，它是有限域上线性方程组可解性问题的量词的类似推广。可解逻辑可以很容易地嵌入到秩逻辑中，但它是否是严格的片段是开放的。在我们的第二个主要结果中，我们给出了这个问题的部分答案：在没有计数的情况下，秩运算符严格地比可解量词更具表现力。
Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from Ptime, almost nothing was known about the limitations of its expressive power.In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR.One important step in our proof is to consider solvability logic FPS which is the analogous extension of FPC by quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.
登录
查看更多内容
DOI：
10.1007/978-3-662-44522-8_5
发表时间：
2014
期刊：
ArXiv
影响因子：
--
作者：
Faried Abu Zaid;E. Grädel;Martin Grohe;Wied Pakusa
通讯作者：
Wied Pakusa
关于 logspace MOD 类的闭包属性的注释
DOI：
10.1016/s0020-0190(00)00091-0
发表时间：
2000
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
U. Hertrampf;S. Reith;H. Vollmer
通讯作者：
H. Vollmer
Logspace-MOD 类的结构和重要性
DOI：
10.1007/bfb0020812
发表时间：
1991
期刊：
Artif. Intell.
影响因子：
--
作者：
G. Buntrock;C. Damm;U. Hertrampf;C. Meinel
通讯作者：
C. Meinel
有界变量逻辑和计数：有限模型研究
DOI：
--
发表时间：
1997
期刊：
Lecture Notes in Logic
影响因子：
--
作者：
M. Otto
通讯作者：
M. Otto
DOI：
--
发表时间：
2012
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
A. Dawar;E. Grädel;Bjarki Holm;Eryk Kopczynski;Wied Pakusa
通讯作者：
Wied Pakusa