Efficient TBox Reasoning with Value Restrictions using the FLower reasoner

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, i.e., 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 FLbot 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 FLbot.