Communicating Automata and the Pi Calculus

Robin Milner

Computer Laboratory


This course lays some of the detailed groundwork for theories of (mobile) interactive systems. It is based on my book (CUP, not expensive!) "Communicating and Mobile Systems: the Pi Calculus". See also a more advanced book (also CUP) "A Theory of Mobile Processes; the Pi Calculus" by Davide Sangiorgi and David Walker.

Communicating automata: Where classical automata theory falls short; Add non-determinism and interaction; Structural congruence and labelled transition systems; Bisimilarity, strong and weak; Examples: a lottery, a jobshop.

Pi calculus: Movement by communicating names, scope extrusion; Examples: mobile phones, disciplined resource use; Transitions and bisimilarity extended; Data structures as processes; Pi calculus as a basic model of computation.