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.
Details
| 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 |
Links
DOI (http://ceur-ws.org/Vol-745/paper_44.pdf)
Related pages
|
People |