Beth Definability in Expressive Description Logics
Beth Definability in Expressive Description Logics
复制标题
表达描述逻辑中的 Beth 可定义性
DOI：
10.5591/978-1-57735-516-8/ijcai11-188
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Inanç Seylan
中科院分区：
文献类型：
--
作者：
B. T. Cate;Enrico Franconi;Inanç Seylan
Beth Distaribality属性是一种来自经典逻辑的众所周知的属性，在描述逻辑的背景下进行了研究：如果一般L-Tbox隐式通过给定签名来暗中定义L-概念，其中L是描述逻辑，则该签名的概念中是否总是存在此概念中的明确定义？此属性以前已经进行过研究，并用于优化描述逻辑中的推理。在本文中，BETH确定性的完整分类是为基本描述逻辑ALC的扩展，具有传递性作用，逆角色，角色层次结构和/或功能限制，包括在任意结构和有限结构上。此外，我们提出了一种基于图表的算法，该算法可计算最多双重指数大小的明确定义。该算法是最佳的，因为它还表明，隐式定义概念的最小显式定义在输入Tbox的大小上可能是双重指数性的。最后，如果允许以一阶逻辑表达明确的定义，则我们展示如何在单个指数时间内计算它们。
The Beth definability property, a well-known property from classical logic, is investigated in the context of description logics: if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a description logic, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in description logics. In this paper a complete classification of Beth definability is provided for extensions of the basic description logic ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic, then we show how to compute them in single exponential time.
DOI：
--
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Boris Konev
通讯作者：
Boris Konev