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

DOI10.1016/0890-5401(87)90041-1zbMath0633.68075MaRDI 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 machine; polynomial number of processors; unambiguous context-free language

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

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

Cites Work

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