E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza.
Teaching Assistants: P. Ezudheen (ezudheen@gmail.com), Inzemamul Haque (inzemamul.haque@csa.iisc.ernet.in), and Snigdha Athaiya (snigdha.athaiya@csa.iisc.ernet.in).

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

04082016: Course overview.

11082015: Recap on Finite State Automata.

16082015, 18082015, 23082015: Buchi's logical characterization of regular languages.

25082015: Automatabased Decision Procedure for Presburger Logic.

06092015: MyhillNerode Theorem.

20092015: Algebraic approach to automata.
 29092015: Intro to ContextFree Grammars. Slides.
 08102015: Parikh's Theorem. Slides.
 27102015: Intro to PDA's. Slides.
 27102015: Equivalence of PDA's and CFG's. Slides.
 03112016 (1.5 classes): Reachability in Pushdown Systems. Slides.
 08112016: Complementing DPDAs. Slides.
 10112016: Visibly Pushdown Automata. Slides.
 16112016: Intro to Turing Machines. Slides.
 17112016: Equivalent models (Slides) and Undecidability of the Halting Problem (Slides).
 22112016: Reductions. Slides.
 23112016: Undecidable problems about CFL's. Slides.
 28112016: 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
 Proof of ShuztenbergerMcNaughtonPapert theorem (FO=starfree=counterfree=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 ContextFree Grammars. Aashraya Sachdev. Fri 18th Nov 2016. Slides.
 Schutzenberger's aperiodic monoid characterization of starfree 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. Slides1, Slides2
 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 FirstOrder Logic.
(see Rob van Glabbeek's notes).
 Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966).

Weightage for evaluation:

Midsemester Exam: 20%

Assignments + Quiz + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Tue, Thu, 9:30 am, CSA Room 252.
 Exam Schedule:

Midsemester Exam:
9:00am, Tue 4th October 2016..

Final Exam:
10:00am, Fri 9th December 2016.