Immunity and pseudorandomness of context-free languages
Immunity and pseudorandomness of context-free languages
复制标题
上下文无关语言的免疫性和伪随机性
DOI：
10.1016/j.tcs.2011.07.013
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
T. Yamakami
中科院分区：
文献类型：
--
作者：
T. Yamakami
我们讨论了上下文无关语言的计算复杂度，重点讨论了两个众所周知的结构特性——免疫和伪随机。无限语言不受regg的影响。， cfl免疫)，如果它不包含无限子集是正则的(例如。（上下文无关）语言。我们证明(i)在REG/n之外存在一种上下文无关的REG-免疫语言，（ii）存在一种可以使用对数空间确定性计算的REG-双免疫语言。我们还证明（iii）存在一个CFL-simple集合，其中CFL-simple语言是一个无限的上下文无关语言，其补体是cfl免疫的。与reg免疫相似，reg原免疫语言没有多项式密集的正则子集。我们进一步证明（iv）存在REG/n-双源免疫的上下文无关语言。关于上下文无关语言的伪随机性，我们证明(v) CFL包含REG/n-伪随机语言。最后，我们证明了（vi）针对REG/n，在配置了只写输出磁带的非确定性下推自动机中存在可计算的几乎1-1伪随机生成器；（vii）针对REG，不存在单磁带图灵机在线性时间内可确定计算的几乎1-1弱伪随机生成器。
We discuss the computational complexity of context-free languages, concentrating on two well-known structural properties—immunity and pseudorandomness. An infinite language is REG-immune (resp., CFL-immune) if it contains no infinite subset that is a regular (resp., context-free) language. We prove that (i) there is a context-free REG-immune language outside REG/n and (ii) there is a REG-bi-immune language that can be computed deterministically using logarithmic space. We also show that (iii) there is a CFL-simple set, where a CFL-simple language is an infinite context-free language whose complement is CFL-immune. Similar to the REG-immunity, a REG-primeimmune language has no polynomially dense subsets that are also regular. We further prove that (iv) there is a context-free language that is REG/n-bi-primeimmune. Concerning pseudorandomness of context-free languages, we show that (v) CFL contains REG/n-pseudorandom languages. Finally, we prove that (vi) against REG/n, there exists an almost 1–1 pseudorandom generator computable in nondeterministic pushdown automata equipped with a write-only output tape and (vii) against REG, there is no almost 1–1 weakly pseudorandom generator computable deterministically in linear time by a single-tape Turing machine.
DOI：
10.1016/j.tcs.2009.08.031
发表时间：
2003-10
期刊：
ArXiv
影响因子：
--
作者：
K. Tadaki;T. Yamakami;Jack C. H. Lin
通讯作者：
K. Tadaki;T. Yamakami;Jack C. H. Lin
资源有限免疫力和简单性
DOI：
--
发表时间：
2005
期刊：
Theoretical Computer Science 347
影响因子：
--
作者：
M.Kumabe;T.Suzuki;T.Yamazaki;Tomoyuki Yamakami(Toshio Suzukiと連名)
通讯作者：
Tomoyuki Yamakami(Toshio Suzukiと連名)