描述逻辑εLN循环术语集的不动点语义及推理  

Fixpoint Semantics and Reasoning of Terminological Cycles in Description Logic εLN

作　　者：蒋运承[1,2] 王驹[1] 史忠植[3] 汤庸[2] 

机构地区：[1]广西师范大学计算机科学与信息工程学院,广西桂林541004 [2]中山大学计算机科学系,广东广州510275 [3]中国科学院计算技术研究所,北京100190

出　　处：《软件学报》2009年第3期477-490,共14页Journal of Software

基　　金：国家自然科学基金;国家重点基础研究发展计划(973));中国博士后科学基金;广东省自然科学重点基金;新世纪优秀人才支持计划;广西自然科学基金~~

摘　　要：循环术语集是描述逻辑长期以来的研究难点,其最基本的问题即语义及推理问题没有得到合理的解决分析了描述逻辑循环术语集的研究现状和存在的问题,将Baader的工作扩展到新的方向.针对更大的描述逻辑系统研究了循环术语集的语义及推理机制,即在描述逻辑εL的基础上添加数量约束构造算子,提出了描述逻辑εLN,给出了εLN的语义(包括不动点语义和描述语义).针对εLN的需要,重新定义了描述图(包括语法描述图和语义描述图).使用描述图之间的模拟关系给出了不动点语义下εLN循环术语集的可满足性和包含关系推理算法,并证明了推理算法是多项式时间复杂的.Terminological cycles have been a very hard problem in description logics for a long time, and their essential problems, i.e. semantics and reasoning problems, have not been solved reasonably. Current research progress and the existing problems of terminological cycles in description logics are analyzed in this paper. Based on the work of Baader, a new direction in terminological cycles is put forward. Aiming at more expressive description logic, the semantics and reasoning mechanism of terminological cycles are studied. The number restrictions are added to description logic eL, and the descripion logic εLN is presented. The semantics （fixpoint semantics and descriptive semantics） of εLN are given. To meet the requirement of εLN, the description graphs （syntax description graph and semantics description graph） are redefined. The satisfiability and subsumption reasoning algorithms of terminological cycles in description logic εLN w.r.t, fixpoint semantics are presented with simulation between description graphs. It is proved that the satisfiability and subsumption reasoning algorithms of terminological cycles in εLN are polynomial.

关 键 词：描述逻辑 εLN 循环术语集 描述图 模拟关系 不动点语义 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]