Skip to main content

Query-Based Entailment and Inseparability for ALC Ontologies

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. (Contact us about this Publication)
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: 03 Nov 2021 11:17 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/91268 (The current URI for this page, for reference purposes)
  • Depositors only (login required):