Formulas as Processes, Deadlock-Freedom as Choreographies (Extended Version)

Matteo Acclavio, Giulia Manara, Fabrizio Montesi [2025].
In CoRR abs/2501.08928.

Abstract

We introduce a novel approach to studying properties of processes in the {\pi}-calculus based on a processes-as-formulas interpretation, by establishing a correspondence between specific sequent calculus derivations and computation trees in the reduction semantics of the recursion-free {\pi}-calculus. Our method provides a simple logical characterisation of deadlock-freedom for the recursion- and race-free fragment of the {\pi}-calculus, supporting key features such as cyclic dependencies and an independence of the name restriction and parallel operators. Based on this technique, we establish a strong completeness result for a nontrivial choreographic language: all deadlock-free and race-free finite {\pi}-calculus processes composed in parallel at the top level can be faithfully represented by a choreography. With these results, we show how the paradigm of computation-as-derivation extends the reach of logical methods for the study of concurrency, by bridging important gaps between logic, the expressiveness of the {\pi}-calculus, and the expressiveness of choreographic languages.

Links

doi.org

Additional notes

None

Cite (BibTeX)

Click to expand

@article{DBLP:journals/corr/abs-2501-08928,
  author       = {Matteo Acclavio and
                  Giulia Manara and
                  Fabrizio Montesi},
  title        = {Formulas as Processes, Deadlock-Freedom as Choreographies (Extended
                  Version)},
  journal      = {CoRR},
  volume       = {abs/2501.08928},
  year         = {2025},
  url          = {https://doi.org/10.48550/arXiv.2501.08928},
  doi          = {10.48550/ARXIV.2501.08928},
  eprinttype    = {arXiv},
  eprint       = {2501.08928},
  timestamp    = {Fri, 21 Feb 2025 21:58:50 +0100},
  biburl       = {https://dblp.org/rec/journals/corr/abs-2501-08928.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org}
}

Peer-reviewed version

Click to show in publication list