Free-algebra models for the π-calculus

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

The finite π-calculus has an explicit set-theoretic functor-category model that is known to be fully abstract for strong late bisimulation congruence. We characterize this as the initial free algebra for an appropriate set of operations and equations in the enriched Lawvere theories of Plotkin and Power. Thus we obtain a novel algebraic description for models of the π-calculus, and validate an existing construction as the universal such model. The algebraic operations are intuitive, covering name creation, communication of names over channels, and nondeterministic choice; the equations then combine these features in a modular fashion. We work in an enriched setting, over a "possible worlds" category of sets indexed by available names. This expands significantly on the classical notion of algebraic theories: we can specify operations that act only on fresh names, or have arities that vary as processes evolve. Based on our algebraic theory of π we describe a category of models for the π-calculus, and show that they all preserve bisimulation congruence. We develop a direct construction of free models in this category; and generalise previous results to prove that all free-algebra models are fully abstract. We show how local modifications to the theory can give alternative models for πI and the early π-calculus. From the theory of π we also obtain a Moggi-style computational monad, suitable for a programming language semantics of mobile communicating systems. This addresses the challenging area of correctly combining computational monads: in this case those for concurrency, name generation, and communication.

Original languageEnglish
Pages (from-to)248-270
Number of pages23
JournalTheoretical Computer Science
Volume390
Issue number2-3
DOIs
Publication statusPublished - 2008

Keywords / Materials (for Non-textual outputs)

  • Nominal sets

Fingerprint

Dive into the research topics of 'Free-algebra models for the π-calculus'. Together they form a unique fingerprint.

Cite this