Parallel recognition and ranking of context-free languages

DOI10.1007/3-540-55808-X_3zbMath1493.68192MaRDI QIDQ5096817

Peter Rossmanith, Wojciech Rytter, Klaus-Joern Lange

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55808-x_3

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68W10: Parallel algorithms in computer science

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel tree-contraction and Fibonacci numbers
• 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 the recognition of parallel 2D-image languages
• On optimal parallel computations for sequences of brackets
• Optimal parallel parsing of bracket languages
• Parallel parsing of programming languages
• On the complexity of parallel parsing of general context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• On efficient parallel computations for some dynamic programming problems
• Parallel parsing on the connection machine
• Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages
• Tree-size bounded alternation
• Unambiguity of circuits
• Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
• A note on optimal parallel transformations of regular expressions to nondeterministic finite automata
• On efficient parallel computations of costs of paths on a grid graph
• The complexity of ranking simple languages
• Optimal parallel generation of a computation tree form
• Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
• Complexity of some problems concerningL systems
• Upper Bounds for Speedup in Parallel Parsing
• Speed of Recognition of Context-Free Languages by Array Automata
• Parallelism in random access machines