Sebastian Rudolph ; Markus Krötzsch ; Pascal Hitzler - Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalog

lmcs:806 - Logical Methods in Computer Science, February 27, 2012, Volume 8, Issue 1 - https://doi.org/10.2168/LMCS-8(1:12)2012
Type-elimination-based reasoning for the description logic SHIQbs using decision diagrams and disjunctive datalogArticle

Authors: Sebastian Rudolph ORCID; Markus Krötzsch ORCID; Pascal Hitzler

    We propose a novel, type-elimination-based method for reasoning in the description logic SHIQbs including DL-safe rules. To this end, we first establish a knowledge compilation method converting the terminological part of an ALCIb knowledge base into an ordered binary decision diagram (OBDD) which represents a canonical model. This OBDD can in turn be transformed into disjunctive Datalog and merged with the assertional part of the knowledge base in order to perform combined reasoning. In order to leverage our technique for full SHIQbs, we provide a stepwise reduction from SHIQbs to ALCIb that preserves satisfiability and entailment of positive and negative ground facts. The proposed technique is shown to be worst case optimal w.r.t. combined and data complexity and easily admits extensions with ground conjunctive queries.

    https://doi.org/10.2168/LMCS-8(1:12)2012
    Source: arXiv.org:1202.0914
    Volume: Volume 8, Issue 1
    Published on: February 27, 2012
    Imported on: May 26, 2011
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Artificial Intelligence,Mathematics - Logic,I.2.4, I.2.3, F.4.3, F.4.1
    Licence: arXiv.org - Non-exclusive license to distribute

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    7 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 1606 times.
    This article's PDF has been downloaded 436 times.