E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza with guest lectures by Kamal Lodaya.
Teaching
Assistants: P
Habeeb and Nabarun
Deka.
Meeting schedule:
 10am on Tue, Thu.
 Google
Meet link for
the course.
 First class at 10am on Thu 5th August 2021.

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
 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.
 Melvin Fitting: FirstOrder Logic and Theorem Proving (See Secs.
5.1, 5.2, and 5.3 for basics
of firstorder logic).

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
 Note on regular languages,
logic and algebra, by Kamal Lodaya.
 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 (Link to Schedule Doc)
 Angluin's algorithm for learning regular languages. Addrija,
Dhruv and Mehul, 5th Nov
2021. Slides.
 Regularity
Preserving Relations by Seifras and McNaughton. Saurabh
Awinashe and Ankit Kurani 11th Nov 2021. Slides.
 Buchi Automata. Abhishek, Kawin and Sasanka. Slides.
 Nested word automata. Harshitha, Jaydeep and Rupashree, 19 Nov 2021.
 Schutzenberger's aperiodic monoid characterization of starfree
languages. Tushar and Umang, 25th Nov. Slides.
 Primitive Recursive Functions and Computability. Aditya
Ravishankar, Moksha Mevada, Ankit Kumar, 26 Nov. Slides.
 Undecidability of Post's Correspondence Problem. Bodhisattva,
Rishav and Sourav, 04 Dec 2021.
 Concatenation of inputs in a 2way automaton. Abhilash and
Prathamesh, 05 Dec 2021. Slides.
 Context Sensitive Grammars and Linear Bounded Automata. Rajesh,
Mayank, and Himanshu, 06 Dec 2021 Slides.
 Presburger Logic and Semilinear Sets
(Paper by
Ginsburg and Spanier, Pacific J. Math, 1966). Chintan, Maitri
and Rohit, 07 Dec 2021. Slides.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van
Glabbeek's notes). Sumanth
Prabhu, 13 Dec 2021. Slides.
 Proof of ShuztenbergerMcNaughtonPapert theorem (FO=starfree=counterfree=aperiodic monoid).
 Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger.

Weightage for evaluation:

Midsemester Exam: 20%

Assignments + Quiz + Seminar: 40%

Final Exam: 40%
 Exam Schedule:

Midsemester Exam:
9:30am Tue 28th September 2021.

Final Exam:
10am Fri 10th December 2021.