Show simple item record

dc.contributor.authorPanangaden, Prakashen_US
dc.contributor.authorStark, Eugene W.en_US
dc.date.accessioned2007-04-23T17:23:13Z
dc.date.available2007-04-23T17:23:13Z
dc.date.issued1987-11en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-883en_US
dc.identifier.urihttps://hdl.handle.net/1813/6723
dc.description.abstractWe 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.en_US
dc.format.extent2341983 bytes
dc.format.extent569915 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleComputations, Residuals, and the Power of Indeterminacyen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics