Recognizing well-parenthesized expressions in the streaming model

DOI10.1145/1806689.1806727MaRDI QIDQ2875152zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

streaming algorithmcommunication complexitylinear hashinginformation costparenthesis expression

Mathematics Subject Classification ID

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)

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

Cited in

(9)

• Augmented index and quantum streaming algorithms for \textsc{Dyck}(2)
• Everywhere-Tight Information Cost Tradeoffs for Augmented Index
• Streaming algorithms for language recognition problems
• Certifying equality with limited interaction
• Streaming algorithms for some problems in log-space
• Lower Bounds for Testing Computability by Small Width OBDDs
• Streaming algorithms for recognizing nearly well-parenthesized expressions
• 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

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)