On efficient parallel computations of costs of paths on a grid graph

DOI10.1016/0020-0190(88)90031-2zbMath0682.68061OpenAlexW86786547MaRDI QIDQ1824395

Wojciech Rytter

Publication date: 1988

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(88)90031-2

zbMATH Keywords

parallel computationcontext-free languagesEREW PRAMparallel recognitioncost of paths in dags

Mathematics Subject Classification ID

Related Items (6)

Fast parallel recognition of LR language suffixes ⋮ Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages ⋮ Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition ⋮ Parallel recognition and ranking of context-free languages ⋮ Context-free recognition via shortest paths computation: a version of Valiant's algorithm ⋮ On the parallel recognition of unambiguous context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of parallel parsing of general context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• Tree-size bounded alternation
• Parallelism in random access machines

This page was built for publication: On efficient parallel computations of costs of paths on a grid graph