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

Research on the Least Common Subsumer in Description Logic εLN

作　　者：张维[1,2] 曹发生[2] 余泉[1,2] 王驹[3] 

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

出　　处：《计算机工程与科学》2012年第2期139-145,共7页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60663001);中国科学院计算机科学国家重点实验室开放课题基金资助项目(SYSKF0904);贵州省教育厅自然科学基金资助项目(黔教科20090047);贵州省科学技术基金资助项目(黔科合J字[2009]2068)

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]