Temporalized EL ontologies for accessing temporal data: complexity of atomic queries

Gutierrez Basulto, Victor ORCID: https://orcid.org/0000-0002-6117-5459, Jung, Jean Christoph and Kontchakov, Roman 2016. Temporalized EL ontologies for accessing temporal data: complexity of atomic queries. Presented at: Twenty-Fifth International Joint Conference on Artificial Intelligence, New York, NY, USA, 9-15 July 2016. Published in: Brewka, Gerhard ed. IJCAI'16: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. AAAI Press, pp. 1102-1108.

Full text not available from this repository.

Abstract

We study access to temporal data with TEL, a temporal extension of the tractable description logic EL. Our aim is to establish a clear computational complexity landscape for the atomic query answering problem, in terms of both data and combined complexity. Atomic queries in full TEL turn out to be undecidable even in data complexity. Motivated by the negative result, we identify well-behaved yet expressive fragments of TEL. Our main contributions are a semantic and sufficient syntactic conditions for decidability and three orthogonal tractable fragments, which are based on restricted use of rigid roles, temporal operators, and novel acyclicity conditions on the ontologies.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Publisher:	AAAI Press
ISBN:	9781577357704
Date of First Compliant Deposit:	4 June 2018
Last Modified:	23 Oct 2022 13:51
URI:	https://orca.cardiff.ac.uk/id/eprint/111927

Citation Data

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

Actions (repository staff only)

Edit Item