描述逻辑εL的二阶线性推理机制

发布时间：2019-04-24 21:30

【摘要】：基于描述逻辑的本体的保守扩充理论、模块抽取理论、通用模块构建理论及其相关算法是本体工程中本体构建、本体融合及重构的核心理论与工具.国际上该领域已有Lutz等人使用形式构模方法证明了ALC的保守扩充判定算法复杂度是二阶时间指数的,而轻量级的系统?L的算法复杂度是一阶时间指数的.但当前文献中的形式构模方法思路复杂,难以把握,几乎不能在实用的工程层面上实现.提出一种面向轻量级的描述逻辑系统家族(DL-Lite family)的统一的二阶线性推理机制,并给出该推理机制的完备性证明.该方法直观,思路清晰,从而在工程中容易实现.同时,该方法对?L,FL0,FL?,v L等DL-Lite家族的所有系统都有效.在该线序推理系统下,可以根据"空间换时间"的原则,设计和实现关于保守扩充判定的图推理机制,其复杂性(相对于空间的大小)是多项式的.
[Abstract]:The theory of conservative extension of ontology based on description logic, the theory of module extraction, the theory of general module construction and its related algorithms are the core theories and tools of ontology construction, ontology fusion and reconstruction in ontology engineering. In this field, Lutz et al have proved that the complexity of the conservative extended decision algorithm of ALC is second-order time exponential, while the algorithm complexity of lightweight system-L is first-order time exponential. However, the formal modeling method in the current literature is complicated and difficult to grasp, and can hardly be realized on the practical engineering level. A unified second-order linear reasoning mechanism for the family of lightweight descriptive logic systems (DL-Lite family) is proposed, and the completeness of the reasoning mechanism is proved. This method is intuitionistic and clear, so it is easy to realize in engineering. At the same time, this method is effective for all systems of DL-Lite family, such as L, FL0, FLO, vL, etc. According to the principle of "space-for-time", a graph reasoning mechanism for conservative extension decision can be designed and implemented under the linear reasoning system. The complexity (relative to the size of space) is polynomial.
【作者单位】：广西可信软件重点实验室(桂林电子科技大学);黔南民族师范学院数学系;
【基金】：国家自然科学基金(61463044;61363030) 广西自然科学基金(2013GXNSFAA019330) 广西可信软件重点实验室开放基金桂林电子科技大学计算机软件创新团队基金(kx201419) 广东省数学教育工程技术研究中心开放基金~~
【分类号】：TP181

【相似文献】