Students are required to write a ten to twelve page term paper, in LaTeX, on a topic of their choice. Below is a list of suggested topics, though you may also choose your own, subject to instructor approval. In order to select a subject that you will find interesting, I suggest browsing through some of the books listed below that have been put on reserve in the library.

The purpose of this project is to learn something about a topic related to the material in the course, and to write a paper explaining some of what you have learned. You are not expected to do any original research. Rather, you will need to organize and synthesize your material and present it in a way that good undergraduate student like yourself would be able to read and understand it, and learn something new and interesting.

This is harder than it sounds, especially if you have never written a math paper before. Make sure to start early!

Some important dates

• Thursday 4/3: One page outline due, in LaTeX.
• Thursday 4/24: Complete draft due.
• Thursday 5/15: Final paper due.

LaTeX

You are required to write your paper using LaTeX, which is the standard method for writing mathematical text. LaTeX is not difficult to use, but it can take a little while to get used to. Here are a few links that should be helpful for both the beginner and the expert.

• Short Math Guide to LaTeX
• The Not So Short Introduction
• CTAN, the Comprehensive TeX Archive Network
• LaTeX on wikipedia, an article with many more links.

Possible topics

Students may choose to write about any topic related to finite model theory. The list below contains some suggestions; one can look through any of the references listed below to come up with other ideas. (Following each topic is a brief description, together with a few relevant references.)

Descriptive complexity theory

Descriptive complexity theory is the study of connections between logical languages and computational complexity classes. Chapter 10 of Libkin contains an introduction, but there's much more that one could write about. Possible references would include Immerman's book, and chapter 3 of the book by Gradel et al. Another option would be to write about computational complexity theory, or circuit complexity.

Logic and automata

This is another subject that will be partially covered in class, but there are a variety of possible topics that one could pursue further. References include Straubing's book, or one of his papers on the subject, some of which are available on his website.

Database theory

There are many connections between finite model theory and database theory since a database is essentially a finite structure. There are many references. One place to begin reading is Vianu's article "Databases and finite-model theory" in Descriptive Complexity and Finite Models, edited by N. Immerman and Ph. Kolaitis. So called constraint databases, which allow finite structures to be embedded into infinite ones, are discussed in chapter 5 of Gradel et al.

Constraint satisfaction problems

Constraint satisfaction problems are a certain type of combinatorial problem that originally arose in artificial intelligence (AI). It has been realized that there are connections between such problems and finite model theory, related to questions about graph homomorphisms. Chapter 6 of Gradel et al. surveys the subject, and contains many further references.

Zero-one laws/random graphs

The basic zero-one law for first-order logic says that any sentence is almost surely true or almost surely false of all finite structures. There are many variations where one considers other probability spaces or stonger logics. References include chapter 12 of Libkin and chapter 4 of Gradel et al. There are also some interesting papers by Kolaitis and Vardi on zero-one laws for fragments of second-order logic.

Logical preservation theorems

A logical preservation theorem relates the semantic properties of a definable class of structures with the syntax of the sentence defining it. For example, a definable class of structures is closed under extensions if and only if it is defined by an existential sentence. There are a wide variety of such preservation theorems over the class of all structures, but most of them fail in the finite. One possible topic would to be write about preservation theorems over infinite and/or finite structures. References include Chang and Keisler, for infinite structures, and Ebbinghaus and Flum, for finite structures. My paper "Some aspects of model theory and finite structures" contains a fairly complete summary of what is known about preservation theorems over finite structures (Available online, from the Bulletin of Symbolic Logic.)

Finite variable logics

For each n, one can consider the logical language that consists of all first-order formula that contain at most n variables, both free and bound. This might seem to be an odd restriction, but these logics are quite interesting and important in finite model theory. Chapter 11 of Libkin contains an introduction, and also includes a list of good and accessible references.

Modal logics

Modal logic is the logic of possibility and necessity. There are many variations, some of which can be viewed as fragments of first-order logic, much like finite variable logics above. Much of the original interest in the subject was philosophical, but recently there have been significant connections to computer science. One reference is chapter 7 of Gradel et al., but there are many others.

Generalized quantifiers

One way to extend first-order logic is to add generalized quantifiers, such as `there are infinitely many x' or `there are an even number of x'. These are discussed in Ebbinghaus and Flum, and in some papers by Vaananen (references 237 and 238 in Libkin). A somewhat different notion, of a `counting quantifier' is discussed in chapter 8 of Libkin.

References

The following references have been put on reserve in the library. Details about some of these books, including tables of contents, can be found on amazon. One can also find reviews of these books online at the AMS's MathSciNet, which is an invaluable resource. (This is a subscription service that will work from the MIT network.)

1. L. Libkin, Elements of Finite Model Theory
2. E. Gradel et al., Finite Model Theory and its Applications
3. H.-D. Ebbinghaus and J. Flum, Finite Model Theory
4. N. Immerman, Descriptive Complexity
5. H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity
6. D. Marker, Model Theory: an Introduction
7. C.C. Chang and H.J. Keisler, Model Theory

• Many recent, and not so recent, journal articles are available online through the journal in which they appear. Some authors also post their papers on their homepages, or the math arXiv.
• The American Mathematical Society's MathSciNet is an online database for almost all mathematical papers. It contains reviews as well as bibilographical information, and is usually the easiest way to find a reference.
• The computer science bibliography DBLP is a very useful way to track down references for papers in computer science.

Last updated March 2008