Parallel and sequential transformations on digital images (Q1064066)

In this paper, the relation between parallel and sequential algorithms is discussed. The author regards algorithms as definitions of transformations and investigates the relation between the sets of transformations defined by parallel and sequential algorithms, respectively. Three problems are treated mainly: (1) Characterization of transformations which are both parallel and sequential - A necessary and sufficient condition for a transformation to be both parallel and sequential is established. (2) Equivalence problems - The equivalence problem for two algorithms, one of which is parallel, is decidable. Hence, the equivalence problem for two sequential algorithms is undecidable. Namely, an algorithm for deciding whether or not two given algorithms, one of which is parallel, define the same transformation is presented. However, it is shown that there is no algorithm for deciding whether or not two given sequential algorithms define the same transformation. (3) Translation problems - An algorithm for translating a parallel (sequential) algorithm into an equivalent sequential (parallel) algorithm is presented. Some other important problems are still left open: (1) investigation of transformations which are defined by combinations of parallel algorithms and those of sequential algorithms; (2) making the neighborhood form, which is fixed in section 5, free, i.e. investigation of the equivalence problem for a certain parallel algorithm and a certain sequential algorithm.