LATPub384

PublikationenPublications

• Nach AutorBy Author
  • Carsten LutzCarsten Lutz
• Nach ForschungsgruppeBy Research Group
  • AutomatentheorieAutomata Theory

Toggle side column

Two Upper Bounds for Conjunctive Query Answering in SHIQ

Carsten LutzCarsten Lutz

• Download

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

• Details
• Bibtex

• 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},
}