On optimal parallel computations for sequences of brackets

Wojciech Rytter and Krzysztof Diks
Additional contact information
Wojciech Rytter: Warsaw University, Institute of Informatics
Krzysztof Diks: Warsaw University, Institute of Informatics

A chapter in Sequences, 1990, pp 92-102 from Springer

Abstract: 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 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/ log2 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.

Keywords: Regular Expression; Finite Automaton; Matching Function; Outerplanar Graph; Reduced Sequence (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_7

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().