Conference item icon

Conference item

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

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.

Actions


Access Document


Files:
Publisher copy:
10.3233/978-1-58603-891-5-25

Authors


Christoph Haase More by this author
Carsten Lutz More by this author

Contributors

Role:
Editor
Role:
Editor
Role:
Editor
Publisher:
IOS Press
Volume:
178
Publication date:
2008-07-01
DOI:
URN:
uuid:bd879a90-27bf-4e44-b1cc-216a9155bdf7
Local pid:
cs:59

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP