Botoeva, Elena, Kontchakov, Roman, Ryzhikov, Vladislav, Wolter, Frank, Zakharyaschev, Michael (2014) Query Inseparability by Games. In: CEUR Workshop Proceedings. Informal Proceedings of the 27th International Workshop on Description Logics, Vienna, Austria, July 17-20, 2014. 1193. pp. 83-95. CEUR-WS.org (KAR id:91305)
|
PDF
Publisher pdf
Language: English 
This work is licensed under a Creative Commons Attribution 4.0 International License.
|
|
|
Download this file (PDF/389kB) |
Preview |
| Request a format suitable for use with assistive technology e.g. a screenreader | |
| Official URL: http://ceur-ws.org/Vol-1193/paper_86.pdf |
|
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 inseparability of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to EXPTIME and 2EXPTIME. We also employ our results to resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both EXPTIME complete for combined complexity
| Item Type: | Conference or workshop item (Proceeding) |
|---|---|
| Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, |
| Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
| Depositing User: | Amy Boaler |
| Date Deposited: | 03 Nov 2021 14:50 UTC |
| Last Modified: | 05 Nov 2024 12:57 UTC |
| Resource URI: | https://kar.kent.ac.uk/id/eprint/91305 (The current URI for this page, for reference purposes) |
University of Kent Author Information
Botoeva, Elena.
| Creator's ORCID: |
 https://orcid.org/0000-0001-5881-0258
|
|---|---|
| CReDIT Contributor Roles: |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):
Download Statistics
Download Statistics
