A complexity measure for data flow models

For common data flow schemes, the number of copies of tokens made during a computation is shown to be a Blum complexity measure.⁽¹⁾ Results from abstract complexity theory (see Ref. 2) then hold for the copy measure, indicating, for example, that any implementation of a data flow processor will be constrained by its ability to copy tokens. The copy measure is a natural measure of complexity for data flow computations, and is distinct from the usual time or space measures. The result is generalized to a wider class of data flow schemas, including those with an apply operator. An example is also given of a data flow scheme which makes no copies.Supported in part by NSF Grant MCS 83-01536 and NSA OCREAE Grant MDA904-85-H-0002.