Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Article type: Research Article
Authors: Stark, Eugene W.
Affiliations: Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794-4400 USA
Note: [] Research supported in part by NSF Grant CCR-8902215. E-mail address: stark@cs.sunysb.edu (Internet)
Abstract: This paper describes an algebraic framework for the study of dataflow networks, which form a paradigm for concurrent computation in which a collection of concurrently and asynchronously executing processes communicate by sending messages between ports connected via FIFO message channels. A syntactic dataflow calculus is defined, having two kinds of terms which represent networks and computations, respectively. By imposing suitable equivalences on networks and computations, we obtain the free dataflow algebra, in which the dataflow networks with m input ports and n output ports are regarded as the objects of a category Snm, and the computations of such networks are represented by the arrows. Functors defined on Snm label each computation by the input buffer consumed and the output buffer produced during that computation, so that each Snm is a span in Cat. It is shown that the free dataflow algebra construction underlies a monad in the category of collections S = {Snm : m, n ≥ 0} of spans in Cat. The algebras of this monad, called dataflow algebras, have a monoid structure representing parallel composition, and are also equipped with an action of a certain collection of continuous functions, thereby representing the formation of feedback loops. The two structures are related by a distributive law of feedback over parallel composition. We also observe the following connection with the theory of fibrations: if S is a dataflow algebra, then each Snm is a split bifibration in Cat.
DOI: 10.3233/FI-1995-22128
Journal: Fundamenta Informaticae, vol. 22, no. 1-2, pp. 167-185, 1995
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
sales@iospress.com
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
info@iospress.nl
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office info@iospress.nl
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
china@iospress.cn
For editorial issues, like the status of your submitted paper or proposals, write to editorial@iospress.nl
如果您在出版方面需要帮助或有任何建, 件至: editorial@iospress.nl