Modal definability of first-order formulas with free variables and query answering
Modal definability of first-order formulas with free variables and query answering
复制标题
DOI：
10.1016/j.jal.2013.03.007
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
S. Kikot;Evgeny Zolin
中科院分区：
文献类型：
--
作者：
S. Kikot;Evgeny Zolin
本文给出了一个算法上有效的多自由变量一阶存在合取公式的模态可定义性判据。然后，我们应用它建立了一些一阶模态公式族的模态可定义性。最后，我们使用我们的可定义性结果表明，在任何表达描述逻辑，回答模态可定义的合取查询的问题是多项式可还原的知识库的一致性问题。
We present an algorithmically efficient criterion of modal definability for first-order existential conjunctive formulas with several free variables. Then we apply it to establish modal definability of some family of first-order ∀∃-formulas. Finally, we use our definability results to show that, in any expressive description logic, the problem of answering modally definable conjunctive queries is polynomially reducible to the problem of knowledge base consistency.