E0 222 Automata Theory and Computability

Teaching Assistants: Sabuj Kumar Jena (sabuj.jena@csa.iisc.ernet.in), Inzemamul Haque (inzemamul.haque@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. 06-08-2015: Course overview.
  2. 11-08-2015: Recap on Finite State Automata.
  3. 13-08-2015, 18-08-2015, 20-08-2015: Buchi's logical characterization of regular languages.
  4. 25-08-2015: Automata-based Decision Procedure for Presburger Logic.
  5. 01-09-2015: Myhill-Nerode Theorem.
  6. 10-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. 15-10-2015: Intro to PDA's. Slides.
  10. 20-10-2015: Equivalence of PDA's and CFG's. Slides.
  11. 22-10-2015 and 27-10-2015: Reachability in Pushdown Systems. Slides.
  12. 29-10-2015: Complementing DPDA's. Slides.
  13. 10-11-2015: Visibly Pushdown Automata. Slides.
  14. 12-11-2015: Intro to Turing Machines. Slides.
  15. 16-11-2015: Undecidability of the Halting Problem. Slides.
  16. 17-11-2015: Reductions Slides.
  17. 19-11-2015: Undecidabile problems about CFL's. Slides.
  18. 23-11-2015: 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 Wed 08 September 2015.
  • Assignment 2 due on Mon 5 October 2015.
  • Assignment 3 due on Mon 9 November 2015.
  • Assignment 4 due on Tue 1 December 2015.

• 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. Slides.
  • 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 (Room 117).

• Exam Schedule:
  • Mid-semester Exam: 10:00am, Fri October 2, 2015.
  • Final Exam: 2:00pm, Wed 9th Dec 2015..