Recognizing well-parenthesized expressions in the streaming model

DOI10.1145/1806689.1806727zbMath1293.68149OpenAlexW2053966137MaRDI QIDQ2875152

Claire Mathieu, Frédéric Magniez, 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

communication complexitylinear hashinginformation coststreaming algorithmparenthesis expression

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (5)

Certifying equality with limited interaction ⋮ Streaming algorithms for language recognition problems ⋮ Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index

This page was built for publication: Recognizing well-parenthesized expressions in the streaming model