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

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