%0 Conference Paper %1 35519e1321804e3f9db8f80c0930a87d %A Baader, Franz %A Koopmann, Patrick %A Michel, Friedrich %A Turhan, Anni-Yasmin %A Zarriess, Benjamin %B DL 2022 - Proceedings of the 35th International Workshop on Description Logics, co-located with Federated Logic Conference, FLoC 2022 %D 2022 %E Arieli, O. %E Homola, M. %E Jung, J.C. %E Mugnier, M.-L. %I CEUR-WS %K imported zno %T Efficient TBox Reasoning with Value Restrictions Using the ℱℒower Reasoner %V 3263 %X The inexpressive Description Logic (DL) ℱℒ0, which has conjunction and value restriction as its only concept constructors, had fallen into disrepute when it turned out that reasoning in ℱℒ0 w.r.t. general TBoxes is ExpTime-complete, that is, as hard as in the considerably more expressive logic AℒC. In the paper published in the journal Theory and Practice of Logic Programming, we rehabilitate ℱℒ0 by presenting a dedicated subsumption algorithm for ℱℒ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 ℱℒower reasoner, compares very well with that of the highly optimized reasoners. ℱℒower can also deal with ontologies written in ℱℒ⊥, the extension of ℱℒ0 with the top and the bottom concept, by employing a polynomial-time reduction, shown in this paper, which eliminates the top and bottom concepts. We also investigate the complexity of reasoning in DLs related to the Horn-fragments of ℱℒ0 and ℱℒ⊥

@inproceedings{35519e1321804e3f9db8f80c0930a87d, abstract = {The inexpressive Description Logic (DL) ℱℒ0, which has conjunction and value restriction as its only concept constructors, had fallen into disrepute when it turned out that reasoning in ℱℒ0 w.r.t. general TBoxes is ExpTime-complete, that is, as hard as in the considerably more expressive logic AℒC. In the paper published in the journal Theory and Practice of Logic Programming, we rehabilitate ℱℒ0 by presenting a dedicated subsumption algorithm for ℱℒ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 ℱℒower reasoner, compares very well with that of the highly optimized reasoners. ℱℒower can also deal with ontologies written in ℱℒ⊥, the extension of ℱℒ0 with the top and the bottom concept, by employing a polynomial-time reduction, shown in this paper, which eliminates the top and bottom concepts. We also investigate the complexity of reasoning in DLs related to the Horn-fragments of ℱℒ0 and ℱℒ⊥}, added-at = {2025-01-06T14:10:16.000+0100}, author = {Baader, Franz and Koopmann, Patrick and Michel, Friedrich and Turhan, Anni-Yasmin and Zarriess, Benjamin}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/20743466e0afda4004aa19dba04090ca4/scadsfct}, booktitle = {DL 2022 - Proceedings of the 35th International Workshop on Description Logics, co-located with Federated Logic Conference, FLoC 2022}, editor = {Arieli, O. and Homola, M. and Jung, J.C. and Mugnier, M.-L.}, interhash = {d3c16698bdaf1c6645dd3a777f78f5df}, intrahash = {0743466e0afda4004aa19dba04090ca4}, keywords = {imported zno}, language = {English}, note = {35th International Workshop on Description Logics, DL 2022 ; Conference date: 07-08-2022 Through 10-08-2022}, publisher = {CEUR-WS}, series = {CEUR Workshop Proceedings}, timestamp = {2025-02-05T15:04:39.000+0100}, title = {Efficient TBox Reasoning with Value Restrictions Using the ℱℒower Reasoner}, volume = 3263, year = 2022 }