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

Vladislav Ryzhikov, Przemyslaw Andrzej Walega, Michael Zakharyaschev

IJCAI 2019 pp. 1851-1857

doi:10.24963/IJCAI.2019/256 /ijcai/2019/ryzhikov2019ijcai-data/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Ryzhikov et al. "Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic Under the Event-Based Semantics." International Joint Conference on Artificial Intelligence, 2019. doi:10.24963/IJCAI.2019/256

Markdown

[Ryzhikov et al. "Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic Under the Event-Based Semantics." International Joint Conference on Artificial Intelligence, 2019.](https://mlanthology.org/ijcai/2019/ryzhikov2019ijcai-data/) doi:10.24963/IJCAI.2019/256

BibTeX

@inproceedings{ryzhikov2019ijcai-data,
  title     = {{Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic Under the Event-Based Semantics}},
  author    = {Ryzhikov, Vladislav and Walega, Przemyslaw Andrzej and Zakharyaschev, Michael},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1851-1857},
  doi       = {10.24963/IJCAI.2019/256},
  url       = {https://mlanthology.org/ijcai/2019/ryzhikov2019ijcai-data/}
}