E0 222 Automata Theory and Computability

Teaching Assistants: Julian D'Costa and Rekha Pai.

• 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. 05-08-2019: Course overview.
  2. 07-08-2019: Recap on Finite State Automata.
  3. 14-08-2019: Quiz on finite-state automata.
  4. 19-08-2019, 21-08-2019: Buchi's logical characterization of regular languages.
  5. 26-08-2019, 28-08-2019: Automata-based Decision Procedure for Presburger Logic.
  6. 04-09-2019, 09-09-2019: Myhill-Nerode Theorem.
  7. 11-09-2019, 16-09-2019: Algebraic approach to automata.
  8. 18-09-2019: Intro to Context-Free Grammars.
  9. 23-09-2019: Chomsky Normal Form, Pumping Lemma for CFGs.
  10. 25-09-2019: 1:30pm Mid-sem exam.
  11. 30-09-2019: Discussion of mid-sem paper.
  12. 07, 09--10-2019: Tree Automata by Kamal Lodaya.
  13. 16-10-2019: Ultimate periodicity for Regular langauges.
  14. 18-10-2019: Parikh's Theorem. Slides.
  15. 21-10-2019: Intro to PDA's. Slides.
  16. 23-10-2019: Equivalence of PDA's and CFG's. Slides.
  17. 28-10-2019: Pushdown Reachability.
  18. 30-10-2019: Complementing DPDAs.
  19. 04-11-2019, 06-11-2019: Visibly Pushdown Languages.
  20. 11-11-2019: Intro to Turing Machines. Slides.
  21. 13-11-2019: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
  22. 18-11-2019: More Undecidable Problems and Reductions.
  23. 22-11-2019: Undecidable problems about CFL's. Slides.
  24. 25-11-2019: 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 Mon 08 September 2019.
  • Assignment 2 due on Fri 27 September 2019.
  • Assignment 3 due on Mon 04 November 2019.
  • Assignment 4 due on Mon 18 November 2019.
  • Assignment 5 due on Mon 02 December 2019.