First-order rewritability of ontology-mediated queries in linear temporal logic
Alessandro Artale, Roman Kontchakov, Alisa Kovtunova, Vladislav Ryzhikov, Frank Wolter, Michael Zakharyaschev · Artificial Intelligence · 2021
We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time ( Z , 1 , or FO ( RPR ) , which extends FO ( < ) with relational primitive recursion. In terms of circuit complexity, FO ( < , ≡ ) - and FO ( RPR ) -rewritability guarantee OMQ answering in uniform and, respectively, . 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.