Verifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach
Proceedings of the ACM on Programming Languages · 05.08.2025 · 9 (ICFP) · 160-189
DOI: 10.1145/3747510 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Programming Languages, online erschienen am 05.08.2025. Verfasst von Marcos Grandury und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 62 Literaturangaben. Gefördert von: Ministerio de Ciencia, Innovación y Universidades, European Research Council.
Abstract (Originalsprache)
Verifying graph algorithms has long been considered challenging in separation logic, mainly due to structural sharing between graph subcomponents. We show that these challenges can be effectively addressed by representing graphs as a partial commutative monoid (PCM), and by leveraging structure-preserving functions (PCM morphisms), including higher-order combinators. PCM morphisms are important because they generalize separation logic’s principle of local reasoning. While traditional framing isolates relevant portions of the heap only at the top level of a specification, morphisms enable contextual localization: they distribute over monoid operations to isolate relevant subgraphs, even when nested deeply within a specification. We demonstrate the morphisms’ effectiveness with novel and concise verifications of two canonical graph benchmarks: the Schorr-Waite graph marking algorithm and the union-find data structure.
Förderung
- Ministerio de Ciencia, Innovación y Universidades
- European Research Council
Zitieren
APA
Grandury, M., Nanevski, A., & Gryzlov, A. (2025). Verifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach. Proceedings of the ACM on Programming Languages, 9(ICFP), 160-189. https://doi.org/10.1145/3747510
Vancouver
Grandury M, Nanevski A, Gryzlov A. Verifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach. Proceedings of the ACM on Programming Languages. 2025;9(ICFP):160-189. doi:10.1145/3747510
BibTeX
@article{Grandury2025,
author = {Grandury, Marcos and Nanevski, Aleksandar and Gryzlov, Alexander},
title = {Verifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach},
journal = {Proceedings of the ACM on Programming Languages},
year = {2025},
volume = {9},
number = {ICFP},
pages = {160--189},
doi = {10.1145/3747510}
}
EUVIMED