Parallel Program Schemata and Maximal Parallelism II: Construction of Closures

Document Type

Article

Department

Computer Science (HMC)

Publication Date

10-1973

Abstract

The phenomenon of maximal parallelism is investigated in the framework of a class of parallel program schemata. Part II is concerned with the actual realization of closures of schemata represented as "flowcharts." In the case that the flowchart is acyclic there is always a closure which is finite-state realizable. However in the case of cyclic flowcharts this is not generally true. Then realizations which are not finite-state are investigated. Of special concern is the class of counter realizations and the class of queue realizations, both a type of "real-time" automaton. It is shown that these form a proper hierarchy in the set of realizations for closures of flowcharts. A class of flowcharts is then presented all of which have queue realizations of their closure. It is shown that for this class, the existence of a finite-state realization for the closure is decidable.

Rights Information

©1973 Association for Computing Machinery

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Link to Full Text

Share

COinS