Query Inseparability by Games
Authors: Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter and Michael Zakharyaschev
Paper Information
| Title: | Query Inseparability by Games |
| Authors: | Elena Botoeva, Roman Kontchakov, Vladislav Ryzhikov, Frank Wolter and Michael Zakharyaschev |
| Proceedings: | DL 2014 Proceedings |
| Editors: | Meghyn Bienvenu, Riccardo Rosati, Magdalena Ortiz and Mantas Simkus |
| Keywords: | query answering, computational complexity, ontology modularity |
| Abstract: | ABSTRACT. We investigate conjunctive query inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query entailment of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to EXPTIME and 2EXPTIME. |
| Pages: | 13 |
| Talk: | Jul 19 14:30 |
| Paper: |  |