Complexity of Subsumption in the EL Family of Description Logics: Acyclic and Cyclic TBoxes

Christoph HaaseChristoph Haase, Carsten LutzCarsten Lutz

Download

Christoph Haase, Carsten Lutz
Complexity of Subsumption in the EL Family of Description Logics: Acyclic and Cyclic TBoxes
In Malik Ghallab and Constantine D. Spyropoulos and Nikos Fakotakis and Nikos Avouris, eds., Proceedings of the 18th European Conference on Artificial Intelligence (ECAI08), volume 178 of Frontiers in Artificial Intelligence and Applications, 25-29, 2008. IOS Press

Details
Bibtex

KurzfassungAbstract
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.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Haase-Lutz-ECAI08,
  author = {Christoph {Haase} and Carsten {Lutz}},
  booktitle = {Proceedings of the 18th European Conference on Artificial Intelligence ({ECAI08})},
  editor = {Malik {Ghallab} and Constantine D. {Spyropoulos} and Nikos {Fakotakis} and Nikos {Avouris}},
  pages = {25--29},
  publisher = {IOS Press},
  series = {Frontiers in Artificial Intelligence and Applications},
  title = {Complexity of Subsumption in the EL Family of Description Logics: Acyclic and Cyclic TBoxes},
  volume = {178},
  year = {2008},
}