DatalogMTL with negation under stable models semantics

Conference item

We introduce negation under stable models semantics in DatalogMTL—a temporal extension of Datalog with metric 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 rationals and decidable in EXPSPACE in data complexity over the integers. We also show that, if we restrict our attention to forward-propagating programs (where rules propagate information in a single temporal direction), reasoning over integers becomes PSPACE-complete in data complexity and hence no harder than over positive programs; however, reasoning over the rationals in this fragment remains undecidable.

Authors: Wałęga, PA; Tena Cucala, DJ; Kostylev, EV; Cuenca Grau, B

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IJCAI Organization
• Host title: Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning
• Pages: 609–618
• Publication date: 2021-11-03
• Acceptance date: 2021-06-15
• Event title: 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021)
• Event location: Virtual event
• Event website: https://kr2021.kbsg.rwth-aachen.de/
• Event start date: 2021-11-03
• Event end date: 2021-11-12
• DOI: 10.24963/kr.2021/58
• ISSN: 2334-1033
• ISBN: 978195679-997
• Language: English
• Keywords: FFR; logic programming; geometric, spatial, and temporal reasoning; answer set programming