EUVIMEDEUVIMED entdecken
Crossref

Verifying Graph Algorithms in Separation Logic: A Case for an Algebraic Approach

Marcos Grandury, Aleksandar Nanevski, Alexander Gryzlov

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →