An Automata Based Approach for Subsumption w.r.t. General Concept Inclusions in the Description Logic FL0

Datum

17.12.2015

Zeit

15:00 - 16:00

Sprecher

Maximilian Pensel

Sprache

en

Hauptthema

Informatik

Andere Themen

Informatik

Beschreibung

In description logic (DL) based knowledge representation and reasoning systems it is always important to weigh expressivity against computational tractability. Sometimes theoretical investigations towards the complexity of reasoning are only weak indicators for realistic algorithmic performances. For an example, special purpose algorithms for reasoning in certain exponential extensions of the otherwise polynomial lightweight DL EL have been shown to behave very well in practice. For the DL FL0, deciding subsumption w.r.t. general concept inclusions is known to be EXPTIME-complete, just like in the considerably more expressive DL ALC. We take on the task of deciding subsumption in FL0 with general concept inclusions by a special purpose algorithm, as an alternative to the employment of non-deterministic tableaux algorithms for ALC. Motivated by the realistic performance results for reasoning with exponential EL extensions, we claim that this algorithm may yield a similar computational behaviour. Due to the characteristics of FL0, we are able to consider an automata-based approach to devise such a practical subsumption algorithm. As a side result, we are able to show a correlation between subsumption in FL0 with general TBoxes and FLreg, an extension of FL0 with several role constructors. Subsequent to our work it remains to implement the algorithm and evaluate its performance within realistic test scenarios. Advisor: Prof. Baader

Letztmalig verändert: 17.12.2015, 08:58:09