Type-Elimination-Based Reasoning for the Description Logic SHIQb_s Using Decision Diagrams and Disjunctive Datalog.

Authors

Sebastian Rudolph
Markus Krotzsch
Pascal Hitzler, Wright State University - Main CampusFollow

Document Type

Article

Publication Date

2012

Abstract

We propose a novel, type-elimination-based method for standard reasoning in the description logic SHIQb_s extended by 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) that 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 SHIQb_s , we provide a stepwise reduction from SHIQb_s 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.

Comments

The authors' hold copyright of this paper and is distributed under the terms of the Creative Commons Attribution Non-Commercial License.

Repository Citation

Rudolph, S., Krotzsch, M., & Hitzler, P. (2012). Type-Elimination-Based Reasoning for the Description Logic SHIQb_s Using Decision Diagrams and Disjunctive Datalog.. Logical Methods in Computer Science, 8 (1), 1-38.
https://corescholar.libraries.wright.edu/knoesis/178