Deciding inseparability and conservative extensions in the description logic E L
Deciding inseparability and conservative extensions in the description logic E L
复制标题
决定描述逻辑中的不可分离性和保守扩展 E L
DOI：
10.1016/j.jsc.2008.10.007
复制
发表时间：
2010
影响因子：
0.7
通讯作者：
Lutz C
中科院分区：
文献类型：
--
作者：
Lutz C
我们研究了在签名Σ中确定两个本体是否不可分割的问题，即它们在签名Σ中是否具有相同的结果。一个特殊的例子是判断一个本体的扩展是否保守。通过改变表述本体的语言和用于描述结果的查询语言，我们可以得到问题的不同版本。我们关注轻量级描述逻辑EL作为本体语言，并考虑基于(i)包含查询，（ii）对abox的实例查询，（iii）对abox的连接查询，以及（iv）二阶逻辑的查询语言。对于查询语言(i)到（iii），我们建立了不可分扩展和保守扩展的exptime -完备性。情形（iv）等价于不可分性和保守扩展的一个模型理论版本，我们证明了它是不可判定的。我们还建立了不可分性的一些鲁棒性性质。
We study the problem of deciding whether two ontologies are inseparable w.r.t. a signature Σ, i.e., whether they have the same consequences in the signature Σ. A special case is to decide whether the extension of an ontology is conservative. By varying the language in which ontologies are formulated and the query language that is used to describe consequences, we obtain different versions of the problem. We focus on the lightweight description logic EL as an ontology language, and consider query languages based on (i) subsumption queries, (ii) instance queries over ABoxes, (iii) conjunctive queries over ABoxes, and (iv) second-order logic. For query languages (i) to (iii), we establish ExpTime-completeness of both inseparability and conservative extensions. Case (iv) is equivalent to a model-theoretic version of inseparability and conservative extensions, and we prove it to be undecidable. We also establish a number of robustness properties for inseparability.