Data Complexity in the EL Family of Description Logics

TitleData Complexity in the EL Family of Description Logics
Publication TypeConference Papers
Year of Publication2007
AuthorsKrisnadhi, A, Lutz, C
EditorDershowitz, N, Voronkov, A
Conference NameLogic for Programming, Artificial Intelligence, and Reasoning, 14th International Conference, LPAR 2007, Yerevan, Armenia, October 15-19, 2007, Proceedings
Volume4790
Pagination333-347
Date Published10/2007
PublisherSpringer
Abstract

We study the data complexity of instance checking and conjunctive query answering in the EL family of description logics, with a particular emphasis on the boundary of tractability. We identify a large number of intractable extensions of EL, but also show that in ELIf , the extension of EL with inverse roles and global functionality, conjunctive query answering is tractable regarding data complexity. In contrast, already instance checking in EL extended with only inverse roles or global functionality is EXPTIME-complete regarding combined complexity

URLhttp://dx.doi.org/10.1007/978-3-540-75560-9_25
DOI10.1007/978-3-540-75560-9_25
Refereed DesignationRefereed