Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
Aus International Center for Computational Logic
Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
Sebastian RudolphSebastian Rudolph, Markus KrötzschMarkus Krötzsch, Pascal HitzlerPascal Hitzler
Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler
Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
Technical Report, Universität Karlsruhe (TH), volume 1767, May 2008
Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
Technical Report, Universität Karlsruhe (TH), volume 1767, May 2008
- KurzfassungAbstract
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. - Weitere Informationen unter:Further Information: Link, Link
- Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems
@techreport{RKH2008,
author = {Sebastian Rudolph and Markus Kr{\"{o}}tzsch and Pascal Hitzler},
title = {Description Logic Reasoning with Decision Diagrams: Compiling
{SHIQ} to Disjunctive Datalog},
institution = {Universit{\"{a}}t Karlsruhe (TH)},
year = {2008},
month = {May}
}