A cost-optimal parallel algorithm for the parentheses matching problem on an EREW PRAM

The article presents a cost-optimal parallel algorithm for the parentheses matching problem on the EREW PRAM model. For n parentheses, the algorithm requires O(n/p+log n) time and O(n+p log p) space, employing p processors. Thus, for p⩽n/log n, it achieves optimal speedup, requiring O(log n ) time and O(n) space. Though the time complexity of the algorithm is comparable with those of the two existing cost-optimal algorithms on the same model, the new approach is simpler and utilizes an extended prefix-sum algorithm. Furthermore, its space requirement employs only (n/log n) processors