Parallel time O(log n) recognition of unambiguous context-free languages

DOI10.1016/0890-5401(87)90041-1zbMath0633.68075OpenAlexW2085339857MaRDI QIDQ1096400

Wojciech Rytter

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90041-1

zbMATH Keywords

parallel random access machinepolynomial number of processorsunambiguous context-free language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Fast parallel recognition of LR language suffixes ⋮ On efficient parallel computations for some dynamic programming problems ⋮ A parallel algorithm for the minimization of finite state automata ⋮ Parallel recognition and ranking of context-free languages ⋮ Unambiguous Boolean grammars ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ Unambiguity of circuits ⋮ Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's ⋮ Parallel algorithms for a class of graphs generated recursively ⋮ Optimal parallel algorithms for dynamic expression evaluation and context-free recognition ⋮ On efficient parallel computations of costs of paths on a grid graph ⋮ Restricted CRCW PRAMs ⋮ On the parallel recognition of unambiguous context-free languages

Cites Work

• Tree-size bounded alternation
• Parallelism in random access machines
• Unnamed Item

This page was built for publication: Parallel time O(log n) recognition of unambiguous context-free languages