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

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

Vladislav Ryzhikov, Przemyslaw Andrzej Walega, Michael Zakharyaschev

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1851-1857. https://doi.org/10.24963/ijcai.2019/256

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.
Keywords:
Knowledge Representation and Reasoning: Geometric, Spatial, and Temporal Reasoning
Knowledge Representation and Reasoning: Description Logics and Ontologies
Knowledge Representation and Reasoning: Computational Complexity of Reasoning