The Library
An optimal parallel algorithm for dynamic expression evaluation and its applications
Tools
Tools
Tools
Gibbons, Alan (Alan M.) and Rytter, Wojciech (1986) An optimal parallel algorithm for dynamic expression evaluation and its applications. Coventry, UK: University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-077.pdf - Requires a PDF viewer. Download (11Mb) | Preview |
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 confilects (P-RAM) with no free preprocessing. This improves the result of Miller and Reif (1985), who described an optimal parallel randomized algorithm. Our algorithm can be used to construct an optimal parallel algorithm 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.
Using our algorithm we show also that preorder and postorder numberings of the nodes of a tree can be computed by optimal parallel algorithms.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Parallel algorithms | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Place of Publication: | Coventry, UK | ||||
| Official Date: | April 1986 | ||||
| Dates: |
|
||||
| Number: | Number 77 | ||||
| Number of Pages: | 16 | ||||
| DOI: | CS-RR-077 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
