The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited

DOI10.1109/TIT.2014.2339859zbMath1360.94077arXiv1004.3165OpenAlexW2964014335MaRDI QIDQ2986125

Ashwin Nayak, Rahul Jain

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1004.3165

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Detection theory in information and communication theory (94A13)

Related Items (5)

Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Streaming algorithms for language recognition problems ⋮ Quantum conditional mutual information and approximate Markov chains ⋮ Everywhere-Tight Information Cost Tradeoffs for Augmented Index ⋮ Quantum Chebyshev's Inequality and Applications

This page was built for publication: The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited