E0 222 Automata Theory and Computability
Teaching Assistants: Julian D'Costa and Rekha Pai.
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.
05-08-2019: Course overview.
07-08-2019: Recap on Finite State Automata.
14-08-2019: Quiz on finite-state automata.
19-08-2019, 21-08-2019: Buchi's logical characterization of regular languages.
26-08-2019, 28-08-2019: Automata-based Decision Procedure for Presburger Logic.
- 04-09-2019, 09-09-2019: Myhill-Nerode Theorem.
- 11-09-2019, 16-09-2019: Algebraic approach to automata.
- 18-09-2019: Intro to Context-Free Grammars.
- 23-09-2019: Chomsky Normal Form, Pumping Lemma for CFGs.
- 25-09-2019: 1:30pm Mid-sem exam.
- 30-09-2019: Discussion of mid-sem paper.
- 07, 09--10-2019: Tree Automata by Kamal Lodaya.
- 16-10-2019: Ultimate periodicity for Regular langauges.
- 18-10-2019: Parikh's Theorem. Slides.
- 21-10-2019: Intro to PDA's. Slides.
- 23-10-2019: Equivalence of PDA's and CFG's. Slides.
- 28-10-2019: Pushdown Reachability.
- 30-10-2019: Complementing DPDAs.
- 04-11-2019, 06-11-2019: Visibly Pushdown Languages.
- 11-11-2019: Intro to Turing Machines. Slides.
- 13-11-2019: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
- 18-11-2019: More Undecidable Problems and Reductions.
- 22-11-2019: Undecidable problems about CFL's. Slides.
- 25-11-2019: 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.
Weightage for evaluation:
Mid-semester Exam: 20%
Assignments + Quiz + Seminar: 40%
Final Exam: 40%
Current meeting schedule: Mon, Wed, 2pm, in Room 252.
1:30pm Wed 25th September 2019.
9:30am Wed 4th December 2019 in Room 252.