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 - CONF
T1 - An Evolutionary Computing Approach for Reasoning in the Semantic Web
Y1 - 2009
A1 - Sebastian Rudolph
A1 - Gaston Tagni
A1 - Christophe Gueret
A1 - Stefan Schlobach
A1 - Pascal Hitzler
PB - International Workshop on Collective Intelligence and Evolution
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 - Pascal Hitzler
A1 - Markus Krotzsch
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 -