Final Research Paper (due 11/23)
CSC 344/444

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:

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|4).

Good places to start browsing:

Many papers you'll  be able to find through google: try or (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

Marcus Schaefer
Last updated: November 4th, 2009