E0 222 Automata Theory and Computability
Teaching Assistants: Inzemamul Haque.
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.
02-08-2018: Course overview, Viraj's slides.
07-08-2018: Recap on Finite State Automata.
14-08-2018, 16-08-2018, 21-08-2018: Buchi's logical characterization of regular languages.
23-08-2018, 30-08-2018: Automata-based Decision Procedure for Presburger Logic.
- 04-09-2018: Myhill-Nerode Theorem (Viraj).
- 06-09-2018: Myhill-Nerode Theorem (Deepak).
- 11-09-2018, 18-09-2018: Algebraic approach to automata.
- 20-09-2018: Intro to Context-Free Grammars.
- 27-09-2018: Mid-sem exam.
- 04-10-2018: Discussion of mid-sem paper.
- 09-10-2018: Chomsky Normal Form, ultimate periodicity for Regular langauges.
- 16-10-2018: Pumping Lemma and Parikh's Theorem for CFLs. Goldstine's proof of Parikh's Theorem.
- 18-10-2018: Recursive Automata.
- 23-10-2018: Pushdown Automata.
- 25-10-2018: Equivalence of PDAs and CFGs.
- 30-10-2018: Pushdown Reachability.
- 06-11-2018: Complementing DPDAs.
- 08-11-2018: Visibly Pushdown Languages.
- 13-11-2018: Intro to Turing Machines. Slides.
- 15-11-2018: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
- 20-11-2018: More Undecidable Problems and Reductions.
- 22-11-2018: Undecidable problems about CFL's. Slides.
- 27-11-2018: 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
- Buchi Automata. Sachin and Lucky. 2pm, Thu 11 October 2018.
- Angluin's algorithm for learning regular languages. Pooja and Rashi. 5pm Fri 9 Nov.
- Nested word automata. Gaurang and Pranshu. 5pm Fri 16 Nov.
- Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger. Rishi, Shubham, and Abhishek. 12pm 23 Nov.
- Probabalistic Context-Free Grammars. Julian and Neha. 5pm, Fri 23 Nov.
- Automata on Trees. Geetham and Stanly. 4pm, Thu 29 Nov.
- Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966). Arka Ghosh and Vishnu Teja, 12pm, Fri 30th Nov.
- Schutzenberger's aperiodic monoid characterization of star-free languages. Amishi and Sreedurga, 4pm Fri 30 Nov.
- Context Sensitive Grammars and Linear Bounded Automata. Habeeb and Alvin. 5pm Fri 30 Nov.
- Undecidability of validity problem of First-Order Logic.
(see Rob van Glabbeek's notes). Sreehari and Sunit. 2pm Wed 5th Dec.
- Proof of Shuztenberger-McNaughton-Papert theorem (FO=star-free=counter-free=aperiodic monoid).
- Undecidability of Post's Correspondence Problem.
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:
2:00pm, Thu 27 September 2018.
2:00pm, Thu 6th December 2018.