Comparison of process algebra equivalences using formats

V.C. Galpin

In J. Wiedermann, P. van Emde Boas, and M. Nielsen, (eds), ICALP '99, (International Colloquium on Automata, Languages and Programming), 26th Annual Colloquium of the EATCS (European Association of Theoretical Computer Science), Lecture Notes in Computer Science 1644, Prague, Czech Republic, 11-15 July 1999. Springer-Verlag, 341-350.


This research defines a new format called extended tyft/tyxt format. This format is able to express process algebras with structured or non-atomic labels and their bisimulation-based semantic equivalences. A general notion of bisimulation is a congruence for this format, under reasonable technical conditions. The aim of this format is to allow the comparison of bisimulation-based semantic equivalences and to this end, this paper defines a number of extensions and gives results showing conditions required to achieve the extensions. This paper also discusses the process algebras that can be expressed in this format and presents a new semantic equivalence comparison result for multiprocessor bisimulation and pomset bisimulation. 

Slides - PDF 


Back to Publications page