Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition

DOI10.1007/3-540-55210-3_178MaRDI QIDQ5096776zbMATH OpenOpenAlexFDO

Authors Lawrence L. Larmore, Wojciech Rytter

Publication date 18 August 2022

Published in STACS 92 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55210-3_178

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms (68W40) Dynamic programming (90C39) Parallel algorithms in computer science (68W10)

Recommendations

• Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
• An optimal sublinear time parallel algorithm for some dynamic programming problems
• On Efficient Parallel Algorithms for Solving Set Recurrence Equations
• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency
• On efficient parallel computations for some dynamic programming problems

Cites work

• scientific article; zbMATH DE number 4205991 (Why is no real title available?)
• scientific article; zbMATH DE number 3926247 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 52889 (Why is no real title available?)
• On efficient parallel computations of costs of paths on a grid graph
• On the parallel recognition of unambiguous context-free languages
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
• Speed of Recognition of Context-Free Languages by Array Automata
• Time complexity of unambiguous path systems

Cited in

(5)

• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• An optimal sublinear time parallel algorithm for some dynamic programming problems
• On Efficient Parallel Algorithms for Solving Set Recurrence Equations
• On a sublinear time parallel construction of optimal binary search trees
• Parallel algorithms for dynamic programming recurrences with more than \(O(1)\) dependency

This page was built for publication: Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096776)