2021/07/27 by Franz Baader, Baader, Franz, Patrick Koopmann +7
Computer Science · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Semantic Web and Ontologies #Service-Oriented Architecture and Web Services
paper · pdf · doi:10.48550/arxiv.2107.12877
openalex publication_date 2021/07/27 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The inexpressive Description Logic (DL) \FL0, which has\nconjunction and value restriction as its only concept constructors, had fallen\ninto disrepute when it turned out that reasoning in \FL0 w.r.t.\ngeneral TBoxes is ExpTime-complete, i.e., as hard as in the considerably more\nexpressive logic \ALC. In this paper, we rehabilitate\n\FL0 by presenting a dedicated subsumption algorithm for\n\FL0, which is much simpler than the tableau-based algorithms\nemployed by highly optimized DL reasoners. Our experiments show that the\nperformance of our novel algorithm, as prototypically implemented in our\n\FLower reasoner, compares very well with that of the highly\noptimized reasoners. \FLower can also deal with ontologies written\nin the extension \FL bot of \FL0 with the top and the\nbottom concept by employing a polynomial-time reduction, shown in this paper,\nwhich eliminates top and bottom. We also investigate the complexity of\nreasoning in DLs related to the Horn-fragments of \FL0 and\n\FL bot.\n