Type-elimination-based Reasoning for SHIQbs
Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler
Type-elimination-based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog
Abstract. 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.
Published at Logical Methods in Computer Science (Journal paper)
Download PDF (last update: May 4 2012)
Citation details
- Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Type-elimination-based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog. In Logical Methods in Computer Science 8 (1). 2012.
author = {Sebastian Rudolph and Markus Kr{\"o}tzsch and
Pascal Hitzler},
title = {Type-elimination-based Reasoning for the
Description Logic $\mathcal{SHIQ}b_s$
using Decision Diagrams and Disjunctive {Datalog}},
journal = {Logical Methods in Computer Science},
volume = {8},
issue = {1},
year = {2012}
}
Remarks
This work extends and improves earlier results on Terminological Reasoning in SHIQ with OBDDs.
See also the journal's page for this article.
