@conference {133, title = {All But Not Nothing: Left-Hand Side Universals for Tractable {OWL} Profiles}, booktitle = {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.}, volume = {1265}, year = {2014}, month = {10/2014}, pages = {97-108}, publisher = {CEUR-WS.org}, organization = {CEUR-WS.org}, abstract = {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.}, keywords = {description logics, Horn Logics, OWL}, url = {http://ceur-ws.org/Vol-1265/owled2014_submission_13.pdf}, author = {David Carral and Adila Krisnadhi and Sebastian Rudolph and Pascal Hitzler}, editor = {C. Maria Keet and Valentina A. M. Tamma} } @article {60, title = {Complexities of Horn Description Logics}, journal = {ACM Trans. Comput. Log.}, volume = {14}, year = {2013}, pages = {2}, abstract = {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.}, keywords = {computational complexity, description logics, Horn logic}, doi = {10.1145/2422085.2422087}, url = {http://doi.acm.org/10.1145/2422085.2422087}, author = {Markus Kr{\"o}tzsch and Sebastian Rudolph and Pascal Hitzler} } @article {65, title = {Type-Elimination-Based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog}, journal = {Logical Methods in Computer Science}, volume = {8}, year = {2012}, abstract = {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.}, keywords = {datalog, decision diagrams, description logics, type elimination}, doi = {10.2168/LMCS-8(1:12)2012}, url = {http://dx.doi.org/10.2168/LMCS-8(1:12)2012}, author = {Sebastian Rudolph and Markus Kr{\"o}tzsch and Pascal Hitzler} }