THE EXPRESSIVE POWER OF INDETERMINANT DATA-FLOW PRIMITIVES

被引：19

作者：

PANANGADEN, P ^{[1
]}

SHANBHOGUE, V ^{[1
]}

机构：

[1] CORNELL UNIV,DEPT COMP SCI,ITHACA,NY 14853

来源：

INFORMATION AND COMPUTATION | 1992年 / 98卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0890-5401(92)90043-F

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We analyze the relative expressive power of variants of the indeterminate fair merge operator in the context of static dataflow. We establish that there are three different, provably inequivalent, forms of unbounded indeterminacy. In particular, we show that the well-known fair merge primitive cannot be expressed with just unbounded indeterminacy. Our proofs are based on a simple trace semantics and on identifying properties of the behaviors of networks that are invariant under network composition. The properties we consider in this paper are all generalizations of monotonicity. © 1992.

引用

页码：99 / 131

页数：33

共 34 条

[1] AALBERSBERG IJ, 1983, THEORET COMPUT SCI, V60, P1
[2] ABRAMSKY S, 1983, 10TH P INT C AUT LAN, P1
[3] ABRAMSKY S, 1989, 1989 P S MATH F PROG
[4] PROOF RULES AND TRANSFORMATIONS DEALING WITH FAIRNESS
APT, KR
OLDEROG, ER
[J]. SCIENCE OF COMPUTER PROGRAMMING, 1983, 3 (01) : 65 - 100
[5] COUNTABLE NONDETERMINISM AND RANDOM ASSIGNMENT
APT, KR
PLOTKIN, GD
[J]. JOURNAL OF THE ACM, 1986, 33 (04) : 724 - 767
[6] BROCK JD, 1981, LECT NOTES COMPUT SC, V107, P252
[7] BROY M, 1983, FORMAL DESCRIPTION P, V2, P125
[8] DEBAKKER JW, 1984, THEORET COMPUT SCI, V34, P134
[9] Francez N., 1986, FAIRNESS
[10] JONSSON B, 1989, 16TH P ANN ACM S PRI

← 1 2 3 4 →