ISSN:
1573-7640
Schlagwort(e):
Data flow scheme
;
abstract complexity measure
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF00996925
Permalink