Comparison of non-interleaving semantic equivalences

V.C. Galpin

Seminar, Concurrency Club, Laboratory for the Foundations of Computer Science, Department of Computer Science, University of Edinburgh, February 1995


Under interleaving semantic equivalences such as bisimilarity and observation equivalence, concurrency is equated with arbitrary interleaving of actions, so for example, equations such as a | b = ab + ba hold. Recently, a number of non-interleaving equivalences have been proposed in the literature. In this talk, I will describe some of the equivalences that have been defined for labelled transition systems. Examples are location equivalence, loose location equivalence, ST-bisimulation and causal bisimulation. I will discuss approaches to comparing these different equivalences and how this relates to the research I propose to do. 

Slides - PDF