DIMACS Workshop on Finite Models and Descriptive Complexity

January 14 - 17, 1996
Princeton University

Phokion Kolaitis, University of California, kolaitis@cse.ucsc.edu
Neil Immerman, Univ. of Massachusetts, immerman@cs.umass.edu
Presented under the auspices of the DIMACS Special Year on Logic and Algorithms.

The main aim of descriptive complexity is to classify algorithmic problems according to the resources needed to express such problems in various logics on finite models. This area has been developing through a continuous interaction between computational complexity, finite model theory, database theory, and combinatorics. Research in descriptive complexity has amplified the close relationship between logic and computation, as evidenced by natural characterizations of major complexity classes in terms of logical expressibility on finite models.

The goal of this workshop is to bring together researchers from all areas involved in the development of descriptive complexity, in a congenial atmosphere where connections can be formed, and research advanced. At the same time this will be a forum for communicating recent advances in descriptive complexity.


Phokion Kolaitis
Computer & Information Sciences
University of California
Santa Cruz, CA 95064
email: kolaitis@cse.ucsc.edu

Neil Immerman
Dept. of Computer Science, LGRC
Univ. of Massachusetts
Amherst, MA 01003-4610

Next: Call for Participation
DIMACS Homepage
Contacting the Center
Document last modified on May 5, 1995