Seminar Topics

Suggested Seminar Topics for participants of the automata and computability course. Please choose a topic each for study and presentation.
  1. Alternating Finite State Automata

  2. Sources: Sheng Yu Article, HFL Vol. 1 and related papers.
  3. Completeness of Kleene Algebra Axiomatization

  4. Sources: Kozen Supplement A and related papers.
    Student: Arnab Basu (25 November, 2003)
  5. Two way finite state automata

  6. Sources: Kozen Ch. 17,18, Hopcroft Textbook (sec. 2.6)
    Student: P. Vijay Suman (11 November 2003)
  7. Automata on Terms and Mihill Nerode Thm

  8. Souce: Kozen Supplement C & D
  9. Collapsing NFAs under Bisimilarity

  10. Source: Kozen Supplemen B
    Student: Neelima Arora (25 November, 2003)
  11. Regular Expression Pattern Matching Algoritms

  12. Algorithms of Brosowski, Thompson and Berry-Sethi
    Source: Papers, Dragonbook
    Student: Shivali Agarwal (13 November, 2003)
  13. Chomski Shutzenberger Theorem for CFL

  14. Source: Kozen Supplement G
  15. Parikh's Theorem for CFLs

  16. Source: Kozen Supplement H
    Student: Chinmoy Dutta (11 November, 2003)
  17. Post Correspondence Problem and Undecidability

  18. Source: Hopcroft Textbook
    Student: N.V. Narendra Kumar (13 November, 2003)
  19. Hierarchy of Undecidable Problems

  20. Oracles and Arithmetic Hierarchy
    Source: Kozen Supplement K, Hopcroft
    Student: K. Benny George (18 November, 2003)
     

    Smaller Topics

  21. Rice's Theorem for R.E. index sets

  22. Source: Hopcroft Textbook (Section 8.4)
  23. Existence of Inherently Ambiguous CFLs

This list is incomplete