Artale, Alessandro, Kontchakov, Roman, Kovtunova, Alisa, Ryzhikov, Vladislav, Wolter, Frank and Zakharyaschev, Michael
(2021)
First-Order Rewritability of Ontology-Mediated Queries in Linear
Temporal Logic.
Artificial Intelligence, 299.
p. 103536.
Text
LTL-main.pdf - Author Accepted Manuscript Download (373kB) | Preview |
Abstract
We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time (Z,<). Queries are given in LTL or MFO(<), monadic first-order logic with a built-in linear order. Our concern is first-order rewritability of ontology-mediated queries (OMQs) consisting of a temporal ontology and a query. By taking account of the temporal operators used in the ontology and distinguishing between ontologies given in full LTL and its core, Krom and Horn fragments, we identify a hierarchy of OMQs with atomic queries by proving rewritability into either FO(<), first-order logic with the built-in linear order, or FO(<,E), which extends FO(<) with the standard arithmetic predicates saying that "x is equivalent to 0 modulo n", for any fixed n > 1, or FO(RPR), which extends FO(<) with relational primitive recursion. In terms of circuit complexity, FO(<,E)- and FO(RPR)-rewritability guarantee OMQ answering in uniform AC0 and, respectively, NC1. We obtain similar hierarchies for more expressive types of queries: positive LTL-formulas, monotone MFO(<)- and arbitrary MFO(<)-formulas. Our results are directly applicable if the temporal data to be accessed is one-dimensional; moreover, they lay foundations for investigating ontology-based access using combinations of temporal and description logics over two-dimensional temporal data.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | cs.LO, cs.LO |
Divisions: | Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science |
Depositing User: | Symplectic Admin |
Date Deposited: | 10 Jun 2021 07:25 |
Last Modified: | 18 Jan 2023 22:35 |
DOI: | 10.1016/j.artint.2021.103536 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3125817 |