Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Computations, Residuals, and the Power of Indeterminacy

Computations, Residuals, and the Power of Indeterminacy

File(s)
87-883.ps (556.56 KB)
87-883.pdf (2.23 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6723
Collections
Computer Science Technical Reports
Author
Panangaden, Prakash
Stark, Eugene W.
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 $\extend$ on the set of computations of the network. For networks of "monotone port automata," we show that the "fair" computations coincide with $\extend$-maximal computations. Our results follow from this extremely convenient property.

Date Issued
1987-11
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-883
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance