Presheaf Models for the pi-Calculus

  • Gian Luca Cattani
  • Ian Stark
  • Glynn Winskel

Abstract

Recent work has shown that presheaf categories provide a general model of concurrency, with an inbuilt notion of bisimulation based on open maps. Here it is shown how this approach can also handle systems where the language of actions may change dynamically as a process evolves. The example is the pi-calculus, a calculus for `mobile processes' whose communication topology varies as channels are created and discarded. A denotational semantics is described for the pi-calculus within an indexed category of profunctors; the model is fully abstract for bisimilarity, in the sense that bisimulation in the model, obtained from open maps, coincides with the usual bisimulation obtained from the operational semantics of the pi-calculus. While attention is concentrated on the `late' semantics of the pi-calculus, it is indicated how the `early' and other variants can also be captured.

 

A version of this paper appears in Category Theory and Computer Science: Proceedings of the 7th International Conference CTCS '97, Lecture Notes in Computer Science 1290. Springer-Verlag, September 1997.

Published
1997-06-04
How to Cite
Cattani, G., Stark, I., & Winskel, G. (1997). Presheaf Models for the pi-Calculus. BRICS Report Series, 4(34). https://doi.org/10.7146/brics.v4i34.18960