Process Algebra: Equational Theories of Communicating Processes
Lecturer: J.C.M. Baeten
- Introduction: Definition. Calculation. History. Contents
- Preliminaries: Notations. Equational theories. Algebras. Term rewriting systems.
- Transition systems: Transition-system spaces. Structural operational semantics.
- Basic process theory: Introduction. The process theory MPT. The term model. The empty process. Projection. Prefix iteration.
- Recursion: Introduction. Recursive specifications. Solutions of recursive specifications. The term model. Recursion principles. Recursion and BSP. Describing a stack. The projective limit model.
- Sequential processes: Sequential composition. The process theory TSP. The term model. Projection in TSP. Iteration. Recursion. Renaming, encapsulation, and skip operators.
- Parallel and communicating processes: Interleaving. The process theory BCP. The term model. Recursion, buffers and bags. The process theory TCP and further extensions. Alternating bit protocol (specification).
- Abstraction: Introduction. Transition systems with silent steps. BSP with silent steps. The term model. Abstraction, encapsulation and projection operators. TCP. Iteration and divergence. Recursion and fair abstraction. Alternating-bit protocol (verification).
- Timing: Introduction. Timed-transition systems. Discrete time, relative time. The term model. Time iteration and delayable actions. The relation between BSP and BSPdrt. The process theory TCPdrt. Fischer’s protocol.
- Data and states: Introduction. Guarded Command. Choice quantification. Propositional signals. State operator
- Features: Priorities. Probabilities. Parallel composition revisited.
- Semantics: Bisimulation and trace semantics. Failures and readiness semantics. The linear time — branching time lattice. Partial order semantics.
- J.C.M. Baeten, T. Basten and M.A. Reniers, Process algebra (equational theories of communicating processes), Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, to appear end 2006 or beginning 2007.
- J.C.M. Baeten and C.A. Middelburg, Process algebra with timing, Monographs in Theoretical Computer Science (an EATCS series), Springer Verlag 2002.