Title

Parallel Algorithms For Parenthesis Matching And Generation Of Random Balanced Sequences Of Parentheses

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Keywords

Computer Science; Theory & Methods

Abstract

Parallel parenthesis-matching algorithm has in the past been used to design parallel algorithms for generation of computation tree forms and parsing. In this paper we present a parallel parenthesis-matching algorithm. A variant of binary search tree is constructed in parallel. The search tree is used to find the matching of each parenthesis. The algorithm takes O(log n) time on a (n / log n)-processor CREW-PRAM. We also present an O(log n)-time parallel algorithm for generation of random sequences of parentheses. These two algorithms can be used to design an O(log n)-time parallel algorithm for generation of a class of random permutations.

Journal Title

Environmental Geology and Water Sciences

Volume

297

Publication Date

1-1-1988

Document Type

Article

Language

English

First Page

970

Last Page

984

WOS Identifier

WOS:A1988N195300057

ISSN

0302-9743

Share

COinS