Finite query answering in expressive description logics with transitive roles

Gogacz, Tomasz, Ibanez Garcia, Yazmin ORCID: https://orcid.org/0000-0002-1276-904X and Murlak, Filip 2018. Finite query answering in expressive description logics with transitive roles. Presented at: 16th International Conference on the Principles of Knowledge Representation and Reasoning, Tempe, Arizona, USA, 27 October - 2 November 2018. Published in: Thielscher, Michael, Toni, Francesca and Wolter, Frank eds. Proceedings of the 16th International Conference on Principles of Knowledge Representation and Reasoning (KR 2018). Palo Alto, California: AAAI Press, pp. 369-378.

Preview

PDF - Accepted Post-Print Version Download (286kB) | Preview

Abstract

We study the problem of finite ontology mediated query an-swering (FOMQA), the variant of OMQA where the represented world is assumed to be finite, and thus only finite models of the ontology are considered. We adopt the most typical setting with unions of conjunctive queries and ontologies expressed in description logics (DLs). The study of FOMQA isrelevant in settings that are not finitely controllable. This is the case not only for DLs without the finite model property, but also for those allowing transitive role declarations. When transitive roles are allowed, evaluating queries is challenging: FOMQA is undecidable for SHOIF and only known to be decidable for the Horn fragment of ALCIF. We show decidability of FOMQA for three proper fragments of SOIF: SOI, SOF, and SIF. Our approach is to characterise models relevant for deciding finite query entailment. Relying on a certain regularity of these models, we develop automata-based decision procedures with optimal complexity bounds.

Item Type:	Conference or Workshop Item (Paper)
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	AAAI Press
ISBN:	9781577358039
Date of First Compliant Deposit:	1 April 2020
Date of Acceptance:	11 July 2018
Last Modified:	07 Nov 2022 09:57
URI:	https://orca.cardiff.ac.uk/id/eprint/130718

Citation Data

Cited 15 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item