Title: Approximate Representation and Reasoning in Description Logics

Project duration: Until end of September 2025

Research Area: Knowledge Representation and Engineering

A considerable amount of research has been devoted to extending traditional Description Logics (DLs) with non-classical semantics that can be used to represent, and reason about, imprecise or approximate knowledge. In this project, we extend previous work on approximation in DLs in two directions. The first focuses on approximate representation and reasoning for ontology-mediated query answering (OMQA). By using approximation, an OMQA system can provide answers that only approximately match the conditions stated in a query, but may nevertheless be of interest for the user. The second direction considers unification in DLs, which tries to make concepts equivalent by adding definitions for atomic concepts. This yields an approximation of equivalence of concepts, which can, e.g., be used to detect redundancies in ontologies.

Aims

In the project “Approximate Representation and Reasoning in Description Logics”, we have two main goals. The first consists of thoroughly comparing the approaches for approximately defining concepts and approximately answering queries, introduced in our previous work. Based on this, we aim to develop a comprehensive framework for OMQA under approximate semantics. Our second objective is to study the decidability and complexity of unification in lightweight DLs w.r.t. ontologies, and to develop practical algorithms for the decidable cases.

Problem

We compare the approaches from our previous work on approximation w.r.t. their expressive power and their computational complexity. Relevant questions in this context include: Is using one approach more efficient than using another? Compare precision and recall of different approaches? Regarding unification, existing techniques cannot deal with arbitrary ontologies, but only with ones satisfying a certain restriction on cyclic dependencies. The main problem is thus to develop new methods that can handle the general case.

Technology

This project requires deep knowledge of the investigated DLs. We also use techniques from complexity theory, logic in computer science, databases, unification theory and automata theory.

Outlook

Our framework for approximately answering queries represents a first step towards extending OMQA systems with approximate semantics. We believe that such systems would enrich the user’s experience during query answering. In particular, approximate answers can be very useful in scenarios where a query has no (only a few) exact answers. Regarding unification, the decidability status of unification w.r.t. unrestricted ontologies in sub-Boolean DLs is a big open problem. A solution to this problem will also be of great interest to researchers on unification theory.

Publications

• Oliver Fernández Gil, Fabrio Patrizi, Giuseppe Perelli, Anni-Yasmin Turhan. Optimal Alignment of Temporal Knowledge Bases. In Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023), vol. 372, IOS Press (2023), pp. 708-715.
• Anni-Yasmin Turhan. Brushing-up DLs to cope with imperfect data (Abstract of Joint DL+NMR Invited Talk). In Proceedings of the 36th International Workshop on Description Logics (DL 2023), vol 3515, CEUR-WS.org (2023).
• Oliver Fernández Gil, Pavlos Marantidis. Towards Extending the Description Logic FL0 with Threshold Concepts Using Weighted Tree Automata. In Proceedings of the 36th International Workshop on Description Logics (DL 2023), vol 3515, CEUR-WS.org (2023).
• Igor de Camargo e Souza Câmara and Anni-Yasmin Turhan: Deciding Subsumption in Defeasible ELI_bot with Typicality Models. In Sarah Alice Gaggl, Maria Vanina Martinez, and Magdalena Ortiz, editors, Logics in Artificial Intelligence – 18th European Conference, JELIA 2023, Dresden, Germany, September 20-22, 2023, Proceedings, volume 14281 of Lecture Notes in Computer Science, pages 531–546. Springer, 2023.
• Franz Baader, Oliver Fernández Gil. Restricted Unification in the Description Logic FL_⊥. In Proceedings of the 36th International Workshop on Unification (UNIF 2022).
• Franz Baader and Deepak Kapur: Deciding the Word Problem for Ground and Strongly Shallow Identities w.r.t. Extensional Symbols. Journal of Automated Reasoning, 66(3):301–329, 2022.
• Satyadharma Tirtarasa and Anni-Yasmin Turhan: A New Dimension to Generalization: Computing Temporal EL Concepts from Positive Examples (Extended Abstract)). In Proceedings of the 35th International Workshop on Description Logics (DL 2022), Haifa, Israel, August 7–10, 2022, CEUR Workshop Proceedings. CEUR-WS.org, 2022.

Team

Lead

• Prof. Dr.-Ing. Franz Baader

Team Members

• Oliver Fernández Gil
• Francesco Kriegel

Partners

• Prof. Dr. Carsten Lutz
• Prof. Dr. Markus Krötzsch