Two Upper Bounds for Conjunctive Query Answering in SHIQ

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

Toggle side column

Two Upper Bounds for Conjunctive Query Answering in SHIQ

Carsten LutzCarsten Lutz
Carsten Lutz
Two Upper Bounds for Conjunctive Query Answering in SHIQ
Proceedings of the 21st International Workshop on Description Logics (DL2008), volume 353 of CEUR-WS, 2008
  • KurzfassungAbstract
    We have shown recently that, in extensions of ALC that involve
     inverse roles, conjunctive query answering is harder than
     satisfiability: it is 2-ExpTime-complete in general and
     NExpTime-hard if queries are connected and contain at least one
     answer variable. In this paper, we show that, in
     SHIQ without inverse roles (and without transitive roles in the
     query), conjunctive query answering is only ExpTime-complete and
     thus not harder than satisfiability. We also show that the
    
    mentioned NExpTime-lower bound is tight.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ Lutz-DL08,
  author = {Carsten {Lutz}},
  booktitle = {Proceedings of the 21st International Workshop on Description Logics ({DL2008})},
  series = {CEUR-WS},
  title = {Two Upper Bounds for Conjunctive Query Answering in SHIQ},
  volume = {353},
  year = {2008},
}