微信服务号

微信订阅号

2025-4-24- 14
Home > Archive>Volume 21, Issue 8, 2010 >1863-1877
PDF HTML XML Export Cite reminder
Determining the SHOIN(D)-Satisfiability with a Complete Disjunctive Normal Form Group
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [22]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    This paper presents an approach to check the satisfiability of acyclic SHOIN(D)-concepts—CDNF (complete disjunctive normal form) algorithm. This calculus can make a direct judgment on the satisfiability of acyclic SHOIN(D)-concept by restructuring it into a hierarchical disjunctive normal form group on concept descriptions which is satisfiability self-telling, and reusing description clauses to block unnecessary extensions. CDNF algorithm eliminates description overlaps to the largest extent for it works on concept description directly. Therefore, CDNF algorithm has much better performance than Tableau as it saves a lot of spatial and temporal costs.

    Reference
    [1] Fensel D, van Harmelen F, Horrocks I, McGuinness DL, Patel-Schneider PF. OIL: An ontology infrastructure for the semantic Web. IEEE Intelligent Systems, 2001,16(2):38?45.
    [2] Connolly D, van Harmelen F, Horrocks I, McGuinness DL, Patel-Schneider PF, Stein LA. DAML+OIL (March 2001) reference description. W3C Note, 2001. http://www.w3.org/TR/2001/NOTE-daml+oil-reference-20011218
    [3] van Harmelen F, Hendler J, Horrocks I, McGuinness DL, Patel-Schneider PF, Stein LA. OWL Web ontology language reference. W3C Working Draft, 2003. http://www.w3.org/TR/2003/WD-owl-ref-20030331
    [4] Grau BC, Horrocks I, Motik B, Parsia B, Patel-Schneider P, Sattler U. OWL 2: The next step for OWL. Journal of Web Semantics: Science, Services and Agents on the World Wide Web, 2008,6(4):309?322.
    [5] Hustadt U, Motik B, Sattler U. Reasoning in description logics by a reduction to disjunctive datalog. Journal of Automated Reasoning, 2007,39(3):351?384. [doi: 10.1007/s10817-007-9080-3]
    [6] Halashek-Wiener C, Parsia B, Sirin E. Description logic reasoning with syntactic updates. In: Meersman, R, Tari Z, eds. Proc. of the 5th Int’l Conf. on Ontologies, Databases, and Applications of Semantics (ODBASE 2006). LNCS 4275, Berlin, Heidelberg: Springer-Verlag, 2006. 722?737.
    [7] Horrocks I, Sattler U. A tableau decision procedure for SHOIQ. Journal of Automated Reasoning, 2007,39(3):249?276. [doi: 10.1007/s10817-007-9079-9]
    [8] Lutz C, Mili?i? M. A tableau algorithm for description logics with concrete domains and general TBoxes. Journal of Automated Reasoning, 2007,38(1-3):227?259. [doi: 10.1007/s10817-006-9049-7]
    [9] Chang L, Lin F, Shi ZZ. A dynamic description logic for representation and reasoning about actions. In: Zhang Z, Siekmann J, eds. Proc. of the KSEM 2007. LNAI 4798, Berlin, Heidelberg: Springer-Verlag, 2007. 115?127.
    [10] Chang L, Shi ZZ, Qiu LR, Lin F. A tableau decision algorithm for dynamic description logic. Chinese Journal of Computers, 2008, 31(6):896?909 (in Chinese with English abstract).
    [11] Jiang YC, Shi ZZ, Tang Y, Wang J. Fuzzy description logic for semantics representation of the semantic Web. Journal of Software, 2007,18(6):1257?1269 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/1257.htm [doi: 10.1360/jos181257]
    [12] Stoilos G, Stamou G, Pan JZ, Tzouvaras V, Horrocks I. Reasoning with Very Expressive Fuzzy Description Logics. Journal of Artificial Intelligence Research, 2007,30(1):273?320.
    [13] Baader F, Calvanese D, McGuinness DL, Nardi D, Patel-Schneider PF. The Description Logic Handbook: Theory, Implementation, and Applications. Cambridge: Cambridge University Press, 2003.
    [14] Horrocks I, Pate1-Schneider PF, van Harmelen F. From SHIQ and RDF to OWL: The Making of a Web Ontology Language. Journa1 of Web Semantics, 2003,1(1):7?26.
    [15] Baader F, Hanschke P. A scheme for integrating concrete domains into concept languages. In: Mylopoulos J, Reiter R, eds. Proc. of the IJCAI’91. San Fransisco: Morgan Kaufmann Publishers, 1991. 452?457.
    [16] Schaerf A. Reasoning with individuals in concept languages. Data and Knowledge Engineering, 1994,13(2):141?176. [doi: 10.1016/0169-023X(94)90002-7]
    [17] Horrocks I, Sattler U. Ontology reasoning in the SHOQ(D) description logic. In: Bernhard N, ed. Proc. of the IJCAI 2001. San Francisco: Morgan Kaufmann Publishers, 2001. 199?204.
    [18] Horrocks I, Sattler U, Tobies S. Practical reasoning for expressive description logics. In: Ganzinger H, McAllester D, Voronkov A, eds. Proc. of the 6th Int’l Conf. on Logic for Programming and Automated Reasoning (LPAR’99). LNAI 1705, Berlin, Heidelberg: Springer-Verlag, 1999. 161?180.
    [19] Tobies S. Complexity results and practical algorithms for logics in knowledge representation [Ph.D. Thesis]. LuFG Theoretical Computer Science, RWTH-Aachen, 2001.
    [20] Horrocks I, Kutz O, Sattler U. The even more irresistible SROIQ. In: Doherty P, Mylopoulos J, Welty C, eds. Proc. of the 10th Int’l Conf. of Knowledge Representation and Reasoning (KR 2006). Menlo Park: AAAI Press, 2006. 57?67.
    附中文参考文献: [10] 常亮,史忠植,邱莉榕,林芬.动态描述逻辑的Tableau判定算法.计算机学报,2008,31(6):896?909.
    [11] 蒋运承,史忠植,汤庸,王驹.面向语义Web语义表示的模糊描述逻辑.软件学报,2007,18(6):1257?1269. http://www.jos.org.cn/ 1000-9825/18/1257.htm [doi: 10.1360/jos181257]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

古华茂,王 勋,凌 云,高 济.完全析取范式群判定SHOIN(D)-可满足性.软件学报,2010,21(8):1863-1877

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:July 31,2008
  • Revised:February 16,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2038072Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063