Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)
This work addresses complexity and rewritability issues for ontology-mediated queries in temporal logic, which is incremental as it builds on existing semantics and data assumptions.
The paper investigates the data complexity of answering queries mediated by metric temporal logic ontologies under event-based semantics, identifying classes of queries that can be answered in complexity classes ranging from AC0 to coNP and providing rewritings to first-order logic and its extensions.
We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes of ontology-mediated queries answering which can be done in AC0, NC1, L, NL, P, and coNP for data complexity, provide their rewritings to first-order logic and its extensions with primitive recursion, transitive closure or datalog, and establish lower complexity bounds.