Streaming algorithms for language recognition problems

Babu, Ajesh ; Limaye, Nutan ; Radhakrishnan, Jaikumar ; Varma, Girish (2011) Streaming algorithms for language recognition problems Arxiv-eprints . pp. 1-21.

[img]
Preview
PDF - Author Version
236kB

Official URL: http://arxiv.org/pdf/1104.0848

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 d1, d2, . . . ,dn and a graph G, whether the degree sequence of G is pre- cisely d1, d2, . . . ,dn. 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.

Item Type:Article
Source:Copyright of this article belongs to Arxiv Publications.
Keywords:Streaming Algorithms; Randomized Algorithms; Communication Complexity; Context Free Language
ID Code:89492
Deposited On:27 Apr 2012 13:41
Last Modified:19 May 2016 04:01

Repository Staff Only: item control page