Structural and Behavioural Equivalences of Networks

Parrow, Joachim (1990) Structural and Behavioural Equivalences of Networks. [SICS Report]



We define an algebraic language for networks of synchronously communicating processes. A node in the Network may have several ports; a port is either external to the whole network or connected through a link to another port. The language contains two types of operations: parallel composition of two networks, and interlinking of two external ports within a network. We interpret this language in two ways: first we give a structural semantics, where terms are mapped to graphs representing the structure of networks, and second we give a behavioural semantics, where terms are mapped to behaviour schemes. A schema corresponds to a behaviour parameterised on the behaviours of the network nodes. These semantics give rise to structural and behavioural equivalences. We compare the equivalences and give sound and complete axiomatisations.

Item Type:SICS Report
Additional Information:Original report number R90015. (Revised and extended version of a paper that appeared under the same title in the Proceedings of the 17th Colloquium on Automata, Languages and Programming, Warwick University, July 1990; Published as Springer Verlag LNCS 443 pages 540-552.)
ID Code:2093
Deposited By:Vicki Carleson
Deposited On:22 Oct 2009
Last Modified:18 Nov 2009 15:59

Repository Staff Only: item control page