|
This volume is based on the satelliteworkshop on Finite and Algorithmic Model
Theory that took place at the University of Durham, January 9–13, 2006, to
inaugurate the scientific program Logic and Algorithms held at the Isaac Newton
Institute for Mathematical Sciences during the first six months of 2006. The
goal of the workshop was to explore the emerging and potential connections
between finite and infinite model theory, and their applications to theoretical
computer science. The primarily tutorial format introduced researchers and
graduate students to a number of fundamental topics. The excellent quality
of the tutorials suggested to the program organizers, Anuj Dawar and Moshe
Vardi, that a volume based on the workshop presentations could serve as a
valuable and lasting reference. They proposed this to the workshop scientific
committee; this volume is the outcome.
The Logic and Algorithms program focused on the connection between
two chief concerns of theoretical computer science: (i) how to ensure and
verify the correctness of computing systems; and (ii) how to measure the
resources required for computations and ensure their efficiency. The two areas
historically have interacted little with each other, partly because of the divergent
mathematical techniques they have employed. More recently, areas of research
in which model-theoretic methods play a central role have reached across both
sides of this divide. Results and techniques that have been developed have
found applications to fields such as database theory, complexity theory, and
verification. |
