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.
展开▼
机译：作者提出了两种新的并行算法，用于在专用读取专用写入并行随机存取机（EREW PRAM）上匹配括号。第一种算法使用n个处理器和O（n）空间，并且需要O（log n）时间来匹配n个括号。第二种算法是成本最优的，并且使用O（/ sub logn /// sup n /）处理器和O（n log n）空间，并且需要O（log n）时间。这些算法比现有算法更简单，更优雅，并且为括号匹配问题提供了新的见解。
展开▼
