|Table of Contents|

[1] Lu Jianjiang, Li Yanhui, Zhang Yafei, Zhou Bo, et al. Reasoning complexity for extended fuzzy description logicwith qualifying number restriction [J]. Journal of Southeast University (English Edition), 2007, 23 (2): 236-240. [doi:10.3969/j.issn.1003-7985.2007.02.017]
Copy

Reasoning complexity for extended fuzzy description logicwith qualifying number restriction()
限制数量约束的扩展模糊描述逻辑的推理复杂性
Share:

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:
23
Issue:
2007 2
Page:
236-240
Research Field:
Automation
Publishing date:
2007-06-30

Info

Title:
Reasoning complexity for extended fuzzy description logicwith qualifying number restriction
限制数量约束的扩展模糊描述逻辑的推理复杂性
Author(s):
Lu Jianjiang1, Li Yanhui2, Zhang Yafei1, Zhou Bo1, Kang Dazhou2
1Institute of Command Automation, PLA University of Science and Technology, Nanjing 210007, China
2School of Computer Science and Engineering, Southeast University, Nanjing 210096, China
陆建江1, 李言辉2, 张亚非1, 周波1, 康达周2
1解放军理工大学指挥自动化学院, 南京 210007; 2东南大学计算机科学与工程学院, 南京 210096
Keywords:
extended fuzzy description logic qualifying number restriction reasoning complexity
扩展模糊描述逻辑 限制数量约束 推理复杂性
PACS:
TP18
DOI:
10.3969/j.issn.1003-7985.2007.02.017
Abstract:
To solve the extended fuzzy description logic with qualifying number restriction(EFALCQ)reasoning problems, EFALCQ is discretely simulated by description logic with qualifying number restriction(ALCQ), and ALCQ reasoning results are reused to prove the complexity of EFALCQ reasoning problems.The ALCQ simulation method for the consistency of EFALCQ is proposed. This method reduces EFALCQ satisfiability into EFALCQ consistency, and uses EFALCQ satisfiability to discretely simulate EFALCQ sat-domain.It is proved that the reasoning complexity for EFALCQ satisfiability, consistency and sat-domain is PSPACE-complete.
为了解决限制数量约束的扩展模糊描述逻辑(EFALCQ)的推理复杂性问题, 采用限制数量约束的描述逻辑(ALCQ)离散模拟EFALCQ, 并重用ALCQ的推理结论来证明EFALCQ推理问题的复杂性.提出了EFALCQ一致性推理问题的ALCQ模拟方法, 将EFALCQ的可满足性推理问题转换为EFALCQ的一致性推理问题, 并用EFALCQ的一致性推理问题离散模拟EFALCQ的可满足区间推理问题.最后证明了EFALCQ的可满足性、一致性、以及可满足区间推理问题的推理复杂性是PSPACE-complete问题.

References:

[1] Baader F, Calvanese D, McGuinness D L, et al.The description logic handbook:theory, implementation, and applications [M].Cambridge:Cambridge University Press, 2003.
[2] Straccia U.Reasoning within fuzzy description logics [J].Journal of Artificial Intelligence Research, 2001, 14:137-166.
[3] Lu Jianjiang, Xu Baowen, Li Yanhui, et al.A family of extended fuzzy description logics [J].International Journal of Business Intelligence and Data Mining, 2006, 1(4):384-400.
[4] Li Yanhui, Xu Baowen, Lu Jianjiang, et al.An extended fuzzy description logic [J].Journal of Southeast University:Natural Science Edition, 2005, 35(5):683-687.(in Chinese)
[5] Li Yanhui, Xu Baowen, Lu Jianjiang, et al.On the computational complexity of the extended fuzzy description logic with numerical constraints [J]. Journal of Software, 2006, 17(5):968-975.(in Chinese)
[6] Li Yanhui, Lu Jianjiang, Xu Baowen, et al.A fuzzy extension of description logic ALCH [C]//Lecture Notes in Artificial Intelligence. Springer-Verlag, 2005, 3789:152-161.
[7] Baader F, Sattler U.An overview of tableau algorithms for description logics [J].Studia Logica, 2001, 69(1):5-40.

Memo

Memo:
Biography: Lu Jianjiang(1968—), male, associate professor, jjlu@seu.edu.cn.
Last Update: 2007-06-20