The Stable Model Semantics of Datalog with Metric Temporal Operators

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-06
Main Authors: Wałęga, Przemysław A, Tena Cucala, David J, Bernardo Cuenca Grau, Kostylev, Egor V
Format: Article
Language:English
Subjects:
Complexity
Declarative programming
Integers
Logic programming
Mathematical programming
Operators
Reasoning
Semantics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 EXPSPACE 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 PSPACE-complete in data complexity, and hence, no harder than over positive programs; however, reasoning over the rational timeline in this fragment remains undecidable. Under consideration in Theory and Practice of Logic Programming (TPLP).
ISSN:2331-8422