Complexity of Subsumption in the ℰℒ Family of Description Logics: Acyclic and Cyclic TBoxes
Christoph Haase, Carsten Lutz · Frontiers in artificial intelligence and applications · 2008
We perform an exhaustive study of the complexity of subsumption in the ℰℒ family of lightweight description logics w.r.t. acyclic and cyclic TBoxes. It turns out that there are interesting members of this family for which subsumption w.r.t. cyclic TBoxes is tractable, whereas it is EXPTIME-complete w.r.t. general TBoxes. For other extensions that are intractable w.r.t. general TBoxes, we establish intractability already for acyclic and cyclic TBoxes.