First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic

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(<,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.