Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages

DOI10.1016/S0304-3975(97)00253-3MaRDI QIDQ1128670zbMATH OpenFDO

Authors Lawrence L. Larmore, Wojciech Rytter

Publication date 13 August 1998

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(97)00253-3

zbMATH Keywords

context-free languagesparallel computationssublinear time

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45) Distributed algorithms (68W15)

Recommendations

• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
• On the parallel recognition of unambiguous context-free languages
• Parallel recognition and ranking of context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• scientific article; zbMATH DE number 3917742

Cites work

• An optimal sublinear time parallel algorithm for some dynamic programming problems
• Fast recognition of deterministic cfl's with a smaller number of processors
• 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?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (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

Cited in

(7)

• Some subclasses of context-free languages in NC^ 1
• A lower bound for the nondeterministic space complexity of context-free recognition
• Fast nondeterministic recognition of context-free languages using two queues
• scientific article; zbMATH DE number 176524 (Why is no real title available?)
• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
• Parallel recognition and ranking of context-free languages
• Fast parallel recognition of LR language suffixes

This page was built for publication: Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages

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