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

Research output: Contribution to journalResearch articleContributedpeer-review

Contributors

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

Original languageEnglish
Pages (from-to)162-192
Number of pages31
JournalTheory and Practice of Logic Programming
Volume22
Issue number2
Publication statusPublished - 2022
Peer-reviewedYes

Keywords

Research priority areas of TU Dresden

    DFG Classification of Subject Areas according to Review Boards

    Subject groups, research areas, subject areas according to Destatis

    Library keywords