Inverse Roles Make Conjunctive Queries Hard

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche

Toggle side column

Inverse Roles Make Conjunctive Queries Hard

Carsten LutzCarsten Lutz
Carsten Lutz
Inverse Roles Make Conjunctive Queries Hard
Proceedings of the 2007 International Workshop on Description Logics (DL2007), CEUR-WS, to appear
  • 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},
}