Necessity of Timing Dependency in Parallel Programming Laguages

摘要

There are two classes of dataflow schemeata DF and AKF. ADF is known to be equivalent to EF and DF. the class of ordinary dataflow schemata, is known to be equiv-alent to EF~d. ADF is given by strengthening with two devices compared with DF, the class of ordinary dataflow schemata. One is recursion and the other is arbiter which allows timing dependent processing. We are interested in whether both devices are necessary for ADF to have such powerful expression ability. In this paper, we examine ex-pression ability of the class RDF which is strengthened with just recursion than DF. As an result we whow RDF is also equivalent to EF~d, which means that wome kind of tim-ing dependency is necessary for the class of dataflow sche-mata to be powerful enough.