Fast parallel recognition of LR language suffixes

DOI10.1016/J.IPL.2004.08.010zbMath1173.68526OpenAlexW2165384578MaRDI QIDQ834947

E. Bertsch, Mark-Jan Nederhof

Publication date: 27 August 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.08.010

zbMATH Keywords

computational complexityparallel algorithmsprogramming languages

Mathematics Subject Classification ID

Theory of programming languages (68N15) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Fast recognition of deterministic cfl's with a smaller number of processors
• On the parallel recognition of unambiguous context-free languages
• On the complexity of parallel parsing of general context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
• On efficient parallel computations of costs of paths on a grid graph
• Noncorrecting syntax error recovery
• Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
• Regular Closure of Deterministic Languages
• Linear-time suffix parsing for deterministic languages
• Parallel RAMs with owned global memory and deterministic context-free language recognition

This page was built for publication: Fast parallel recognition of LR language suffixes