TCS Journal 2013 Journal Article
Streaming algorithms for language recognition problems
- Ajesh Babu
- Nutan Limaye
- Jaikumar Radhakrishnan
- Girish Varma
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 recognized by a randomized one-pass O ( log n ) 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 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 an 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 an error bounded by ϵ < 1 / 2 must use Ω ( 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 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.