Project proposal on automata theory and computation

Seminar Topics
Deciding Presburger Arithmetic using automata. paper by Comon. Arvind and Mallesham 17 September. Slides.
Arden's Theorem, and Kleene Algebra. Vinod Jadhao and Sravan, 1st October.
Regularity preserving relations. See also writeup by Kozen. Madhav and Adinarayana, 14 October, 5:00pm. Slides.
A linear algorithm for testing equivalence of finite automata, J.E. Hopcroft and R.M.Karp (1971). Bhavana and Gurpreet. 15 October, 5:30pm. Slides.
Regular approximation of CFGs, Harikrishna and Shalini, 22 October. Slides.
Collapsing Non-deterministic automata. Punya Murthy and Prabhakaran. 29 October.
Two-way DFA's. Girish Maskeri Rama. 11 November. Slides.
Interface Automata. Jay Thakkar and Amogh Margoor. 12 November. Slides.
CKY parsing algorithm and CFL reachability. Ravindra and Suresh. 18 November.
Context Sensitive Grammars and Linear Bounded Automata. Arvind S R and Omesh Pandita Seminar. 19 November.
Undecidability of Post Correspondence Problem and Tiling Problem. Raghunandan. 25 November.
Mu-recursive functions capture Turing computable functions. 26 November.
Derivatives of Regular expressions (paper by Brzozowski). See also Regular expressions to DFA's (paper by Berry and Sethi). Parag Jambhulkar. 5:00pm 6th December. Slides.
The Chomsky-Schutzenberger theorem.