TREE-BASED PARALLEL ALGORITHM DESIGN

In this paper a systematic method for the design of efficient parallel algorithms for the dynamic evaluation of computation trees and/or exp ressions is presented. This method involves the use of uniform closure properties of certain certain classes of unary functions. Using this method, optimal parallel algorithms are given for many computation tre e problems which are important in parallel algebraic and numerical com putation, and parallel code generation on exclusive read and exclusive write parallel random access machines. Our algorithmic result is comp lemented by a P-complete tree problem.