BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/residuals.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: Computations, Residuals, and the Power of Indeterminacy
        TYPE:: Preprint
      AUTHOR:: Panangaden, Prakash, 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:: March, 1988
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/residuals.ps.gz
       NOTES:: A version of this paper appeared as:
                   P. Panangaden, E. W. Stark
                   "Computations, Residuals, and the Power of Indeterminacy,"
                   Automata, Languages, and Programming,
                   pp. 439-454
                   T. Lepisto and A. Salomaa (eds.)
                   Volume 317 of Lecture Notes in Computer Science
                   Springer-Verlag, 1988

ABSTRACT::

We investigate the power of Kahn-style dataflow networks, with
processes that may exhibit indeterminate behavior.  Our main result is
a theorem about networks of ``monotone'' processes, which shows: (1)
that the input/output relation of such a network is a total and
monotone relation; and (2) every relation that is total, monotone, and
continuous in a certain sense, is the input/output relation of such a
network.  Now, the class of monotone networks includes networks that
compute arbitrary continuous input/output functions, an ``angelic
merge'' network, and an ``infinity-fair merge'' network that exhibits
countably indeterminate branching.  Since the ``fair merge'' relation
is neither monotone nor continuous, a corollary of our main result is
the impossibility of implementing fair merge in terms of continuous
functions, angelic merge, and infinity-fair merge.

Our results are established by applying the powerful technique of
``residuals'' to the computations of a network.  Residuals, which have
previously been used to investigate optimal reduction strategies for
the lambda calculus, have recently been demonstrated by one of the
authors (Stark) also to be of use in reasoning about concurrent
systems.  Here, we define the general notion of a ``residual
operation'' on an automaton, and show how residual operations defined
on the components of a network induce a certain preorder $<=$ on
the set of computations of the network.  For networks of ``monotone
port automata,'' we show that the ``fair'' computations coincide with
<=-maximal computations.  Our results follow from this
extremely convenient property.

END:: SBCS//stark/residuals.dvi