Inverse Roles Make Conjunctive Queries Hard

C. LutzC. Lutz

Download

C. 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},
}