Data complexity in the \(\mathcal{EL}\) family of description logics. (English) Zbl 1137.68593
Dershowitz, Nachum (ed.) et al., Logic for programming, artificial intelligence, and reasoning. 14th international conference, LPAR 2007, Yerevan, Armenia, October 15–19, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-75558-6/pbk). Lecture Notes in Computer Science 4790. Lecture Notes in Artificial Intelligence, 333-347 (2007).
Summary: We study the data complexity of instance checking and conjunctive query answering in the \(\mathcal{EL}\) family of description logics, with a particular emphasis on the boundary of tractability. We identify a large number of intractable extensions of \(\mathcal{EL}\), but also show that in \(\mathcal{ELI}^f\), the extension of \(\mathcal{EL}\) with inverse roles and global functionality, conjunctive query answering is tractable regarding data complexity. In contrast, already instance checking in \(\mathcal{EL}\) extended with only inverse roles or global functionality is ExpTime-complete regarding combined complexity.
For the entire collection see [Zbl 1136.68004].
For the entire collection see [Zbl 1136.68004].
