1 results
The Stable Model Semantics of Datalog with Metric Temporal Operators
-
- Journal:
- Theory and Practice of Logic Programming / Volume 24 / Issue 1 / January 2024
- Published online by Cambridge University Press:
- 02 August 2023, pp. 22-56
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
We introduce negation under the stable model semantics in DatalogMTL – a temporal extension of Datalog with metric temporal operators. As a result, we obtain a rule language which combines the power of answer set programming with the temporal dimension provided by metric operators. We show that, in this setting, reasoning becomes undecidable over the rational timeline, and decidable in
${{\rm E}{\small\rm XP}{\rm S}{\small\rm PACE}}$ in data complexity over the integer timeline. We also show that, if we restrict our attention to forward-propagating programs, reasoning over the integer timeline becomes 
${{\rm PS}{\small\rm PACE}}$-complete in data complexity, and hence, no harder than over positive programs; however, reasoning over the rational timeline in this fragment remains undecidable.
