Why does deterministic recognition of DYCK(2) languages in the streaming model take linear space?

Question

I was reading the paper "Recognizing Well-Paranthesized Expressions in the Streaming Model" by Magniez, Mathieu and Nayak where they give upper and lower bounds on the space required to recognize DYCK(2) languages in the streaming model. Quoting a sentence from the introduction section of the paper - "Using a straightforward one-way communication complexity argument for EQUALITY, we can deduce that DYCK(2) requires linear space for deterministic one-pass streaming algorithms." Can anyone see the straightforward argument? (I can't, but perhaps I am being blind.)

Some background -

DYCK(2) languages are basically sequences of two kinds of parantheses that are well-formed. For example, the sequence [()] is in DYCK(2), but the sequence [(]) is not.

One-way communication complexity of EQUALITY refers to the following problem. Alice and Bob both have one n-bit string each. Alice does some computation on her bits and sends some information to Bob. Bob can do computation on this information plus his bits and has to decide whether his n-bit string is exactly equal to Alice's bit string or not. It can be shown using simple communication complexity arguments that the number of bits that must be communicated is $\Omega(n)$.

Communication complexity lower bounds are often used for proving lower bounds for streaming algorithms. The usual scheme is the following. Suppose the problem you want to solve in streaming is P. Pick a communication complexity problem P' for which you know of a lower bound on the number of bits that need to be communicated. Then assume that the problem P can be solved in the streaming model using $o(f(n))$ space. Now in the communication complexity problem P', assume that Alice has as her input the first few bits of the input for P (or some mapping of the first few bits to something else). Then assume that the protocol they use for communication is that Alice runs the streaming algorithm on her input, sends the working space to Bob and then Bob finishes off using his input. In the end, prove that the solution to the streaming problem somehow gives a solution for the communication complexity problem. This will show that the communication complexity problem can be solved with $o(f(n))$ bits of complexity. The trick is to choose $f(n)$ in such a way that this leads to a contradiction.

Answer 1

Consider the restricted case in which the opening parentheses all come before the closing ones. Map ( and ) to 0, and [ and ] to 1. Then (after the map) an expression is well formed if and only if the first half is equal to the second half reversed.

Consider then a one-pass streaming algorithm that solves this restricted version of the problem in sublinear space. Using the construction in your question, to get a protocol for the equality problem with sublinear communication, Alice runs the streaming algorithm on her input (mapping 0 to ( and 1 to [), sends the working space to Bob, and Bob finishes off using the reverse of his input (mapping 0 to ) and 1 to ]). The streaming algorithm will output that the sequence of parentheses is well formed iff their original inputs are equal.