Description logics

Description logics (DLs) encompass a range of closely related knowledge representation languages, that, depending on your point of view, correspond to certain fragments of (guarded) first-order logic or to specific hybrid logics. Though research dates back to the 1980s, DLs have greatly gained popularity with the advent of Semantic Web research.

Most of my original work in this area relates to tractability and complexity, and also to conjunctive queries. Recently, we have also investigated description logic rules, and the related tractable logic ELP.

A more specialized topic is the development of the ELK reasoner.

Useful resources

• An very first introduction to DLs with pointers to further resources is given in the IEEE Intelligent Systems article "Description Logics"; a free (unreviewed) version of this content is also available in form of the DL Primer.
• Wikipedia article on DLs; general intro and further links/references
• The Description Logic Complexity Navigator is an immensely helpful tool to find key publications on expressive DLs; a good starting point even if complexities are not your main interest
• The list of current description logic reasoners

Publications related to this topic

Updates to the following list are also available as RSS feed. A list of all publications is also available.

• Markus Krötzsch, Sebastian Rudolph. Is Your Database System a Semantic Web Reasoner?. In Künstliche Intelligenz 30(2).  2016. (view details, download)
   
• Stefan Bischof, Markus Krötzsch, Axel Polleres, Sebastian Rudolph. Schema-Agnostic Query Rewriting for OWL QL. In Diego Calvanese, Boris Konev, eds.: Proceedings of the 28th International Workshop on Description Logics (DL-15).  2015. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Peter H. Schmitt. A Closer Look at the Semantic Relationship between Datalog and Description Logics. In Semantic Web Journal, volume 6:1.  2015. (view details)
   
• Giorgio Stefanoni, Boris Motik, Markus Krötzsch, Sebastian Rudolph. The Complexity of Answering Conjunctive and Navigational Queries over OWL 2 EL Knowledge Bases. In Journal of Artificial Intelligence Research, volume 51.  2014. (view details, download)
   
• Markus Krötzsch. P ≠ P: Why Some Reasoning Problems are More Tractable Than Others. In Roman Kontchakov, Marie-Laure Mugnier, eds.: Proceedings of the 8th International Conference on Web Reasoning and Rule Systems (RR-14).  2014. (view details, download)
   
• Stefan Bischof, Markus Krötzsch, Axel Polleres, Sebastian Rudolph. Schema-Agnostic Query Rewriting in SPARQL 1.1. In Peter Mika, Tania Tudorache, Abraham Bernstein, Chris Welty, Craig A. Knoblock, Denny Vrandečić, Paul T. Groth, Natasha F. Noy, eds.: Proceedings of the 13th International Semantic Web Conference.  2014. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph. Nominal Schemas in Description Logics: Complexities Clarified. In Chitta Baral, Giuseppe De Giacomo, Thomas Eiter, eds.: Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR 2014).  2014. (view details, download)
   
• Pierre Bourhis, Markus Krötzsch, Sebastian Rudolph. How to Best Nest Regular Path Queries. In Meghyn Bienvenu, Magdalena Ortiz, Riccardo Rosati, Mantas Simkus, eds.: Proceedings of the 27th International Workshop on Description Logics (DL-14).  2014. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph. Complexities for Nominal Schemas: Extended Abstract. In Meghyn Bienvenu, Magdalena Ortiz, Riccardo Rosati, Mantas Simkus, eds.: Proceedings of the 27th International Workshop on Description Logics (DL-14).  2014. (view details, download)
   
• Markus Krötzsch, František Simančík, Ian Horrocks. Description Logics. In IEEE Intelligent Systems, volume 29:1.  2014. (view details, download)
   
• Despoina Magka, Markus Krötzsch, Ian Horrocks. A rule-based ontological framework for the classification of molecules. In Journal of Biomedical Semantics, volume 5:17.  2014. (view details, download)
   
• Markus Krötzsch, František Simančík, Ian Horrocks. A Description Logic Primer. In Jens Lehmann, Johanna Völker, eds.: Perspectives on Ontology Learning.  2014. (view details)
   
• Yevgeny Kazakov, Markus Krötzsch, František Simančík. The Incredible ELK: From Polynomial Procedures to Efficient Reasoning with EL Ontologies. In Journal of Automated Reasoning 53:1.  2013. (view details, download)
   
• Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang. Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies. In Journal of Artificial Intelligence Research, volume 47.  2013. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. Complexities of Horn Description Logics. In ACM Transactions on Computational Logic 14 (1).  2013. (view details, download)
   
• Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph. 语义Web技术基础.  2012. (view details)
   
• Markus Krötzsch. The Not-So-Easy Task of Computing Class Subsumptions in OWL RL. In Philippe Cudré-Mauroux, Jeff Heflin, Evren Sirin, Tania Tudorache, Jérôme Euzenat, Manfred Hauswirth, Josiane Xavier Parreira, Jim Hendler, eds.: Proceedings of the 11th International Semantic Web Conference.  2012. (view details, download)
   
• Bernardo Cuenca Grau, Ian Horrocks, Markus Krötzsch, Clemens Kupke, Despoina Magka, Boris Motik, Zhe Wang. Acyclicity Conditions and their Application to Query Answering in Description Logics. In Gerhard Brewka, Thomas Eiter, Sheila A. McIlraith, eds.: Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012).  2012. (view details, download)
   
• Yevgeny Kazakov, Markus Krötzsch, František Simančík. Practical Reasoning with Nominals in the EL Family of Description Logics. In Gerhard Brewka, Thomas Eiter, Sheila A. McIlraith, eds.: Proceedings of the 13th International Conference on Principles of Knowledge Representation and Reasoning (KR 2012).  2012. (view details, download)
   
• Yevgeny Kazakov, Markus Krötzsch, František Simančík. ELK Reasoner: Architecture and Evaluation. In Ian Horrocks, Mikalai Yatskevich, Ernesto Jimenez-Ruiz, eds.: Proceedings of the OWL Reasoner Evaluation Workshop 2012.  2012. (view details, download)
   
• Markus Krötzsch. OWL 2 Profiles: An Introduction to Lightweight Ontology Languages. In Thomas Eiter, Thomas Krennwallner, eds.: Reasoning Web Summer School 2012.  2012. (view details, download)
   
• Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Type-elimination-based Reasoning for the Description Logic SHIQbs using Decision Diagrams and Disjunctive Datalog. In Logical Methods in Computer Science 8 (1).  2012. (view details, download)
   
• Yevgeny Kazakov, Markus Krötzsch, František Simančík. ELK: A Reasoner for OWL EL Ontologies. In Technical Report.  2012. (view details, download)
   
• Markus Krötzsch, František Simančík, Ian Horrocks. A Description Logic Primer. In CoRR abs/1201.4089.  2012. (view details, download)
   
• Yevgeny Kazakov, Markus Krötzsch, František Simančík. Concurrent Classification of EL Ontologies. In Lora Aroyo, Chris Welty, Harith Alani, Jamie Taylor, Abraham Bernstein, Lalana Kagal, Natasha Noy, Eva Blomqvist, eds.: Proceedings of the 10th International Semantic Web Conference.  2011. (view details, download)
   
• Yevgeny Kazakov, Markus Krötzsch, František Simančík. Unchain My EL Reasoner. In Riccardo Rosati, Sebastian Rudolph, Michael Zakharyaschev, eds.: Proceedings of the 24th International Workshop on Description Logics (DL-11).  2011. (view details, download)
   
• František Simančík, Boris Motik, Markus Krötzsch. Fixed Parameter Tractable Reasoning in DLs via Decomposition. In Riccardo Rosati, Sebastian Rudolph, Michael Zakharyaschev, eds.: Proceedings of the 24th International Workshop on Description Logics (DL-11).  2011. (view details, download)
   
• Markus Krötzsch, Frederick Maier, Adila A. Krisnadhi, Pascal Hitzler. Nominal Schemas for Integrating Rules and Ontologies. In Riccardo Rosati, Sebastian Rudolph, Michael Zakharyaschev, eds.: Proceedings of the 24th International Workshop on Description Logics (DL-11).  2011. (view details, download)
   
• Markus Krötzsch. Efficient Rule-Based Inferencing for OWL EL. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11).  2011. (view details, download)
   
• Markus Krötzsch, Frederick Maier, Adila A. Krisnadhi, Pascal Hitzler. A Better Uncle for OWL: Nominal Schemas for Integrating Rules and Ontologies. In Proceedings of the 20th International Conference on the World Wide Web (WWW-11).  2011. (view details, download)
   
• Markus Krötzsch. Efficient Inferencing for OWL EL. In Tomi Janhunen, Ilkka Niemelä, eds.: Proceedings of the 12th European Conference on Logics in Artificial Intelligence.  2010. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Peter H. Schmitt. On the Semantic Relationship between Datalog and Description Logics. In Pascal Hitzler, Thomas Lukasiewicz, eds.: Proceedings of the 4th International Conference on Web Reasoning and Rule Systems.  2010. (view details, download)
   
• Markus Krötzsch. Adventures of Two Little OWLs in Rule Land.  2010. (view details, download)
   
• Markus Krötzsch. Description Logic Rules.  2010. (view details, download)
   
• Birte Glimm, Markus Krötzsch. SPARQL Beyond Subgraph Matching. In Peter F. Patel-Schneider, Yue Pan, Birte Glimm, Pascal Hitzler, Peter Mika, Jeff Pan, Ian Horrocks, eds.: Proceedings of the 9th International Semantic Web Conference.  2010. (view details, download)
   
• Markus Krötzsch. Efficient Inferencing for the Description Logic Underlying OWL EL.  2010. (view details, download)
   
• Markus Krötzsch, Anees Mehdi, Sebastian Rudolph. Orel: Database-Driven Reasoning for OWL 2 Profiles. In Volker Haarslev, David Toman, Grant Weddell, eds.: Proceedings of the 23rd International Workshop on Description Logics (DL2010).  2010. (view details, download)
   
• Pascal Hitzler, Markus Krötzsch, Bijan Parsia, Peter F. Patel-Schneider, Sebastian Rudolph (eds.). OWL 2 Web Ontology Language Primer.  27 October 2009. (view details)
   
• Michael Smith, Ian Horrocks, Markus Krötzsch, Birte Glimm (eds.). OWL 2 Web Ontology Language Conformance.  27 October 2009. (view details)
   
• Markus Krötzsch, Sebastian Rudolph. The Largest DLP Possible.  2009. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph. A Matter of Principles: Towards the Largest DLP Possible. In Proceedings of the 22nd International Workshop on Description Logics (DL2009).  2009. (view details, download)
   
• Pascal Hitzler, Markus Krötzsch, Sebastian Rudolph. Foundations of Semantic Web Technologies.  2009. (view details)
   
• Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. ELP: Tractable Rules for OWL 2. In Amit Sheth, Steffen Staab, Mike Dean, Massimo Paolucci, Diana Maynard, Timothy Finin, Krishnaprasad Thirunarayan, eds.: Proceedings of the 7th International Semantic Web Conference (ISWC-08).  2008. (view details, download)
   
• Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Description Logic Reasoning with Decision Diagrams – Compiling SHIQ to Disjunctive Datalog. In Amit Sheth, Steffen Staab, Mike Dean, Massimo Paolucci, Diana Maynard, Timothy Finin, Krishnaprasad Thirunarayan, eds.: Proceedings of the 7th International Semantic Web Conference (ISWC-08).  2008. (view details, download)
   
• Tuvshintur Tserendorj, Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Approximate OWL-Reasoning with Screech. In Diego Calvanese, Georg Lausen, eds.: Proceedings of the 2nd International Conference on Web Reasoning and Rule Systems (RR-08).  2008. (view details, download)
   
• Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Cheap Boolean Role Constructors for Description Logics. In Steffen Hölldobler, Carsten Lutz, Heinrich Wansing, eds.: Proceedings of the 11th European Conference on Logics in Artificial Intelligence (JELIA-08).  2008. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. Description Logic Rules. In Malik Ghallab, Constantine D. Spyropoulos, Nikos Fakotakis, Nikos Avouris, eds.: Proceedings of the 18th European Conference on Artificial Intelligence (ECAI-08).  2008. (view details, download)
   
• Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI-08).  2008. (view details, download)
   
• Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler. All Elephants are Bigger than All Mice. In Proceedings of the 21st International Workshop on Description Logics (DL-08).  2008. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. Conjunctive Queries for a Tractable Fragment of OWL1.1. In Karl Aberer, Key-Sun Choi, Natasha Noy, Dean Allemang, Kyung-Il Lee, Lyndon Nixon, Jennifer Golbeck, Peter Mika, eds.: Proceedings of the 6th International Semantic Web Conference (ISWC-07).  2007. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. Complexity Boundaries for Horn Description Logics. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI-07).  2007. (view details, download)
   
• Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler, Michael Sintek, Denny Vrandečić. Efficient OWL Reasoning with Logic Programs – Evaluations. In Massimo Marchiori, Jeff Z. Pan, Christian de Sainte Marie, eds.: Proceedings of The First International Conference on Web Reasoning and Rule Systems 2007 (RR-07).  2007. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph. Conjunctive Queries for EL with Role Composition. In Proceedings of the 20th International Workshop on Description Logics (DL-07).  2007. (view details, download)
   
• Markus Krötzsch. Practical Reasoning with OWL and Rules.  2007. (view details, download)
   
• Markus Krötzsch, Pascal Hitzler, Denny Vrandečić, Michael Sintek. How to reason with OWL in a logic programming system. In Thomas Eiter, Enrico Franconi, Ralph Hodgson, Susie Stephens, eds.: Proceedings of the Second International Conference on Rules and Rule Markup Languages for the Semantic Web (RuleML-06).  2006. (view details, download)
   
• Markus Krötzsch, Sebastian Rudolph, Pascal Hitzler. On the Complexity of Horn Description Logics. In Bernardo Cuenca Grau, Pascal Hitzler, Conor Shankey, Evan Wallace, eds.: Proceedings of the 2nd Workshop on OWL: Experiences and Directions (OWLED-06).  2006. (view details, download)
   
• Markus Krötzsch. Practical Reasoning with OWL and DL-Safe Rules.  2006. (view details, download)
   
• Pascal Hitzler, Peter Haase, Markus Krötzsch, York Sure, Rudi Studer. DLP isn't so bad after all. In Bernardo Cuenca Grau, Ian Horrocks, Bijan Parsia, Peter Patel-Schneider, eds.: Proceedings of the 1st Workshop on OWL: Experiences and Directions (OWLED-05).  2005. (view details, download)
   

enDescription logics