ISSN:
1573-7640
Keywords:
Data flow scheme
;
abstract complexity measure
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract For common data flow schemes, the number of copies of tokens made during a computation is shown to be a Blum complexity measure.(1) 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00996925
Permalink