E0 222 Automata Theory and Computability

Teaching Assistants: Inzemamul Haque.

• Course outline
  • 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 Myhill-Nerode theorem.
  • 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 Counter Automata.
  • 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.

• Lectures
  1. 02-08-2018: Course overview, Viraj's slides.
  2. 07-08-2018: Recap on Finite State Automata.
  3. 14-08-2018, 16-08-2018, 21-08-2018: Buchi's logical characterization of regular languages.
  4. 23-08-2018, 30-08-2018: Automata-based Decision Procedure for Presburger Logic.
  5. 04-09-2018: Myhill-Nerode Theorem (Viraj).
  6. 06-09-2018: Myhill-Nerode Theorem (Deepak).
  7. 11-09-2018, 18-09-2018: Algebraic approach to automata.
  8. 20-09-2018: Intro to Context-Free Grammars.
  9. 25-09-2018: Mid-sem exam.
  10. 04-10-2018: Discussion of mid-sem paper.
  11. 09-10-2018: Chomsky Normal Form, ultimate periodicity for Regular langauges.
  12. 16-10-2018: Pumping Lemma and Parikh's Theorem for CFLs. Goldstine's proof of Parikh's Theorem.
  13. 18-10-2018: Recursive Automata.
  14. 23-10-2018: Pushdown Automata.
  15. 25-10-2018: Equivalence of PDAs and CFGs.
  16. 30-10-2018: Pushdown Reachability.
  17. 06-11-2018: Complementing DPDAs.
  18. 08-11-2018: Visibly Pushdown Languages.
  19. 13-11-2018: Intro to Turing Machines. Slides.
  20. 15-11-2018: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
  21. 20-11-2018: More Undecidable Problems and Reductions.
  22. 22-11-2018: Undecidable problems about CFL's. Slides.
  23. 27-11-2018: Godel's incompleteness theorem. Slides.

• Books and other material
  1. Dexter Kozen: Automata and Computability. Springer 1999.
  2. Hopcroft J.E. and Ullman J.D.: Introduction to Automata, Languages and Computation. Addison Wesley, 1979.
  3. Wolfgang Thomas: Automata on infinite objects, in Handbook of Theoretical Computer Science, Volume B, Elsevier, 1990.
  4. H. R. Lewis and C. H. Papadimitriou: Elements of the Theory of Computation. Prentice Hall, 1981.
  5. Deepak D'Souza and Priti Shankar (Eds.): Modern Applications of Automata Theory, World Scientific, 2012.
  6. Note on Buchi's MSO characterisation of regular languages.
  7. Wolfgang Thomas: Notes on applied automata theory
  8. Chapter by Comon and Kirschner (see Chapter 2, Section 2.8 on Presburger Logic).
  9. Chapter by Straubing and Weil.
  10. Visibly Pushdown Automata by Alur and Madhusudan.

• Assignments
  • Assignment 1 due on Tue 04 September 2018.
  • Assignment 2 due on Thu 04 October 2018.
  • Assignment 3 due on Mon 12 November 2018.
  • Assignment 4 due on Mon 03 December 2018.

• Seminar Topics
  • Buchi Automata. Deepak and Nabarun, 12pm, Fri 25 October 2019.
  • Angluin's algorithm for learning regular languages. Pranshul and Utkarsh.
  • Nested word automata.
  • Direct automaton construction for Parikh's Theorem. Paper by Esparza, Ganty, Kiefer, Luttenberger.
  • Probabalistic Context-Free Grammars. Soumik.
  • Automata on Trees.
  • Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966). Adithya and Rohit.
  • Schutzenberger's aperiodic monoid characterization of star-free languages.
  • Context Sensitive Grammars and Linear Bounded Automata. Prajwal Koul.
  • Undecidability of validity problem of First-Order Logic. (see Rob van Glabbeek's notes).
  • Proof of Shuztenberger-McNaughton-Papert theorem (FO=star-free=counter-free=aperiodic monoid).
  • Undecidability of Post's Correspondence Problem. Arnab Chatterjee.

• Weightage for evaluation:
  • Mid-semester Exam: 20%
  • Assignments + Quiz + Seminar: 40%
  • Final Exam: 40%

• Current meeting schedule: Tue, Thu, 2:00 pm, CSA Room 252.

• Exam Schedule:
  • Mid-semester Exam: 2:00pm, Thu 27 September 2018.
  • Final Exam: 2:00pm, Thu 6th December 2018.