Formulas as Processes, Deadlock-Freedom as Choreographies (Extended Version)
Matteo Acclavio, Giulia Manara, Fabrizio Montesi · 2025
Read Formulas as Processes, Deadlock-Freedom as Choreographies (Extended Version) by Matteo Acclavio, Giulia Manara, Fabrizio Montesi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-08928.txt.
Description
Matteo Acclavio, Giulia Manara, and Fabrizio Montesi link logic proofs to running programs in this 2025 paper. Their setting is the pi-calculus, a formal language for processes that communicate and can deadlock, stuck waiting on each other forever.
The team reads formulas as processes and proofs as computation trees. Sequent calculus derivations match the step by step behavior of a process without recursion. That match yields a simple logical test for deadlock freedom. The test covers the fragment without races and with cyclic dependencies. Building on it, they prove a strong completeness result. Every deadlock free, race free process of the studied kind, run in parallel, can be faithfully written as a choreography, a global script of who talks to whom.
Catalog record
| CREATOR | Matteo Acclavio, Giulia Manara, Fabrizio Montesi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 325 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-08928