On Computational Complexity of the Extended Fuzzy Description Logic with Numerical Restriction
On Computational Complexity of the Extended Fuzzy Description Logic with Numerical Restriction
复制标题
DOI：
10.1360/jos170968
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Liu Yanhui;Xu Baowen;Lu Jian-jiang;Kang Da-zhou
中科院分区：
文献类型：
--
作者：
Liu Yanhui;Xu Baowen;Lu Jian-jiang;Kang Da-zhou
扩展模糊描述逻辑EFALCN是具有数值限制的描述逻辑ALCN的模糊扩展，但缺乏推理算法和对推理任务的复杂性分析。本文提出了一种基于约束传播的Tableau算法，并证明了该算法可以在PSPACE(多项式空间)上执行。由于存在一个多项式时间约简，可以将ALCN推理任务归结为EFALCN推理任务，并且ALCN推理任务是PSPACE-完全的，EFALCN推理任务是
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