Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

On decidability and tractability of querying in temporal EL

Gutierrez Basulto, Victor, Jung, Jean Christoph and Kontchakov, Roman 2016. On decidability and tractability of querying in temporal EL. Presented at: 29th International Workshop on Description Logics, Cape Town, South Africa, 22-25 April 2016.

[img]
Preview
PDF - Accepted Post-Print Version
Download (339kB) | Preview

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: Completion
Status: Unpublished
Schools: Computer Science & Informatics
Date of First Compliant Deposit: 4 June 2018
Last Modified: 16 Aug 2018 16:21
URI: http://orca.cf.ac.uk/id/eprint/111940

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics