| 本文已被：浏览 5044次 下载 6067次 |
码上扫一扫！ |
|
|
| 支持数量约束的扩展模糊描述逻辑复杂性研究 |
|
李言辉1,2, 徐宝文1,2, 陆建江1,2,3, 康达周1,2
|
|
1.东南大学,计算机科学与工程系,江苏,南京,210096;2.江苏省软件质量研究所,江苏,南京,210096;3.解放军理工大学,指挥自动化学院,江苏,南京,210007
|
|
| 摘要: |
| 扩展模糊描述逻辑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问题. |
| 关键词: 模糊 描述逻辑 语义Web 数量约束 知识表示 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60373066, 60425206, 90412003 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2002CB312000 (国家重点基础研究发展规划(973)); the National Research Foundation for the Doctoral Program of Higher Education of China under Grant No.20020286004 (高等学校博士学科点专项科研基金) |
|
| On Computational Complexity of the Extended Fuzzy Description Logic with Numerical Restriction |
|
LI Yan-Hui,XU Bao-Wen,LU Jian-Jiang,KANG Da-Zhou
|
| Abstract: |
| 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. |
| Key words: fuzzy description logic semantic Web numerical restriction knowledge representation |
