2026-07-24T03:28:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14786 2024-03-06T10:54:38Z ddc:004 open_access

Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic Ryzhikov, Vladislav Savateev, Yury Zakharyaschev, Michael Linear temporal logic ontology-mediated query first-order rewritability Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) given in linear temporal logic LTL over (ℤ, <) and deciding whether it is rewritable to an FO(<)-query, possibly with extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC⁰, ACC⁰ and NC¹ coincides with FO(<,≡)-rewritability using unary predicates x ≡ 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We then show that deciding FO(<)-, FO(<,≡)- 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(<,≡)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSpace-, Π₂^p- and coNP-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vladislav Ryzhikov and Yury Savateev and Michael Zakharyaschev 2021 Is Part Of LIPIcs, Volume 206, 28th International Symposium on Temporal Representation and Reasoning (TIME 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2021.10 urn:nbn:de:0030-drops-147867 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2021.10 eng https://creativecommons.org/licenses/by/4.0/legalcode