Recognizing well-parenthesized expressions in the streaming model
DOI10.1145/1806689.1806727zbMATH Open1293.68149OpenAlexW2053966137MaRDI QIDQ2875152FDOQ2875152
Authors: Frédéric Magniez, Claire Mathieu, Ashwin Nayak 
Publication date: 13 August 2014
Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.192.5237
Recommendations
- Recognizing well-parenthesized expressions in the streaming model
- Streaming algorithms for recognizing nearly well-parenthesized expressions
- scientific article; zbMATH DE number 1833419
- Streaming algorithms for language recognition problems
- Information cost tradeoffs for augmented index and streaming language recognition
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cited In (9)
- Streaming algorithms for language recognition problems
- Recognizing well-parenthesized expressions in the streaming model
- Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
- Everywhere-Tight Information Cost Tradeoffs for Augmented Index
- Streaming algorithms for some problems in log-space
- Lower Bounds for Testing Computability by Small Width OBDDs
- Augmented index and quantum streaming algorithms for \textsc{Dyck}(2)
- Certifying equality with limited interaction
- Streaming algorithms for recognizing nearly well-parenthesized expressions
This page was built for publication: Recognizing well-parenthesized expressions in the streaming model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875152)
