Nonexpressibility of Fairness and Signaling
Permanent Link(s)
Collections
Author
McAllester, David
Panangaden, Prakash
Abstract
In this paper, we establish new expressiveness results for indeterminate dataflow primitives. We consider choice primitives with three differing fairness assumptions and show that they are strictly inequivalent in expressive power. We also show that the ability to announce choices enhances the expressive power of two of the primitives. These results are proved using a very crude semantics and thus apply in any reasonable theory of process equivalence.
Date Issued
1989-02
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR89-972
Type
technical report