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

摘要

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