DatalogMTL: Computational Complexity and Expressive Power
Authors: Przemysław A. Wałęga, Bernardo Cuenca Grau, Mark Kaminski, Egor V. Kostylev
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity and expressive power of Datalog MTL a knowledge representation language that extends Datalog with operators from metric temporal logic (MTL) and which has found applications in ontology-based data access and stream reasoning. We establish tight PSpace data complexity bounds and also show that Datalog MTL extended with negation on input predicates can express all queries in PSpace; this implies that MTL operators add significant expressive power to Datalog. Furthermore, we provide tight combined complexity bounds for the forwardpropagating fragment of Datalog MTL, which was proposed in the context of stream reasoning, and show that it is possible to express all PSpace queries in the fragment extended with the falsum predicate. |
| Researcher Affiliation | Academia | Przemysław A. Wał ega1,2 , Bernardo Cuenca Grau1 , Mark Kaminski1 and Egor V. Kostylev1 1Department of Computer Science, University of Oxford, UK 2Institute of Philosophy, University of Warsaw, Poland {przemyslaw.walega, bernardo.cuenca.grau, mark.kaminski, egor.kostylev}@cs.ox.ac.uk |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of open-source code for the methodology described. |
| Open Datasets | No | The paper describes theoretical research and does not use or provide concrete access information for a publicly available or open dataset for training. |
| Dataset Splits | No | The paper describes theoretical research and does not provide specific dataset split information for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical work and does not provide specific hardware details used for running experiments. |
| Software Dependencies | No | The paper describes theoretical work and does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper describes theoretical work and does not contain specific experimental setup details, hyperparameter values, or training configurations. |