6533b835fe1ef96bd129e919
RESEARCH PRODUCT
Parallel Algorithms for Listing Well-Formed Parentheses Strings
Vincent VajnovszkiJean Marcel Pallosubject
Gray codeSet (abstract data type)Shared memoryHardware and ArchitectureComputer scienceString (computer science)Parallel algorithmParallel random-access machineLexicographical orderTime complexityAlgorithmSoftwareTheoretical Computer Sciencedescription
We present two cost-optimal parallel algorithms generating the set of all well-formed parentheses strings of length 2n with constant delay for each generated string. In our first algorithm we generate in lexicographic order well-formed parentheses strings represented by bitstrings, and in the second one we use the representation by weight sequences. In both cases the computational model is based on an architecture CREW PRAM, where each processor performs the same algorithm simultaneously on a different set of data. Different processors can access the shared memory at the same time to read different data in the same or different memory locations, but no two processors are allowed to write into the same memory location simultaneously. These results complete a recent parallel generating algorithm for well-formed parentheses strings in a linear array of processors model, due to Akl and Stojmenović.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-03-01 | Parallel Processing Letters |