E0 222 Automata Theory and Computability
Instructor:
Deepak
D'Souza.
Teaching Assistants: Sabuj Kumar Jena (sabuj.jena@csa.iisc.ernet.in), Inzemamul Haque (inzemamul.haque@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

06082015: Course overview.

11082015: Recap on Finite State Automata.

13082015, 18082015, 20082015: Buchi's logical characterization of regular languages.

25082015: Automatabased Decision Procedure for Presburger Logic.

01092015: MyhillNerode Theorem.

10092015: Algebraic approach to automata.
 29092015: Intro to ContextFree Grammars. Slides.
 08102015: Parikh's Theorem. Slides.
 15102015: Intro to PDA's. Slides.
 20102015: Equivalence of PDA's and CFG's. Slides.
 22102015 and 27102015: Reachability in Pushdown Systems. Slides.
 29102015: Complementing DPDA's. Slides.
 10112015: Visibly Pushdown Automata. Slides.
 12112015: Intro to Turing Machines. Slides.
 16112015: Undecidability of the Halting Problem. Slides.
 17112015: Reductions Slides.
 19112015: Undecidabile problems about CFL's. Slides.
 23112015: 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
 Angluin's algorithm for learning regular languages. Ezudheen, 5pm, Wed 28 Oct 2015. Slides.
 A linear
algorithm for testing equivalence of finite automata,
J.E. Hopcroft and R.M.Karp (1971). Shinjini Biswas and Ramit Hansdah, Wed 4th Nov, 5:00pm.
 Proof of ShuztebergerMcNaughtonPapert theorem (FO=starfree=counterfree=aperiodic monoid). Soumya and Harsha. 5:30pm, Fri 13 Nov. Slides.
 Applications of Context Free Grammar in Natural Language Processing. Harit Vishwakarma and Vishal Kakkar. 5pm Wed 18th Nov. Slides.
 Probabalistic DFA's. Ashish Srivastava and Harshil Pathak. 5pm Fri 27th Nov. Slides.
 Undecidability of validity problem of FirstOrder Logic.
(see Rob van Glabbeek's notes). Prerak Dhoot and Nirmalendu Prakash. 11:00 Tue 1st Dec.
 Direct automaton construction for Parikh's Theorem.
Paper by Esparza, Ganty, Kiefer, Luttenberger. Mohammand and Jawad, 12:00pm Tue 1st Dec.
 Automata on Trees. Sajiv Kumar, 2:00pm, Tue 1st Dec.
 Combinatorial Contextual Grammars. Gopu and Ashwin. 3:00pm, Tue 1st Dec.
Slides.
 Nested word automata. Paper by Alur and Madhusudan. (Pankaj + Yogesh) 10:00am, 2nd Dec.
 Context Sensitive Grammars and Linear Bounded Automata. (Manohar + Lucky) 11:00am, 2nd Dec.
 Presburger Logic and Semilinear Sets (Paper by Ginsburg and Spanier, Pacific J. Math, 1966).
Raghuram Bharadwaj and Sudhir Babu. 12:00pm 2nd Dec.
 Undecidability of Post's Correspondence Problem. Deshant, Hariom, and ?, 2:00pm, Wed 2nd Dec.
 Angluin's algorithm for alternating Automata. Shivam Gupta, 5:30pm Wed 2nd Dec.
 Collapsing Nondeterministic automata. Vipin Nagar and Rahul Hasija, 6:30pm Wed 2nd Dec.

Weightage for evaluation:

Midsemester Exam: 20%

Assignments (Lab + written) + Seminar: 40%

Final Exam: 40%

Current meeting schedule: Tue, Thu, 2:00 pm, CSA Lecture Hall
(Room 117).
 Exam Schedule:

Midsemester Exam:
10:00am, Fri October 2, 2015.

Final Exam:
2:00pm, Wed 9th Dec 2015..