Data Complexity in the EL family of Description Logics

Adila KrisnadhiAdila Krisnadhi, Carsten LutzCarsten Lutz

Download

Adila Krisnadhi, Carsten Lutz
Data Complexity in the EL family of Description Logics
In Nachum Dershowitz and Andrei Voronkov, eds., Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR2007), volume 4790 of Lecture Notes in Artificial Intelligence, 333-347, 2007. Springer

Details
Bibtex

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

The final publication is available at Springer.

@inproceedings{ Krisnadhi-Lutz-LPAR-07,
  author = {Adila {Krisnadhi} and Carsten {Lutz}},
  booktitle = {Proceedings of the 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning ({LPAR2007})},
  editor = {Nachum {Dershowitz} and Andrei {Voronkov}},
  pages = {333--347},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Data Complexity in the $\mathcal{EL}$ family of Description Logics},
  volume = {4790},
  year = {2007},
}