Submission: you can submit the final paper by hardcopy (dropping it off at the 4th floor of the CDM building) or by sending it to me as an email.

Select a topic related to our class that you are interested in and find research material on that topic (on the order of 20 pages, the length of two standard length conference papers or a longer journal paper). Read the paper(s) and write up an exposition of the the topic/issue based on standard resources (like the books we have used in class and some of the resources below) and present the solutions/discussions offered by the research paper. The papers can be survey papers, they do not have to be technical.  Your paper should be between 5-7 pages.

Some possible topic areas

Topics fall into two areas, roughly, applications and theory. For applications you can't do much better than look through the appendices of our book (G-Q) and look for pointers there. Topics here include, natural languages, AI, security protocols, compilers, etc. More theoretical topics include:

• Data structures
  • OBDDs (Appendix B.1 is a starting point)
  • XML and variants
• Model checking, temporal logics
• Cellular Automata
• Relationships to logic and games:
  • Büchi automata and monadic second order logic (Khoussainov/Nerode Section 3.10)
  • Rabin automata (Khoussainov/Nerode chapters 5/6; very hard material)
  • Decidability of Presburger arithmetic
    

Optional: I suggest you hand in your choice of topic and bibliography by 11/9, so I can make sure that what you are attempting is reasonable. For example, if I were planning to report on the Greibach normal form, my report could look like this:

Topic:  I'm planning to explain how every context-free grammar can be turned into Greibach normal form. Rich outlines an algorithm to do so in Appendix D.1 of Automata, Computability, and Complexity. I will compare the procedure described by Rich to the one outlined in a paper by Blum and Koch, Greibach Normal Form Transformation, Revisted, Information and Computation, 150  (1), 1999, pages 112-118 which yields a grammar of size O(|G|⁴).

Good places to start browsing:

• Journal of Automata, Languages and Combinatorics,
• LATA (Language and Automata Theory and Applications), a very young conference on languages and automata
• STACS, Symposium on Theoretical Aspects of Computer Science, an older conference that still contains automata theoretic material (more so in the past); web-site has proceedings online for the past two years; before that, Springer would have the papers

Many papers you'll  be able to find through google: try books.google or scholar.google (computer scientists tend to make their papers available online), and others (e.g. papers published with Springer) you'll be able to access through the library's web-page.

Some books (but also do a search for automata theory on books.google):

• Introduction to Automata Theory, Languages, and Computation, by Hopcroft, Motwani, Ullman; this is one of the classic textbooks of the subject, currently in the third edition
• Introduction to the Theory of Computation, by Michael Sipser; does not quite cover automata theory in the same depth as the other books, but gives a very readable introduction.
• Automata theory and its applications, by Khoussainov, Nerode; goes deep into applications of automata theory to decidability in 2nd order logic.