Complexity of Subsumption in the EL Family of Description Logics: Acyclic and Cyclic TBoxes
Christoph Haase and Carsten Lutz
Abstract
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.
Details
| Book Title |
Proceedings of the 18th European Conference on Artificial Intelligence (ECAI'08) |
| Editor |
Malik Ghallab and Constantine D. Spyropoulos and Nikos Fakotakis and Nikos Avouris |
| Location |
Patras‚ Greece |
| Month |
July |
| Pages |
25–29 |
| Publisher |
IOS Press |
| Series |
Frontiers in Artificial Intelligence and Applications |
| Volume |
178 |
| Year |
2008 |
Links
Related pages
|
People |