摘要
扩展模糊描述逻辑EFALCN(extendedfuzzyattributiveconceptdescriptionlanguagewithcomplementsandunqualifiednumberrestriction)是支持数量约束的描述逻辑ALCN的模糊扩展,但该逻辑的推理问题缺乏相应的算法和复杂性证明.提出EFALCN推理问题基于约束传播的Tableau算法,并证明该算法可在PSPACE(polynomialspace)约束下执行.由ALCN(attributiveconceptdescriptionlanguagewithcomplementsandunqualifiednumberrestriction)的推理问题可多项式时间归约到EFALCN推理问题,且ALCN的推理问题是PSPACE-complete问题.所以,EFALCN推理问题是PSPACE-hard问题.综上所述,EFALCN推理问题是PSPACE-complete问题.
Extended fuzzy description logic EFALCN （extended fuzzy attributive concept description language with complements and unqualified number restriction） is the fuzzy extension of the description logic with numerical restriction ALCN （attributive concept description language with complements and unqualified number restriction）, but it lacks of reasoning algorithms and complexity analysis for reasoning tasks. In this paper, a constraint-propagation based tableau algorithm is proposed, and it is proved that this algorithm can be executed in PSPACE （polynomial space）. For there is a polynomial time reduction that can reduce ALCN reasoning tasks into EFALCN reasoning tasks and ALCN reasoning tasks are PSPACE-complete, EFALCN reasoning tasks are PSPACE-hard. Thus, it can be proved that the EFALCN reasoning tasks are PSPACE-complete.
出处
《软件学报》
EI
CSCD
北大核心
2006年第5期968-975,共8页
Journal of Software
基金
国家自然科学基金
国家重点基础研究发展规划(973)
高等学校博士学科点专项科研基金~~
关键词
模糊
描述逻辑
语义WEB
数量约束
知识表示
fuzzy
description logic
semantic Web
numerical restriction
knowledge representation
