Seminar Topics
Suggested Seminar Topics for participants of the automata and computability
course. Please choose a topic each for study and presentation.

Alternating Finite State Automata
Sources: Sheng Yu Article, HFL Vol. 1 and related papers.

Completeness of Kleene Algebra Axiomatization
Sources: Kozen Supplement A and related papers.
Student: Arnab Basu (25 November, 2003)

Two way finite state automata
Sources: Kozen Ch. 17,18, Hopcroft Textbook (sec. 2.6)
Student: P. Vijay Suman (11 November 2003)

Automata on Terms and Mihill Nerode Thm
Souce: Kozen Supplement C & D

Collapsing NFAs under Bisimilarity
Source: Kozen Supplemen B
Student: Neelima Arora (25 November, 2003)

Regular Expression Pattern Matching Algoritms
Algorithms of Brosowski, Thompson and BerrySethi
Source: Papers, Dragonbook
Student: Shivali Agarwal (13 November, 2003)

Chomski Shutzenberger Theorem for CFL
Source: Kozen Supplement G

Parikh's Theorem for CFLs
Source: Kozen Supplement H
Student: Chinmoy Dutta (11 November, 2003)

Post Correspondence Problem and Undecidability
Source: Hopcroft Textbook
Student: N.V. Narendra Kumar (13 November, 2003)

Hierarchy of Undecidable Problems
Oracles and Arithmetic Hierarchy
Source: Kozen Supplement K, Hopcroft
Student: K. Benny George (18 November, 2003)
Smaller Topics

Rice's Theorem for R.E. index sets
Source: Hopcroft Textbook (Section 8.4)

Existence of Inherently Ambiguous CFLs
This list is incomplete