Streaming algorithms for language recognition problems

We study the complexity of the following problems in the streaming model.Membership testing forDLIN. We show that every language in DLIN  can be recognized by a randomized one-pass O(logn) space algorithm with an 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 forLL(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(rlogn) space algorithm with an inverse polynomial (in n) one-sided error.Membership testing forDCFL. We show that randomized algorithms as efficient as the ones described above for DLIN  and (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 an error bounded by ϵ<1/2 must use Ω(n/p) space.Degree sequence problem. We study the problem of determining, given a sequence d1,d2,…,dn and a graph G, whether the degree sequence of G is precisely d1,d2,…,dn. We give a randomized one-pass O(logn) space algorithm with an 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.  [1]; our lower bounds are obtained by considering related communication complexity problems.