E0 222 Automata Theory and Computability
Instructors:
Deepak
D'Souza and
Viraj Kumar.
Teaching Assistants: Inzemamul Haque.

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

02082018: Course overview, Viraj's slides.

07082018: Recap on Finite State Automata.

14082018, 16082018, 21082018: Buchi's logical characterization of regular languages.

23082018, 30082018: Automatabased Decision Procedure for Presburger Logic.
 04092018: MyhillNerode Theorem (Viraj).
 06092018: MyhillNerode Theorem (Deepak).
 11092018, 18092018: Algebraic approach to automata.
 20092018: Intro to ContextFree Grammars.
 25092018: Midsem exam.
 04102018: Discussion of midsem paper.
 09102018: Chomsky Normal Form, ultimate periodicity for Regular langauges.
 16102018: Pumping Lemma and Parikh's Theorem for CFLs. Goldstine's proof of Parikh's Theorem.
 18102018: Recursive Automata.
 23102018: Pushdown Automata.
 25102018: Equivalence of PDAs and CFGs.
 30102018: Pushdown Reachability.
 06112018: Complementing DPDAs.
 08112018: Visibly Pushdown Languages.
 13112018: Intro to Turing Machines. Slides.
 15112018: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
 20112018: More Undecidable Problems and Reductions.
 22112018: Undecidable problems about CFL's. Slides.
 27112018: 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.
 Angluin's algorithm for learning regular languages. Pranshul and Utkarsh.
 Nested word automata.
 Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger.
 Probabalistic ContextFree Grammars. Soumik.
 Automata on Trees.
 Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966).
Adithya and Rohit.
 Schutzenberger's aperiodic monoid characterization of starfree languages.
 Context Sensitive Grammars and Linear Bounded Automata.
Prajwal Koul.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van Glabbeek's notes).
 Proof of ShuztenbergerMcNaughtonPapert theorem (FO=starfree=counterfree=aperiodic monoid).
 Undecidability of Post's Correspondence Problem. Arnab Chatterjee.

Weightage for evaluation:

Midsemester Exam: 20%

Assignments + Quiz + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Tue, Thu, 2:00 pm, CSA Room 252.
 Exam Schedule:

Midsemester Exam:
2:00pm, Thu 27 September 2018.

Final Exam:
2:00pm, Thu 6th December 2018.