描述逻辑系统εLN中概念最小公共包含推理研究

J4 ›› 2012, Vol. 34 ›› Issue (2): 139-145.

描述逻辑系统εLN中概念最小公共包含推理研究

张维1,2，曹发生2，余泉1,2，王驹3

1.黔南民族师范学院数学系,贵州都匀 558000;2.毕节学院逻辑、语言与认知研究中心,贵州毕节 551700;3.广西师范大学计算机科学与信息工程学院,广西桂林 541004）

收稿日期:2010-05-10 修回日期:2010-08-28 出版日期:2012-02-25 发布日期:2012-02-25

Research on the Least Common Subsumer in Description Logic εLN

ZHANG Wei1,2，CAO Fasheng2，YU Quan1,2，WANG Ju3

(1.Department of Mathematics,Qiannan Normal College for Nationalities,Duyun 558000;2.Center for Logic，Language and Cognition,Bijie University,Bijie 551700;3.School of Computer Science and Information Engineering,Guangxi Normal University,Guilin 541004，China)

Received:2010-05-10 Revised:2010-08-28 Online:2012-02-25 Published:2012-02-25

摘要/Abstract

摘要：

描述逻辑的非标准推理是上世纪末本世纪初研究者们提出来的一种新的推理机制，它主要包括最具体概念、最小公共包含、匹配问题以及概念的重写等等。非标准推理的提出主要是为了解决人们在知识库的构建、管理、维护等方面遇到的问题，它能为自下而上的知识库构建方式提供必要的支持，这些是传统的标准推理无法提供的。随着描述逻辑的运用越来越广泛，知识库的构建、管理、维护是人们无法回避的问题，因此描述逻辑的非标准推理的研究成为近年来描述逻辑研究者们所关注的热点问题。本文分析了描述逻辑中概念最小公共包含（LCS）推理机制的研究现状和存在的问题，针对目前LCS推理在同时处理存在限制和数量限制的不足，研究了描述逻辑系统εLN的LCS推理算法。首先定义了εLN中的概念描述树及其同态关系，利用描述树之间同态关系给出了概念间包含关系算法。然后通过定义描述树的笛卡尔积给出了εLN中的LCS推理算法，并指出该算法是多项式时间复杂的。

关键词: 描述逻辑;描述树;同态;最小公共包含

Abstract:

Nonstandard inference is a new inference service in description logic，which was proposed at the turn of the century. It mainly includes the most specific concept，the least common subsumer，matching problem，concept rewriting and so on. Nonstandard inference aims to deal with the construction and management of the knowledge base and some other problems which researchers have to face in applications. Nonstandard inference can support the bottomup construction method，as the description logic is widely applied in other areas，the knowledge base construction and management is more and more critical and inevitable，but the standard inference almost cannot provide any help. So the nonstandard inference becomes a main issue which researchers are focusing on in recent years. In this paper the fundamentality of nonstandard inference in description logic, especially the current research progress and existing problem of the LCS(least common subsumer) inference in description logic are analyzed. Aiming to the insufficiency of the LCS inference which cannot handle existential restriction and number restriction at the same time, the LCS inference in description logic εLN is studied. Firstly the εLNdescription tree and its homomorphism are defined, a subsumption algorithm is presented by computing the homomorphism between two description trees. Then the product of description trees is defined and the LCS inference algorithm is presented by computing the product of description trees. The complexity of the LCS inference algorithm in εLN is polynomial.

Key words: description logic；description tree；homomorphism；least common subsumer

张维1,2，曹发生2，余泉1,2，王驹3. 描述逻辑系统εLN中概念最小公共包含推理研究[J]. J4, 2012, 34(2): 139-145.

ZHANG Wei1,2，CAO Fasheng2，YU Quan1,2，WANG Ju3. Research on the Least Common Subsumer in Description Logic εLN[J]. J4, 2012, 34(2): 139-145.