Pi-Calculus

Draft

Introduction

The PI calculus is a kind of "process algebra" or process calculus. It allows to model a process as the interaction from communicating parts (programs and/or humans).

The PI calculus provides the mathematical foundations of some modern workflow languages like BPMN, BPEL, BPML and BPQL.

Definitions

“In theoretical computer science, the π-calculus is a process calculus originally developed by Robin Milner, Joachim Parrow and David Walker as a continuation of work on the process calculus CCS (Calculus of Communicating Systems). The aim of the π-calculus is to be able to describe concurrent computations whose configuration may change during the computation [...] The π-calculus belongs to the family of process calculi, mathematical formalisms for describing and analyzing properties of concurrent computation.” (Wikipedia, retrieved 15:35, 23 July 2010 (UTC))

The Pi-calculus is “a calculus of communicating systems in which one can naturally express processes which have changing structure. Not only may the component agents of a system be arbitrarily linked, but a communication between neighbours may carry information which changes tha linkage. The calculus is an extension of the process algebra CCS, following work by Engberg and Nielsen who added mobility to CCS while preserving its algebraic properties. The pi-calculus gains simplicity by removing all distinction between variables and constants; communication links are identified by names, and computation is represented purely as the communication of names across links.” (Milner et al. 1989:1)

“π-calculus is a model of computation for concurrent systems. The syntax of π-calculus lets you represent processes, parallel composition of processes, synchronous communication between processes through channels, creation of fresh channels, replication of processes, and nondeterminism. That's it!” (FAQ on π-Calculus, retrieved 15:35, 23 July 2010 (UTC)).

There seem to be several notations and slight variants of the Pi-calculus. (However, I don't know for real - Daniel K. Schneider 15:35, 23 July 2010 (UTC)).

Bibliography and links

Slides

• PowerPoint by Simon Gay, University of Glasgow.

FAQs

• FAQ on π-Calculus by Jeanette M. Wing, 2002.

(Mostly difficult) introductions

• Robin Milner. Polyadic Pi-Calculus: a tutorial. Proceedings of the International Summer School on Logic Algebra of Specification, Springer Verlag, 1992.

• Milner Robin (1999). Communicating and mobile systems: the π-calculus, Cambridge University Press.

• Pierce, Benjamin (1996). Foundational Calculi for Programming Languages. In Allen B. Tucker (ed.) Handbook of Computer Science and Engineering, CRC Press. (PS Reprint

• Parrow, Joachim (undated), pi (PS, preprint of a chapter Bergstra et al. (eds). Handbook of Process Algebra, Elsevier.

• Sangiorgi Davide and David Walker (2001). The π-calculus: a Theory of Mobile Processes, Cambridge University Press.

Papers

• Milner Robin (1993). Elements of Interaction. Communication of ACM (jan 1993).

• Milner, R; J. Parrow and D. Walker (1989). A Calculus of Mobile Processes, Technical report ECS-LFCS-89-85, University of Edingburgh. (Abstract/PS, preprint of Information and Computation 100(1) pp.1-40, Sept 1992.)

• Milner, R., Parrow, J. and Walker, D. (1992). A calculus of mobile processes. Part I and II. Information and Computation, 100(1)

Indexes and bibliographies

• Selected Bibliography on Mobile Processes by Kohei Honda (last updated 1998 as of 15:35, 23 July 2010 (UTC)).

• Bibliography on Calculi for Mobile Processes (last update 2004 as of 15:35, 23 July 2010 (UTC))