Two Erew Algorithms For Parentheses Matching

We present two new parallel algorithms for matching parentheses on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). The first algorithm uses n processors and O(n) space, and requires O(logn)time to match n parentheses. The second algorithm is cost-optimal, and uses O(n/log n) processors and O(n log n) space, and it requires O(log n)time. These algorithms are simpler and more elegant than the existing ones, and provide new insights into the parentheses matching problem