Volume 7 Number 2 (Feb. 2012)
Home > Archive > 2012 > Volume 7 Number 2 (Feb. 2012) >
JSW 2012 Vol.7(2): 322-331 ISSN: 1796-217X
doi: 10.4304/jsw.7.2.322-331

Deciding the SHOQ(D)-Satisfiability with a Fully Tiered Clause Group

Huamao Gu, Jinqin Shi, and Xun Wang

Zhejiang Gongshang University/Institute of Artificial Intelligence, Hangzhou, China

Abstract—SHOQ(D) is one of the fundamental theories In Description Logics due to its support to concrete datatypes and named individuals. At present, deciding the satisfiability of SHOQ(D)-concepts is mainly completed by enhancing Tableau algorithm with blocking. However, there is still much to be desired in performance as there are tremendous description overlaps in completion forest, thus causing great spatial waste as a result. To tackle this problem, this paper presented a new approach to check the satisfiability of acyclic SHOQ(D)-concepts——FTC(Fully Tiered Clauses) algorithm. This calculus can make a direct judgement on the satisfiability of acyclic SHOQ(D)-concept by translating its description into a fully tiered clause group whose satisfiability is directly available, and reusing clauses to block unnecessary extensions. FTC algorithm eliminates description overlaps to the largest extent as it works on concept description directly. Therefore, FTC algorithm has notably better performance than Tableau by saving a lot of spatial costs.

Index Terms—Satisfiability, Concept Clause, SHOQ(D), Fully Tiered Clauses


Cite: Huamao Gu, Jinqin Shi and Xun Wang, "Deciding the SHOQ(D)-Satisfiability with a Fully Tiered Clause Group," Journal of Software vol. 7, no. 2, pp. 322-331, 2012.

General Information

  • ISSN: 1796-217X (Online)

  • Abbreviated Title: J. Softw.

  • Frequency:  Quarterly

  • APC: 500USD

  • DOI: 10.17706/JSW

  • Editor-in-Chief: Prof. Antanas Verikas

  • Executive Editor: Ms. Yoyo Y. Zhou

  • Abstracting/ Indexing: DBLP, EBSCO,
           CNKIGoogle Scholar, ProQuest,
           INSPEC(IET), ULRICH's Periodicals
           Directory, WorldCat, etc

  • E-mail: jsweditorialoffice@gmail.com

  • Jun 12, 2024 News!

    Vol 19, No 2 has been published with online version   [Click]

  • Jan 04, 2024 News!

    JSW will adopt Article-by-Article Work Flow

  • Apr 01, 2024 News!

    Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec)     [Click]

  • Apr 01, 2024 News!

    Papers published in JSW Vol 18, No 1- Vol 18, No 6 have been indexed by DBLP   [Click]

  • Mar 01, 2024 News!

    Vol 19, No 1 has been published with online version    [Click]