Temporalized EL Ontologies for Accessing Temporal Data: Complexity of Atomic Queries
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1102-1107.
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.
@inproceedings{ijcai2016p160,
title = {Temporalized EL Ontologies for Accessing Temporal Data: Complexity of Atomic Queries},
author = {Gutiérrez-Basulto, Víctor and Jung, Jean Christoph and Kontchakov, Roman},
booktitle = {Proceedings of the Twenty-Fifth International Joint Conference on
Artificial Intelligence, {IJCAI-16}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Subbarao Kambhampati},
pages = {1102--1107},
year = {2016},
month = {7},
url = {https://ijcai.org/proceedings/2016/160},
}
TY - CPAPER TI - Temporalized EL Ontologies for Accessing Temporal Data: Complexity of Atomic Queries AU - Gutiérrez-Basulto, Víctor AU - Jung, Jean Christoph AU - Kontchakov, Roman T2 - Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2016 SP - 1102 EP - 1107 UR - https://ijcai.org/proceedings/2016/160 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
