Expressive Power and Succinctness of the Positive Calculus of Relations
Expressive Power and Succinctness of the Positive Calculus of Relations
复制标题
关系正演算的表达力和简洁性
DOI：
10.1007/978-3-030-43520-2_13
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yoshiki Nakamura
中科院分区：
文献类型：
--
作者：
Yoshiki Nakamura
本文研究了关系正演算的表达能力和简洁性。我们证明：（1）微积分在二元关系方面具有与三变量存在正（一阶）逻辑相同的表达能力;（2）微积分比三变量存在正逻辑的简洁性要低指数级，即从三变量存在正逻辑到微积分没有多项式大小的翻译，而在匡威的方向上有线性大小的翻译。此外，我们给出了一个更细粒度的表达能力之间的关系（全）演算和三变量一阶逻辑的量词交替层次。关系演算是否也比三变量一阶逻辑的简洁性要低得多，这仍然是一个未知数。
In this paper, we study the expressive power and succinctness ofthe positive calculus of relations. We show that (1) the calculus has the same expressive power as that of three-variable existential positive (first-order) logic in terms of binary relations, and (2) the calculus is exponentially less succinct than three-variable existential positive logic, namely, there is no polynomial-size translation from three-variable existential positive logic to the calculus, whereas there is a linear-size translation in the converse direction. 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.