支持数量约束的扩展模糊描述逻辑复杂性研究

被引：18

作者：

李言辉

徐宝文

陆建江

康达周

机构：

[1] 东南大学计算机科学与工程系

[2] 江苏省软件质量研究所

来源：

软件学报 | 2006年 / 05期

基金：

高等学校博士学科点专项科研基金;

关键词：

模糊; 描述逻辑; 语义Web; 数量约束; 知识表示;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

扩展模糊描述逻辑EFALCN(extendedfuzzyattributiveconceptdescriptionlanguagewithcomplementsandunqualifiednumberrestriction)是支持数量约束的描述逻辑ALCN的模糊扩展,但该逻辑的推理问题缺乏相应的算法和复杂性证明.提出EFALCN推理问题基于约束传播的Tableau算法,并证明该算法可在PSPACE(polynomialspace)约束下执行.由ALCN(attributiveconceptdescriptionlanguagewithcomplementsandunqualifiednumberrestriction)的推理问题可多项式时间归约到EFALCN推理问题,且ALCN的推理问题是PSPACE-complete问题.所以,EFALCN推理问题是PSPACE-hard问题.综上所述,EFALCN推理问题是PSPACE-complete问题.

引用

页码：968 / 975

页数：8