Stratified Negation in Datalog with Metric Temporal Operators

David J. Tena Cucala, Przemyslaw Andrzej Walega, Bernardo Cuenca Grau, Egor V. Kostylev

AAAI 2021 pp. 6488-6495

doi:10.1609/AAAI.V35I7.16804 /aaai/2021/cucala2021aaai-stratified/

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.

PDF AAAI Semantic Scholar

Cite

Text

Cucala et al. "Stratified Negation in Datalog with Metric Temporal Operators." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I7.16804

Markdown

[Cucala et al. "Stratified Negation in Datalog with Metric Temporal Operators." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/cucala2021aaai-stratified/) doi:10.1609/AAAI.V35I7.16804

BibTeX

@inproceedings{cucala2021aaai-stratified,
  title     = {{Stratified Negation in Datalog with Metric Temporal Operators}},
  author    = {Cucala, David J. Tena and Walega, Przemyslaw Andrzej and Grau, Bernardo Cuenca and Kostylev, Egor V.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {6488-6495},
  doi       = {10.1609/AAAI.V35I7.16804},
  url       = {https://mlanthology.org/aaai/2021/cucala2021aaai-stratified/}
}