%0 Conference Paper %B Proceedings of the 11th International Workshop on OWL: Experiences and Directions (OWLED 2014) co-located with 13th International Semantic Web Conference on (ISWC 2014), Riva del Garda, Italy, October 17-18, 2014. %D 2014 %T All But Not Nothing: Left-Hand Side Universals for Tractable OWL Profiles %A David Carral %A Adila Krisnadhi %A Sebastian Rudolph %A Pascal Hitzler %E C. Maria Keet %E Valentina A. M. Tamma %K description logics %K Horn Logics %K OWL %X We show that occurrences of the universal quantifier in the left-hand side of general concept inclusions can be rewritten into EL++ axioms under certain circumstances. I.e., this intuitive modeling feature is available for OWL EL while retaining tractability. Furthermore, this rewriting makes it possible to reason over corresponding extensions of EL++ and Horn-SROIQ using standard reasoners. %B Proceedings of the 11th International Workshop on OWL: Experiences and Directions (OWLED 2014) co-located with 13th International Semantic Web Conference on (ISWC 2014), Riva del Garda, Italy, October 17-18, 2014. %I CEUR-WS.org %V 1265 %P 97-108 %8 10/2014 %G eng %U http://ceur-ws.org/Vol-1265/owled2014_submission_13.pdf %0 Journal Article %J ACM Trans. Comput. Log. %D 2013 %T Complexities of Horn Description Logics %A Markus Krötzsch %A Sebastian Rudolph %A Pascal Hitzler %K computational complexity %K description logics %K Horn logic %X Description Logics (DLs) have become a prominent paradigm for representing knowledge bases in a variety of application areas. Central to leveraging them for corresponding systems is the provision of a favourable balance between expressivity of the knowledge representation formalism on the one hand, and runtime performance of reasoning algorithms on the other. Due to this, Horn description logics (Horn DLs) have attracted attention since their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large sets of instance data (ABoxes). However, the natural question whether Horn DLs also provide advantages for schema (TBox) reasoning has hardly been addressed so far. In this paper, we therefore provide a thorough and comprehensive analysis of the combined complexities of Horn DLs. While the combined complexity for many Horn DLs studied herein turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning. We also provide convenient normal forms for Horn DLs. %B ACM Trans. Comput. Log. %V 14 %P 2 %G eng %U http://doi.acm.org/10.1145/2422085.2422087 %R 10.1145/2422085.2422087 %0 Journal Article %J Logical Methods in Computer Science %D 2012 %T Type-Elimination-Based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog %A Sebastian Rudolph %A Markus Krötzsch %A Pascal Hitzler %K datalog %K decision diagrams %K description logics %K type elimination %X We propose a novel, type-elimination-based method for standard reasoning in the description logic SHIQbs 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 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. %B Logical Methods in Computer Science %V 8 %G eng %U http://dx.doi.org/10.2168/LMCS-8(1:12)2012 %R 10.2168/LMCS-8(1:12)2012