E0 222 Automata Theory and Computability

Teaching Assistants: P. Ezudheen (ezudheen@gmail.com), Inzemamul Haque (inzemamul.haque@csa.iisc.ernet.in), and Snigdha Athaiya (snigdha.athaiya@csa.iisc.ernet.in).

• 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. 04-08-2016: Course overview.
  2. 11-08-2015: Recap on Finite State Automata.
  3. 16-08-2015, 18-08-2015, 23-08-2015: Buchi's logical characterization of regular languages.
  4. 25-08-2015: Automata-based Decision Procedure for Presburger Logic.
  5. 06-09-2015: Myhill-Nerode Theorem.
  6. 20-09-2015: Algebraic approach to automata.
  7. 29-09-2015: Intro to Context-Free Grammars. Slides.
  8. 08-10-2015: Parikh's Theorem. Slides.
  9. 27-10-2015: Intro to PDA's. Slides.
  10. 27-10-2015: Equivalence of PDA's and CFG's. Slides.
  11. 03-11-2016 (1.5 classes): Reachability in Pushdown Systems. Slides.
  12. 08-11-2016: Complementing DPDAs. Slides.
  13. 10-11-2016: Visibly Pushdown Automata. Slides.
  14. 16-11-2016: Intro to Turing Machines. Slides.
  15. 17-11-2016: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
  16. 22-11-2016: Reductions. Slides.
  17. 23-11-2016: Undecidable problems about CFL's. Slides.
  18. 28-11-2016: 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 06 September 2016.
  • Assignment 2 due on Fri 30 September 2016.
  • Assignment 3 due on Fri 18 November 2016.
  • Assignment 4 due on Fri 2 December 2016.

• Seminar Topics
  • Proof of Shuztenberger-McNaughton-Papert theorem (FO=star-free=counter-free=aperiodic monoid). Sayantan and Ishan. 2pm Friday 16th Sep 2016. [Slides]
  • Buchi Automata. Arvind and Biswajit. 2pm Friday 23rd Sep 2016.
  • Angluin's algorithm for learning regular languages. Ullas Aparanji. Fri 4 October 2016. Slides.
  • Probabalistic Context-Free Grammars. Aashraya Sachdev. Fri 18th Nov 2016. Slides.
  • Schutzenberger's aperiodic monoid characterization of star-free languages. Prokash.
  • Undecidability of Post's Correspondence Problem. Gaurav Sharma, 10:00 am, Thu 1st Dec. Slides.
  • Checking Equivalence of DFAs. Rubee Tandon and Swapnil Ramteke, Fri 2nd Dec, 2pm.
  • Context Sensitive Grammars and Linear Bounded Automata. Rajaguru and Manoharan. 12:00pm Wed 7th Dec. Slides-1, Slides-2
  • Direct automaton construction for Parikh's Theorem. Paper by Esparza, Ganty, Kiefer, Luttenberger. Ashish Kumar Sen and Jagan P M. 2:30pm Wed 7th Dec.
  • Automata on Trees. Shivam Gupta. 12:00pm Thu 8th Dec.
  • Nested word automata. Paper by Alur and Madhusudan. Ashok Rawat, Dara Singh, Jiben Surendran. 12:30pm, Thu 8th Dec. Slides.
  • Undecidability of validity problem of First-Order Logic. (see Rob van Glabbeek's notes).
  • Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966).

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

• Current meeting schedule: Tue, Thu, 9:30 am, CSA Room 252.

• Exam Schedule:
  • Mid-semester Exam: 9:00am, Tue 4th October 2016..
  • Final Exam: 10:00am, Fri 9th December 2016.