The Complexity of Conjunctive Query Answering in Expressive Description Logics

Carsten LutzCarsten Lutz

Download

Carsten Lutz
The Complexity of Conjunctive Query Answering in Expressive Description Logics
In Alessandro Armando and Peter Baumgartner and Gilles Dowek, eds., Proceedings of the 4th International Joint Conference on Automated Reasoning (IJCAR2008), LNAI, 179-193, 2008. Springer

Details
Bibtex

KurzfassungAbstract
Conjunctive query answering plays a prominent role in applications of description logics (DLs) that involve instance data, but its exact complexity was a long-standing open problem. We determine the complexity of conjunctive query answering in expressive DLs between ALC and SHIQ, and thus settle the problem. In a nutshell, we show that conjunctive query answering is 2ExpTime-complete in the presence of inverse roles, and only ExpTime-complete without them.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ Lutz-IJCAR08,
  author = {Carsten {Lutz}},
  booktitle = {Proceedings of the 4th International Joint Conference on Automated Reasoning ({IJCAR2008})},
  editor = {Alessandro {Armando} and Peter {Baumgartner} and Gilles {Dowek}},
  number = {5195},
  pages = {179--193},
  publisher = {Springer},
  series = {LNAI},
  title = {The Complexity of Conjunctive Query Answering in Expressive Description Logics},
  year = {2008},
}