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

DOI10.1109/TIT.2014.2339859zbMath1360.94077arXiv1004.3165MaRDI 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

94A12: Signal theory (characterization, reconstruction, filtering, etc.)

94A13: Detection theory in information and communication theory

Related Items

Everywhere-Tight Information Cost Tradeoffs for Augmented Index