Preface
Finite model theory, as understood here, is an area of mathematical logic that
has developed in close connection with applications to computer science, in
particular the theory of computational complexity and database theory. One
of the fundamental insights of mathematical logic is that our understanding
of mathematical phenomena is enriched by elevating the languages we use to
describe mathematical structures to objects of explicit study. If mathematics
is the science of patterns, then the media through which we discern patterns,
as well as the structures in which we discern them, command our attention. It
is this aspect of logic which is most prominent in model theory, “the branch of
mathematical logic which deals with the relation between a formal language
and its interpretations”. No wonder, then, that mathematical logic, and finite
model theory in particular, should find manifold applications in computer
science: from specifying programs to querying databases, computer science
is rife with phenomena whose understanding requires close attention to the
interaction between language and structure.
This volume gives a broad overview of some central themes of finite model
theory: expressive power, descriptive complexity, and zero–one laws, together
with selected applications to database theory and artificial intelligence, espe-
cially constraint databases and constraint satisfaction problems. The final
chapter provides a concise modern introduction to modal logic, which empha-
sizes the continuity in spirit and technique with finite model theory. Chapters
2–7 are extensively revised and updated versions of tutorials presented at the
University of Pennsylvania on April 12–15, 1999, under the sponsorship of
Penn’s Institute for Research in Cognitive Science (IRCS) and the Center
for Discrete Mathematics and Theoretical Computer Science (DIMACS) at
Rutgers University. We would like to express our gratitude to DIMACS and
IRCS for their support, which made these tutorials possible. The tutorials
were presented to a diverse audience of computer scientists, linguists, logi-
cians, mathematicians, and philosophers, and the chapters of the book retain
the broad accessibility and wide appeal of the tutorials. The introductory
chapter highlights common themes among the tutorials that follow.
