BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/fibrations.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: Dataflow Networks are Fibrations
        TYPE:: Preprint
      AUTHOR:: Stark, Eugene W.
     CONTACT:: Eugene W. Stark, Department of Computer Science,
                   SUNY at Stony Brook, Stony Brook, NY 11794-4400
                   Tel: 516-632-8444 <stark@cs.sunysb.edu>
	DATE:: February, 1990
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/fibrations.ps.gz
       NOTES:: A version of this paper appeared as:
                   E. W. Stark,
                   "Dataflow Networks are Fibrations"
                   Proceedings of the Summer Conference on Category Theory
                      and Computer Science
                   Springer LNCS 530
                   pp. 261-281
                   September, 1991.

ABSTRACT::

Dataflow networks are a paradigm for concurrent computation in which
a collection of concurrently and asynchronously executing processes
communicate by sending messages over FIFO message channels.  In a
previous paper, we showed that dataflow networks could be represented
as certain spans in a category of automata, or more abstractly, in a
category of domains, and we identified some universal properties of
various operations for building networks from components.  Not all
spans corresponded to dataflow processes, and we raised the question
of what might be an appropriate categorical characterization of those
spans that are ``dataflow-like.''  In this paper, we answer this
question by obtaining a characterization of the dataflow-like spans as
*split right fibrations*, either in a 2-category of automata or a
2-category of domains.  This characterization makes use of the theory
of fibrations in a 2-category developed by Street.  In that theory,
the split right fibrations are the algebras of a certain doctrine (or
2-monad) R on a category of spans.  For the 2-categories we
consider, R has a simple interpretation as an ``input buffering''
construction.

END:: SBCS//stark/fibrations.dvi