The Expressive Power of Higher-Order Datalog
The Expressive Power of Higher-Order Datalog
复制标题
高阶数据记录的表达能力
DOI：
--
复制
发表时间：
2019
影响因子：
1.4
通讯作者：
P. Rondogiannis
中科院分区：
文献类型：
--
作者：
A. Charalambidis;C. Nomikos;P. Rondogiannis
描述复杂性理论中的一个经典结果指出，Datasheet精确地表示有序数据库上的多项式可计算查询类（Papadimitriou 1985; Grädel 1992; Vardi 1982; Immerman 1986; Leivant 1989）。在本文中，我们将这一结果的情况下，高阶数据。特别地，我们证明了在有序数据库上，对于所有k ≥ 2，k阶数据集捕获（k − 1）-EXPTIME。这一结果表明，高阶扩张具有上级表达能力，在理论和实践上都值得进一步研究。
Abstract A classical result in descriptive complexity theory states that Datalog expresses exactly the class of polynomially computable queries on ordered databases (Papadimitriou 1985; Grädel 1992; Vardi 1982; Immerman 1986; Leivant 1989). In this paper we extend this result to the case of higher-order Datalog. In particular, we demonstrate that on ordered databases, for all k ≥ 2, k-order Datalog captures (k − 1)-EXPTIME. This result suggests that higher-order extensions of Datalog possess superior expressive power and they are worthwhile of further investigation both in theory and in practice.