Browse Prior Art Database

Parallel Algorithms for Parenthesis Matching and Generation of Random Balanced Sequences of Parenethes

IP.com Disclosure Number: IPCOM000128316D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 32K

Publishing Venue

Software Patent Institute

Related People

Dilip Sarkar: AUTHOR [+4]

Abstract

The computation model used in this paper is concurrent-read, exclusive-write, parallel random-access machine (CREW-PRAM), where the processors may read simultaneously from a common memory, but cannot write simultaneously into the same memory cell.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Parallel Algorithms for Parenthesis Matching and Generation of Random Balanced Sequences of Parenethes

by

Dilip Sarkar and Narsingh Deo

CS-TR-87-03

PARALLEL ALGORITHMS FOR PARENTHESIS MATCHING AND

GENERATION OF RANDOM BALANCED SEQUENCES OF PARENTHESES

Dilip Sarkar Narsingh Deo

Department of Computer Science University of Central Florida Orlando, FL 32816 0001

PARALLEL ALGORITHMS FOR PARENTHESIS MATCHING AND GENERATION OF RANDOM BALANCED SEQUENCES OF PARENTHESES

Dilip Sarkar Narsingh Deo

Parallel parenthesis-matching algorithm has in the past been used to design paral-lel 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 0 (log n) time on a (n / log n)-processor CREW-PRAM. We also present an 0 (log n)-time parallel algorithm for generation of random sequences of parentheses. These two algorithms can be used to design an 0 (log n)-time parallel algorithm for generation of a class of random permutations.

L INTRODUCTION

The computation model used in this paper is concurrent-read, exclusive-write, parallel random- access machine (CREW-PRAM), where the processors may read simultaneously from a common memory, but cannot write simultaneously into the same memory cell.

In this paper, we consider the parenthesis-matching problem. The problem is to find the matching parenthesis for each parenthesis in a given "legal" sequence of n parrentheses. By "legal" it is meant that every parenthesis has its matching parenthesis in the sequence. It is easy to construct an 0 (n)-time sequential algorithm for the prob-lem. Bar-On and Vishkin [21 have proposed an 0 (log n)-time parallel parenthesis-matching algorithm and used it to design an optimal parallel algorithm for generation of computation tree forms. To design the algorithm for parallel generation of computa-tion tree form they'have adopted the parenthesis-insertion technique of Knuth [6]. Their 0 (log n)-time parallel algorithm on a (n /log n)-processor CREW- PRAM is an improvement over Dekel and Sahni's [5) algorithm for construction of computation tree forms of arithmetic expressions on an EREW-PRAM. The motivation behind their con- struction of computation tree forms in logarithmic time is logarithmic-time arithmetic expression evaluation algorithms of Brent [31 and Miller and Reif [7). They have shown that if the

University of Central Florida Page 1 Dec 31, 1987

Page 2 of 12

Parallel Algorithms for Parenthesis Matching and Generation of Random Balanced Sequences of Parenethes

computation tree of an arithmetic expression is given, the expression can be evaluated in 0 (log
n)-time using n processors, even if the height of the com-putation tree is greater than log n. Sarkar and Deo [8) have shown that a cl...