Characterizations and computational complexity of some models of parallel computation
Sam Myo Kim · 1983
The primary objective of this thesis is to investigate the problems related to structually restricted but powerful models of parallel computation. Specifically, we investigate three different systolic models: Trellis automata (TA's), binary tree automata (BTA's) and linear iterative arrays (LIA's). We characterize these models and their variations in terms of simple Turing machines. The characterizations are then used to prove new results as well as give simpler proofs of known results concerning the models. Some open problems in the literature are also settled. Since the characterizations allow one to convert sequential programs for the sequential machines into parallel programs for the parallel models (and vice versa), the sequential machines can be used as programming tools for the parallel models.