Efficient TBox Reasoning with Value Restrictions using the ℱℒ0wer Reasoner

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

Abstract

The inexpressive Description Logic (DL) FL0, which has conjunction and value restriction as its only concept constructors, had fallen into disrepute when it turned out that reasoning in FL0 w.r.t. general TBoxes is ExpTime-complete, that is, as hard as in the considerably more expressive logic ALC. In this paper, we rehabilitate FL0 by presenting a dedicated subsumption algorithm for FL0, which is much simpler than the tableau-based algorithms employed by highly optimized DL reasoners. Our experiments show that the performance of our novel algorithm, as prototypically implemented in our FLower reasoner, compares very well with that of the highly optimized reasoners. FLower can also deal with ontologies written in the extension FL⊥ of FL0 with the top and the bottom concept by employing a polynomial-time reduction, shown in this paper, which eliminates top and bottom. We also investigate the complexity of reasoning in DLs related to the Horn-fragments of FL0 and FL⊥.

Details

OriginalspracheEnglisch
Seiten (von - bis)162-192
Seitenumfang31
FachzeitschriftTheory and Practice of Logic Programming
Jahrgang22
Ausgabenummer2
PublikationsstatusVeröffentlicht - 2022
Peer-Review-StatusJa

Schlagworte

DFG-Fachsystematik nach Fachkollegium

Fächergruppen, Lehr- und Forschungsbereiche, Fachgebiete nach Destatis

Bibliotheksschlagworte