一种带传递关系的认知描述逻辑研究

Study of an Epistemic Description Logic with Transitive Roles

描述逻辑是语义Web的逻辑基础,它是形式化表达领域知识的一种工具.描述逻辑是一阶逻辑的可判定子集,适合对领域知识的概念术语进行建模.因为某些应用程序的需要和领域知识难以完全描述的因素,Web上有大量的不完全知识.描述逻辑基于开放世界假设,只能表达单调推理,不能处理不完全知识.在描述逻辑中加入认知运算符K可以得到认知描述逻辑.认知描述逻辑因其非单调特性和良好的时间复杂度等特点在处理不完全知识方面有较好的优势.在认知描述逻辑ALCK的基础上加入传递关系属性提出了新的认知描述逻辑语言ALCKR+,保留了描述逻辑原有的优点,增强了表达能力并通过认知查询拥有了非单调推理的能力.设计了ALCKR+的语法、语义以及表算法,给出了表算法的正确性以及可判定性证明,证明表算法的时间复杂度为PSPACE-complete.

Description logic is the logical foundation of the semantic Web. It is a tool for formally expressing domain knowledge. Description logic is the decidable fragment of the first order logic and suitable for modeling the concept terminology of domain knowledge. Because some application requirements and people can not describe all of the domain knowledge, there is lots of incomplete knowledge on the Web. Description logic is based on the open world assumption. It can only express the monotonic reasoning and can not solve the incomplete knowledge. By adding the epistemic operator ＂K＂ to the description logic, the epistemic description logic can be obtained. It has the advantage of dealing with the incomplete knowledge because of the non-monotonic features and the good computational complexity. The authors present a new epistemic description logic ALCKR~ based on the epistemic description logic ALCK, preserve the primary advantage of the description logic, add transitive roles for improving the expressivity, express the non-monotonic reasoning ability through the epistemic query, and design the syntax and semantic of ALCKR＋. The corresponding tableau algorithm is also provided. The soundness and decidability of the tableau algorithm are proved. It is shown that the complexity of tableau algorithm is PSPACE-complete.