Inverse Roles Make Conjunctive Queries Hard

Carsten LutzCarsten Lutz

Download

Carsten Lutz
Inverse Roles Make Conjunctive Queries Hard
Proceedings of the 2007 International Workshop on Description Logics (DL2007), CEUR-WS, to appear

Details
Bibtex

KurzfassungAbstract
Conjunctive query answering is an important DL reasoning task. Although this task is by now quite well-understood, tight complexity bounds for conjunctive query answering in expressive DLs have never been obtained: all known algorithms run in deterministic double exponential time, but the existing lower bound is only an ExpTime one. In this paper, we prove that conjunctive query answering in ALCI is 2-ExpTime-hard (and thus complete), and that it becomes NExpTime-complete under some reasonable assumptions.
Bemerkung: Note: To appear.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Lutz-DL-07,
  author = {C. {Lutz}},
  booktitle = {Proceedings of the 2007 International Workshop on Description Logics ({DL2007})},
  note = {To appear.},
  series = {CEUR-WS},
  title = {Inverse Roles Make Conjunctive Queries Hard},
  year = {2007},
}