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

[PDF]

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)
Frequency:  Quarterly
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: jsw@iap.org
  • Apr 26, 2021 News!

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

  • Nov 18, 2021 News!

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

  • Dec 24, 2021 News!

     Vol 15, No 1- Vol 15, No 6 has been indexed by IET-(Inspec)   [Click]

  • Jan 04, 2024 News!

    JSW will adopt Article-by-Article Work Flow

  • Dec 06, 2019 News!

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