Complexity of Subsumption in the EL Family of Description Logics: Acyclic and Cyclic TBoxes
- We perform an exhaustive study of the complexity of subsumption in the EL 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.
- IOS Press
- Publication date:
- Local pid:
- Copyright date:
Views and Downloads
If you are the owner of this record, you can report an update to it here: Report update to this record