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

作者：李言辉; 徐宝文; 陆建江; 康达周

来源：软件学报, 2006, (05): 968-975.

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

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

• 单位
  中国人民解放军陆军工程大学; 东南大学