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