MobilityReadingGroup

Event Structure Semantics of Parallel Extrusion in the Pi-Calculus

Silvia CRAFA, Daniele VARACCA, Nobuko YOSHIDA

We give a compositional event structure semantics of the π-calculus. The main issues to deal with are the communication of free names and the extrusion of bound names. These are the source of the expressiveness of the π-calculus, but they also allow subtle forms of causal dependencies. We show that free name communications can be modeled in terms of “incomplete/potential synchronization” 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 propose 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 as to capture the causal dependencies introduced by scope extrusion. The correctness of our true concurrent semantics is shown by an operational adequacy theorem with respect to the standard late semantics of the π-calculus.

@inproceedings{CVY2012,
  author = {Silvia Crafa and Daniele Varacca and Nobuko Yoshida},
  title = {{Event Structure Semantics of Parallel Extrusion in the Pi-Calculus}},
  booktitle = {15th International Conference on Foundations of Software Science and Computational Structures},
  series = {LNCS},
  volume = {7213},
  pages = {225--239},
  publisher = {Springer},
  year = 2012
}

@inproceedings{CVY2012,
  author = {Silvia Crafa and Daniele Varacca and Nobuko Yoshida},
  title = {{Event Structure Semantics of Parallel Extrusion in the Pi-Calculus}},
  booktitle = {15th International Conference on Foundations of Software Science and Computational Structures},
  series = {LNCS},
  volume = {7213},
  pages = {225--239},
  publisher = {Springer},
  doi = "10.1007/978-3-642-28729-9_15",
  year = 2012
}