Back to Search
Start Over
Efficient TBox Reasoning with Value Restrictions using the ${\cal F}{{\cal L}_0}$ wer Reasoner.
- Source :
- Theory & Practice of Logic Programming; Mar2022, Vol. 22 Issue 2, p162-192, 31p
- Publication Year :
- 2022
-
Abstract
- The inexpressive Description Logic (DL) ${\cal F}{{\cal L}_0}$ , which has conjunction and value restriction as its only concept constructors, had fallen into disrepute when it turned out that reasoning in ${\cal F}{{\cal L}_0}$ w.r.t. general TBoxes is ExpTime-complete, that is, as hard as in the considerably more expressive logic ${\cal A}{\cal L}{\cal C}$. In this paper, we rehabilitate ${\cal F}{{\cal L}_0}$ by presenting a dedicated subsumption algorithm for ${\cal F}{{\cal L}_0}$ , 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 ${\cal F}{{\cal L}_0}$ wer reasoner, compares very well with that of the highly optimized reasoners. ${\cal F}{{\cal L}_0}$ wer can also deal with ontologies written in the extension ${\cal F}{{\cal L}_ \bot }$ of ${\cal F}{{\cal L}_0}$ 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 ${\cal F}{{\cal L}_0}$ and ${\cal F}{{\cal L}_ \bot }$. [ABSTRACT FROM AUTHOR]
- Subjects :
- DESCRIPTION logics
LOGIC
ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 14710684
- Volume :
- 22
- Issue :
- 2
- Database :
- Complementary Index
- Journal :
- Theory & Practice of Logic Programming
- Publication Type :
- Academic Journal
- Accession number :
- 158785636
- Full Text :
- https://doi.org/10.1017/S1471068421000466