Recognizing Well-Parenthesized Expressions in the Streaming Model

Motivated by a concrete problem and with the goal of understanding the relationship between the complexity of streaming algorithms and the computational complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with s different types of parentheses. We present a one-pass randomized streaming algorithm for Dyck(2) with space of ${O}(\sqrt{n\log n}\,)$ bits, time per letter ${polylog}(n)$, and one-sided error. We prove that this one-pass algorithm is optimal, up to a $\log n$ factor, even when two-sided error is allowed. Surprisingly, the space requirement shrinks drastically if we have access to the input stream in reverse. We present a two-pass randomized streaming algorithm for Dyck(2) with space of ${O}((\log n)^2)$, time polylog(n) and one-sided error, where the second pass is in the reverse direction. Both algorithms can be extended to Dyck(s) since this problem is reducible to Dyck(2) for a suitable notion of reduction in the streaming model. Except for an e...