Nonexpressibility of fairness and signaling

摘要

In this paper we establish new expressiveness results for indeterminate datatlow primitives. We consider split primitives with three differing fairness assumptions and show that they are strictly inequivalent in expressive power. We also show that the ability to announce internal choices enhances the expressive power of two of the primitives. These results are proved using a very crude notion of observation and thus apply in any reasonable theory of process equivalence.