TY - CONF
T1 - A Better Uncle For OWL - Nominal Schemas for Integrating Rules and Ontologies
T2 - International World Wide Web Conference (WWW2011)
Y1 - 2011
A1 - Markus Krotzsch
A1 - Frederick Maier
A1 - Adila Alfa Krisnadhi
A1 - Pascal Hitzler
KW - Datalog
KW - Description Logic
KW - Semantic Web Rule Language
KW - SROIQ
KW - tractability
KW - Web Ontology Language
AB - We propose a description-logic style extension of OWL 2 with nominal schemas which can be used like 'variable nominal classes' within axioms. This feature allows ontology languages to express arbitrary DL-safe rules (as expressible in SWRL or RIF) in their native syntax. We show that adding nominal schemas to OWL 2 does not increase the worst-case reasoning complexity, and we identify a novel tractable language SROELV_3(⊓, X) that is versatile enough to capture the lightweight languages OWL EL and OWL RL.
JA - International World Wide Web Conference (WWW2011)
PB - Proceedings of the 20th International World Wide Web Conference (WWW2011)
CY - New York
ER -
TY - CONF
T1 - Nominal Schemas for Integrating Rules and Description Logics
Y1 - 2011
A1 - Markus Krotzsch
A1 - Frederick Maier
A1 - Adila Alfa Krisnadhi
A1 - Pascal Hitzler
AB - We propose an extension of SROIQ with nominal schemas which can be used like Âvariable nominal conceptsÂ within axioms. This feature allows us to express arbitrary DL-safe rules in description logic syntax. We show that adding nominal schemas to SROIQ does not increase its worst-case reasoning complexity, and we identify a family of tractable DLs SROELVn that allow for restricted use of nominal schemas.
ER -
TY - BOOK
T1 - Foundations of Semantic Web Technologies
Y1 - 2010
A1 - Pascal Hitzler
A1 - Markus Krotzsch
A1 - Sebastian Rudolph
KW - foundations of semantic web
KW - foundations of semantic web technologies
ER -
TY - BOOK
T1 - Foundations of Semantic Web Technologies
Y1 - 2009
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
ER -
TY - CONF
T1 - Approximate OWL Instance Retrieval with Screech
T2 - Approximate OWL Instance Retrieval with Screech
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Tuvshintur Tserendorj
A1 - Pascal Hitzler
AB - With the increasing interest in expressive ontologies for the Semantic Web, it is critical to develop scalable and efficient ontology reasoning techniques that can properly cope with very high data volumes. For certain application domains, approximate reasoning solutions, which trade soundness or completeness for increased reasoning speed, will help to deal with the high computational complexities which state of the art ontology reasoning tools have to face. In this paper, we present a comprehensive overview of the SCREECH approach to approximate instance retrieval with OWL ontologies, which is based on the KAON2 algorithms, facilitating a compilation of OWL DL TBoxes into Datalog, which is tractable in terms of data complexity. We present three different instantiations of the Screech approach, and report on experiments which show that the gain in efficiency outweighs the number of introduced mistakes in the reasoning process.
JA - Approximate OWL Instance Retrieval with Screech
ER -
TY - CONF
T1 - Approximate OWL-Reasoning with Screech
T2 - International Conference, RR 2008
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Tuvshintur Tserendorj
A1 - Pascal Hitzler
AB - Applications of expressive ontology reasoning for the Semantic Web require scalable algorithms for deducing implicit knowledge from explicitly given knowledge bases. Besides the development of more efficient such algorithms, awareness is rising that approximate reasoning solutions will be helpful and needed for certain application domains. In this paper, we present a comprehensive overview of the Screech approach to approximate reasoning with OWL ontologies, which is based on the KAON2 algorithms, facilitating a compilation of OWL DL TBoxes into Datalog, which is tractable in terms of data complexity.We present three different instantiations of the Screech approach, and report on experiments which show that a significant gain in efficiency can be achieved.
JA - International Conference, RR 2008
PB - Second International Conference, RR 2008
CY - Karlsruhe, Germany
ER -
TY - CONF
T1 - Cheap Boolean Role Constructors for Description Logics
T2 - 11th European Conference on Logics in Artificial Intelligence (JELIA)
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - We investigate the possibility of incorporating Boolean role constructors on simple roles into some of today's most popular description logics, focussing on cases where those extensions do not increase complexity of reasoning. We show that the expressive DLs SHOIQ and SROIQ, serving as the logical underpinning of OWL and the forthcoming OWL 2, can accommodate arbitrary Boolean expressions. The prominent OWL-fragment SHIQ can be safely extended by safe role expressions, and the tractable fragments EL++ and DLP retain tractability if extended by conjunction on roles, where in the case of DLP the restriction on role simplicity can even be discarded.
JA - 11th European Conference on Logics in Artificial Intelligence (JELIA)
CY - Dresden, Germany
ER -
TY - CONF
T1 - Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
T2 - The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - 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.
JA - The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
PB - The Semantic Web - ISWC 2008, 7th International Semantic Web Conference
CY - Karlsruhe, Germany
ER -
TY - CONF
T1 - Description Logic Rules
T2 - 18th European Conference on Artificial Intelligence, ECAI
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - We introduce description logic (DL) rules as a new rule-based formalism for knowledge representation in DLs. As a fragment of the Semantic Web Rule Language SWRL, DL rules allow for a tight integration with DL knowledge bases. In contrast to SWRL, however, the combination of DL rules with expressive description logics remains decidable, and we show that the DL SROIQ - the basis for the ongoing standardisation of OWL 2 - can completely internalise DL rules. On the other hand, DL rules capture many expressive features of SROIQ that are not available in simpler DLs yet. While reasoning in SROIQ is highly intractable, it turns out that DL rules can be introduced to various lightweight DLs without increasing their worst-case complexity. In particular, DL rules enable us to significantly extend the tractable DLs EL++ and DLP.
JA - 18th European Conference on Artificial Intelligence, ECAI
CY - Patras, Greece
ER -
TY - CONF
T1 - ELP: Tractable Rules for OWL 2
T2 - ELP: Tractable Rules for OWL 2
Y1 - 2008
A1 - Markus Krotzsch
A1 - Sebastian Rudolph
A1 - Pascal Hitzler
AB - We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role.We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP.While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
JA - ELP: Tractable Rules for OWL 2
ER -
TY - RPRT
T1 - ELP: Tractable Rules for OWL 2
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role. We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP. While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
JA - ELP: Tractable Rules for OWL 2
ER -
TY - ABST
T1 - ELP: Tractable Rules for OWL 2
Y1 - 2008
A1 - Markus Krotzsch
A1 - Sebastian Rudolph
A1 - Pascal Hitzler
AB - We introduce ELP as a decidable fragment of the Semantic Web Rule Language (SWRL) that admits reasoning in polynomial time. ELP is based on the tractable description logic EL++, and encompasses an extended notion of the recently proposed DL rules for that logic. Thus ELP extends EL++ with a number of features introduced by the forthcoming OWL 2, such as disjoint roles, local reflexivity, certain range restrictions, and the universal role.We present a reasoning algorithm based on a translation of ELP to Datalog, and this translation also enables the seamless integration of DL-safe rules into ELP.While reasoning with DL-safe rules as such is already highly intractable, we show that DL-safe rules based on the Description Logic Programming (DLP) fragment of OWL 2 can be admitted in ELP without losing tractability.
ER -
TY - ABST
T1 - Expressive Tractable Description Logics based on SROIQ Rules
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - We introduce description logic (DL) rules as a new rule-based formalism for knowledge representation in DLs. As a fragment of the Semantic Web Rule Language SWRL, DL rules allow for a tight integration with DL knowledge bases. In contrast to SWRL, however, the combination of DL rules with expressive description logics remains decidable, and we show that the DL SROIQ - the basis for the ongoing standardisation of OWL 2 - can completely internalise DL rules. On the other hand, DL rules capture many expressive features of SROIQ that are not available in simpler DLs yet. While reasoning in SROIQ is highly intractable, it turns out that DL rules can be introduced to various lightweight DLs without increasing their worst-case complexity. In particular, DL rules enable us to significantly extend the tractable DLs EL++ and DLP.
ER -
TY - BOOK
T1 - Semantic Web. Grundlagen
Y1 - 2008
A1 - Sebastian Rudolph
A1 - York Sure
A1 - Markus Krotzsch
A1 - Pascal Hitzler
ER -
TY - CONF
T1 - Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
T2 - Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - We present a new algorithm for reasoning in the description logic SHIQ, which is the most prominent fragment of the Web Ontology Language OWL. The algorithm is based on ordered binary decision diagrams (OBDDs) as a data structure for storing and operating on large model representations. We thus draw on the success and the proven scalability of OBDD-based systems. To the best of our knowledge, we present the very first algorithm for using OBDDs for reasoning with general Tboxes.
JA - Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
ER -
TY - ABST
T1 - Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
Y1 - 2008
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - We present a new algorithm for reasoning in the description logic SHIQ, which is the most prominent fragment of the Web Ontology Language OWL. The algorithm is based on ordered binary decision diagrams (OBDDs) as a data structure for storing and operating on large model representations. We thus draw on the success and the proven scalability of OBDD-based systems. To the best of our knowledge, we present the very first algorithm for using OBDDs for reasoning with general Tboxes.
ER -
TY - CONF
T1 - Complexity Boundaries for Horn Description Logics
T2 - The 22nd AAAI Conference on Artficial Intelligence
Y1 - 2007
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - Horn description logics (Horn-DLs) have recently started to attract attention due to the fact that their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large ABoxes. However, the natural question whether Horn-DLs also provide advantages for 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 turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning.
JA - The 22nd AAAI Conference on Artficial Intelligence
CY - Vancouver, British Columbia, Canada
ER -
TY - ABST
T1 - Complexity of Horn Description Logics
Y1 - 2007
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - Horn description logics (Horn-DLs) have recently started to attract attention due to the fact that their (worst-case) data complexities are in general lower than their overall (i.e. combined) complexities, which makes them attractive for reasoning with large ABoxes. However, the natural question whether Horn-DLs also provide advantages for 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 turns out to be the same as for their non-Horn counterparts, we identify subboolean DLs where Hornness simplifies reasoning.
ER -
TY - CONF
T1 - Conjunctive Queries for a Tractable Fragment of OWL 1.1
T2 - 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
Y1 - 2007
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - Despite the success of the Web Ontology Language OWL, the development of expressive means for querying OWL knowledge bases is still an open issue. In this paper, we investigate how a very natural and desirable form of queries-namely conjunctive ones-can be used in conjunction with OWL such that one of the major design criteria of the latter-namely decidability-can be retained. More precisely, we show that querying the tractable fragment EL++ of OWL 1.1 is decidable. We also provide a complexity analysis and show that querying unrestricted EL++ is undecidable.
JA - 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
PB - The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
CY - Busan, Korea
ER -
TY - CONF
T1 - Efficient OWL Reasoning with Logic Programs - Evaluations
T2 - International Conference on Web Reasoning and Rule Systems, RR2007
Y1 - 2007
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Michael Sintek
A1 - Denny Vrandecic
A1 - Pascal Hitzler
AB - We report on efficiency evaluations concerning two different approaches to using logic programming for OWL [1] reasoning and show, how the two approaches can be combined. Introduction. Scalability of reasoning remains one of the major obstacles in leveraging the full power of the Web Ontology Language OWL [1] for practical applications. Among the many possible approaches to address scalability, one of them concerns the use of logic programming for this purpose. It was recently shown that reasoning in Horn-SHIQ [2-4] can be realised by invoking Prolog systems on the output of the
JA - International Conference on Web Reasoning and Rule Systems, RR2007
CY - Innsbruck, Austria
ER -
TY - CONF
T1 - Quo Vadis, CS? - On the (non)-impact of Conceptual Structures on the Semantic Web
T2 - ICCS 2007
Y1 - 2007
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - Conceptual Structures is a field of research which shares abstract concepts and interests with recent work on knowledge representation for the Semantic Web. However, while the latter is an area of research and development which is rapidly expanding in recent years, the former fails to participate in these developments on a large scale. In this paper, we attempt to stimulate the Conceptual Structures community to catch the Semantic Web train.
JA - ICCS 2007
CY - Sheffield, UK
ER -
TY - CONF
T1 - On the Complexity of Horn Description Logics
Y1 - 2006
A1 - Sebastian Rudolph
A1 - Markus Krotzsch
A1 - Pascal Hitzler
AB - Horn-*SHIQ* has been identified as a fragment of the description logic *SHIQ* for which inferencing is in PT_{IME} with respect to the size of the ABox. This enables reasoning with larger ABoxes in situations where the TBox is static, and represents one approach towards tractable description logic reasoning. In this paper, we show that reasoning in Horn-*SHIQ*, in spite of its low datacomplexity, is E_{xp}T_{IME}-hard with respect to the overall size of the knowledge base. While this result is not unexpected, the proof is not a mere modification of existing reductions since it has to account for the restrictions of Hornness. We establish the result for Horn-*FLE*, showing that Hornness does not simplify TBox reasoning even for very restricted description logics. Moreover, we derive a context-free grammar that defines Horn-*SHIQ* in a simpler and more intuitive way than existing characterisations.
PB - Second Workshop OWL - Experiences and Directions, OWLED2006
ER -
TY - CONF
T1 - How to Reason with OWL in a Logic Programming System
T2 - the Second International Conference on Rules and Rule Markup Languages for the Semantic Web, RuleML2006
Y1 - 2006
A1 - M. Krotzsch
A1 - D. Vrandecic
A1 - M. Sintek
A1 - Pascal Hitzler
AB - Logic programming has always been a major ontology modeling paradigm, and is frequently being used in large research projects and industrial applications, e.g., by means of the F-Logic reasoning engine OntoBroker or the TRIPLE query, inference, and transformation language and system. At the same time, the Web Ontology Language OWL has been recommended by the W3C for modeling ontologies for the web. Naturally, it is desirable to investigate the interoperability between both paradigms. In this paper, we do so by studying an expressive fragement of OWL DL for which reasoning can be reduced to the evaluation of Horn logic programs. Building on the KAON2 algorithms for transforming OWL DL into disjunctive Datalog, we give a detailed account of how and to what extent OWL DL can be employed in standard logic programming systems. En route, we derive a novel, simplified characterization of the supported fragment of OWL DL.
JA - the Second International Conference on Rules and Rule Markup Languages for the Semantic Web, RuleML2006
CY - Athens, Georgia
ER -
TY - CONF
T1 - Querying Formal Contexts with Answer Set Programs
T2 - 14th International Conference on Conceptual Structures, ICCS 2006
Y1 - 2006
A1 - M. Krotzsch
A1 - Pascal Hitzler
AB - Recent studies showed how a seamless integration of formal concept analysis (FCA), logic of domains, and answer set programming (ASP) can be achieved. Based on these results for combining hierarchical knowledge with classical rule-based formalisms, we introduce an expressive common-sense query language for formal contexts. Although this approach is conceptually based on order-theoretic paradigms, we show how it can be implemented on top of standard ASP systems. Advanced features, such as default negation and disjunctive rules, thus become practically available for processing contextual data.
JA - 14th International Conference on Conceptual Structures, ICCS 2006
CY - Aalborg, Denmark
ER -
TY - ABST
T1 - Category Theory in Ontology Research: Concrete Gain from an Abstract Approach
Y1 - 2005
A1 - Markus Krotzsch
A1 - Marc Ehrig
A1 - York Sure
AB - The focus of research on representing and reasoning with knowledge traditionally has been on single speciÃ¯Â¬Âcations and appropriate inference paradigms to draw conclusions from such data. Accordingly, this is also an essential aspect of ontology research which has received much attention in recent years. But ontologies introduce another new challenge based on the distributed nature of most of their applications, which requires to relate heterogeneous ontological speciÃ¯Â¬Âcations and to integrate information from multiple sources. These problems have of course been recognized, but many current approaches still lack the deep formal backgrounds on which todays reasoning paradigms are already founded. Here we propose category theory as a well-explored and very extensive mathematical foundation for modelling distributed knowledge. A particular prospect is to derive conclusions from the structure of those distributed knowledge bases, as it is for example needed when merging ontologies.
ER -
TY - CONF
T1 - DLP Isn't So Bad After All
Y1 - 2005
A1 - York Sure
A1 - Rudi Studer
A1 - Markus Krotzsch
A1 - Peter Haase
A1 - Pascal Hitzler
AB - We discuss some of the recent controversies concerning the DLP fragment of OWL. We argue that it is a meaningful fragment and can serve as a basic interoperability layer between OWL and logic programming-based ontology languages.
ER -
TY - CONF
T1 - DLP Isn't So Bad After All
T2 - DLP Isn't So Bad After All
Y1 - 2005
A1 - Pascal Hitzler
A1 - York Sure
A1 - Rudi Studer
A1 - Markus Krotzsch
A1 - Peter Haase
JA - DLP Isn't So Bad After All
ER -
TY - CONF
T1 - Morphisms in Context
T2 - 13th International Conference on Conceptual Structures, ICCS '05
Y1 - 2005
A1 - Markus Krotzsch
A1 - Guo-Qiang Zhang
A1 - Pascal Hitzler
AB - Morphisms constitute a general tool for modelling complex relationships between mathematical objects in a disciplined fashion. In Formal Concept Analysis (FCA), morphisms can be used for the study of structural properties of knowledge represented in formal contexts, with applications to data transformation and merging. In this paper we present a comprehensive treatment of some of the most important morphisms in FCA and their relationships, including dual bonds, scale measures, infomorphisms, and their respective relations to Galois connections. We summarize our results in a concept lattice that cumulates the relationships among the considered morphisms. The purpose of this work is to lay a foundation for applications of FCA in ontology research and similar areas, where morphisms help formalize the interplay among distributed knowledge bases.
JA - 13th International Conference on Conceptual Structures, ICCS '05
CY - Kassel, Germany
ER -
TY - CONF
T1 - What Is Ontology Merging? - A Category-Theoretical Perspective Using Pushouts
Y1 - 2005
A1 - York Sure
A1 - Markus Krotzsch
A1 - Marc Ehrig
A1 - Pascal Hitzler
AB - In this paper we explain how merging of ontologies is captured by the pushout construction from category theory, and argue that this is a very natural approach to the problem. We study this independent of a specific choice of ontology representation language, and thus provide a sort of blueprint for the development of algorithms applicable in practice. For this purpose, we view category theory as a universal 'meta specification language' that enables us to specify properties of ontological relationships and constructions in a way that does not depend on any particular implementation. This can be achieved since the basic objects of study in category theory are the relationships between multiple ontological specifications, not the internal structure of a single knowledge representation. Categorical pushouts are already considered in some approaches to ontology research (Jannink et al. 1998; Schorlemmer, Potter, & Robertson 2002; Goguen 2005; Kent 2005) and we do not claim our treatment to be entirely original. Still we have the impression that the potential of category theoretic approaches is by far not exhausted in todays ontology research. For our particular case the treatment will focus on the ontology merging, for which we will give both intuitive explanations and precise definitions. This reflects our belief that, at the current stage of research, it is not desirable to fade out the mathematical details of the categorical approach completely, since the interfaces to current techniques in ontology research are not yet available to their full extent. We will also keep this treatment rather general, not narrowing the discussion to specific formalisms - this added generality is one of the strengths of category theory. A long version of this paper with a tutorial character is available from the first author's homepage.
PB - 20th National Conference on Artificial Intelligence, AAAI-05
ER -