%0 Book
%D 2010
%T Foundations of Semantic Web Technologies
%A Pascal Hitzler
%A Markus Krotzsch
%A Sebastian Rudolph
%K foundations of semantic web
%K foundations of semantic web technologies
%G eng
%0 Conference Paper
%D 2009
%T An Evolutionary Computing Approach for Reasoning in the Semantic Web
%A Sebastian Rudolph
%A Gaston Tagni
%A Christophe Gueret
%A Stefan Schlobach
%A Pascal Hitzler
%I International Workshop on Collective Intelligence and Evolution
%G eng
%0 Book
%D 2009
%T Foundations of Semantic Web Technologies
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%G eng
%0 Conference Paper
%B Approximate OWL Instance Retrieval with Screech
%D 2008
%T Approximate OWL Instance Retrieval with Screech
%A Sebastian Rudolph
%A Markus Krotzsch
%A Tuvshintur Tserendorj
%A Pascal Hitzler
%X 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.
%B Approximate OWL Instance Retrieval with Screech
%G eng
%0 Conference Paper
%B International Conference, RR 2008
%D 2008
%T Approximate OWL-Reasoning with Screech
%A Sebastian Rudolph
%A Markus Krotzsch
%A Tuvshintur Tserendorj
%A Pascal Hitzler
%X 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.
%B International Conference, RR 2008
%I Second International Conference, RR 2008
%C Karlsruhe, Germany
%P 165-180
%8 10/2008
%G eng
%0 Conference Paper
%B 11th European Conference on Logics in Artificial Intelligence (JELIA)
%D 2008
%T Cheap Boolean Role Constructors for Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B 11th European Conference on Logics in Artificial Intelligence (JELIA)
%C Dresden, Germany
%P 362-374
%8 09/2008
%G eng
%0 Conference Paper
%B The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
%D 2008
%T Description Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B The Semantic Web - ISWC 2008, 7th International Semantic Web Conference, 2008
%I The Semantic Web - ISWC 2008, 7th International Semantic Web Conference
%C Karlsruhe, Germany
%P 435-450
%G eng
%0 Conference Paper
%B 18th European Conference on Artificial Intelligence, ECAI
%D 2008
%T Description Logic Rules
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B 18th European Conference on Artificial Intelligence, ECAI
%C Patras, Greece
%P 80-84
%8 07/2008
%G eng
%0 Conference Paper
%B ELP: Tractable Rules for OWL 2
%D 2008
%T ELP: Tractable Rules for OWL 2
%A Markus Krotzsch
%A Sebastian Rudolph
%A Pascal Hitzler
%X 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.
%B ELP: Tractable Rules for OWL 2
%G eng
%0 Report
%D 2008
%T ELP: Tractable Rules for OWL 2
%A Sebastian Rudolph
%A Pascal Hitzler
%A Markus Krotzsch
%X 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.
%B ELP: Tractable Rules for OWL 2
%G eng
%0 Generic
%D 2008
%T ELP: Tractable Rules for OWL 2
%A Markus Krotzsch
%A Sebastian Rudolph
%A Pascal Hitzler
%X 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.
%G eng
%0 Generic
%D 2008
%T Expressive Tractable Description Logics based on SROIQ Rules
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%G eng
%0 Book
%D 2008
%T Semantic Web. Grundlagen
%A Sebastian Rudolph
%A York Sure
%A Markus Krotzsch
%A Pascal Hitzler
%G eng
%0 Conference Paper
%B Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%D 2008
%T Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%G eng
%0 Generic
%D 2008
%T Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%G eng
%0 Conference Paper
%B The 22nd AAAI Conference on Artficial Intelligence
%D 2007
%T Complexity Boundaries for Horn Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B The 22nd AAAI Conference on Artficial Intelligence
%C Vancouver, British Columbia, Canada
%G eng
%0 Generic
%D 2007
%T Complexity of Horn Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%G eng
%0 Conference Paper
%B 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
%D 2007
%T Conjunctive Queries for a Tractable Fragment of OWL 1.1
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
%I The Semantic Web, 6th International Semantic Web Conference, 2nd Asian Semantic Web Conference, ISWC 2007 + ASWC
%C Busan, Korea
%P 310-323
%8 11/2007
%G eng
%0 Conference Paper
%B International Conference on Web Reasoning and Rule Systems, RR2007
%D 2007
%T Efficient OWL Reasoning with Logic Programs - Evaluations
%A Sebastian Rudolph
%A Markus Krotzsch
%A Michael Sintek
%A Denny Vrandecic
%A Pascal Hitzler
%X 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
%B International Conference on Web Reasoning and Rule Systems, RR2007
%C Innsbruck, Austria
%P 370-373
%G eng
%0 Conference Paper
%B ICCS 2007
%D 2007
%T Quo Vadis, CS? - On the (non)-impact of Conceptual Structures on the Semantic Web
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%B ICCS 2007
%C Sheffield, UK
%G eng
%0 Conference Paper
%D 2006
%T On the Complexity of Horn Description Logics
%A Sebastian Rudolph
%A Markus Krotzsch
%A Pascal Hitzler
%X 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.
%I Second Workshop OWL - Experiences and Directions, OWLED2006
%G eng