Name
Abstract | ||
|---|---|---|
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 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 @e |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.tcs.2012.12.028 | Theoretical Computer Science |
Keywords | DocType | Volume |
randomized algorithm,language recognition problem,membership testing forll,membership testing fordlin,randomized one-pass o,inverse polynomial one-sided error,space algorithm,one-sided error,membership testing fordcfl,deterministic p-pass o,randomized p-pass algorithm,automata theory,lower bound,data structure,degree sequence,error probability,formal language,streaming algorithm,communication complexity | Journal | 494, |
ISSN | Citations | PageRank |
0304-3975 | 2 | 0.42 |
References | Authors | |
21 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ajesh Babu | 1 | 7 | 1.20 |
| Nutan Limaye | 2 | 134 | 20.59 |
| Jaikumar Radhakrishnan | 3 | 1123 | 96.04 |
| Girish Varma | 4 | 45 | 9.38 |