Expressive power and succinctness of the positive calculus of binary relations
Expressive power and succinctness of the positive calculus of binary relations
复制标题
二元关系正演算的表达力和简洁性
DOI：
10.1016/j.jlamp.2022.100760
复制
发表时间：
2022
影响因子：
0.9
通讯作者：
Yoshiki Nakamura
中科院分区：
文献类型：
--
作者：
Lorenzo Cavallina;Giorgio Poggesi;Toshiaki Yachimura;谷地村 敏明;谷地村 敏明;谷地村 敏明;Yoshiki Nakamura
在本文中，我们研究（二元）关系的正演算的表达能力和简洁性。我们证明，对于二元关系，（1）微积分具有与三变量存在正（一阶）逻辑相同的表达能力，（2）微积分比三变量存在正逻辑简洁得多，即从三变量存在正逻辑到微积分不存在次指数大小的转换。此外，我们根据量词交替层次给出了（完整）关系演算和三变量一阶逻辑之间更细粒度的表达能力等价。关系演算是否也比三变量一阶逻辑简洁得多，这一点仍然悬而未决。
In this paper, we study the expressive power and succinctness ofthe positive calculus of (binary) relations. We show that, for binary relations, (1) the calculus has the same expressive power as that of three-variable existential positive (first-order) logic, and (2) the calculus is exponentially less succinct than three-variable existential positive logic, namely, there is no subexponential-size translation from three-variable existential positive logic to the calculus. Additionally, we give a more fine-grained expressive power equivalence between the (full) calculus of relations and three-variable first-order logic in terms of the quantifier alternation hierarchy. It remains open whether the calculus of relations is also exponentially less succinct than three-variable first-order logic.
登录
查看更多内容
时态逻辑 Ehrenfeucht-Fraïssé 博弈的直到层次结构和其他应用
影响因子：
1
作者：
K. Etessami;T. Wilke
通讯作者：
T. Wilke
DOI：
10.1007/978-3-030-43520-2_13
发表时间：
2020
期刊：
Relational and Algebraic Methods in Computer Science
影响因子：
--
作者：
Yoshiki Nakamura
通讯作者：
Yoshiki Nakamura
DOI：
10.1007/s10817-006-9062-x
发表时间：
2006
期刊：
Journal of Automated Reasoning
影响因子：
--
作者：
S. Givant
通讯作者：
S. Givant
寓言
DOI：
10.2307/j.ctvxkn700.38
发表时间：
2020
期刊：
Stardust Media
影响因子：
--
作者：
Yoshiki Nakamura
通讯作者：
Yoshiki Nakamura
有限自动机、有向图连通性和正则表达式大小
DOI：
10.1007/978-3-540-70583-3_4
发表时间：
2008
期刊：
Bull. EATCS
影响因子：
--
作者：
Hermann Gruber;M. Holzer
通讯作者：
M. Holzer