描述逻辑关于CBox的推理复杂性  

The Reasoning Complexity of CBox in Description Logics

作　　者：于洋[1] 王戟[2] 陈火旺[2] 

机构地区：[1]中国国防科技信息中心六室,北京100036 [2]国防科技大学计算机学院,湖南长沙410073

出　　处：《计算机工程与科学》2008年第2期131-134,共4页Computer Engineering & Science

基　　金：国家973计划资助项目(2005CB321802)

摘　　要：本文证明基础描述逻辑ALC关于CBox推理是非确定指数完全的。这个结论说明了描述逻辑关于CBox推理是一致地困难。本文还指出了哪些DL对于基数约束的数字编码是敏感的。This paper proves that the complexity of reasoning in the basic description logic （DL） ALC w. r. t. CBox is NExpTime-complete. This means that the reasoning in DL w. r. t. CBox is commonly difficult. Furthermore, we point out what kind of DLs is sensitive to the coding of number in cardinality restrictions.

关 键 词：描述逻辑 基数约束 计算复杂性 

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