  We study the complexity of the following problems in the streaming model.
  Membership testing for \DLIN We show that every language in \DLIN\ can be
recognised by a randomized one-pass $O(\log n)$ space algorithm with inverse
polynomial one-sided error, and by a deterministic p-pass $O(n/p)$ space
algorithm. We show that these algorithms are optimal.
  Membership testing for \LL$(k)$ For languages generated by \LL$(k)$ grammars
with a bound of $r$ on the number of nonterminals at any stage in the left-most
derivation, we show that membership can be tested by a randomized one-pass
$O(r\log n)$ space algorithm with inverse polynomial (in $n$) one-sided error.
  Membership testing for \DCFL We show that randomized algorithms as efficient
as the ones described above for \DLIN\ and $\LL(k)$ (which are subclasses of
\DCFL) cannot exist for all of \DCFL: there is a language in \VPL\ (a subclass
of \DCFL) for which any randomized p-pass algorithm with error bounded by
$\epsilon < 1/2$ must use $\Omega(n/p)$ space.
  Degree sequence problem We study the problem of determining, given a sequence
$d_1, d_2,..., d_n$ and a graph $G$, whether the degree sequence of $G$ is
precisely $d_1, d_2,..., d_n$. We give a randomized one-pass $O(\log n)$ space
algorithm with inverse polynomial one-sided error probability. We show that our
algorithms are optimal.
  Our randomized algorithms are based on the recent work of Magniez et al.
\cite{MMN09}; our lower bounds are obtained by considering related
communication complexity problems.
