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

DOI10.1007/3-540-55210-3_178zbMath1493.68394OpenAlexW1492683431MaRDI QIDQ5096776

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

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

Related Items (2)

An optimal sublinear time parallel algorithm for some dynamic programming problems ⋮ On a sublinear time parallel construction of optimal binary search trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parallel recognition of unambiguous context-free languages
• Time complexity of unambiguous path systems
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• On efficient parallel computations of costs of paths on a grid graph
• 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

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