Title

Two Erew Algorithms For Parentheses Matching

Abstract

We present two new parallel algorithms for matching parentheses on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). The first algorithm uses n processors and O(n) space, and requires O(logn)time to match n parentheses. The second algorithm is cost-optimal, and uses O(n/log n) processors and O(n log n) space, and it requires O(log n)time. These algorithms are simpler and more elegant than the existing ones, and provide new insights into the parentheses matching problem.

Publication Date

1-1-1991

Publication Title

Proceedings - 5th International Parallel Processing Symposium, IPPS 1991

Number of Pages

126-131

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/IPPS.1991.153767

Socpus ID

84914919501 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84914919501

This document is currently not available here.

Share

COinS