Botoeva, Elena, Lutz, Carsten, Ryzhikov, Vladislav, Wolter, Frank, Zakharyaschev, Michael (2016) Query-Based Entailment and Inseparability for ALC Ontologies. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016. . pp. 1001-1007. IJCAI/AAAI Press ISBN 978-1-57735-770-4. E-ISBN 978-1-57735-771-1. (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:91268)
| The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided. | |
| Official URL: http://www.ijcai.org/Abstract/16/146 |
Abstract
We investigate the problem whether two ALC knowledge bases are indistinguishable by queries over a given vocabulary. We give model-theoretic criteria and prove that this problem is undecidable for conjunctive queries (CQs) but decidable in 2EXPTIME for unions of rooted CQs. We also consider the problem whether two ALC TBoxes give the same answers to any query in a given vocabulary over all ABoxes, and show that for CQs this problem is undecidable, too, but becomes decidable and 2EXPTIME-complete in Horn-ALC, and even EXPTIME-complete in Horn-ALC when restricted to (unions of) rooted CQs.
| Item Type: | Conference or workshop item (Paper) |
|---|---|
| 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: | 02 Nov 2021 14:19 UTC |
| Last Modified: | 17 Aug 2022 12:22 UTC |
| Resource URI: | https://kar.kent.ac.uk/id/eprint/91268 (The current URI for this page, for reference purposes) |
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):
Download Statistics
Download Statistics
