 Abstract:

The finite picalculus has an explicit settheoretic 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 picalculus, and validate an existing construction as the universal such model.
<p>
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.
<p>
Based on our algebraic theory of pi we describe a category of models for the picalculus, 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 freealgebra models are fully abstract. We show how local modifications to the theory can give alternative models for piI and the early picalculus.
<p>
From this theory of pi we also obtain a Moggistyle 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 for concurrency, name generation, and communication.
 Links To Paper
 Page by publisher
 Bibtex format
 @Article{EDIINFRR1207,
 author = {
Ian Stark
},
 title = {FreeAlgebra Models for the PiCalculus},
 journal = {Theoretical Computer Science},
 publisher = {Elsevier},
 year = 2007,
 doi = {10.1016/j.tcs.2007.09.024},
 url = {http://dx.doi.org/10.1016/j.tcs.2007.09.024},
 }
