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

May 30, 2019 · The Ethereal · 🏛 International Joint Conference on Artificial Intelligence

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Vladislav Ryzhikov, Przemyslaw Andrzej Walega, Michael Zakharyaschev arXiv ID 1905.12990 Category cs.LO: Logic in CS Cross-listed cs.AI, cs.CC Citations 30 Venue International Joint Conference on Artificial Intelligence Last Checked 1 month ago

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.