The Expressive Power of Parallelism

We explore an algebraic language for networks consisting of a fixed number of reactive units, communicating synchronously over a fixed linking structure. The language has only two operators: disjoint parallelism, where two networks are composed in parallel without any interconnection, and linking, where an interconnection is formed between two ports. The intention is that these operators corresponds to the primitive steps when constructing networks, and that they therefore are conceptually simpler than the operators in existing process algebras. We investigate the expressive power of our language. The results are: (1) Definability of behaviours: with only three simple processing units, every finite-state behaviour can be constructed. (2) Definability of operators: we characterize the network operators which are definable within the language; these turn out to include most operators previously suggested for describing parallelism. Our results hold for any congruence between trace equivalence and observation equivalence.Original report number R90016. (Revised and extended version of the paper "The Expressive power of simple parallelism" in the proceedings of PARLE '89 Vol. II, Eindhoven, June 1989, publ. as Springer Verlag LNCS 366 pages 389-405.)