Status QIO: An Update
Birte Glimm · 2011
We prove co-N2ExpTime-hardness for conjunctive query entailment in the description logic ALCOIF, 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.