E0 222 Automata Theory and Computability
Teaching Assistants: P. Ezudheen (firstname.lastname@example.org), Inzemamul Haque (email@example.com), and Snigdha Athaiya (firstname.lastname@example.org).
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.
04-08-2016: Course overview.
11-08-2015: Recap on Finite State Automata.
16-08-2015, 18-08-2015, 23-08-2015: Buchi's logical characterization of regular languages.
25-08-2015: Automata-based Decision Procedure for Presburger Logic.
06-09-2015: Myhill-Nerode Theorem.
20-09-2015: Algebraic approach to automata.
- 29-09-2015: Intro to Context-Free Grammars. Slides.
- 08-10-2015: Parikh's Theorem. Slides.
- 27-10-2015: Intro to PDA's. Slides.
- 27-10-2015: Equivalence of PDA's and CFG's. Slides.
- 03-11-2016 (1.5 classes): Reachability in Pushdown Systems. Slides.
- 08-11-2016: Complementing DPDAs. Slides.
- 10-11-2016: Visibly Pushdown Automata. Slides.
- 16-11-2016: Intro to Turing Machines. Slides.
- 17-11-2016: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
- 22-11-2016: Reductions. Slides.
- 23-11-2016: Undecidable problems about CFL's. Slides.
- 28-11-2016: 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
- 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:
9:00am, Tue 4th October 2016..
10:00am, Fri 9th December 2016.