License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2021.10
URN: urn:nbn:de:0030-drops-147867
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14786/
Go to the corresponding LIPIcs Volume Portal

Ryzhikov, Vladislav ; Savateev, Yury ; Zakharyaschev, Michael

Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic

pdf-format:
LIPIcs-TIME-2021-10.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ryzhikov_et_al:LIPIcs.TIME.2021.10,
  author =	{Ryzhikov, Vladislav and Savateev, Yury and Zakharyaschev, Michael},
  title =	{{Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic}},
  booktitle =	{28th International Symposium on Temporal Representation and Reasoning (TIME 2021)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-206-8},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{206},
  editor =	{Combi, Carlo and Eder, Johann and Reynolds, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14786},
  URN =		{urn:nbn:de:0030-drops-147867},
  doi =		{10.4230/LIPIcs.TIME.2021.10},
  annote =	{Keywords: Linear temporal logic, ontology-mediated query, first-order rewritability}
}

Keywords: Linear temporal logic, ontology-mediated query, first-order rewritability
Collection: 28th International Symposium on Temporal Representation and Reasoning (TIME 2021)
Issue Date: 2021
Date of publication: 16.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI