TY - JOUR
T1 - The algebra of stream processing functions
AU - Broy, Manfred
AU - Tefnescu, Gheorghe
N1 - Funding Information:
The 5rst author was partially supported by the DFG within Sonderforschungsbereich 342 “Werkzeuge und Methoden fuAr die Nutzung paralleler Rechnerarchitekturen”. The second author was partially supported by a DAAD grant and by the Graduate School for Logics and Informatics, Technische UniversitA at and Ludwig-Maximilians-UniversitaAt MuAnchen. ∗Corresponding author. E-mail address: [email protected] (M. Broy), [email protected] (G. S(tefa)nescu).
PY - 2001
Y1 - 2001
N2 - Data flow networks are a model of concurrent computation. They consist of a collection of concurrent asynchronous processes which communicate by sending data over FIFO channels. In this paper we study the algebraic structure of the data flow networks and base their semantics on stream processing functions. Our algebraic theory is based on the calculus of flownomials. With an additive (or cantorian) interpretation the calculus gives a unified presentation of the classical algebraic models for control structures, that is, regular algebra and iteration theories. The kernel of the calculus is an equational axiomatization called basic network algebra (BNA) for flow graphs modulo graph isomorphism. We show that the algebra of stream processing functions called SPF (used for deterministic networks) and the algebra of sets of stream processing functions called PSPF (used for nondeterministic networks) are BNA algebras. Actually they give a multiplicative (or cartesian) 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 satisfied by the branching constants in these two algebraic theories. For the deterministic case we study in addition the coarser equivalence relation on networks given by the input-output behavior and provide a correct and complete axiomatization.
AB - Data flow networks are a model of concurrent computation. They consist of a collection of concurrent asynchronous processes which communicate by sending data over FIFO channels. In this paper we study the algebraic structure of the data flow networks and base their semantics on stream processing functions. Our algebraic theory is based on the calculus of flownomials. With an additive (or cantorian) interpretation the calculus gives a unified presentation of the classical algebraic models for control structures, that is, regular algebra and iteration theories. The kernel of the calculus is an equational axiomatization called basic network algebra (BNA) for flow graphs modulo graph isomorphism. We show that the algebra of stream processing functions called SPF (used for deterministic networks) and the algebra of sets of stream processing functions called PSPF (used for nondeterministic networks) are BNA algebras. Actually they give a multiplicative (or cartesian) 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 satisfied by the branching constants in these two algebraic theories. For the deterministic case we study in addition the coarser equivalence relation on networks given by the input-output behavior and provide a correct and complete axiomatization.
UR - http://www.scopus.com/inward/record.url?scp=0034911434&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(99)00322-9
DO - 10.1016/S0304-3975(99)00322-9
M3 - Article
AN - SCOPUS:0034911434
SN - 0304-3975
VL - 258
SP - 99
EP - 129
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -