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.
 27092018: 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. Sachin and Lucky. 2pm, Thu 11 October 2018.
Slides.
 Angluin's algorithm for learning regular languages. Pooja and Rashi. 5pm Fri 9 Nov.
 Nested word automata. Gaurang and Pranshu. 5pm Fri 16 Nov.
Slides.
 Direct automaton construction for Parikh's Theorem.
Slides.
Paper by Esparza, Ganty, Kiefer, Luttenberger. Rishi, Shubham, and Abhishek. 12pm 23 Nov.
 Probabalistic ContextFree Grammars. Julian and Neha. 5pm, Fri 23 Nov.
Slides.
 Automata on Trees. Geetham and Stanly. 4pm, Thu 29 Nov.
Slides.
 Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966). Arka Ghosh and Vishnu Teja, 12pm, Fri 30th Nov.
Slides.
 Schutzenberger's aperiodic monoid characterization of starfree languages. Amishi and Sreedurga, 4pm Fri 30 Nov.
Slides.
 Context Sensitive Grammars and Linear Bounded Automata. Habeeb and Alvin. 5pm Fri 30 Nov.
CSL Slides.
LBA Slides.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van Glabbeek's notes). Sreehari and Sunit. 2pm Wed 5th Dec.
 Proof of ShuztenbergerMcNaughtonPapert theorem (FO=starfree=counterfree=aperiodic monoid).
 Undecidability of Post's Correspondence Problem.

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.