Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

DOI10.1613/JAIR.1.14061arXiv2207.06210OpenAlexW4324130885WikidataQ130836285 ScholiaQ130836285MaRDI QIDQ6135954FDOQ6135954

Authors: Agi Kurucz, Vladislav Ryzhikov, Yury Savateev, Michael Zakharyaschev 

Publication date: 28 August 2023

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/2207.06210

Recommendations

• First-order rewritability of ontology-mediated queries in linear temporal logic
• First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• Ontology-mediated query answering over temporal data: a survey (invited talk)
• Temporal Ontology-Mediated Queries and First-Order Rewritability: A Short Course

zbMATH Keywords

temporal reasoningdescription logicsontologiessemantic web

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• The DL-Lite Family and Relations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computational Complexity
• Linking Data to Ontologies
• Title not available (Why is that?)
• Many-dimensional modal logics: theory and applications
• Some Recent Results in Metric Temporal Logic
• Complexity of some problems from the theory of automata
• Title not available (Why is that?)
• A Proof of Kamp's theorem
• Nonsolvable finite groups all of whose local subgroups are solvable
• Clausal temporal resolution
• Real-time logics: Complexity and expressiveness
• Elements of finite model theory.
• Handbook of modal logic
• Boolean function complexity. Advances and frontiers.
• Parallel complexity of logical query programs
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• Title not available (Why is that?)
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Parity, circuits, and the polynomial-time hierarchy
• On finite monoids having only trivial subgroups
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Regular languages in \(NC\)
• On rules with existential variables: walking the decidability line
• Finite-automaton aperiodicity is PSPACE-complete
• Finite monoids and the fine structure of NC ¹
• The membership problem in aperiodic transformation monoids
• Towards more expressive ontology languages: the query answering problem
• A note on the reduction of two-way automata to one-way automata
• Solvability of finite groups via conditions on products of 2-elements and odd \(p\)-elements.
• The subgroup structure of finite classical groups in terms of geometric configurations.
• Explicit bounds for primes in arithmetic progressions
• Undecidable boundedness problems for datalog programs
• The parallel complexity of simple logic programs
• Temporal logics in computer science. Finite-state systems
• Title not available (Why is that?)
• The intersection problem for finite monoids
• The complexity of boundedness for guarded logics
• The complexity of clausal fragments of LTL
• Querying log data with metric temporal logic
• Aperiodic two-way transducers and FO-transductions
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• Rewritability in monadic disjunctive Datalog, MMSNP, and expressive description logics
• A tetrachotomy of ontology-mediated queries with a covering axiom
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity
• First-order rewritability of ontology-mediated queries in linear temporal logic
• First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries

Cited In (1)

• First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries

This page was built for publication: Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135954)