  Our concern is the problem of determining the data complexity of answering an
ontology-mediated query (OMQ) formulated in linear temporal logic LTL over
(Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with
some extra predicates. First, we observe that, in line with the circuit
complexity and FO-definability of regular languages, OMQ answering in AC^0,
ACC^0 and NC^1 coincides with FO(<,\equiv)-rewritability using unary predicates
x \equiv 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using
relational primitive recursion, respectively. We prove that, similarly to known
PSPACE-completeness of recognising FO(<)-definability of regular languages,
deciding FO(<,\equiv)- and FO(<,MOD)-definability is also \PSPACE-complete
(unless ACC^0 = NC^1). We then use this result to show that deciding FO(<)-,
FO(<,\equiv)- and FO(<,MOD)-rewritability of LTL OMQs is EXPSPACE-complete, and
that these problems become PSPACE-complete for OMQs with a linear Horn ontology
and an atomic query, and also a positive query in the cases of FO(<)- and
FO(<,\equiv)-rewritability. Further, we consider FO(<)-rewritability of OMQs
with a binary-clause ontology and identify OMQ classes, for which deciding it
is PSPACE-, Pi_2^p- and coNP-complete.
