First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
First-Order Rewritability of Frontier-Guarded Ontology-Mediated Queries
复制标题
前沿防护本体介导的查询的一阶可重写性
DOI：
10.24963/ijcai.2018/236
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Andreas Pieris
中科院分区：
文献类型：
--
作者：
P. Barceló;Gerald Berger;C. Lutz;Andreas Pieris
我们专注于基于（边界）保护的存在规则和（工会）连接性查询的本体论介导的查询（OMQ），我们研究了FO-剥夺性的问题，即是否可以将OMQ作为一阶重写询问。我们采用两种不同的方法。第一种方法采用标准的双向交替平均树自动机。尽管它不会导致紧密的复杂性绑定，但它提供了基于广为人知的工具的透明解决方案。第二种方法依赖于复杂的自动机模型，称为COST AUTOMATA。这使我们能够证明我们的问题是2Exptime-Complete。在这两种方法中，我们都提供了具有独立利益的FO-剥夺性的语义特征。
We focus on ontology-mediated queries (OMQs) based on (frontier-)guarded existential rules and (unions of) conjunctive queries, and we investigate the problem of FO-rewritability, i.e., whether an OMQ can be rewritten as a first-order query. We adopt two different approaches. The first approach employs standard two-way alternating parity tree automata. Although it does not lead to a tight complexity bound, it provides a transparent solution based on widely known tools. The second approach relies on a sophisticated automata model, known as cost automata. This allows us to show that our problem is 2EXPTIME-complete. In both approaches, we provide semantic characterizations of FO-rewritability that are of independent interest.
有界问题的可判定性结果
DOI：
10.2168/lmcs-10(3:2)2014
发表时间：
2011
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
Achim Blumensath;Martin Otto;Mark Weyer
通讯作者：
Mark Weyer