Paper Info
Title
An optimal parallel algorithm for dynamic expression evaluation and its applications
Abstract
We describe a deterministic parallel algorithm to compute algebraic expressions in log n time using n/log(n) processors on a parallel random access machine without write conflicts (P-RAM) with no free preprocessing. The input to our algorithm is a string, given by an array, of the expression. Such a form for the input enables a consecutive numbering of the operands in the expression in log(n) time with n/log(n) processors. This corresponds to a consecutive numbering of leaves in the tree of the expression which further enables a suitable partitioning of the leaves into small segments. We improve the result of Miller and Reif (1985), who described an optimal parallel randomized algorithm. Our algorithm can be used to construct optimal parallel algorithms for the recognition of two nontrivial subclasses of context-free languages: bracket and input-driven languages. These languages are the most complicated context-free languages known to be recognizable in deterministic logarithmic space. This strengthens the result of Matheyses and Fiduccia (1982) who constructed an almost optimal parallel algorithm for Dyck languages, since Dyck languages are a proper subclass of input-driven languages.
Year
DOI
Venue
1986
10.1007/3-540-17179-7_28
FSTTCS
Keywords
Field
DocType
optimal parallel algorithm,dynamic expression evaluation,parallel algorithm,randomized algorithm,computer algebra,context free language,parallel random access machine
Numbering,Randomized algorithm,Binary logarithm,Discrete mathematics,Combinatorics,Parse tree,Parallel random-access machine,Computer science,Parallel algorithm,Binary tree,Algebraic expression
Conference
Volume
ISSN
ISBN
241
0302-9743
0-387-17179-7
Citations 
PageRank 
References 
24
1.88
5
Authors
2
Name
Order
Citations
PageRank
A. M. Gibbons1241.88
wojciech rytter213017.13