计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2013年
20期
29-33,166
,共6页
认知角色%逆角色%K算子%查询表算法%复杂度
認知角色%逆角色%K算子%查詢錶算法%複雜度
인지각색%역각색%K산자%사순표산법%복잡도
epistemic role%inverse role%K operator%query tableau algorithm%complexity
针对认知角色不能表达个体间双向关系的问题，在描述逻辑ALCK中加入逆角色得到ALCIK，以扩充其表达能力，在能够捕获最小知识和实现自省推理的同时可以更加方便地对实际问题建模，给出了ALCIK的语法和语义，并且在Tbox为空集，Abox中无K算子的情况下，设计了ALCIK概念的查询表算法，根据概念结构归纳证明了表算法的可靠性和完备性，并且一定会停机，最后讨论了复杂度。理论分析表明，此时认知查询问题是可判定的，并且计算复杂度为PSpace-hard。
針對認知角色不能錶達箇體間雙嚮關繫的問題，在描述邏輯ALCK中加入逆角色得到ALCIK，以擴充其錶達能力，在能夠捕穫最小知識和實現自省推理的同時可以更加方便地對實際問題建模，給齣瞭ALCIK的語法和語義，併且在Tbox為空集，Abox中無K算子的情況下，設計瞭ALCIK概唸的查詢錶算法，根據概唸結構歸納證明瞭錶算法的可靠性和完備性，併且一定會停機，最後討論瞭複雜度。理論分析錶明，此時認知查詢問題是可判定的，併且計算複雜度為PSpace-hard。
침대인지각색불능표체개체간쌍향관계적문제，재묘술라집ALCK중가입역각색득도ALCIK，이확충기표체능력，재능구포획최소지식화실현자성추리적동시가이경가방편지대실제문제건모，급출료ALCIK적어법화어의，병차재Tbox위공집，Abox중무K산자적정황하，설계료ALCIK개념적사순표산법，근거개념결구귀납증명료표산법적가고성화완비성，병차일정회정궤，최후토론료복잡도。이론분석표명，차시인지사순문제시가판정적，병차계산복잡도위PSpace-hard。
Aiming at epistemic role being not capable of expressing bi-directional relationship between individuals, this paper embeds inverse role into description logic ALCK and obtains ALCIK in order to extend expressiveness, models practical prob-lems more conveniently while keeping capturing minimal knowledge and introspecting. It gives semantic and syntax of ALCIK and designs query tableau algorithm on condition that Tbox is empty and Abox is K-free. It also proves that the algorithm which will terminate definitely is sound and complete by induction on structure of ALCIK concept and investigates its computational complexity at last. The theoretical analysis shows that in this situation epistemic query problem is decidable and complexity is in PSpace-hard class.
