(Non-)Succinctness of uniform interpolants of general terminologies in the description logic EL
(Non-)Succinctness of uniform interpolants of general terminologies in the description logic EL
复制标题
描述逻辑 EL 中通用术语的统一插值的（非）简洁性
DOI：
10.1016/j.artint.2014.06.005
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
S. Rudolph
中科院分区：
文献类型：
--
作者：
Nadeschda Nikitina;S. Rudolph
EL是一种流行的描述逻辑，在大型现有知识库中用作核心形式主义。知识库的均匀插值是非常重要的，例如在知识库应该部分重用的情况下。然而，据我们所知，还没有程序提出计算均匀EL插值的一般EL术语。到目前为止，也上界的均匀EL插值的大小仍然是未知的。在这篇文章中，我们提出了一种方法来计算一个有限的均匀插值的一般EL术语，如果它存在。为此，我们开发了一个二次表示EL TBoxes作为定期树文法。此外，我们表明，如果一个有限的均匀EL插值存在，那么存在一个是最多三重指数的原始TBox的大小，并且，在最坏的情况下，没有更小的插值存在，从而建立严格的最坏情况下的界限，其大小。除了显示这些界限，本文中建立的概念和结果也提供了有用的见解，设计高效的本体重构算法，例如，在模块提取的上下文中。
EL is a popular description logic, used as a core formalism in large existing knowledge bases. Uniform interpolants of knowledge bases are of high interest, eg in scenarios where a knowledge base is supposed to be partially reused. However, to the best of our knowledge no procedure has yet been proposed that computes uniform EL interpolants of general EL terminologies. Up to now, also the bound on the size of uniform EL interpolants has remained unknown. In this article, we propose an approach to computing a finite uniform interpolant for a general EL terminology if it exists. To this end, we develop a quadratic representation of EL TBoxes as regular tree grammars. Further, we show that, if a finite uniform EL interpolant exists, then there exists one that is at most triple exponential in the size of the original TBox, and that, in the worst case, no smaller interpolants exist, thereby establishing tight worst-case bounds on their size. Beyond showing these bounds, the notions and results established in this paper also provide useful insights for designing efficient ontology reformulation algorithms, for instance, within the context of module extraction.
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Boris Konev
通讯作者：
Boris Konev