01631nas a2200181   4500008004100000245004400041210004400085300000600129490000700135520112800142653002901270653002301299653001501322100002201337700002301359700002001382856004701402       2013                        eng d00aComplexities of Horn Description Logics0 aComplexities of Horn Description Logics  a20 v143 aDescription 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.10acomputational complexity10adescription logics10aHorn logic1 aKrötzsch, Markus1 aRudolph, Sebastian1 aHitzler, Pascal  uhttp://doi.acm.org/10.1145/2422085.242208701833nas a2200253   4500008004100000245005100041210004900092260003900141300001200180490000900192520112700201653002301328653000801351653001001359100002001369700001801389700002001407700002101427700002101448700001501469700002201484700002201506856005101528       2012                        eng d00aRecent Advances in Integrating {OWL} and Rules0 aRecent Advances in Integrating OWL and Rules  aAustria, ViennabSpringerc09/2012  a225-2280 v74973 aAs part of the quest for a unifying logic for the Semantic Web Technology Stack, a central issue is finding suitable ways of integrating description logics based on the Web Ontology Language (OWL) with rule-based approaches based on logic programming. Such integration is difficult since naive approaches typically result in the violation of one or more desirable design principles. For example, while both OWL 2 DL and RIF Core (a dialect of the Rule Interchange Format RIF) are decidable, their naive union is not, unless carefully chosen syntactic restrictions are applied.

We report on recent advances and ongoing work by the authors in integrating OWL and rulesWe take an OWL-centric perspective, which means that we take OWL 2 DL as a starting point and pursue the question of how features of rulebased formalisms can be added without jeopardizing decidability. We also report on incorporating the closed world assumption and on reasoning algorithms. This paper essentially serves as an entry point to the original papers, to which we will refer throughout, where detailed expositions of the results can be found.10adescription logics10aOWL10aRules1 aKnorr, Matthias1 aCarral, David1 aHitzler, Pascal1 aKrisnadhi, Adila1 aMaier, Frederick1 aWang, Cong1 aKrötzsch, Markus1 aStraccia, Umberto  uhttp://dx.doi.org/10.1007/978-3-642-33203-6_2001393nas a2200181   4500008004100000245011800041210006900159490000600228520078700234653001201021653002201033653002301055653002101078100002301099700002201122700002001144856004701164       2012                        eng d00aType-Elimination-Based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog0 aTypeEliminationBased Reasoning for the Description Logic SHIQbs 0 v83 aWe 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.10adatalog10adecision diagrams10adescription logics10atype elimination1 aRudolph, Sebastian1 aKrötzsch, Markus1 aHitzler, Pascal  uhttp://dx.doi.org/10.2168/LMCS-8(1:12)2012