E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza
Teaching Assistants: Julian D'Costa and Rekha Pai.

Course outline

Automata and Logic: Buchi's logical characterization of regular
languages; Automatabased 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
MyhillNerode theorem.

Pushdown Systems: Parikh's theorem on semilinearity 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 omegaregular
languages, including closure under complementation; Deterministic
Buchi automata; Revisiting Buchi's logical characterization.

Automata on Trees: Closure properties, decision procedures,
congruences and minimization.

Lectures

05082019: Course overview.

07082019: Recap on Finite State Automata.

14082019: Quiz on finitestate automata.

19082019, 21082019: Buchi's logical characterization of regular languages.

26082019, 28082019: Automatabased Decision Procedure for Presburger Logic.
 04092019, 09092019: MyhillNerode Theorem.
 11092019, 16092019: Algebraic approach to automata.
 18092019: Intro to ContextFree Grammars.
 23092019: Chomsky Normal Form, Pumping Lemma for CFGs.
 25092019: 1:30pm Midsem exam.
 30092019: Discussion of midsem paper.
 07, 09102019: Tree Automata by Kamal Lodaya.
 16102019: Ultimate periodicity for Regular langauges.
 18102019: Parikh's Theorem. Slides.
 21102019: Intro to PDA's. Slides.
 23102019: Equivalence of PDA's and CFG's. Slides.
 28102019: Pushdown Reachability.
 30102019: Complementing DPDAs.
 04112019, 06112019: Visibly Pushdown Languages.
 11112019: Intro to Turing Machines. Slides.
 13112019: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
 18112019: More Undecidable Problems and Reductions.
 22112019: Undecidable problems about CFL's. Slides.
 25112019: 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
languages.

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.
 Assignments
Seminar Topics
 Buchi Automata. Deepak and Nabarun, 12pm, Fri 25 October 2019.
Slides.
 Angluin's algorithm for learning regular languages. Pranshul and Utkarsh. Slides.
 Nested word automata. Alvin and Raseek. Slides1, Slides2.
 Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966).
Adithya and Rohit. Slides
 Regularity Preserving Relations by Seifras and McNaughton. Soumik and Shreyas.
Slides1,
Slides2.
 Context Sensitive Grammars and Linear Bounded Automata.
Prajwal Koul. Slides.
 Schutzenberger's aperiodic monoid characterization of starfree languages.
Ankur Naskar. Slides.
 Undecidability of Post's Correspondence Problem. Arnab Chatterjee.
Slides.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van Glabbeek's notes).
 Proof of ShuztenbergerMcNaughtonPapert theorem (FO=starfree=counterfree=aperiodic monoid).
 Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger.
 Probabalistic ContextFree Grammars.
 Automata on Trees.
Weightage for evaluation:

Midsemester Exam: 20%

Assignments + Quiz + Seminar: 40%

Final Exam: 40%
Current meeting schedule: Mon, Wed, 2pm, in Room 252.
Exam Schedule:

Midsemester Exam:
1:30pm Wed 25th September 2019.

Final Exam:
9:30am Wed 4th December 2019 in Room 252.