a course during the 15th European Summer School in Logic, Language, and Information (ESSLLI2003)
Finite model-theory, as an interdisciplinary subject between mathematics and computer science, has been particularly successfully applied in the study of complexity classes defined by Boolean circuits.
In this course, we will discuss in detail logical characterizations known for the classes AC0, TC0, NC1 (see  below) and the very recent characterization of SAC1
- logical reductions
- generalized quantifiers given by different groupoid word problems
- built-in relations: addition and multiplication vs. the bit-predicate.
We will discuss applications from a complexity theoretic point of view as well as consequences for the expressive power of certain logical languages.
The course will be aimed at advanced Masters or Ph.D. students with a minimal background in elementary first-order logic and computation (Turing machines, basic time and space bounded classes as LogSpace, PTime, NPTime). It will lead them from the basic concepts in circuit complexity to the study of current research problems in the field.
- Heribert Vollmer, Introduction to Circuit Complexity, Springer 1999.
- C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer, The descriptive complexity approach to LOGCFL; Journal of Computer and Systems Sciences, 62(4),629-652, 2001
- Lecture Notes (postscript file)
Logic and Circuit Complexity on the Web
- Circuit Complexity (Book by H. Vollmer)
- Introduction to Descriptive Complexity by Neil Immerman
- Descriptive Complexity (Book by N. Immerman)
- Complexity Theory Lecture Notes by Eric Allender
- The Complexity of Boolean Functions (Book by Ingo Wegener)
- Boolean Functions and Computation Models (Book by Clote, Kranakis)
- Finite Model Theory Homepage