TY - CONF T1 - All But Not Nothing: Left-Hand Side Universals for Tractable OWL Profiles T2 - 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. Y1 - 2014 A1 - David Carral A1 - Adila Krisnadhi A1 - Sebastian Rudolph A1 - Pascal Hitzler ED - C. Maria Keet ED - Valentina A. M. Tamma KW - description logics KW - Horn Logics KW - OWL AB - 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. JF - 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. PB - CEUR-WS.org VL - 1265 UR - http://ceur-ws.org/Vol-1265/owled2014_submission_13.pdf ER - TY - CONF T1 - EL-ifying Ontologies T2 - Automated Reasoning - 7th International Joint Conference, IJCAR 2014, Held as Part of the Vienna Summer of Logic, {VSL} 2014, Vienna, Austria, July 19-22, 2014. Proceedings Y1 - 2014 A1 - David Carral A1 - Cristina Feier A1 - Cuenca Grau, Bernardo A1 - Pascal Hitzler A1 - Ian Horrocks KW - description logics KW - OWL KW - Rewriting KW - Tractable Reasoning AB -

The OWL 2 profiles are fragments of the ontology language OWL 2 for which standard reasoning tasks are feasible in polynomial time. Many OWL ontologies, however, contain a typically small number of out-of-profile axioms, which may have little or no influence on reasoning outcomes. We investigate techniques for rewriting axioms into the EL and RL profiles of OWL 2. We have tested our techniques on both classification and data reasoning tasks with encouraging results.

JF - Automated Reasoning - 7th International Joint Conference, IJCAR 2014, Held as Part of the Vienna Summer of Logic, {VSL} 2014, Vienna, Austria, July 19-22, 2014. Proceedings UR - http://dx.doi.org/10.1007/978-3-319-08587-6_36 ER - TY - CONF T1 - Pushing the Boundaries of Tractable Ontology Reasoning T2 - The Semantic Web - ISWC 2014 - 13th International Semantic Web Conference, Riva del Garda, Italy, October 19-23, 2014. Proceedings, Part II Y1 - 2014 A1 - David Carral A1 - Cristina Feier A1 - Cuenca Grau, Bernardo A1 - Pascal Hitzler A1 - Ian Horrocks KW - description logics KW - OWL KW - Tractable Reasoning AB -

We identify a class of Horn ontologies for which standard reasoning tasks such as instance checking and classification are tractable. The class is general enough to include the OWL 2 EL, QL, and RL profiles. Verifying whether a Horn ontology belongs to the class can be done in polynomial time. We show empirically that the class includes many real-world ontologies that are not included in any OWL 2 profile, and thus that polynomial time reasoning is possible for these ontologies.

JF - The Semantic Web - ISWC 2014 - 13th International Semantic Web Conference, Riva del Garda, Italy, October 19-23, 2014. Proceedings, Part II UR - http://dx.doi.org/10.1007/978-3-319-11915-1_10 ER - TY - CONF T1 - Revisiting default description logics – and their role in aligning ontologies T2 - Semantic Technology, 4th Joint International Conference, JIST 2014 Y1 - 2014 A1 - Kunal Sengupta A1 - Pascal Hitzler A1 - Krzysztof Janowicz ED - T. Supnithi ED - T. Yamaguchi ED - Jeff Z. Pan ED - V. Wuwongse ED - M. Buranarach KW - default logic KW - defaults KW - description logics KW - Ontology Alignment AB - We present a new approach to extend the Web Ontology Language (OWL) with the capabilities to reason with defaults. This work improves upon the previously established results on integrating defaults with description logics (DLs), which were shown to be decidable only when the application of defaults is restricted to named individuals in the knowledge base. We demonstrate that the application of defaults (integrated with DLs) does not have to be restricted to named individuals to retain decidability and elaborate on the application of defaults in the context of ontology alignment and ontology-based systems. JF - Semantic Technology, 4th Joint International Conference, JIST 2014 PB - Lecture Notes in Computer Science, Springer CY - Chiang Mai, Thailand VL - 8943 ER - TY - CONF T1 - Is Your Ontology as Hard as You Think? Rewriting Ontologies into Simpler DLs T2 - Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014. Y1 - 2014 A1 - David Carral A1 - Cristina Feier A1 - Ana Armas Romero A1 - Cuenca Grau, Bernardo A1 - Pascal Hitzler A1 - Ian Horrocks KW - description logics KW - OWL KW - Tractable Reasoning AB -

We investigate cases where an ontology expressed in a seemingly hard DL can be polynomially reduced to one in a simpler logic, while preserving reasoning outcomes for classification and fact entailment. Our transformations target the elimination of inverse roles, universal and existential restrictions, and in the best case allow us to rewrite the given ontology into one of the OWL 2 profiles. Even if an ontology cannot be fully rewritten into a profile, in many cases our transformations allow us to exploit further optimisation techniques. Moreover, the elimination of some out-of-profile axioms can improve the performance of modular reasoners, such as MORe. We have tested our techniques on both classification and data reasoning tasks with encouraging results.

JF - Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014. UR - http://ceur-ws.org/Vol-1193/paper_75.pdf ER - TY - JOUR T1 - Complexities of Horn Description Logics JF - ACM Trans. Comput. Log. Y1 - 2013 A1 - Markus Krötzsch A1 - Sebastian Rudolph A1 - Pascal Hitzler KW - computational complexity KW - description logics KW - Horn logic AB - 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. VL - 14 UR - http://doi.acm.org/10.1145/2422085.2422087 ER - TY - CONF T1 - Towards an Efficient Algorithm to Reason over Description Logics Extended with Nominal Schemas T2 - Web Reasoning and Rule Systems - 7th International Conference, {RR} 2013, Mannheim, Germany, July 27-29, 2013. Proceedings Y1 - 2013 A1 - David Carral A1 - Cong Wang A1 - Pascal Hitzler KW - description logics KW - EL++ KW - Nominal Schemas AB -

Extending description logics with so-called nominal schemas has been shown to be a major step towards integrating description logics with rules paradigms. However, establishing efficient algorithms for reasoning with nominal schemas has so far been a challenge. In this paper, we present an algorithm to reason with the description logic fragment ELROVn, a fragment that extends EL++ with nominal schemas. We also report on an implementation and experimental evaluation of the algorithm, which shows that our approach is indeed rather efficient.

JF - Web Reasoning and Rule Systems - 7th International Conference, {RR} 2013, Mannheim, Germany, July 27-29, 2013. Proceedings UR - http://dx.doi.org/10.1007/978-3-642-39666-3_6 ER - TY - CONF T1 - Extending Description Logic Rules T2 - The Semantic Web: Research and Applications - 9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 27-31, 2012. Proceedings Y1 - 2012 A1 - David Carral A1 - Pascal Hitzler KW - description logics KW - OWL KW - Rules AB -

Description Logics – the logics underpinning the Web Ontology Language OWL – and rules are currently the most prominent paradigms used for modeling knowledge for the Semantic Web. While both of these approaches are based on classical logic, the paradigms also differ significantly, so that naive combinations result in undesirable properties such as undecidability. Recent work has shown that many rules can in fact be expressed in OWL. In this paper we extend this work to include some types of rules previously excluded. We formally define a set of first order logic rules, C-Rules, which can be expressed within OWL extended with role conjunction. We also show that the use of nominal schemas results in even broader coverage.

JF - The Semantic Web: Research and Applications - 9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 27-31, 2012. Proceedings UR - http://dx.doi.org/10.1007/978-3-642-30284-8_30 ER - TY - CONF T1 - A logical geo-ontology design pattern for quantifying over types T2 - SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), SIGSPATIAL'12, Redondo Beach, CA, USA, November 7-9, 2012 Y1 - 2012 A1 - David Carral A1 - Krzysztof Janowicz A1 - Pascal Hitzler KW - Biodiversity KW - description logics KW - Ontology Design Patterns KW - OWL JF - SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), SIGSPATIAL'12, Redondo Beach, CA, USA, November 7-9, 2012 UR - http://doi.acm.org/10.1145/2424321.2424352 ER - TY - CONF T1 - Recent Advances in Integrating OWL and Rules T2 - Web Reasoning and Rule Systems - 6th International Conference, RR 2012, Vienna, Austria, September 10-12, 2012. Proceedings Y1 - 2012 A1 - Matthias Knorr A1 - David Carral A1 - Pascal Hitzler A1 - Adila Krisnadhi A1 - Frederick Maier A1 - Cong Wang ED - Markus Krötzsch ED - Umberto Straccia KW - description logics KW - OWL KW - Rules AB - As 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. JF - Web Reasoning and Rule Systems - 6th International Conference, RR 2012, Vienna, Austria, September 10-12, 2012. Proceedings PB - Springer CY - Austria, Vienna VL - 7497 UR - http://dx.doi.org/10.1007/978-3-642-33203-6_20 ER - TY - JOUR T1 - Type-Elimination-Based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog JF - Logical Methods in Computer Science Y1 - 2012 A1 - Sebastian Rudolph A1 - Markus Krötzsch A1 - Pascal Hitzler KW - datalog KW - decision diagrams KW - description logics KW - type elimination AB - 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. VL - 8 UR - http://dx.doi.org/10.2168/LMCS-8(1:12)2012 ER - TY - JOUR T1 - Concept learning in description logics using refinement operators JF - Machine Learning Y1 - 2010 A1 - Jens Lehmann A1 - Pascal Hitzler KW - description logics KW - Inductive logic programming KW - OWL KW - refinement operators KW - Semantic Web KW - Structured Machine Learning AB -

With the advent of the Semantic Web, description logics have become one of the most prominent paradigms for knowledge representation and reasoning. Progress in research and applications, however, is constrained by the lack of well-structured knowledge bases consisting of a sophisticated schema and instance data adhering to this schema. It is paramount that suitable automated methods for their acquisition, maintenance, and evolution will be developed. In this paper, we provide a learning algorithm based on refinement operators for the description logic ALCQ including support for concrete roles. We develop the algorithm from thorough theoretical foundations by identifying possible abstract property combinations which refinement operators for description logics can have. Using these investigations as a basis, we derive a practically useful complete and proper refinement operator. The operator is then cast into a learning algorithm and evaluated using our implementation DL-Learner. The results of the evaluation show that our approach is superior to other learning approaches on description logics, and is competitive with established ILP systems.

VL - 78 UR - http://springerlink.metapress.com/content/c040n45u15qrnu44/ ER -