BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/relations.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: On the Relations Computable by a Class of Concurrent
                   Automata
        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:: October, 1989
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/relations.ps.gz
       NOTES:: A version of this paper appeared as:
                   E. W. Stark
                   "On the Relations Computed by a Class of
                        Concurrent Automata,"
                   Seventeenth Annual ACM Symposium on Principles
                        of Programming Languages
                   pp. 329-340
                   ACM, 1990

ABSTRACT::

We consider *monotone input/output automata*, which model a
usefully large class of dataflow networks of indeterminate (or
nonfunctional) processes.  We obtain a characterization of the
relations computable by these automata, which states that a relation
R: X --> 2**Y (viewed as a ``nondeterministic function'') is
the input/output relation of an automaton iff there exists a certain
kind of Scott domain D, a continuous function F: X --> [D --> Y]
and a continuous function G: X --> Rel(D), such that
R(x) = <F(x)>(G(x)) for all inputs x in X.  Here Rel denotes a certain
powerdomain operator, and <F(x)> denotes the pointwise extension to Rel(D)
of the function F(x) on D.  An attractive feature of this result is that
it specializes to two subclasses of automata, *determinate* automata,
for which G is single-valued, and *semi-determinate* automata,
for which G is a constant function.  A corollary of the latter result is
the impossibility of implementing ``angelic merge'' by a network of
determinate processes and ``infinity-fair merge'' processes.

END:: SBCS//stark/relations.dvi