E0 222 Automata Theory and Computability
Teaching Assistants: Sabuj Kumar Jena (firstname.lastname@example.org), Inzemamul Haque (email@example.com)
Automata and Logic: Buchi's logical characterization of regular
languages; Automata-based decision procedures for logics of natural
numbers with order (N,<); logic of natural numbers with + (N,+)
(Presburger logic); Undecidability of (N,+,x); Algebraic approach to
regular languages, the syntactic monoid and relation to the
Pushdown Systems: Parikh's theorem on semi-linearity of CFL's;
Reachability in pushdown systems, saturation algorithm for Pre* and
Post*; Deterministic PDA's and complementation; Visibly Pushdown
Automata; Decidability results for PDA's and subclasses like
Automata on infinite words: Closure properties of omega-regular
languages, including closure under complementation; Deterministic
Buchi automata; Revisiting Buchi's logical characterization.
Automata on Trees: Closure properties, decision procedures,
congruences and minimization.
06-08-2015: Course overview.
11-08-2015: Recap on Finite State Automata.
13-08-2015, 18-08-2015, 20-08-2015: Buchi's logical characterization of regular languages.
25-08-2015: Automata-based Decision Procedure for Presburger Logic.
01-09-2015: Myhill-Nerode Theorem.
10-09-2015: Algebraic approach to automata.
- 29-09-2015: Intro to Context-Free Grammars. Slides.
- 08-10-2015: Parikh's Theorem. Slides.
- 15-10-2015: Intro to PDA's. Slides.
- 20-10-2015: Equivalence of PDA's and CFG's. Slides.
- 22-10-2015 and 27-10-2015: Reachability in Pushdown Systems. Slides.
- 29-10-2015: Complementing DPDA's. Slides.
- 10-11-2015: Visibly Pushdown Automata. Slides.
- 12-11-2015: Intro to Turing Machines. Slides.
- 16-11-2015: Undecidability of the Halting Problem. Slides.
- 17-11-2015: Reductions Slides.
- 19-11-2015: Undecidabile problems about CFL's. Slides.
- 23-11-2015: Godel's incompleteness theorem. Slides.
- Books and other material
Dexter Kozen: Automata and Computability. Springer 1999.
Hopcroft J.E. and Ullman J.D.: Introduction to Automata, Languages
and Computation. Addison Wesley, 1979.
Wolfgang Thomas: Automata on infinite objects, in Handbook of
Theoretical Computer Science, Volume B, Elsevier, 1990.
- H. R. Lewis and C. H. Papadimitriou: Elements of the
Theory of Computation. Prentice Hall, 1981.
- Deepak D'Souza and Priti Shankar (Eds.): Modern Applications of
Automata Theory, World Scientific, 2012.
- Note on Buchi's MSO characterisation of regular
Wolfgang Thomas: Notes on applied automata theory
- Chapter by Comon and Kirschner (see Chapter 2, Section 2.8 on Presburger Logic).
- Chapter by Straubing and Weil.
- Visibly Pushdown Automata by Alur and Madhusudan.
- Seminar Topics
- Angluin's algorithm for learning regular languages. Ezudheen, 5pm, Wed 28 Oct 2015. Slides.
- A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971). Shinjini Biswas and Ramit Hansdah, Wed 4th Nov, 5:00pm.
- Proof of Shuzteberger-McNaughton-Papert theorem (FO=star-free=counter-free=aperiodic monoid). Soumya and Harsha. 5:30pm, Fri 13 Nov. Slides.
- Applications of Context Free Grammar in Natural Language Processing. Harit Vishwakarma and Vishal Kakkar. 5pm Wed 18th Nov. Slides.
- Probabalistic DFA's. Ashish Srivastava and Harshil Pathak. 5pm Fri 27th Nov. Slides.
- Undecidability of validity problem of First-Order Logic.
(see Rob van Glabbeek's notes). Prerak Dhoot and Nirmalendu Prakash. 11:00 Tue 1st Dec.
- Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger. Mohammand and Jawad, 12:00pm Tue 1st Dec.
- Automata on Trees. Sajiv Kumar, 2:00pm, Tue 1st Dec.
- Combinatorial Contextual Grammars. Gopu and Ashwin. 3:00pm, Tue 1st Dec.
- Nested word automata. Paper by Alur and Madhusudan. (Pankaj + Yogesh) 10:00am, 2nd Dec.
- Context Sensitive Grammars and Linear Bounded Automata. (Manohar + Lucky) 11:00am, 2nd Dec.
- Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966).
Raghuram Bharadwaj and Sudhir Babu. 12:00pm 2nd Dec.
- Undecidability of Post's Correspondence Problem. Deshant, Hariom, and ?, 2:00pm, Wed 2nd Dec.
- Angluin's algorithm for alternating Automata. Shivam Gupta, 5:30pm Wed 2nd Dec.
- Collapsing Non-deterministic automata. Vipin Nagar and Rahul Hasija, 6:30pm Wed 2nd Dec.
Weightage for evaluation:
Mid-semester Exam: 20%
Assignments (Lab + written) + Seminar: 40%
Final Exam: 40%
Current meeting schedule: Tue, Thu, 2:00 pm, CSA Lecture Hall
- Exam Schedule:
10:00am, Fri October 2, 2015.
2:00pm, Wed 9th Dec 2015..