Matching parentheses in parallel

Parallel algorithms for evaluating arithmetic expressions generally assume the computation tree form to be at hand. The computation tree form can be generated within the same resource bounds as the parenthesis matching problem can be solved. The authors provide a new cost optimal parallel algorithm for the latter problem, which runs in time O(logn) using O(n/logn) processors on an EREW PRAM. They also prove that the algorithm is the fastest possible independently of the number of processors available.