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

On Computational Complexity of the Extended Fuzzy Description Logic with Numerical Restriction

扩展模糊描述逻辑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.