WorksComputer Science
Two Sides of the Same Proof: Extraction and Projection in Choreographic Programming
Abstract
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.
ACM Reference Format: Matteo Acclavio, Giulia Manara, Fabrizio Montesi, and, Marco Peressotti. 2018. Two Sides of the Same Proof: Extraction and Projection in Choreographic Programming. In Proceedings of Make sure to enter the correct conference title from your rights confirmation email (Conference acronym ’XX). ACM, New York, NY, USA, 32 pages. https://doi.org/XXXXXXX.XXXXXXX
Introduction
Choreographic programming (CP) is a programming paradigm for concurrent and distributed systems, where the programmer specifies a global description of the system, called choreography, and then the compiler produces a network of local programs that implement the choreography using a procedure called endpoint projection (EPP) [37, 38]. Correctness of EPP establishes a behavioral equivalence, usually in terms of strong bisimulation, between choreographies and their compiled networks produced by EPP. The advantage of CP is that global descriptions of the system avoids the occurrence of communication problems, such as deadlocks and race conditions, and therefore a network obtained through EPP is guaranteed to be free from such errors.
The theory of CP revolves around two central notions: realisability and expressivity.
Realisability regards the question of which choreographies can be implemented by networks. This question is usually answered constructively by designing EPP procedures that, given a choreography, produce a network behaviorally equivalent of the choreography.
Expressivity regards the question of which networks can be specified by choreographic languages. A constructive way to answer this question is to design extraction procedures that,
Authors’ Contact Information: Matteo Acclavio; Giulia Manara; Fabrizio Montesi; Marco Peressotti, FORM, University of Southern Denmark, Odense, Denmark.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. Conference acronym ’XX, Woodstock, NY © 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX given a network satisfying certain properties, produce a choreography behaviourally equivalent to the network.
Ideally, these two directions should form two facets of the same underlying correspondence. The diagram in Figure 1 summarises this relationship: realisable choreographies correspond to expressible networks via behavioural equivalence, the classes of projectable choreographies and projected networks identify the fragments connected by projection and the classes of extracted choreographies and extractable networks identify the fragments connected by extraction, respectively.
Figure 1. Realisability and expressivity of choreographies and networks.
Most work on choreographic programming has focused on the first question. This is partly because endpoint projection gives a concrete compilation problem with immediate practical relevance, and partly because it is technically more tractable. The tractability stems from the fundamental difference the information directly available in networks and choreographies: at the network level, the overall behavior of the system emerges from local programs that describe the behavior of each endpoint separately, whereas at the choreographic level the overall behavior is explicit, with choreographic programs directly describing the intended communications and the recursive structure of infinite behaviors. Extraction therefore faces the more challenging task of reconstructing emergent global behavior from distributed local code, a notoriously difficult problem [30].
The few works that approach the expressivity question in CP [12, 16, 26] (or in the adjacent field of Multiparty Session Types [29]) provide extraction procedures and establish their correctness with ad hoc arguments, without a direct correspondence with projection. This leaves open a central question: what is the precise relationship between realisability and expressivity, that is, between networks that realise choreographies and networks expressible as choreographies, or, dually, between realisable choreographies and choreographies that express networks?
Acclavio et al. [2] made a first step towards answering the question by introducing a new perspective, called choreographies-as-proofs, which replaces algorithmic constructs used in previous attempts by proof-theoretic ones. As the name suggest, this approach is based on the interpretation of choreographies as proofs in an extension of linear logic, using a process-as-formulas interpretation of processes, similar what studied in [10, 25, 32, 33, 35, 41, 42], where the behavior of a process is represented as a formula in linear logic, and the operational semantics of processes is represented as a proof system for the formulas, following the logic-programming paradigm. The core outcome of this approach is the possibility to establish a correspondence between some special representations of the LTSs of a network, called execution trees, and derivations in a sequent calculus extending multiplicative additive (first-order) linear logic. Then, the extraction of a choreography from a network is obtained by performing a proof search with some restrictions on the search space, and the choreography naturally emerges from the structure of the proof. However, the results are limited to choreographies with finite behaviors.
Contribution of the paper
In this work, we show that the choreographies-as-proofs approach can be extended to choreographies with infinite behaviors. In particular, we show that it can be used not only to design a complete extraction procedure for tail-recursive lock-free networks, but also to establish a new proof of endpoint projection. These two results show that the class of choreographies with infinite behaviors is expressive enough to capture the class of tail-recursive lock-free networks, solving an open problem in the theory of choreographic programming, and that endpoint projection is complete with respect to this class of choreographies. Together, these results place the theory of choreographic programming on a solid logical foundation based on the proof theory of linear logic, providing a unified and intuitive framework in which notions of realizability and expressivity can be studied in terms of proof-theoretic notions of derivability and proof search.
For this purpose, we rely on recent development in the proof theory of cyclic proofs (e.g., [1, 3, 17, 19, 20, 27, 36, 47]) and in particular of the extension of multiplicative additive linear logic with fixpoints () [6, 7, 8, 18, 21, 39], to extend the work in [2] with rules capturing (greatest) fixpoints, required to model infinite behaviors. We introduce a novel notion of fairness for proof, providing the proof-theoretic counterpart of the homonymous notion used in the theory of process calculi stronger than the notion of progressiveness used in the theory of non-wellfounded proofs, which is sound and complete with respect to the class of sequents encoding lock-free tail-recursive networks. We then define the system of synthetic rules (in the sense of [5, 34, 40]), which allow us to restrict the proof search space while preserving completeness. Fair proofs in are in bijection with choreographies, and the proof search procedure can be used to extract a choreography from a network.
The method we propose allows us to extract a choreography from the following network,
by performing a proof search in a restricted proof-search space in for a sequent encoding the network in (1), obtaining the following cyclic proof (where the labels two rules marking the roots of two isomorphic subtrees of the proof).
Then, from the structure of the proof in (2), we can extract the following choreography, which we can prove be bisimilar to the initial network in (1).
The same framework, allows us for a new proof of the endpoint projection theorem, by showing that if we can translate a choreography into a fair proof in , then the conclusion of the proof is a sequent encoding a network that is bisimilar to the choreography. Interestingly, this approach allows us to project more choreographies than the ones that can be projected by the endpoint projection algorithms in the literature.
For example, the following choreography is not projectable by the standard endpoint projection algorithm (see, e.g., [38]), because of the absence of communication of the knowledge of choice [11] about the choice made by p to r.
However, the corresponding proof does not require the knowledge of choice to be transmitted, because the two branches of the C-bra-rule are uniform in their context, meaning that the non-active formulas in both branches are the same, in the same way as for the rule of the additive conjunction in linear logic.
This allows us to define a more flexible endpoint projection procedure, which can project choreographies that would have required amendment (in the sense of [13, 14, 28]) in the standard approach.
Structure of the paper
In § 2 we recall some background notions on labeled transition systems and bisimilarity, to fix the notation we use in the paper. In § 3 we recall the syntax and semantics of networks, and we introduce the notion of execution tree, which is a special representation of the LTS of a network. In Section 4 we introduce the syntax and semantics of choreographies, and we recall the standard endpoint projection theorem. In § 5 we extend the system PiL with rules for fixpoints, and we study its theory. In § 6 we introduce the system ChorL of synthetic rules, and we show that fair proofs in ChorL are in bijection execution trees of lock-free tail-recursive networks. In § 7 we use this correspondence to define extraction and projection procedures, and we prove their correctness and completeness. We conclude in § 8 with a discussion of related and future work.
Background
In this section we recall the standard notion of (strong) bisimulation on labeled transition systems (LTSs), which we use throughout the paper to relate choreographies and networks under a common notion of behavioral equivalence.
A labeled transition system is a triple where is a set of states, is a set of labels, and is a transition relation. As customary, we write for , where ranges over . A reduction sequence is a sequence of states such that for all , in which case we may write (or simply if labels are irrelevant or clear from the context). We write there is no such that for some .
The choreographies and networks defined in § 3 and 4 are both equipped with labeled transition systems, each consisting of the terms of the corresponding language, a set of labels, and a transition relation induced by its operational semantics.
We recall the standard notion of bisimulation between labelled transition systems.
Definition 2.1. Let be an LTS. A binary relation is a bisimulation if for each pair and each :
if , then there is a such that and ;
if , then there is a such that and .
Two states and are bisimilar, written , if there is a bisimulation such that .
Network Calculus and Reduction Trees
In this section, we introduce the network calculus, a process calculus for communicating parallel processes that serves as the target language of the endpoint projection of choreographies. We assume a synchronous communication model, where each pair of processes communicate directly using a unique private communication channel; this features gave race freedom by design, which is a crucial property we need to prove the completeness of our extraction procedure. We also restrict our attention to tail-recursive processes and networks, i.e., those whose procedure calls occur only in tail position. This restriction ensures that every network has a finite set of reachable states.
Processes
We define process terms from given pairwise disjoint countable sets of process names (PN), variables (V), expressions (E), process variables (PV), and label names (L) using the following grammar:
where , , , , and
The set of active process names in a process term is the set of process names that appear in before any procedure call. That is, we define as follows:
A (process) procedure definition is a pair where (said to be defined by the procedure definition), and is a process term (called the body of the procedure definition). A procedure definition it is guarded if . A set of procedure definitions is closed if it contains a procedure definition for each process variable occurring in a procedure definition in . It is closed with respect to a process term if it is closed and minimal with respect to the property of containing all the process variables occurring in and in . In the following, as in standard presentations of process calculi [45, 46], whenever we define a process , we assume that we also fix a finite closed set of guarded procedure definitions , which is minimal with respect to the property of containing all the process variables occurring in . Then, the set of process names in a process term is defined by extending the function to also include process names occurring in all process terms in .
The set of process names in a process term is defined by the same inductive clauses as , except for process variables. In particular, if is a process variable and , then . Thus, also accounts for the process names occurring in the bodies of the procedure definitions reached through recursive calls.
Networks
A network is a function mapping process names in to process terms with finite support (i.e., for only finitely many ), such that no process name is mapped to a process term mentioning itself (i.e., . It is atomic if there exists a unique with , in which case we write , where . If and are networks with disjoint supports (i.e., if then with for all ), their parallel composition, is the network defined as the union of the two functions. The parallel composition is a commutative monoid for disjoint networks [38] with neutral element defined as the function mapping all process names to .
Remark 1. Every network can be written as the (finite) parallel composition of the atomic networks of the form , with in the support of .
As for processes, given a network we assume that we also fix a finite closed set of guarded procedure definitions , which is minimal with respect to the property of containing all the process variables occurring in and in the processes occurring in .
The operational semantics of networks is given by the three reduction steps in the top of Figure 2 with labels from the following set.
Figure 2. Operational rules for the semantics of networks, and the auxiliary rules required to define them.
The function is extended to these labels by letting , . Note that, we always have in the above labels because of the definition of networks.
Definition 3.1. A network is LF if for any network such that , if for some , then there are networks and such that with .
We introduce the notion of reduction tree, whose branches represent possible executions of a network. Whenever a node has multiple successors, these successors correspond to distinct internal choices made by the same process: each successor is obtained by selecting a different label among those available to that process.
Definition 3.2. A reduction tree of a network is a (possibly infinite) tree of networks, with nodes networks and with edges by reductions such that:
the root of is the state ;
if the state has a unique child then for a ;
if the state has more than one child, then and the set of children of is the set of all states such that with ;
is maximal: a state has no children only if .
An execution in is a maximal path .
A reduction tree is fairly lock-free if every state occurring in with , has a descendant with a child such that (for a label with ) and .
Lemma 3.3. Let be a network admitting a fairly lock-free reduction tree . If then admits a fairly lock-free reduction tree .
Proof. If already occurs as a state of , we let be the subtree of rooted at . The obtained tree is a reduction tree and is fairly lock-free since is.
Otherwise, we construct an auxiliary reduction tree rooted at extending the transition . We show that this tree is fairly lock-free, and conclude by considering its subtree rooted at . If , the root has as its unique child, and we continue by following the reductions of . When the transition labeled by is encountered in , we skip it and continue from its successor. If , besides we add all the other children required by Definition 3.2.3. For each such child , we continue by following the corresponding subtree of . Whenever the same choice node is reached, only the branch labelled is retained. Hence, every branch of the new tree is obtained from a branch of by removing the initial reductions involving the processes in that have already been performed at the root. All remaining reductions are unchanged, and therefore the resulting tree is a reduction tree. The fairly lock-free property is preserved: for every state in the new tree and every process with , the witnessing reduction required by the fairly lock-free condition in is either preserved in the new tree or coincides with the initial reduction already performed at the root.
Theorem 3.4. Let be a network. Then, is lock-free iff it admits a fairly lock-free reduction tree.
Proof. If is lock-free, then any execution of in a reduction tree satisfies the lock-free property, and therefore is fairly lock-free. Conversely, assume that . By repeatedly applying Lemma 3.3, we obtain a fairly lock-free reduction tree . The result follows from the definition of a fairly lock-free reduction tree.
Definition 3.5. A reduction tree is finitely representable if it can be represented by a finite graph (with edges labels on edges), whose paths are in bijection with the executions of . We call such graph the cyclic representation of .
Remark 2. Since we are considering only tail-recursive networks, the set of reachable states of a network is finite. Therefore, any reduction tree of a network is finitely representable.
Choreographies…now with tensor!
In this section, we fix the syntax and semantics of the choreographic language used in this paper. To establish completeness of our extraction procedure, we extend the standard syntax of choreographies with a tensor operator (), which composes choreographies with disjoint sets of process names and represents independent behaviors proceeding in parallel.
To get the intuition on why the tensor operation is needed, consider the following network, where processes p and q engage in a choice, while r and s repeatedly communicate independently of that choice:
where , , and .
The behavior of this network decomposes into two fully independent components: the interaction between p and q, and the interaction between r and s. The choreography capturing it must reflect this separation, as in (9).
Without the tensor, any tail recursive choreography over all four processes p, q, r, s would force their behaviors to share the same recursive variable, conflating independent components into a single recursive structure. This prevents bisimilarity with the network above: if p and q chose and terminated, the choreography would also force r and s to terminate, whereas in the network they continue communicating independently.
Remark 3. The semantics of choreographies we consider in this paper does not include runtime terms to represent partially unfolded procedure calls, as in [38]. While these runtime terms are in general necessary in the presence of ‘-transitions’ in the network semantics to unfold the procedure calls, our network semantics does not include such transitions, and the runtime terms are therefore unnecessary.
In fact, our extraction procedure benefits from this simplification, as it eases the extraction of the choreography from the network, even when amendment (in the sense of [13, 14, 28]) is required due to a lack of knowledge-of-choice transmission, as shown in Example 7.4.
Syntax
The set choreographies is generated from the same pairwise disjoint sets of process names (PN), variables (V), expressions (E), choreographic variables (CV), and label names (L) used in the definition of networks. Its syntax is given by the following grammar:
where and and , .
The term denotes a terminated choreography, while denotes a choreographic variable, which we use to allow our semantics to define recursive terms (see below). The choreography starts with an instruction requiring to send the expression to , and continue as , where is replaced by at . The choreography instructs p to choose one label in and communicate it to q, to then continue as for the selected label . Here q could, a priori, offer more labels than those that p can select, which is why we have . The choreography is the parallel composition of two choreographies.
A choreography is finite if it contains no choreographic variables. The set of active process names in a choreography is the set of process names that appear in before any procedure call. That is, we define as follows:
We define (choreographic) procedure definitions similarly to process procedure definitions: they are pairs where the variable is defined by the choreography (the body of the procedure definition). The set of process names in a choreography is defined by extending the function to also include process names occurring in all choreographies occurring in the set of procedure definitions .1 A procedure definition is guarded if . A set of procedure definitions is closed if it contains a procedure definition for each choreographic variable occurring in a procedure definition in .
Notation 1. In the following, as in standard presentations of process calculi [45, 46], whenever we define a choreography we assume that we also fix a finite closed set of guarded procedure definitions , which is minimal with respect to the property of containing all the choreographic variables occurring in
Definition 4.1. A choreography is well-formed if, for every sub-term of the form , the sets of process names of and are disjoint. That is, .
Remark 4. By definition, a recursive variable cannot occur in both components of a parallel composition in a well-formed choreography. Indeed, if occurs in both and , then the process names occurring in the body of belong to both and . Hence, .
Example 4.2. The choreography with and is well-formed, while the choreography , with is not well-formed since .
Semantics
In Figure 3, we define the labelled operational semantics of choreographies. Transitions are labelled by elements of , defined in Equation (8). Intuitively, a label records the processes participating in the corresponding step. The semantics extends the standard operational semantics of choreographies with tensor composition quite naturally:

Figure 3. Semantics of choreographies.
Rule com executes a communication: process p sends e to q, and the choreography continues as , that is, the choreography where all occurrences of x at q are replaced by e.
Rule proc unfolds a choreographic variable according to its procedure definition.
Rules choice and label implement choices in two steps. First, p selects a label ; then, the selected label is communicated to q, and the choreography proceeds as . The rules tensor-left and tensor-right allow either component of a tensor composition to reduce independently.
Rules delay-com and delay-choice allow a transition in a continuation to be performed before its enclosing communication or choice, provided that the transition does not involve the processes controlling that prefix. In rule delay-com, the delayed transition must not involve either p or q. In rule delay-choice, it must not involve either p or q and must be enabled in every branch for . Thus, the delayed transition is independent of the label eventually selected by p.
The bisimulation equivalence () induced by the semantics of choreographies on the set of choreographies has the following properties.
Proposition 4.3. For all choreographies , , , , the following properties hold:
We recall the definition of lock-freedom and the statement of the lock-freedom holds for well-formed choreographies.
Definition 4.4. A choreography is lock-free if, for every such that and every , there exist and a choreography such that with and for all .
Theorem 4.5. Let be a well-formed choreography, then is lock-free.
Proof. We reason by induction on the structure of . For finite choreographies, the claim is trivial (see, e.g., [38]). Otherwise, we can assume and and, by guardedness every process name in is also in . Hence, eventually perform a transition involving p if and only if the finite choreography obtained from by replacing every choreography variable with can eventually perform a transition involving p. □
Cyclic proofs in PiL
In this section, we introduce the proof theoretical framework used to establish the completeness of our extraction procedure. We recall the fragment of the system PiL introduced in [2] an extension of multiplicative additive linear logic with a non-commutative, non-associative, and self-dual connective , and nominal quantifiers to capture action prefixing and name restriction in process calculi. However, in this paper, we are not interested in the binding operators of process calculi, therefore we take a fragment of PiL without nominal quantifiers.
In this work we are interested in reasoning about processes with procedure calls, requiring to introduce a way to capture procedure calls in the logic. One option could be to use fixpoint operators as in MALL, the extension of multiplicative additive linear logic with least and greatest fixpoint operators [6, 8, 18, 23]. See Remark 6. However, we want to reason about processes with procedure calls without introducing the full power of fixpoint operators, and keep the syntax and the semantics of the logic as close as possible to the one of processes with procedure calls. Therefore, we extend the system PiL with procedural variables to model procedure calls. These could be seen either as second-order propositional variables quantified by an existential quantifier, but where the witness is fixed to be the body of the procedure definition, or as fixpoint formulas of the form , where is the formula encoding the body of the procedure definition.2
Formulas
Formulas are generated from the set of process names PN, the set of expressions E, the set of label L, the set of propositional variables3 PV, and a set of variables V and the unit using the following grammar:
with a pair of distinct process names p, q PN, V E L, X PV, and V.
A formula is an atom if it is either an output formula , or an input formula . We call a channel with endpoints p and q.4 They can be seen as binary predicates, where the first argument is a channel (made of a pair of process names, representing its endpoints) and the second is the message which is sent or received on that channel. The connectives \parr and (resp. and ) are the multiplicative (resp. additive) disjunction and conjunction of linear logic. The connective is a non-commutative, non-associative, self-dual multiplicative connective. The quantifiers and are the standard first-order quantifiers. Finally, X is a propositional variable.
In the following, we may write and \bigmathbin{\&}_{i=1}^{n} A_i as shorthand for and , respectively. In particular, we may write \bigmathbin{\&}_{i=1}^{1} A_i to simply denote .
We assume the following de Morgan duality for formulas:
The notion of free and bound variables is defined in the standard way, with the quantifiers and binding the variable in their scope, and the propositional variables X being always free.5 denote by the set of free variables of a formula .
We consider formulas to be defined up to -equivalence generated by the following clauses:
We can encode process terms as formulas in PiL as follows using the encoding defined by induction as follows:
We encode process terms as formulas in PiL by the inductively defined encoding given in Equation (14). Note that, is defined as the identity on being at the same time the set of process variables used to define process terms and the set of propositional variables used to define formulas.
The terminated process is encoded as the multiplicative unit . A process variable is encoded as its corresponding propositional variable. Output prefixes are encoded by a -formula with the formula representing the output action on the left and the encoding of the continuation on the right. Similarly, an input prefix is encoded by a -formula with the formula representing the input action on the left and the encoding of the continuation on the right. However, here the encoding uses the existential quantification to capture the binding of the input variable in the continuation. Selections and branchings are encoded as additive choices. A process making an internal choice is encoded using the additive conjunction (ranging over the labels in ) of -formulas with the formula representing the output of the label on the left and the encoding of the continuation on the right. Similarly, a process making an external choice is encoded using the additive disjunction (ranging over the labels in ) of -formulas with the formula representing the input of the label on the left and the encoding of the continuation on the right.
Remark 5. By definition of the encoding of atomic networks, only contains atoms of the form or for some channel variables of the form , where the may not necessarily be the same for all atoms in , but the process name is the same for all atoms in .
Sequent calculi
We assume the reader to be familiar with the general notions of sequent calculus and cyclic proofs, which we recall briefly for the sake of completeness.
A sequent is a set of formula occurrences.5 The set of free variables of a sequent is the union of the free variables of the formulas in .
Definition 5.1. We extend the encoding of ‘processes as formulas’ in Equation (14) to ‘networks as sequents’ by letting the encoding of a network be the sequent containing the encoding of each process in the atomic network constituting it. That is,
We may also write for the sequent obtained from by removing all occurrences of the unit except when .
Note that the encoding of a network is a set of formulas where all atoms have the same process name appearing in their channel variables, and such is the same for all formulas in (see Remark 5). We call such process name the location of a formula in .
Definition 5.2. A sequent rule with premises and conclusion is written . Given a set of rules , a derivation in of a sequent is a tree of sequents, with conclusion (i.e., root) , where the children of each sequent in are the premises of an instance of a rule in with conclusion the sequent labeling the parent node. If a node has no children, then either is the conclusion of a rule with no premises (e.g., rules ax and in Figure 4), or it is called an open premise of the derivation. A proof is a derivation with no open premises. A subderivation of a derivation is a subtree of .

Figure 4. Sequent calculus rules for PiL.
Two derivations are isomorphic if there is a bijection between their nodes preserving the structure of the tree and the sequents labeling the nodes.
Notation 2. We write for a proof with conclusion , and for a derivation with conclusion and one open premise , or if it is made only of instances of a same rule .
We may denote by a rule with conclusion and a premise for each .
The rules for the sequent calculus PiL on the formulas defined in Equation (11) are given in Figure 4. They include the standard rules for first-order multiplicative-additive linear logic (with a very limited set of atoms), plus a rule for the non-commutative connective . It is a generalization of the standard rules for the tensor to the case where we have multiple pairs of formulas connected by . In particular, the case corresponds to the rule for mix [24].
We write to denote that there is a derivation with conclusion a sequent of formulas using the rules in Figure 4.
We do not go into the details of the proof theory of PiL, but the system satisfies both initial and final coherence (that is, the general axiom rule AX is derivable, and the cut rule cut is admissible), and the structural congruence of processes is captured by the logical equivalence in the logic.
Cyclic Proofs
To extend the expressiveness of the sequent calculus we consider in this paper, we allow for cyclic proofs, which are a generalization of standard (well-founded) proofs where the underlying proof tree can be infinite, but it is required to satisfy a certain correctness condition.
Definition 5.3. A procedure definition is an equation of the form , where is a propositional variable (defined by the procedure definition) and is a formula, called the body of the procedure definition. The sequent system is defined by all rules in Figure 4 plus the following unfolding rule, replacing propositional variable in the sequent with a formula according to a procedural definition from a set , used as parameter of the rule (and the system).
We denote by .
Definition 5.4. Let be a set of procedure definitions, and a sequent. The set is defined as the set of process names occurring in the channel variables of the formulas in , together with the process names occurring in the bodies of the procedure definitions in that are used to recursively unfold propositional variables occurring in .
Remark 6. As mentioned at the beginning of this section, we could have considered a logical framework obtained by extending the system for with the non-commutative connective and the first-order quantifiers ( and ). In this setting, the encoding of processes as formulas would be similar to the one we have defined in Equation (14), but would have to use greatest fixpoint formulas. That is, the encoding of the atomic network should be the formula , where are the propositional variables corresponding to the procedure calls in .
In the following, the reader familiar with non-wellfounded proofs may find useful to keep in mind the nature of procedural definitions as greatest fixpoints to get an intuition about why the unfolding rules are used to define the progress condition. This ensures that the system is non-trivial, i.e., it cannot derive every formula of the language.
As standard in the literature of non-wellfounded proofs, we define the notion of progress allowing us to identify infinite derivations that are sound, and therefore can be considered as proofs.
Definition 5.5. An occurrence of a formula in the conclusion (resp. in a premise) of a rule, which does not appear in its premises (resp. not in its conclusion) is called principal (resp. active). A thread in a derivation is a maximal sequence of formula occurrences traced along the sequents of the tree, such that:
if is principal, then is an active sub-formula from one of its premises. For instance, if , then , while if is an occurrence of a propositional variable, then is the formula from the procedural definition used in the unfolding rule that makes principal.
if is not principal, then is the corresponding occurrence carried into a premise. In the case of , the occurrence is duplicated in both premises, and the thread chooses one copy.
A progress point for a thread in a derivation in is an occurrence of a propositional variable that occurs principal for the rule unfold in the thread.
In the definition of reduction tree, we identified the counterpart of the notions of fairness and progress from the standard literature on process calculi. We now define the corresponding notions in the proof-theoretical setting.
Definition 5.6. A branch of a derivation is a maximal path of sequents from the conclusion (the root) in the underlying tree of . It is fair if:
every non-principal formula in a sequent of the branch is principal in a sequent above in the same branch;
every time a formula of the form occurs principal infinitely often in the branch, each formula is also active infinitely often for every .
A progress point for a thread in a derivation is an element of the thread that is principal for some specific rules.6 A derivation is:
progressing if every infinite branch contains a thread with infinitely many progress points.
regular if it contains only a finite number of distinct non-isomorphic subderivations. It is cyclic if infinite and regular.
fair if every fair branch is fair.
If is a set of derivations, we say that a sequent is provable in , denoted , if there is a derivation in with conclusion .
Remark 7. Every fair proof derivation is necessarily progressing.
Remark 8. In process calculi, the justness condition is used to rule out infinite executions where some enabled action is never performed. This, in proof-theoretical terms, corresponds Condition 1 in Definition 5.6, which requires that every non-principal formula in a sequent of a branch is principal in a sequent above in the same branch.
However, this condition does not have specific requirement on the behavior of a process when a choice is enabled infinitely often: it only requires that if a choice is enabled infinitely often, then it is eventually chosen. A stronger condition, called fairness, is often used in process calculi to rule out infinite executions where a choice is always resolved in the same way. Condition 2 in Definition 5.6 is the proof-theoretical counterpart of the additional requirement imposed by fairness on the behavior of a process when a choice is enabled infinitely often, in addition to the requirement imposed by justness.
Notation 3. Regular derivations (also called cyclic derivations) are a standard notion in the theory of cyclic proofs. They can be represented as finite graphs, where we mark with matching symbols rules whose conclusions are the roots of isomorphic subderivations. For example, the following infinite derivation on the left in with , where the right-most branch continue infinitely reproducing the same structure, can be represented as show on the right, where we mark with the two instances of whose conclusions are the roots of isomorphic subderivations.
If we assume the rule unfold to be the rule defining progress points, then the above derivation is progressing, but it is not fair because the right-most branch contains a thread whose formulas (the ’s) are never active in any rule.
Proofs as Execution Trees
In this section, we show how we can establish a correspondence between reduction trees of a network and a special class of proofs in . To simplify the correspondence, we introduce a set of derivable rules in , called ChorL, which are sound and complete with respect to set of networks-as-sequents derivable in . Then, we prove that the set of cyclic proofs in ChorL is sound and complete with respect to sequents that are encoding of lock-free networks.
The system ChorL𝔉
The sequent system ChorL is given by the rules in Figure 5, which are synthetic rules (in the sense of [4, 33]) derivable in .

Figure 5. Sequent calculus rules for the system ChorL𝔉.
Proposition 6.1. Rules in ChorL are derivable in , that is, for every rule in ChorL, with conclusion and premises , there is a derivation in with conclusion and open premises .
Proof. The rule C-Init is an instance of the -rule. The rule C-mix is an instance of the -rule with with additional side condition on the process names of the sequents. The rule C-clean is derivable using C-mix and C-Init. The rule unfold is a rule in , and the rule C-unfold can be derived using a some unfold-rules. The rule C-com is derivable by using bottom-up, a -rule to substitute the variable with the expression in , a -rule with with left premise a sequent of the form , on which we can apply an ax-rule. The rule C-choi is derivable by using bottom-up, possibly multiple -rules branching the derivation into branches, each starting with a -rule with with the left premise a sequent of the form , on which we can apply an ax-rule. □
We define the class of proofs in ChorL which we are interested in, which are the ones that correspond to reduction trees of networks. For this, the notion of progress point is defined in terms of the rule C-unfold. This condition ensures two important properties of the progressing proofs in ChorL by construction: they are regular and fair.
Definition 6.2. Let be a set of procedural definitions. A progress point of a thread in a derivation in ChorL is a formula occurrence that is principal for the rule C-unfold. A proof in ChorL is progressing if every infinite branch contains a thread with infinitely many progress points; it is nice if it is progressing and such that the premise of any rule other than C-mix cannot be the premise of a C-mix-rule, and that the active formulas of C-choi-rule is always principal for a C-lab-rule.
We define Chorl (resp. Chorl) as the set of progressing (resp. nice) proofs in Chorl.
Lemma 6.3. Let be a network. If , then there is a regular proof of in Chorl.
Proof. Let be a derivation in Chorl with conclusion . There are only finitely many sequents that can occur in because contains only finitely many subformulas, is finite and closed, and, except for unfold and C-unfold, rules in Chorl do not introduce new formulas. We conclude observing that, since any infinite branch of must repeat a sequent, is a regular proof.
Lemma 6.4. Let be a network. If , then .
Proof. Let be a proof in Chorl of . We transform into a nice proof in two steps. First, if with disjoint supports, then we can insert a C-mix-rule to the sequent , and split the subproof above the sequent into the two proofs in the premises of the C-mix-rule, one with conclusion and the other with conclusion , made of the rules applied to the formulas in and , respectively. Then, we permute the C-lab-rules downward until they reach the C-choi-rules that make their active formulas principal, using the permutations of Figure 6. The resulting derivation is nice by construction.
Figure 6. Rule permutations defining the proof equivalence in Chorl, with and .
Proofs as Execution Trees, and Lock-freedom as provability
Each rule in Chorl is designed to faithfully correspond to a single transition in the network semantics. In particular, we here show that the results in [2] can be extended to networks with infinite behavior.
Lemma 6.5. Let be a network. There is a one-to-one correspondence between reduction trees of and proofs of in ChorL.
Proof. We extend the translation of networks into sequents to reduction trees as shown in Figure 7 allowing us to translate a reduction tree into a derivation in ChorL.

Figure 7. Translation of execution trees to derivations, where dotted lines represents possible applications of unfold. Dotted lines in the derivations represent possible applications the rule noted on the left of the line.
Corollary 6.6. The translation maps regular (resp. fairly lock-free) reduction trees into regular (resp. nice) proofs in ChorL.
Proof. For fairly lock-free reduction trees, every non-nil state eventually advances, so the translation produces a fair proof (thus progressing ones).
We can now establish the central result of this section: the system ChorL is a proof system deciding lock-freedom for networks.
Theorem 6.7. A network is lock-free if and only if .
Proof. By Theorem 3.4, if is lock-free, then there is a fairly lock-free reduction tree of . By Lemma 6.5, each reduction tree of can be translated into a proof in ChorL of . Therefore, if is lock-free, then .
The implication from provability in ChorL to lock-free relies crucially on the fact that our networks are race-free: each send action has a unique matching receive, and each C-choi-rule has a unique set of matching C-lab-rules. Hence, every rule in the proof corresponds unambiguously to a single network transition, and the progress condition of ChorL ensures that every such transition is eventually taken.
As a corollary, we obtain a result that serves as basis for the definition of the extraction procedure in § 7, proving that if a network is lock-free, then there is a proof of in ChorL.
Corollary 6.8. Let be a network. If is lock-free, then admits a proof in ChorL.
Proof. Consequence of Theorem 6.7 and Lemma 6.4.
Proofs as Choreographies
In this section we establish a correspondence between choreographies and proofs in . We show that we can translate a choreography into a proof with conclusion a sequent describing a network , such that is bisimilar to . Then, we show that we can reverse the argument, and define a choreography from a successful proof search in of a sequent describing a network , such that the extracted choreography is bisimilar to .
Endpoint Projection, Logically
To reconstruct the endpoint projection of a choreography as a proof translation, we proceed in two steps. We first define a system obtained by relaxing the rule C-choi of into a rule limbo whose premises may have completely unrelated contexts. This allows us to define a total function translating any choreography into a derivation in , without checking any condition equivalent to projectability. We then identify the projectable choreographies as those for which every occurrence of limbo in can be replaced by the sound rule C-choi, yielding a proof in .
To translate a recursive call into a proof, we need to identify the processes having genuinely infinite behavior in . These processes are the ones that receive a recursive propositional variable in the translation. In fact, the choreography associated with may contain finite branches in which some processes are not necessarily involved in the recursion, as show in the example in Equation (5). We capture this distinction using recursive names, defined as follows.
Definition 7.1. The function recursive names mapping choreographies to sets of process names that are involved in infinite behaviors, inductively defined as follows.
Example 7.2. Consider the choreography with from Equation (5). We have , since occurs only in the finite branch of the continuation, and is therefore not included in .
We can now define a first map from choreographies to derivations in a system obtained by relaxing the rule C-choi of into a rule limbo whose premises may have unrelated contexts.7
Definition 7.3. We define the system , where the rule limbo is defined as follows.
We associate a derivation in pre–ChorL to a choreography by induction on the structure of , using the translation defined in Figure 8. We say that is projectable if every occurrence of limbo in is such that we can replace each non-principal formula with a single formula , for each , and the resulting derivation is still a proof in ChorL (see Example 7.4).
Figure 8. Translation of a choreography into a pre-derivation, with and with . The dotted lines represent the possible applications instances of the C-clean.
If is projectable, then we define as the proof in ChorL obtained by translation defined as in Figure 8 by changing the way we translate the limbo-rules, which are translated as shown in the bottom of Figure 8 with respect to the translation .
Remark 9. We define the translation of a choreography into a derivation in pre–ChorL by progressively decomposing the choreography. To each choreography we associate a sequent , where . Each clause of Figure 8 extends the derivation associated with the continuation of the choreography by adding the rule corresponding to its outermost constructor. The formulas introduced by the rule replace the formulas associated with the involved processes throughout the open derivation below it. In particular, in the communication case, the formulas introduced by C-com replace the formula (resp. ) with (resp. ) in the derivation below. In the recursive case, only the processes in , with , are associated with propositional variables. Thus, procedure calls are introduced only for the processes occurring in the recursive behavior of ; processes occurring solely in finite sub-choreographies are instead represented by their finite formulas.
Example 7.4. Consider the choreography from Equation (5). When we translate into a derivation in , we start by translating the outermost constructor of into a limbo-rule, obtaining the following derivation in pre–ChorL:
which would require to satisfy the following equations:
In order to define , it suffices to check if the equation admits a solution with the current constraints, which is the case here. If we assume , we can safely continue translating the right branch obtaining the following derivation in ChorL.
The derivation is defined as in Equation (5).
Remark 10. The way the choice is translated into a proof, allows us to have a better handling of the knowledge of choice in the choreography as shown in the previous example. In fact, the choreography in Equation (4) cannot be projected using standard techniques (as, e.g., in [38]) because of the lack of knowledge of choice for . However, the conclusion sequent of is bisimilar to the following network we obtain using our new endpoint projection technique.
In fact, the fairness property of the proof highlight the fact that because r is not involved in the recursive behavior of , and r does not need to be aware of the choice made by p and q.
Remark 11. Notice that by construction the conclusion of is always of the form .
We can now show that if two choreographies are projectable, and their translations are equivalent proofs in modulo the equivalence relation over derivations in inductively generated by the rule permutations in Figure 6, then the two choreographies are bisimilar.
Lemma 7.5. Let and projectable choreographies. If , then .
Proof. Since we are assuming if there is a finite sequence of rule permutations transforming into , we can reason by induction on the number of rule permutations in the sequence. In fact, each rule permutation requires that the process names involved in the active formulas of the two rules are disjoint, and therefore preserves the bisimilarity of the corresponding choreographies via delay rules. □
We can now prove the main result of this section, which is a reformulation of the endpoint projection of choreographies in logical terms. For this purpose, we recall the definition of bisimulation between choreographies and networks.
Definition 7.6. A binary relation between choreographies and networks is a bisimulation of networks and choreographies if for all pair , for all :
(1) if , then there is a such that and ; (2) if , then there is a such that and .
A network and a choreography are bisimilar, written , if there is a weak bisimulation such that .
Theorem 7.7 (EPP). Let be a choreography. If is a well-defined proof in ChorLnice with conclusion , then there exists a network lock-free such that and .
Proof. By Remark 11 there is such that . Since is a proof of so by Corollary 6.8 is lock-free. To show that we show that the relation is the conclusion of is a bisimulation. We verify the two bisimulation conditions of Definition 7.6.
(1) We proceed by case analysis on the bottom-most rule r in the derivation of the transition in the operational semantics of choreographies, by letting being the conclusion of and being the conclusion of .
If r = com, then and the bottom-most rule of is an instance of C-com with conclusion and premise , the conclusion of . We conclude since .
If r = choice (resp. r = label) we conclude similarly to the previous case, but considering the fact that the bottom-most rule in is a C-choi (resp. C-lab) and (resp. ).
If r = tensor-left (resp. tensor-right), then and the bottom-most rule of is C-mix with conclusion and two premises and , each conclusion of a proof and , respectively. By inductive hypothesis on (resp. ), there exists (resp. ) with (resp. ) and (resp. ), the conclusion of (resp. ). We conclude because we have (resp. ) thanks to the rule par in the operational semantics of networks.
If r = delay-com, then where , and the bottom-most rule of is a C-com. By inductive hypothesis on , there exists with , the conclusion of . Since , we have for all , hence . Moreover, is obtained from by appending the same C-com as bottom-most rule, so .
If r = delay-choice we conclude similarly to the previous case, but assuming that the bottom-most rule of is C-choi followed by instances of C-lab and that the transition is derived in the network semantics using the rule proc.
If r = proc, we conclude by inductive hypothesis, noting that the corresponding network step uses rule proc.
(2) We proceed by induction on the maximal distance in the derivation of the rule corresponding to the transition with label from the root of the derivation in all its branches. If , then the bottom-most rule of directly encodes the transition labeled by : if (resp. , ), the bottom-most rule is C-com (resp. C-choi preceded by instances of C-lab, C-lab), and we conclude with a reasoning similar to the one we used in the previous point.
For the inductive step, : the bottom-most rule of Pr (C) encodes a transition, whose process names of its label are not in ; it is one of C-mix, C-com, C-choi, C-lab, or C-unfold. In each subcase, applying the inductive hypothesis to the relevant sub-derivation (where the maximum depth of the rule for decreases by one) and concluding by the same argument as in the tensor-left, delay-com, delay-choice, and proc in the previous point, respectively.
Extraction, logically
We design an algorithm for extracting a choreography from a proof of a sequent encoding a lock-free network, and we show that the extracted choreography is bisimilar to the original network.
Definition 7.8. Let be a proof in of a sequent . The choreography extracted from is the choreography defined by induction on the structure of as described in Figure 9.
Figure 9. Translation from ChorL proofs to choreographies.
Lemma 7.9. The proof equivalence induces a bisimulation of choreographies. That is, if two derivations and in are such that , then .
Proof. We observe that the permutations in Figure 6 preserve niceness. First, C-mix and C-unfold cannot be permuted with each other. Second, only finitely many steps are permuted; therefore, an infinite derivation still contains infinitely many progress points. If , then there is a finite sequence of rule permutations as in Figure 6 transforming into . We conclude by induction on the number of rule permutations in the sequence, after observing that each rule permutation preserves the bisimilarity of the extracted choreographies. □
Theorem 7.10 (Extraction). Let and let be the network such that is the conclusion of . Then .
Proof. We define the following relation between choreographies and networks,
and we show that it is a bisimulation (see Definition 7.6) containing .
Proof that if , then there is a such that and :
If , then there is such that and . We can then construct a proof with conclusion such that and, . By definition of , , and we can conclude using transitivity of bisimilarity that .
We proceed by case analysis on the label . Thanks to Lemma 7.9 and guardedness of choreographies, we can always assume that the bottom of is made of possibly some instances of C-mix and C-unfold only involving the process names in , followed by either C-com, C-choi or C-lab, accordingly whether is , or .
If , then
where the unfold-rules may only involve formulas where p or q occur, and so
with and . We can then let be defined as follows:
with . We observe that and we conclude since .
The other cases are similar, with case needing to prove (by definition of , and the definition of the rule delay-choice) that if , then for all .
Proof that if , then there is a such that and :
If and with being the conclusion of , then, we can again assume that the bottom-most rule in is either C-com, C-choi or C-lab (possibly preceded by instances of C-mix and C-unfold), accordingly whether is , or and that with being the child of corresponding to the transition labeled by .
To conclude, it suffices to show that the subderivation with conclusion is such that . The argument is similar to the one we used in Item (1). ∎
Theorem 7.11 (Completeness). Let be a network. Then
Proof. If is lock-free, then by Theorem 6.7, admits a proof . We conclude by Theorem 7.10 by letting . □
Remark 12. The nice condition on proofs ensures that, when extracting a choreography from a proof, the extraction procedure immediately separate the independent components of a choreography using the C-mix-rule. This guarantees that independent components give rise to disjoint choreographies composed by , as in Equation (9). For example, while the network
is bisimilar to both the following choreographies:
the extraction procedure will always produce the second choreography, which is the one that better reflects disjoint the structure of the network.
Conclusions and Future Work
In this paper we provided a new framework for the study of choreographies and their relation with process calculi, based on the proof theory of linear logic. We showed that projection and extraction can be studied in a uniform way, by establishing a correspondence between specific proofs in the sequent calculus and trees of executions in the network calculus.
The main insight, is that adopting a logic-programming oriented view of process calculi, allows studying the properties of processes by reasoning on the corresponding proofs in the logic, and vice versa, in a quite natural way. This characterization is simple and elegant. Lock-freedom, which is a fundamental property of networks, can then be characterized in simple terms of existence of proofs in the logic, which, in turn, can be seen as successful execution of a logic program. The same framework allowed us to define a new endpoint projection with two notable advantages over existing approaches. First, it dispenses from the merge operator [9, 22, 38], a syntactic mechanism traditionally used to reconstruct the knowledge of choice during endpoint projection, whose correctness relies on technically involved metatheoretical arguments [48]. Secondly, removing merge does not restrict the class of projectable choreographies. On the contrary, our proof-theoretic formulation naturally extends it, allowing the projection of choreographies with recursive choices such as the one in (4), which, to the best of our knowledge, have not been handled by previous projection procedures.
Perspectives. The work presented in this paper provides an effective framework for choreographic extraction. By implementing proof search algorithms for the logic, it is possible to automatically extract choreographies from networks. For lock-free networks with only tail-recursive calls, the extraction algorithm is guaranteed to terminate, and, based on the complexity results for proof search in MALL [31], it should be possible to implement an extraction algorithm with polynomial-space complexity.8 In fact, the first-order component of the logic is only used in a very limited way in the proof search for sequents encoding networks, and the tail-recursive restriction on networks ensures that only a finite number of formulas (modulo first-order substitutions) can appear in the proof search, thus allowing to implement a polynomial-space proof search algorithm cyclic proofs.
Our also suggests a new generation of choreographic compilers based directly on the proof-theoretic endpoint projection developed in this paper that supports a strictly larger class of choreographies w.r.t., alternative approaches for comparable languages without incurring in runtime costs of auxiliary combinations [43, 44] or complex procedures like the merge operator [15, 38] and amendment [14].
References
Details of Proofs
Theorem 7.7 (EPP). Let be a choreography. If is a well-defined proof in with conclusion , then there exists a network lock-free such that and .
Proof. By Remark 11 there is such that . Since is a proof of so by Corollary 6.8 is lock-free. To show that we show that the relation is the conclusion of is a bisimulation. We verify the two bisimulation conditions of Definition 7.6.
We proceed by case analysis on the bottom-most rule in the derivation of the transition in the operational semantics of choreographies, by letting being the conclusion of and being the conclusion of .
If , then and the bottom-most rule of is an instance of C-com with conclusion and premise , the conclusion of . We conclude since .
If (resp. ) we conclude similarly to the previous case, but considering the fact that the bottom-most rule in is a C-choi (resp. C-lab) and (resp. ).
If (resp. ), then and the bottom-most rule of is C-mix with conclusion and two premises and , each conclusion of a proof and , respectively. By inductive hypothesis on (resp. ), there exists (resp. ) with (resp. ) and (resp. ), the conclusion of (resp. ). We conclude because we have (resp. ) thanks to the rule par in the operational semantics of networks.
If , then where , and the bottom-most rule of is a C-com. By inductive hypothesis on , there exists with and , the conclusion of . Since , we have for all , hence . Moreover, is obtained from by appending the same C-com as bottom-most rule, so .
If we conclude similarly to the previous case, but assuming that the bottom-most rule of is C-choi followed by instances of C-lab and that the transition is derived in the network semantics using the rule proc.
If , we conclude by inductive hypothesis, noting that the corresponding network step uses rule proc.
We proceed by induction on the maximal distance in the derivation of the rule corresponding to the transition with label from the root of the derivation in all its branches.
If , then the bottom-most rule of directly encodes the transition labeled by : if (resp. , ), the bottom-most rule is C-com (resp. C-choi preceded by instances of C-lab, C-lab), and we conclude with a reasoning similar to the one we used in the previous point.
For the inductive step, : the bottom-most rule of encodes a transition, whose process names of its label are not in ; it is one of C-mix, C-com, C-choi, C-lab, or C-unfold. In each subcase, applying the inductive hypothesis to the relevant sub-derivation (where the maximum depth of the rule for decreases by one) and concluding by the same argument as in the tensor-left, delay-com, delay-choice, and proc in the previous point, respectively.
Theorem 7.10 (Extraction). Let and let be the network such that is the conclusion of . Then .
Proof. We define the following relation between choreographies and networks,
and we show that it is a bisimulation (see Definition 7.6) containing .
(1) Proof that if , then there is a such that and :
If , then there is such that and . We can then construct a proof with conclusion such that and, . By definition of , , and we can conclude using transitivity of bisimilarity that .
We proceed by case analysis on the label . Thanks to Lemma 7.9 and guardness of choreographies, we can always assume that the bottom of is made of possibly some instances of C-mix and C-unfold only involving the process names in , followed by either C-com, C-choi or C-lab, accordingly whether is , or .
If , then
where the unfold-rules may only involve formulas where or occur, and so
with and . We can then let be defined as follows:
with . We observe that and we conclude since .
If , then we let
where the unfold-rules may only involve formulas where p or q occur, and so
with and . We can then let be defined as follows:
with . We observe that, by ??,
and we conclude since .
If , then we let
where and the unfold-rules may only involve formulas where p or q occur, and so
with and . We can then let be defined as follows:
with . We observe that and we conclude since .
(2) Proof that if , then there is a such that and :
If and with being the conclusion of , then, we can again assume that the bottom-most rule in is either C-com, C-choi or C-lab (possibly preceded by instances of C-mix and C-unfold), accordingly wether is , or and that with being the child of corresponding to the transition labeled by . To conclude, it suffices to show that the subderivation with conclusion is such that
We conclude by an argument similar to the one we used in Item (1) above.
References
- [1]Matteo Acclavio, Gianluca Curzi, and Giulio Guerrieri. 2023. Infinitary cut-elimination via finite approximations. CoRR abs/2308.07789 (2023). arXiv:2308.07789 doi:10.48550/ARXIV.2308.07789
- [2]Matteo Acclavio, Giulia Manara, and Pierpaolo Montesi. 2025. Formulas as Processes, Deadlock-Freedom as Choreographies. In Programming Languages and Systems, Viktor Vafeiadis (Ed.). Springer Nature Switzerland, Cham, 23–55.DOI
- [3]Bahareh Afshari, Graham E. Leigh, and Guillermo Menéndez Turata. 2025. Demystifying μ. Fundamenta Informaticae Volume 194, Issue 2: Fixed Points in Computer Science 2023, Article 3 (Aug 2025), 51 pages. doi:10.46298/fi.12773DOI
- [4]Jean-Marc Andreoli. 1992. Logic Programming with Focusing Proofs in Linear Logic. Journal of Logic and Computation 2, 3 (06 1992), 297–347. arXiv:https://academic.oup.com/logcom/article-pdf/2/3/297/6137548/2-3-297.pdf doi:10.1093/logcom/2.3.297
- [5]Jean-Marc Andreoli. 2001. Focussing and proof construction. Annals of Pure and Applied Logic 107, 1 (2001), 131–163. doi:10.1016/S0168-0072(00)00032-4DOI
- [6]David Baelde. 2012. Least and Greatest Fixed Points in Linear Logic. ACM Trans. Comput. Logic 13, 1, Article 2 (Jan. 2012), 44 pages. doi:10.1145/2071368.2071370DOI
- [7]David Baelde, Amina Doumane, and Alexis Saurin. 2016. Infinitary Proof Theory: the Multiplicative Additive Case. In 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France (LIPIcs, Vol. 62), Jean-Marc Talbot and Laurent Regnier (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 42:1–42:17. doi:10.4230/LIPIcs.CSL.2016.42DOI
- [8]David Baelde and Dale Miller. 2007. Least and Greatest Fixed Points in Linear Logic. In Logic for Programming, Artificial Intelligence, and Reasoning, 14th International Conference, LPAR 2007, Yerevan, Armenia, October 15-19, 2007, Proceedings (Lecture Notes in Computer Science, Vol. 4790), Nachum Dershowitz and Andrei Voronkov (Eds.). Springer, 92–106. doi:10.1007/978-3-540-75560-9_9DOI
- [9]Lorenzo Bettini, Mario Coppo, Loris D’Antoni, Marco De Luca, Mᵃ̇ngiola Dezani-Ciancaglini, and Nobuko Yoshida. 2008. Global Progress in Dynamically Interleaved Multiparty Sessions. In CONCUR 2008 - Concurrency Theory, 19th International Conference, CONCUR 2008, Toronto, Canada, August 19-22, 2008. Proceedings (Lecture Notes in Computer Science, Vol. 5201), Franck van Breugel and Marsha Chechik (Eds.). Springer, 418–433. doi:10.1007/978-3-540-85361-9_33
- [10]Paola Bruschi. 2002. A purely logical account of sequentiality in proof search. In International Conference on Logic Programming. Springer, 302–316.
- [11]Giuseppe Castagna, Mariangiola Dezani-Ciancaglini, and Luca Padovani. 2012. On Global Types and Multi-Party Session. Log. Methods Comput. Sci. 8, 1 (2012). doi:10.2168/LMCS-8(1:24)2012DOI
- [12]Luís Cruz-Filipe, Kim S. Larsen, and Fabrizio Montesi. 2017. The Paths to Choreography Extraction. In Foundations of Software Science and Computation Structures - 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conference on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings (Lecture Notes in Computer Science, Vol. 10203), Javier Esparza and Andrzej S. Murawski (Eds.). 424–440. doi:10.1007/978-3-662-54458-7_25DOI
- [13]Luís Cruz-Filipe and Fabrizio Montesi. 2020. A core model for choreographic programming. Theor. Comput. Sci. 802 (2020), 38–66. doi:10.1016/J.TCS.2019.07.005
- [14]Luís Cruz-Filipe and Fabrizio Montesi. 2023. Now It Compiles! Certified Automatic Repair of Uncompilable Protocols. In 14th International Conference on Interactive Theorem Proving, ITP 2023, July 31 to August 4, 2023, Bialystok, Poland (LIPIcs, Vol. 268), Adam Naumowicz and René Thiemann (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 11:1–11:19. doi:10.4230/LIPIcs.ITP.2023.11
- [15]Luís Cruz-Filipe, Fabrizio Montesi, and Marco Peressotti. 2023. A Formal Theory of Choreographic Programming. Journal of Automated Reasoning 67, 21 (2023), 1–34. doi:10.1007/s10817-023-09665-3
- [16]Luís Cruz-Filipe, Fabrizio Montesi, and Larisa Safina. 2019. Implementing choreography extraction. arXiv:1910.11741 [cs.PL] https://arxiv.org/abs/1910.11741
- [17]Anupam Das and Abhishek De. 2024. A Proof Theory of (ω)-Context-Free Languages, via Non-wellfounded Proofs. In Automated Reasoning, Christoph Benzmüller, Marijn J.H. Heule, and Renate A. Schmidt (Eds.). Springer Nature Switzerland, Cham, 237–256.
- [18]Anupam Das, Abhishek De, and Alexis Saurin. 2022. Decision Problems for Linear Logic with Least and Greatest Fixed Points. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022) (Leibniz, Vol. 1, No. 1, Article . Publication date: October 2018. International Proceedings in Informatics (LIPIcs), Vol. 228), Amy P. Felty (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 20:1–20:20. doi:10.4230/LIPIcs.FSCD.2022.20
- [19]Anupam Das and Marianna Girlanda. 2022. Cyclic Proofs, Hypersequents, and Transitive Closure Logic. In Automated Reasoning, Jasmin Blanchette, Laura Kovács, and Dirk Pattinson (Eds.). Springer International Publishing, Cham, 509–528.arxiv.org/abs/2205.08616
- [20]Anupam Das and Damien Pous. 2018. Non-Wellfounded Proof Theory for (Kleene+Action)(Algebras+Lattices). In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 119), Dan R. Ghica and Achim Jung (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 19:1–19:18. doi:10.4230/LIPIcs.CSL.2018.19DOI
- [21]Abhishek De, Farzad Jafarahmani, and Alexis Saurin. 2022. Phase Semantics for Linear Logic with Least and Greatest Fixed Points. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 250), Anuj Dawar and Venkatesan Guruswami (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 35:1–35:23. doi:10.4230/LIPIcs.FSTTCS.2022.35
- [22]Pierre-Malo Deniélou, Nobuko Yoshida, Andi Bejleri, and Raymond Hu. 2012. Parameterised Multiparty Session Types. Log. Methods Comput. Sci. 8, 4 (2012). doi:10.2168/LMCS-8(4):2012
- [23]Amina Doumane. 2017. On the infinitary proof theory of logics with fixed points. Theses. Université Sorbonne Paris Cité. https://hal.science/tel-01676953DOI
- [24]Arnaud Fleury and Christian Retoré. 1994. The mix rule. Mathematical Structures in Computer Science 4, 2 (1994), 273–285. doi:10.1017/S0960129500000451DOI
- [25]Ross Horne, Alwen Tiu, Bogdan Aman, and Gabriel Ciobanu. 2016. Private Names in Non-Commutative Logic. In 27th International Conference on Concurrency Theory (CONCUR 2016) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 59), Josée Desharnais and Radha Jagadeesan (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 31:1–31:16. doi:10.4230/LIPIcs.CONCUR.2016.31DOI
- [26]Bjørn Angel Kjær, Luís Cruz-Filipe, and Fabrizio Montesi. 2022. From Infinity to Choreographies: Extraction for Unbounded Systems. arXiv:2207.08884 [cs.PL]
- [27]Johannes Kloibhofer, Valentina Trucco Dalmas, and Yde Venema. 2026. Interpolation for Converse PDL. In Automated Reasoning with Analytic Tableaux and Related Methods, Gian Luca Pozzato and Tarmo Uustalu (Eds.). Springer Nature Switzerland, Cham, 258–277.
- [28]Ivan Lanese, Fabrizio Montesi, and Gianluigi Zavattaro. 2013. Amending Choreographies. In Proceedings 9th International Workshop on Automated Specification and Verification of Web Systems, WVV 2013, Florence, Italy, 6th June 2013 (EPTCS, Vol. 123), António Ravara and Josep Silva (Eds.). 34–48. doi:10.4204/EPTCS.123.5DOI
- [29]Julien Lange, Emilio Tuosto, and Nobuko Yoshida. 2015. From Communicating Machines to Graphical Choreographies. 50, 1 (jan 2015), 221–232. doi:10.1145/2775051.2676964
- [30]Tanakorn Lesataponrwongsa, Jeffrey F. Lukman, Shan Lu, and Haryadi S. Gunawi. 2016. TaxDC: A Taxonomy of Non-Deterministic Concurrency Bugs in Datacenter Distributed Systems. In Proceedings of the Twenty-First International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS 2016, Atlanta, GA, USA, April 2-6, 2016, Tom Conte and Yuanyuan Zhou (Eds.). ACM, 517–530. doi:10.1145/2872362.2872374
- [31]Patrick Lincoln, John Mitchell, Andre Scedrov, and Natarajan Shankar. 1992. Decision problems for propositional linear logic. Annals of Pure and Applied Logic 56, 1 (1992), 239–311. doi:10.1016/0168-0072(92)90075-B
- [32]Dale Miller. 1993. The π-calculus as a theory in linear logic: Preliminary results. In Extensions of Logic Programming, E. Lamma and M. Mello (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 242–264.DOI
- [33]Dale Miller. 2025. Proof Theory and Logic Programming: Computation as Proof Search. Cambridge University Press.DOI
- [34]Dale Miller, Gopalan Nadathur, Frank Pfenning, and Andre Scedrov. 1991. Uniform proofs as a foundation for logic programming. Annals of Pure and Applied Logic 51, 1 (1991), 125–157. doi:10.1016/0168-0072(91)90068-WDOI
- [35]Dale Miller and Alwen Tiu. 2005. A proof theory for generic judgments. ACM Trans. Comput. Logic 6, 4 (oct 2005), 749–783. doi:10.1145/1094622.1094628DOI
- [36]Jordi Serra Miranda, Thomas Studer, and Lukas Zenger. 2024. Coalgebraic proof translations for non-wellfounded proofs. In Proceedings of Advances in Modal Logic (AiML 2024). 22 pages. https://arxiv.org/abs/2506.01711 To appear.
- [37]Fabrizio Montesi. 2013. Choreographic Programming. Ph.D. Thesis. IT University of Copenhagen. https://www.fabriziomontesi.com/files/choreographic-programming.pdf.
- [38]Fabrizio Montesi. 2023. Introduction to Choreographies. Cambridge University Press. doi:10.1017/9781108981491DOI
- [39]Rémi Nollet, Alexis Saurin, and Christine Tasson. 2018. Local Validity for Circular Proofs in Linear Logic with Fixed Points. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 119), Dan R. Ghica and Achim Jung (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 35:1–35:23. doi:10.4230/LIPIcs.CSL.2018.35DOI
- [40]Carlos Olarte and Elaine Pimentel. 2017. On concurrent behaviors and focusing in linear logic. Theoretical Computer Science 685 (2017), 46–64. doi:10.1016/j.tcs.2016.08.026 Logical and Semantic Frameworks with Applications.DOI
- [41]Carlos Olarte, Elaine Pimentel, and Vivek Nigam. 2015. Subexponential concurrent constraint programming. Theoretical Computer Science 606 (2015), 98–120. doi:10.1016/j.tcs.2015.06.031 Logical and Semantic Frameworks with Applications.DOI
- [42]Elaine Pimentel, Carlos Olarte, and Vimac Nigam. 2021. Process-Ass-Formula Interpretation: A Substructural Multimodal View. In 6th International Conference on Formal Structures for Computation and Deduction (FSCD 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 195), Naoki Kobayashi (Ed.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 31:1–31:21. doi:10.4230/LIPIcs.FSCD.2021.3
- [43]Johannes Åman Pohjola, Alejandro Gómez-Londoño, James Shaker, and Michael Norris. 2022. Kalas: A Verified, End-To-End Compiler for a Choreographic Language. In 13th International Conference on Interactive Theorem Proving (ITP 2022) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 237), June Andronick and Leonardo de Moura (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 27:1–27:18. doi:10.4230/LIPIcs.ITP.2022.27DOI
- [44]Mila Dalla Preda, Maurizio Gabbrielli, Saverio Giallorenzo, Ivan Lanese, and Jacopo Mauro. 2017. Dynamic Choreographies: Theory And Implementation. Log. Methods Comput. Sci. 13, 2 (2017). doi:10.23638/LMCS-13(2:1)2017
- [45]Davide Sangiorgi. 2011. Introduction to bisimulation and coinduction. Cambridge University Press.DOI
- [46]Davide Sangiorgi and David Walker. 2001. The Pi-Calculus - a theory of mobile processes. Cambridge University Press.
- [47]Luigi Santocanale. 2002. A Calculus of Circular Proofs and Its Categorical Semantics. In Foundations of Software Science and Computation Structures, Mogens Nielsen and Uffe Engberg (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 357–371.
- [48]Alceste Scalas and Nobuko Yoshida. 2019. Less is more: multiparty session types revisited. Proc. ACM Program. Lang. 3, POPL (2019), 30:1–30:29. doi:10.1145/3290343DOI




