Optimal parallel algorithms for dynamic expression evaluation and context-free recognition

DOI10.1016/0890-5401(89)90027-8zbMath0682.68046OpenAlexW2015439916MaRDI QIDQ1824389

Wojciech Rytter, Alan M. Gibbons

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0890-5401(89)90027-8

zbMATH Keywords

analysis of algorithmsparallel algorithmsparallel random access machinedynamic expression evaluationcontext-free recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45)

Related Items

Improved parallel depth-first search in undirected planar graphs, An optimal parallel algorithm for planar cycle separators, AN EFFICIENT EREW ALGORITHM FOR MINIMUM PATH COVER AND HAMILTONICITY ON COGRAPHS, Parallel evaluation of arithmetic circuits, A class of problems efficiently solvable on mesh-connected computers including dynamic expression evaluation, Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition, Parallel recognition and ranking of context-free languages, A time-optimal solution for the path cover problem on cographs., Parallel tree-contraction and Fibonacci numbers, On optimal parallel computations for sequences of brackets

Cites Work

• An introduction to parallelism in combinatorial optimization
• An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• Optimal parallel generation of a computation tree form
• Unnamed Item
• Unnamed Item
• Unnamed Item