The Complexity of Conjunctive Query Answering in Expressive Description Logics

From International Center for Computational Logic

Toggle side column

The Complexity of Conjunctive Query Answering in Expressive Description Logics

Carsten LutzCarsten Lutz
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
  • 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},
}