Streaming algorithms for language recognition problems
Streaming algorithms for language recognition problems
复制标题
DOI：
10.1016/j.tcs.2012.12.028
复制
发表时间：
2013-07-08
影响因子：
1.1
通讯作者：
Varma, Girish
中科院分区：
文献类型：
--
作者：
Babu, Ajesh;Limaye, Nutan;Varma, Girish
我们研究了流模型中以下问题的复杂性：DLIN的成员测试。我们发现，DLIN中的每一种语言都可以通过一个随机的单通O（log n）空间算法与逆多项式单侧误差和确定性的p-通O（n/p）空间算法来识别。我们证明了这些算法是最优的。LL（k）的成员检验。对于由LL（k）文法生成的语言，在最左边的推导的任何阶段，非终结符的数量的界限为r，我们证明了成员资格可以通过一个随机的一次通过O（rlog n）空间算法进行测试，具有逆多项式（in n）单侧错误。我们证明了，对于DLIN和LL（k）（它们是DCFL的子类）来说，不可能存在与上述算法一样有效的随机算法：在VPL（DCFL的子类）中存在一种语言，对于这种语言，任何误差小于1/2的随机p遍算法都必须使用Omega（n/p）空间。我们研究的问题确定，给定一个序列d（1），d（2），. . .，d（n）和一个图G，判定G的度序列是否恰好为d（1），d（2），. . .，d（n）.我们给出了一个随机的单程O（log n）空间算法与逆多项式单侧错误概率。我们证明了我们的算法是最优的。我们的随机化算法是基于Magniez等人[1]最近的工作;我们的下界是通过考虑相关的通信复杂性问题得到的。(c)2013 Elsevier B. V.保留所有权利。
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 epsilon < 1/2 must use Omega(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. (c) 2013 Elsevier B.V. All rights reserved.