Skip to main content

Status QIO: An Update

Birte Glimm‚ Yevgeny Kazakov and Carsten Lutz

Abstract

We prove that conjunctive query answering in the description logic ALCOIF is co-N2ExpTime-hard, thus improving the previously known 2ExpTime lower bound. The result transfers to OWL DL and OWL2 DL, of which ALCOIF is an important fragment. A matching upper bound remains open.

Book Title
Description Logics
Editor
Riccardo Rosati and Sebastian Rudolph and Michael Zakharyaschev
Publisher
CEUR−WS.org
Series
CEUR Workshop Proceedings
Volume
745
Year
2011