Pi-Calculus

From EduTech Wiki
Jump to: navigation, search

This article or section is a stub. A stub is an entry that did not yet receive substantial attention from editors, and as such does not yet contain enough information to be considered a real article. In other words, it is a short or insufficient piece of information and requires additions.

Draft

1 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.

2 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)).

3 Bibliography and links

Slides
FAQs
(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