On the Complexity of Axiom Pinpointing in the EL Family of Description Logics
On the Complexity of Axiom Pinpointing in the EL Family of Description Logics
复制标题
DOI：
--
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
R. Peñaloza;B. Sertkaya
中科院分区：
文献类型：
--
作者：
R. Peñaloza;B. Sertkaya
我们研究了公理精确定位的计算复杂性，公理精确定位是寻找具有给定结果的描述逻辑知识库的最小子集的任务。我们考虑了有序和无序枚举这样的子集的问题，并给出了对于命题角片段或描述逻辑EL已经成立的硬结果。我们展示了这些片段的其他几个相关决策和枚举问题的复杂性结果，这些问题扩展到更具表达性的逻辑。我们特别指出，这些问题的困难不仅取决于片段的可表达性，而且取决于所使用的公理的形状。
We investigate the computational complexity of axiom pinpointing, which is the task of finding minimal subsets of a Description Logic knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used.