2023/06/13 by Przemysław Andrzej Wałęga, David J. Tena Cucala, Wałęga, Przemysław A. +5
Computer Science · #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation #Semantic Web and Ontologies
paper · pdf · doi:10.48550/arxiv.2306.07625
openalex publication_date 2023/06/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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).