A new format for process algebras

V.C. Galpin

Unpublished conference presentation, Joint Conference of the American Mathematical Society, the South African Mathematical Society and the Southern African Mathematical Sciences Association, Pretoria, South Africa, June 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. In this talk, I will first briefly 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. I will next look at the meta-theory of process algebras and describe the notion of a format which is a signature and set of rules satisfying certain conditions that can be used to define process algebras. As the main focus of the talk, I will 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. 

Slides - PDF