Stratified Negation in Datalog with Metric Temporal Operators

Authors

  • David J Tena Cucala University of Oxford
  • Przemysław A Wałęga University of Oxford
  • Bernardo Cuenca Grau University of Oxford
  • Egor Kostylev University of Oslo

DOI:

https://doi.org/10.1609/aaai.v35i7.16804

Keywords:

Geometric, Spatial, and Temporal Reasoning

Abstract

We extend DatalogMTL—Datalog with operators from metric temporal logic—by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rational timeline, study their properties, and establish the computational complexity of reasoning. We show that, as in negation-free DatalogMTL, fact entailment in our language is PSPACE-complete in data and EXPSPACE-complete in combined complexity. Thus, the extension with stratified negation does not lead to higher complexity.
AAAI-21 Proceedings Cover

Downloads

Published

2021-05-18

How to Cite

Tena Cucala, D. J., Wałęga, P. A., Cuenca Grau, B., & Kostylev, E. (2021). Stratified Negation in Datalog with Metric Temporal Operators. Proceedings of the AAAI Conference on Artificial Intelligence, 35(7), 6488-6495. https://doi.org/10.1609/aaai.v35i7.16804

Issue

Vol. 35 No. 7: AAAI-21 Technical Tracks 7

Section

AAAI Technical Track on Knowledge Representation and Reasoning