Data Complexity in the EL family of DLs

A. KrisnadhiA. Krisnadhi, Carsten LutzCarsten Lutz

Download

A. Krisnadhi, Carsten Lutz
Data Complexity in the EL family of DLs
Proceedings of the 2007 International Workshop on Description Logics (DL2007), CEUR-WS, to appear

Details
Bibtex

KurzfassungAbstract
We study the data complexity of instance checking and conjunctive query answering in the EL family of DLs, 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, instance checking in EL extended with only inverse roles or global functionality is ExpTime-complete regarding combined complexity.
Bemerkung: Note: To appear.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Krisnadhi-Lutz-DL-07,
  author = {A. {Krisnadhi} and C. {Lutz}},
  booktitle = {Proceedings of the 2007 International Workshop on Description Logics ({DL2007})},
  note = {To appear.},
  series = {CEUR-WS},
  title = {Data Complexity in the $\mathcal{EL}$ family of DLs},
  year = {2007},
}