Almost fully-parallel parentheses matching

DOI10.1016/0166-218X(93)E0137-NzbMath0814.68071WikidataQ126527625 ScholiaQ126527625MaRDI QIDQ1345960

Uzi Vishkin, Omer Berkman

Publication date: 19 March 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

parentheses matching problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items

Finding level-ancestors in trees, An optimal parallel algorithm for computing a near-optimal order of matrix multiplications

Cites Work

• Unnamed Item
• Unnamed Item
• Parallel parsing of programming languages
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• A new parallel algorithm for parsing arithmetic infix expressions
• Parallel approximation algorithms for bin packing
• Parallel Generation of Postfix and Tree Forms
• Fast Algorithms for Finding Nearest Common Ancestors
• Optimal parallel generation of a computation tree form
• Relations between Concurrent-Write Models of Parallel Computation
• Parallel Prefix Computation
• Finding the maximum, merging, and sorting in a parallel computation model
• Recursive Star-Tree Parallel Data Structure
• Parallelism in Comparison Problems
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs