Two EREW algorithms for parentheses matching
Sushil K. Prasad, Narsingh Deo · 2002
The authors 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(log n) time to match n parentheses. The second algorithm is cost-optimal, and uses O(/sub logn///sup 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.>