Speaker: Dr. Tomoyuki Yamakami
Title: Immunity and pseudorandomness of context-free languages
Context-free languages are a fundamental notion in formal languages and automata theory. In this seminar talk, I discuss the computational complexity of the context-free languages, concentrating on two well-known structural properties---immunity and pseudorandomness. An infinite language is called REG-immune (resp., CFL-immune) if it contains no infinite subset that is a regular (resp., context-free) language. Here, I explain the existence of REG-immune and CFL-immune languages inside and outside of advised language families. I also show that there is a CFL-simple set, where a CFL-simple language is an infinite context-free language whose complement is CFL-immune. A polynomially dense (p-dense) language is REG/n-primeimmune if it has no p-dense subsets that are advised regular. I show the existence of a context-free REG/n-bi-primeimmune language. Concerning pseudorandomness of context-free languages, I will show that CFL contains REG/n-pseudorandom languages. Finally, I turn to pseudorandom generators. I show that there exist two almost 1-1 pseudorandom generators against REG/n and against CFL/n, both of which are relatively easy to compute.
This seminar talk is based on the following three papers of mine:
(1) Immunity and pseudorandomness of context-free languages. Theor.
Comput. Sci. 412(45): 6432-6450 (2011)
(2) Pseudorandom generators against advised context-free languages.
Theor. Comput. Sci. 613: 1-27 (2016)
(3) Swapping Lemmas for Regular and Context-Free Languages with
Advice. CoRR abs/0808.4122 (2008)
Tomoyuki Yamakami received a Ph.D. Degree from the University of Toronto under supervision of Stephen A. Cook. He took a post-doctoral position at Princeton University before taking a position at the University of Ottawa and teaching at Trent University. He then took positions at the University of Aizu, Japan, and at the University of Fukui, Japan. He is currently a visiting professor at the University of Toronto between August 1, 2016 and March 30, 2017. His interest varies in computational complexity, automata theory, quantum computing, and mathematical logic.