BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/spans.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: Compositional Relational Semantics for Indeterminate
                   Dataflow Networks
        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:: May, 1989
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/spans.ps.gz
       NOTES:: A version of this paper appeared as:
                   E. W. Stark
                   Compositional Relational Semantics for Indeterminate
                       Dataflow Networks
                   Category Theory and Computer Science,
                       Manchester, England
                   pp. 52-74
                   Volume 389 of Lecture Notes in Computer Science
                   Springer-Verlag, 1989

ABSTRACT::

Given suitable categories T, C and functor F: T --> C,
if X, Y are objects of T, then we define an *(X, Y)-relation in* C
to be a triple (R, r0, r1), where R is an object of C and
r0: R --> FX and r1: R --> FY are morphisms of C.  We define an algebra
of relations in C, including operations of ``relabeling,''
``sequential composition,'' ``parallel composition,'' and
``feedback,'' which correspond intuitively to ways in which processes
can be composed into networks.  Each of these operations is defined in
terms of composition and limits in C, and we observe that any
operations defined in this way are preserved under the mapping from
relations in C to relations in C' induced by a continuous
functor G: C --> C'.

To apply the theory, we define a category AUTO of concurrent
automata, and we give an operational semantics of dataflow-like
networks of processes with indeterminate behaviors, in which a network
is modeled as a relation in AUTO.  We then define a category
EVDOM of ``event domains,'' a (non-full) subcategory of the
category of Scott domains and continuous maps, and we obtain a
coreflection between AUTO and EVDOM.  It follows, by the
limit-preserving properties of coreflectors, that the denotational
semantics in which dataflow networks are represented by relations in
EVDOM, is ``compositional'' in the sense that the mapping from
operational to denotational semantics preserves the operations on
relations.  Our results are in contrast to examples of Brock and
Ackerman, which imply that no compositional semantics is possible in
terms of set-theoretic relations.

END:: SBCS//stark/spans.dvi