The inexpressive Description Logic (DL) FL_0, which has conjunction and value restriction asits only concept constructors, had fallen into disrepute when it turned out that reasoning inFL_0 w.r.t. general TBoxes is ExpTime-complete, that is, as hard as in the considerably moreexpressive logic ALC. In this paper, we rehabilitate FL_0 by presenting a dedicated subsumptionalgorithm for FL_0, which is much simpler than the tableau-based algorithms employed by highlyoptimized DL reasoners. Our experiments show that the performance of our novel algorithm, asprototypically implemented in our FLower reasoner, compares very well with that of the highlyoptimized reasoners. FLower can also deal with ontologies written in the extension FL_⊥ of FL_0with the top and the bottom concept by employing a polynomial-time reduction, shown in thispaper, which eliminates top and bottom. We also investigate the complexity of reasoning in DLsrelated to the Horn-fragments of FL_0 and FL_⊥.
展开▼
