Final Research Paper (due 11/22)
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). At least one of the papers should be a recent paper (published within the last 10 years). 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 and it should explain the material in your own words. Be very scrupulous about acknowledging sources of pictures or text you include from other articles. Structure your paper: use sections for the different parts of your paper (start with a summary of what your paper will cover).

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/8, 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 and it's more theoretical aspects, my report could look like this (in terms of number of pages it's maybe a bit on the short side):

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 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):


Marcus Schaefer
Last updated: November 2nd, 2010