Beschreibungslogiken mit existentiellen Quantoren und polynominellen Subsumtionsproblem und ihre Anwendung im Bereich biomedizinischer Ontologien

• Applicant: Professor Dr.-Ing. Franz Baader
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 24881586

Beschreibungslogiken, die Werterestriktionen (universelle Quantoren) zulassen, sind inzwischen wohl-untersucht. Insbesondere wurden hier sehr ausdrucksstarke Logiken entwickelt, für die es trotz ihrer hohen worst-case Komplexität praktikable Algorithmen gibt, deren hoch-optimierte Implementierungen sich in Anwendungen sehr gut verhalten. Es hat sich aber herausgestellt, dass in Ontologieanwendungen, insbesondere im biomedizinischen Bereich, ausdrucksschwache Logiken mit existentiellen Quantoren, aber ohne Werterestriktionen, ausreichen. Derartige Beschreibungslogiken verhalten sich aus komplexitätstheoretischer Sicht viel besser als die entsprechenden Logiken mit Werterestriktionen. Insbesondere ermöglichen sie auch bei Anwesenheit von Terminologien und allgemeinen Konzeptinklusionsaxiomen noch polynomielle Subsumtionsalgorithmen. In diesem Projekt sollen Beschreibungslogiken mit existentiellen Quantoren sowohl aus theoretischer als auch aus praktischer Sicht genauer untersucht werden. Dies beinhaltet zum einen die genaue Erforschung der Grenze zwischen Logiken mit polynomiellem und nicht-polynomiellem Subsumtionsproblem. Zum anderen sollen Optimierungsansätze für die polynomiellen Subsumtionsalgorithmen entwickelt und an großen biomedizinischen Ontologien evaluiert werden. Außerdem wollen wir auch andere Schlussfolgerungsprobleme (wie das Instanz- und das Anfrageproblem) untersuchen sowie Beschreibungslogiken mit existentiellen Quantoren lokalisieren, die zwar nicht mehr polynomiell sind, aber doch Algorithmen zulassen, die sich besser verhalten als die bekannten Algorithmen für ausdrucksstarke Logiken

• DFG Programme: Research Grants
• Participating Person: Professor Dr. Carsten Lutz