Description Logic Reasoning with Decision Diagrams

From korrekt.org

Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler

Description Logic Reasoning with Decision Diagrams – Compiling SHIQ to Disjunctive Datalog

Abstract. We propose a novel method for reasoning in the description logic SHIQ. After a satisfiability preserving transformation from SHIQ to the description logic ALCIb, the obtained ALCIb Tbox T is converted into an ordered binary decision diagram (OBDD) which represents a canonical model for T. This OBDD is turned into a disjunctive datalog program that can be used for Abox reasoning. The algorithm is worst-case optimal w.r.t. data complexity, and admits easy extensions with DL-safe rules and ground conjunctive queries.

Published at ISWC2008 (Conference paper)

Download PDF (last update: July 10 2008)

Citation details

Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Description Logic Reasoning with Decision Diagrams – Compiling SHIQ to Disjunctive Datalog. In Proceedings of the 7th International Semantic Web Conference (ISWC-08). Springer 2008.

Remarks

This work extends our earlier work on using binary decision diagrams for terminological DL reasoning with a datalog translation that allows for Aboxes to be incorporated.