EUVIMEDEUVIMED entdecken
Crossref

When Separation Arithmetic is Enough, or How to Automate the Proof of Programs that Use Pointers

Jean-Christophe Filliâtre, Andrei Paskevich, Olivier Danvy

Formal Aspects of Computing · 09.11.2026

DOI: 10.1145/3861272 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Formal Aspects of Computing, online erschienen am 09.11.2026. Verfasst von Jean-Christophe Filliâtre und 2 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In deductive program verification, the more automated the proofs, the more practical the verification. Today, the best tools for mechanized verification are SMT solvers, due to their combination of first-order logic and linear arithmetic. SMT solvers, however, are not well suited for inductive reasoning, and inductive reasoning is often needed to cater for recursive data structures such as lists or trees. In this article, we show how to specify imperative programs over pointer-based recursive data structures in a way that stays within the reach of first-order provers. The idea is to map a recursive structure onto an integer-indexed sequence, in such a way that separation and frame properties can be expressed using only simple arithmetic relations. We illustrate this approach with various programs over lists, trees, and graphs, ranging from a new in-place list reversal to the Schorr-Waite graph-marking algorithm.

Zitieren

APA

Filliâtre, J., Paskevich, A., & Danvy, O. (2026). When Separation Arithmetic is Enough, or How to Automate the Proof of Programs that Use Pointers. Formal Aspects of Computing. https://doi.org/10.1145/3861272

Vancouver

Filliâtre J, Paskevich A, Danvy O. When Separation Arithmetic is Enough, or How to Automate the Proof of Programs that Use Pointers. Formal Aspects of Computing. 2026. doi:10.1145/3861272

BibTeX
@article{Fillitre2026,
  author = {Filliâtre, Jean-Christophe and Paskevich, Andrei and Danvy, Olivier},
  title = {When Separation Arithmetic is Enough, or How to Automate the Proof of Programs that Use Pointers},
  journal = {Formal Aspects of Computing},
  year = {2026},
  doi = {10.1145/3861272}
}
Kostenlos starten →