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

DOI10.1613/jair.1.14061arXiv2207.06210OpenAlexW4324130885MaRDI QIDQ6135954

Agi Kurucz, Michael Zakharyashchev, Vladislav Ryzhikov, Yury Savateev

Publication date: 28 August 2023

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

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

zbMATH Keywords

temporal reasoningdescription logicsontologiessemantic web

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Datalog rewritability of disjunctive Datalog programs and non-Horn ontologies
• Towards more expressive ontology languages: the query answering problem
• Boolean function complexity. Advances and frontiers.
• On rules with existential variables: walking the decidability line
• Explicit bounds for primes in arithmetic progressions
• Real-time logics: Complexity and expressiveness
• Elements of finite model theory.
• Finite-automaton aperiodicity is PSPACE-complete
• Parallel complexity of logical query programs
• A note on the reduction of two-way automata to one-way automata
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages in \(NC\)
• Many-dimensional modal logics: theory and applications
• A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\)
• A tetrachotomy of ontology-mediated queries with a covering axiom
• First-order rewritability of ontology-mediated queries in linear temporal logic
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• Temporal Logics in Computer Science
• The Complexity of Clausal Fragments of LTL
• Undecidable boundedness problems for datalog programs
• The intersection problem for finite monoids
• Parity, circuits, and the polynomial-time hierarchy
• Some Recent Results in Metric Temporal Logic
• The DL-Lite Family and Relations
• Complexity of some problems from the theory of automata
• Finite monoids and the fine structure of NC ¹
• Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
• The parallel complexity of simple logic programs
• The membership problem in aperiodic transformation monoids
• PREDICATE BOUNDEDNESS OF LINEAR MONADIC DATALOG IS IN PSPACE
• Querying Log Data with Metric Temporal Logic
• Ontology-Mediated Queries
• The Complexity of Boundedness for Guarded Logics
• SOLVABILITY OF FINITE GROUPS VIA CONDITIONS ON PRODUCTS OF 2-ELEMENTS AND ODD p-ELEMENTS
• Ontology-Based Data Access
• Computational Complexity
• On finite monoids having only trivial subgroups
• A Proof of Kamp's theorem
• Linking Data to Ontologies
• Nonsolvable finite groups all of whose local subgroups are solvable
• Clausal temporal resolution
• 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