A new format for process algebras

V.C. Galpin

Seminar, Department of Computer Science, University of the Witwatersrand, May 1997


Since the development of CCS (Calculus of Communicating Systems) and other process algebras based on structured operational semantics, many extensions to these process algebras have been proposed to model different aspects of concurrent computation. It is important both theoretically and practically to understand the relationships between these process algebras and between the semantic equivalences that are defined for them. 

This talk is divided into three parts. I shall first describe process algebras, looking specifically at CCS and its extensions, and bisimulation equivalence, a standard semantic equivalence associated with CCS. An important property of semantic equivalences is congruence with respect to the operators of the language. The second part of the talk discusses formats -- a general approach to describing process algebras defined using operational semantics -- and describe how they can be used to achieve general congruence results. Finally, I shall then present a new format which is suitable for process algebras with non-atomic actions (a feature of most of the extensions to CCS) and derive a new congruence result.