pipette
ESEspañol

Two Sides of the Same Proof: Extraction and Projection in Choreographic Programming

Matteo Acclavio, Giulia Manara, Fabrizio Montesi, Marco Peressotti

Preprint

In the authors' words

A new approach to the theory of choreographic languages has recently been proposed, based on the interpretation of choreographies with finite behaviors as proofs in an extension of linear logic. This paper further develops this approach to cyclic proofs to be capable of representing infinite behaviors, and prove a completeness result for choreographies with respect to the class of lock-free networks. We show that in a choreographies-as-proofs correspondence, the proof equivalence induced by rule permutations corresponds to bisimilarity, and that, under adequate assumption on the procedure definitions, the proof search procedure has a finite search space, and can be used to extract a choreography from a network.

Main resultLimitation the authors admit

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.