On optimal parallel computations for sequences of brackets

We present an optimal parallel algorithm (log₂n time, n/ log₂n processors) for computing the matching function for a sequence of brackets and for transforming sequences of brackets to trees on the parallel access machine without read and write conflicts (EREW PRAM). It gives also an optimal parallel transformation on EREW PRAM of texts of expressions and expression-trees. Previously an optimal parallel for this problem was known [2] on a stronger model of parallel computations (CREW PRAM), in [2] read conflicts were essential. It is not clear presently how big is the difference of the power of CREW and EREW PRAM’s. Our result implies optimal parallel algorithms on EREW PRAM for several other algorithmic problems which previously had optimal parallel algorithms only on a CREW PRAM: expression evaluation [1,3,5,7], recognition of input-driven languages [6], transforming regular expressions to finite automata [9] and parsing bracket languages [8]. The structure of our algorithm for computing the matching function is similar to that of Bar-on and Vishkin [2]. The matching function is computed in the preprocessing phase for a subset of O(n/ log₂n) brackets and later it guides the computation for all brackets. Our initial subset of brackets is a subset of that used in [2]. It is small enough to eliminate read conflicts in the preprocessing phase, however it complicates other phases.