Two EREW algorithms for parentheses matching

摘要

The authors present two new parallel algorithms for matchingparentheses on an exclusive-read exclusive-write parallel random-accessmachine (EREW PRAM). The first algorithm uses n processors andO(n) space, and requires O(log n) time to match n parentheses. The second algorithm is cost-optimal, and usesO(_logn/ⁿ) processors and O(n log n) space, and it requires O(log n) time. These algorithmsare simpler and more elegant than the existing ones, and provide newinsights into the parentheses matching problem