Functional models and Data Complexity for FL0
From International Center for Computational Logic
Functional models and Data Complexity for FL0
Talk by Pavlos Marantidis
- Location: APB 3027
- Start: 15. March 2018 at 9:20 am
- End: 15. March 2018 at 10:50 am
- Research group: Automata Theory
- Event series: KBS Seminar
- iCal
In the early days of Description Logic research, the inexpressive DL FL0 was considered to be the smallest possible DL. When it was later shown that subsumption reasoning wrt general TBoxes is as hard as for the more expressive ALC, the community lost interest in this DL. However, the recent approach of reasoning with so-called functional models has rekindled the interest, since, on the one hand it has the potential to outperform ALC reasoners (even though it stays ExpTime-hard in the worst case), and on the other hand, it has already helped in answering open problems about non-standard inferences for FL0, like existence and computation of least common subsumer and most specific concept, and the exact data complexity of query answering.
In this talk, we will describe the approach of functional models, and demonstrate how it has been used to show that answering instance queries for FL0 is tractable regarding data complexity.
