1 January 2022 in SSRN Electronic Journal
Establishing equivalences between programs or systems is crucial both for verifying correctness of programs and for justifying optimisations and program transformations. There exist several equivalence relations for programs, and bisimulations are among the most versatile of these equivalences. Among bisimulations one distinguishes strong bisimulation that requires that each action of a program is simulated by a single action of the equivalent program, and weak bisimulation that allows some of the actions to be invisible, and thus not simulated by the equivalent program.pNet is a generalisation of automata that model open systems. They feature variables and hierarchical composition. Open pNets are pNets with holes, i.e. placeholders inside the hierarchical structure that can be filled later by sub-systems. However, there is no standard tool for defining the semantics of an open system in this context, this article first defines open automata that are labelled transition systems with parameters and holes.Relying on open automata, this article defines bisimulation relations for the comparison of systems specified as pNets. We first define a strong bisimulation for open pNets. We then define an equivalence relation similar to the classical weak bisimulation, and study its properties. Among these properties we are interested in compositionality: if two systems are proven equivalent they will be undistinguishable by their context, and they will also be undistinguishable when their holes are filled with equivalent systems.We identify sufficient conditions to ensure compositionality of strong and weak bisimulation. The article is illustrated with a transport protocol running example.