On the parallel recognition of unambiguous context-free languages

DOI10.1016/0304-3975(91)90199-CzbMath0731.68063OpenAlexW1975185331MaRDI QIDQ808269

Wojciech Rytter, Maxime Crochemore, Michal Chytil, Burkhard Monien

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90199-c

zbMATH Keywords

parallel complexityCREW PRAMrecognition of context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Grammars and rewriting systems (68Q42)

Related Items (7)

Fast parallel recognition of LR language suffixes ⋮ Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages ⋮ Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition ⋮ Parallel recognition and ranking of context-free languages ⋮ Efficient parallel and incremental parsing of practical context-free languages ⋮ Fast recognition of deterministic cfl's with a smaller number of processors ⋮ Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's

Cites Work

• Parallel time O(log n) recognition of unambiguous context-free languages
• Tree-size bounded alternation
• Time complexity of unambiguous path systems
• On efficient parallel computations of costs of paths on a grid graph
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the parallel recognition of unambiguous context-free languages