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.
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:	05 Nov 2024 12:56 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/91268 (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:

Depositors only (login required):

Download Statistics

Total unique views for this document in KAR since July 2020. For more details click on the image.