The algebra of stream processing functions

Manfred Broy, Gheorghe Tefnescu

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)99-129
Number of pages31
JournalTheoretical Computer Science
Volume258
Issue number1-2
DOIs
StatePublished - 2001

Fingerprint

Dive into the research topics of 'The algebra of stream processing functions'. Together they form a unique fingerprint.

Cite this