Verification of Unary Communicating Datalog Programs
Proceedings of the ACM on Management of Data · 10.05.2024 · 2 (2) · 1-26
DOI: 10.1145/3651590 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2024. Verfasst von C. Aiswarya und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 27 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: HORIZON EUROPE Framework Programme, PRIN MUR, Free University of Bozen-Bolzano.
Abstract (Originalsprache)
We study verification of reachability properties over Communicating Datalog Programs (CDPs), which are networks of relational nodes connected through unordered channels and running Datalog-like computations. Each node manipulates a local state database (DB), depending on incoming messages and additional input DBs from external services. Decidability of verification for CDPs has so far been established only under boundedness assumptions on the state and channel sizes, showing at the same time undecidability of reachability for unbounded states with only two unary relations or unbounded channels with a single binary relation. The goal of this paper is to study the open case of CDPs with bounded states and unbounded channels, under the assumption that channels carry unary relations only. We discuss the significance of the resulting model and prove the decidability of verification of variants of reachability, captured in fragments of first-order CTL. We do so through a novel reduction to coverability problems in a class of high-level Petri Nets that manipulate unordered data identifiers. We study the tightness of our results, showing that minor generalizations of the considered reachability properties yield undecidability of verification, both for CDPs and the corresponding Petri Net model.
Förderung
- HORIZON EUROPE Framework Programme
- PRIN MUR
- Free University of Bozen-Bolzano
- Knut and Alice Wallenberg Foundation
- Province of Bolzano
Zitieren
APA
Aiswarya, C., Calvanese, D., Cosmo, F. D., & Montali, M. (2024). Verification of Unary Communicating Datalog Programs. Proceedings of the ACM on Management of Data, 2(2), 1-26. https://doi.org/10.1145/3651590
Vancouver
Aiswarya C, Calvanese D, Cosmo FD, Montali M. Verification of Unary Communicating Datalog Programs. Proceedings of the ACM on Management of Data. 2024;2(2):1-26. doi:10.1145/3651590
BibTeX
@article{Aiswarya2024,
author = {Aiswarya, C. and Calvanese, Diego and Cosmo, Francesco Di and Montali, Marco},
title = {Verification of Unary Communicating Datalog Programs},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {2},
pages = {1--26},
doi = {10.1145/3651590}
}
EUVIMED