Streaming algorithms for language recognition problems

Abstract

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 ε < ½ must use Ω(n/p) space. Degree sequence problem. We study the problem of determining, given a sequence d₁, d₂, . . . ,d_n and a graph G, whether the degree sequence of G is pre- cisely d₁, d₂, . . . ,d_n. We give a randomized one-pass O(log n) space algorithm with inverse polynomial one-sided error probability. We show that our algo- rithms 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 com- plexity problems.