Technical Report


The Algebra of Stream Processing Functions.


Author(s): Manfred Broy, Gheorghe Stefanescu
Year: 1996
Number: TUM-I9620
Editor:
CR Classification:
CR General Terms:
Keywords: Stream Processing Functions, Flownomials, Dataflow Networks, Basic Network Algebra
Abstract:Dataflow 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 dataflow networks and base their semantics on stream processing functions. The algebraic theory is provided by the calculus of flownomials which gives a unified presentation of regular algebra and iteration theories. The kernel of the calculus is an equational axiomatization called Basic Network Algebra (BNA) for flowgraphs 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. As a byproduct this shows that both semantic models are compositional. We also identify the additional axioms satisfied by the branching components that correspond to 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 behaviour and provide a correct and complete axiomatization.


Available as compressed Postscript

BibTeX-Entry:

@techreport{ TUM-I9620, author = {Manfred Broy and Gheorghe Stefanescu}, title = {The Algebra of Stream Processing Functions.}, number = {TUM-I9620}, institution = {Technische Univerit\"at M\"unchen}, year = {1996}, url = {http://www4.informatik.tu-muenchen.de/reports/TUM-I9620.html}, abstract = {Dataflow 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 dataflow networks and base their semantics on stream processing functions. The algebraic theory is provided by the calculus of flownomials which gives a unified presentation of regular algebra and iteration theories. The kernel of the calculus is an equational axiomatization called Basic Network Algebra (BNA) for flowgraphs 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. As a byproduct this shows that both semantic models are compositional. We also identify the additional axioms satisfied by the branching components that correspond to 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 behaviour and provide a correct and complete axiomatization. }, CRClassification = {}, CRGenTerms = {} }