Paper Info
Title
On the Complexity of Parallel Parsing of General Context-free Languages
Abstract
Let T ( n ) be the time to recognize context-free languages on a parallel random-access machine without write conflicts (P-RAM) using a polynomial number of processors. We assume that T(n) = Ω( log n) . Let P ( n ) be the time to compute a representation of a parsing tree for strings of length n using a polynomial number of processors. Then we prove P ( n ) = O( T ( n )). A related result is a parallel time log n computation of the transitive closure of directed graphs having special structure.
Year
DOI
Venue
1986
10.1016/0304-3975(86)90155-6
Theor. Comput. Sci.
Keywords
DocType
Volume
general context-free language,Parallel Parsing,parallel parsing,General Context-free Languages
Journal
47
Issue
ISSN
Citations 
3
Theoretical Computer Science
9
PageRank 
References 
Authors
1.49
2
1
Name
Order
Citations
PageRank
wojciech rytter113017.13