The algebra of stream processing functions

Data flow networks are a model of concurrent computation. They consist of a collection of concurrent asynchronous processes which communicate by sendi ng data over FIFO channels. In this paper we study the algebraic structure of the data flow networks and base their semantics on stream processing fun ctions. Our algebraic theory is based on the calculus of flownomials. With an additive (or cantorian) interpretation the calculus gives a unified pres entation of the classical algebraic models for control structures, that is, regular algebra and iteration theories. The kernel of the calculus is an e quational a axiomatization called basic network algebra (BNA) for flow grap hs module graph isomorphism. We show that the algebra of stream processing functions called SPF (used for deterministic networks) and the algebra of s ets of stream processing functions called PSPF (used for nondeterministic n etworks) are BNA algebras. Actually they give a multiplicative (or cartesia n) interpretation of the calculus of flownomials. As a byproduct this shows that both semantic models are compositional. This means the semantics of a network may be described in terms of the semantics of its components. (As it is well known this is not true for the input-output relational semantics of nondeterministic networks.) We also identify additional axioms satisfie d by the branching constants in these two algebraic theories. For the deter ministic case we study in addition the coarser equivalence relation on netw orks given by the input-output behavior and provide a correct and complete axiomatization. (C) 2001 Elsevier Science B.V. All rights reserved.