On the parallel recognition of unambiguous context-free languages

DOI10.1016/0304-3975(91)90199-CMaRDI QIDQ808269zbMATH OpenOpenAlexFDO

Authors Michal Chytil, Maxime Crochemore, Wojciech Rytter, Burkhard Monien

Publication date 1991

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

Full work available at URL https://doi.org/10.1016/0304-3975(91)90199-c

zbMATH Keywords

CREW PRAMparallel complexityrecognition of context-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Grammars and rewriting systems (68Q42)

Recommendations

• Parallel time O(log n) recognition of unambiguous context-free languages
• scientific article; zbMATH DE number 3917742
• Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's
• Parallel RAMs with owned global memory and deterministic context-free language recognition
• Parallel recognition and ranking of context-free languages

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 3960999 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• On efficient parallel computations of costs of paths on a grid graph
• Parallel time O(log n) recognition of unambiguous context-free languages
• Time complexity of unambiguous path systems
• Tree-size bounded alternation

Cited in

(21)

• Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's
• scientific article; zbMATH DE number 3917742 (Why is no real title available?)
• scientific article; zbMATH DE number 3978426 (Why is no real title available?)
• scientific article; zbMATH DE number 3960999 (Why is no real title available?)
• Fast parallel recognition of LR language suffixes
• scientific article; zbMATH DE number 4033108 (Why is no real title available?)
• Bounded length UCFG equivalence
• Parallel time O(log n) recognition of unambiguous context-free languages
• Parallel RAMs with owned global memory and deterministic context-free language recognition
• A simple proof of Valiant's lemma
• scientific article; zbMATH DE number 2219896 (Why is no real title available?)
• Efficient parallel and incremental parsing of practical context-free languages
• Fast recognition of deterministic cfl's with a smaller number of processors
• scientific article; zbMATH DE number 7453188 (Why is no real title available?)
• On Efficient Parallel Algorithms for Solving Set Recurrence Equations
• Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
• scientific article; zbMATH DE number 176524 (Why is no real title available?)
• Parallel recognition and ranking of context-free languages
• Fast nondeterministic recognition of context-free languages using two queues
• On efficient parallel computations of costs of paths on a grid graph
• Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition

This page was built for publication: On the parallel recognition of unambiguous context-free languages

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