Paper Info
Title
On optimal parallel computations for sequences of brackets
Abstract
We present an optimal parallel algorithm (log2 n time, n/log2 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 to expression-trees. Previously an optimal parallel algorithm for this problem was known (Bar-On, Vishkin (1985)) on a stronger model of parallel computations (CREW PRAM), where read conflicts were essential. It is not clear presently how big the difference is between the power of CREW and EREW PRAMs. 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 (Abrahamson et al. (1987); Brent (1974); Gibbons, Rytter (1986); Miller, Reif (1985)); recognition of input-driven languages (Gibbons, Rytter (1988)); transforming regular expressions to finite automata (Rytter (1987)) and parsing bracket languages (Rytter, Giancarlo (1987)). If the tree of the expression is given then the expression can be optimally evaluated on the EREW PRAM, see Cole, Vishkin (1988); Kosaraju, Delcher (1988). However optimal parallel transformation of expression to corresponding trees was previously known only on the CREW PRAM. The structure of our algorithm for computing the matching function is similar to that of Bar-On and Vishkin (1985). The matching function is computed in the preprocessing phase for a subset of O(n/log2n) brackets and later it guides the computation for all brackets. Our initial subset of brackets is a subset of that used in Bar-On, Vishkin (1985). It is small enough to eliminate read conflicts in the preprocessing phase, however it complicates other phases.
Year
DOI
Venue
1991
10.1016/0304-3975(91)90326-W
Theor. Comput. Sci.
Keywords
Field
DocType
optimal parallel computation
Discrete mathematics,Combinatorics,Regular expression,Outerplanar graph,Expression (mathematics),Parallel algorithm,Finite-state machine,Preprocessor,Parsing,Mathematics,Computation
Journal
Volume
Issue
ISSN
87
2
0304-3975
ISBN
Citations 
PageRank 
0-387-97186-6
2
0.38
References 
Authors
0
2
Name
Order
Citations
PageRank
wojciech rytter113017.13
Krzysztof Diks2665.83