The Library
Optimal parallel parsing of bracket languages
Tools
Tools
Tools
Rytter, Wojciech and Giancarlo, Raffaele (1985) Optimal parallel parsing of bracket languages. University of Warwick. Department of Computer Science. (Department of Computer Science Research Report). (Unpublished)
|
PDF
WRAP_cs-rr-085.pdf - Requires a PDF viewer. Download (10Mb) | Preview |
Abstract
We prove that the parsing problem for bracket context-free languages can be solved in log(n) time using n/log(n) processors on a parallel random access machine without write conflicts (P-RAM). On the way we develop a new general technique for tree compression based on the bracket structure of the tree.
| 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): | Parsing (Computer grammar) | ||||
| Series Name: | Department of Computer Science Research Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | October 1985 | ||||
| Dates: |
|
||||
| Number: | Number 85 | ||||
| Number of Pages: | 12 | ||||
| DOI: | CS-RR-085 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | W. Rytter and R. Giancarlo, “Optimal Parallel Parsing of Bracket Languages”, <i>Theoretical Computer Science</i> <b>53</b>(2-3), pp. 295-306 (1987) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
