Event structure semantics of parallel extrusion in the pi-calculus

Abstract. We give a compositional event structure semantics of the pi-calculus. The main issues to deal with are the communication of free names and the extru-sion of bound names. These are the source of the expressivity of the pi-calculus, but they also allow subtle forms of causal dependencies. We show that free name communications can be modeled in terms of ”incomplete/potential synchroniza-tion ” events. On the other hand, we argue that it is not possible to satisfactorily model parallel extrusion within the framework of stable event structures. We pro-pose to model a process as a pair (E,X) where E is a prime event structure and X is a set of (bound) names. Intuitively, E encodes the structural causality of the process, while the set X affects the computation on E so to capture the causal dependencies introduced by scope extrusion. The correctness of our true concur-rent semantics is shown by an operational adequacy theorem with respect to the standard late semantics of the pi-calculus.