Synchronisation Flow Algebra

J. Parrow

Abstract: A synchronisation flow network is a network where independent processing units engage in synchronisations with each other and with the environment of the network. We explore an algebra for description of such networks. This algebra has two operators: disjoint parallelism, where the arguments are composed in parallel without any interconnections, and linking, whereby an interconnection is formed between two ports. The intention is that these operators correspond to the primitive steps when constructing interconnection structures. The results on this algebra are: (1) Expressibility of terms: with only three simple processing units, every finite state behaviour can be constructed. (2) Expressibility of operators: we characterise the operators which are expressible within the algebra. (3) Axiomatisation: We present an axiomatisation for valid equations which is sound and complete with respect to a large class of behaviour equivalences.

LFCS report ECS-LFCS-87-35

Previous | Index | Next