On the complexity of parallel parsing of general context-free languages

DOI10.1016/0304-3975(86)90155-6zbMath0632.68081OpenAlexW1990225380MaRDI QIDQ1095675

Wojciech Rytter

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/60774/7/WRAP_cs-rr-075.pdf

zbMATH Keywords

context-free languagesparallel random-access machineparsing treetransitive closure of directed graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Theory of compilers and interpreters (68N20)

Related Items

Fast parallel recognition of LR language suffixes ⋮ Optimal parallel parsing of bracket languages ⋮ On efficient parallel computations for some dynamic programming problems ⋮ Parallel recognition and ranking of context-free languages ⋮ Parallel algorithms for a class of graphs generated recursively ⋮ On efficient parallel computations of costs of paths on a grid graph

Cites Work

• Tree-size bounded alternation
• An Efficient Parallel Biconnectivity Algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item