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

DOI10.1016/S0304-3975(97)00253-3zbMath0902.68097MaRDI QIDQ1128670

Wojciech Rytter, Lawrence L. Larmore

Publication date: 13 August 1998

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

zbMATH Keywords

context-free languagesparallel computationssublinear time

Mathematics Subject Classification ID

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

Related Items (2)

Fast parallel recognition of LR language suffixes ⋮ Parallel recognition and ranking of context-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• An optimal sublinear time parallel algorithm for some dynamic programming problems
• On efficient parallel computations of costs of paths on a grid graph

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