کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10333925 | 689839 | 2011 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Immunity and pseudorandomness of context-free languages
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 412, Issue 45, 21 October 2011, Pages 6432-6450
Journal: Theoretical Computer Science - Volume 412, Issue 45, 21 October 2011, Pages 6432-6450
نویسندگان
Tomoyuki Yamakami,