Axioms for concurrency
Faron Moller · ERA · 1989
We study properties of equational characterisations of congruences defined over process algebras.The languages on which we concentrate are based on CCS, and our equivalences are generally restricted to observational congruences.We start by defining and investigating the notion of extensionality or w-completeness of an axiomatisation with respect to some semantic equivalence, as an extension of simple completeness, and show that, whereas in some cases the ability to wcompletely axiomatise a system is straightforward, there are sometimes difficulties in doing this when our algebra contains the symmetric full merge operator.We then consider the problem of decomposing a process into the parallel composition of simpler processes.Here we present several example systems where we I would first like to record my gratitude to Robin Milner who demonstrated to me the recipe for a good supervisor: an abundant supply of inspiration, endless patience and encouragement, and a touch of gentle prodding when the results were slow coming.Further inspiration, scholarly debate, and fun were always on offer from Mads Dam and Andreas Knobel.They were both willing sounding boards to my ideas, offering illuminating comments which almost always shaped my viewpoint and outlook on the problems addressed by this thesis.After Robin and Mads and Andreas, my problems and ideas were then presented to the Wednesday afternoon Concurrency Club, where I was always guaranteed substantial and eager comments on the ideas, bringing them from half-to three-quarter-baked status.I thank all members of the Club who ever made a comment during one of my talks, as I am sure every comment made had its effect on the final product.I especially thank David Walker and Cohn Stirling for extra discussions and interest taken in my ideas outside of the Club.In the end, it was Chris Toftf who influenced' the later stages of the work and took an early draft of my thesis on a skiing holiday.Life was made enjoyable by numerous new friends I have made in Scotland, who made the experience of doing a thesis bearable.My thanks go out especially to Martin, Laurent, Lise, Murray and Ally.I