PARALLEL ALGORITHMS FOR EVALUATING SEQUENCES OF SET-MANIPULATION OPERATIONS

Given an off-line sequence S of n set-manipulation operations, we inve stigate the parallel complexity of evaluating S (i.e., finding the res ponse to every operation in S and returning the resulting set). We sho w that the problem of evaluating S is in NC for various combinations o f common set-manipulation operations. Once we establish membership in NC (or, if membership in NC is obvious), we develop techniques for imp roving the time and/or processor complexity.