Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics (Full Version)

2019/05/30 by Ryzhikov, Vladislav, Walega, Przemyslaw Andrzej, Zakharyaschev, Michael · 1 citation
#Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #I.2.4 #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1905.12990

Abstract

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.

Cited by

• Inconsistency Handling in DatalogMTL

Related

• Temporal Conjunctive Query Answering in the Extended DL-Lite Family
• 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 EL
• Temporal Minimal-World Semantics for Sparse ABoxes
• Ontology-Mediated Queries: Combined Complexity and Succinctness of\n Rewritings via Circuit Complexity