03. – 08. September 2017, Dagstuhl Seminar 17361

Finite and Algorithmic Model Theory


Anuj Dawar (University of Cambridge, GB)
Erich Grädel (RWTH Aachen, DE)
Phokion G. Kolaitis (University of California – Santa Cruz, US)
Thomas Schwentick (TU Dortmund, DE)

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team


Gemeinsame Dokumente


Finite and Algorithmic Model Theory (FAMT) encompasses a number of research themes united by the common use of methods for the analysis of the expressive power of logical formalisms on structures that are finite or finitely representable. These are precisely the structures that can serve as inputs to computation and, for this reason, FAMT is intimately connected to computer science. Over the past several decades, the subject has developed through a close interaction between theoretical computer science and closely related areas of mathematics, including logic and combinatorics.

Many foundational areas of research in computer science can be understood as investigating the relationship between formal languages (programming languages, database query languages, specification languages) and structures they describe (data structures, databases, program models). In such areas, methods developed in FAMT have played an increasingly important role. Complexity theory, database theory, and computer-aided verification are three, by now classical, such areas.

While these areas have long-standing connections with FAMT, recent years have seen exciting new developments both in core areas of FAMT and in new areas of application. Particularly significant is the deployment of new areas of mathematics in the study of the expressive power of logics. These include the exploration of algebraic methods, such as the introduction of logical operators based on linear algebra, the use of polynomial bases algorithms, and the combinatorics of permutation groups. Connections have been made between finite model theory and combinatorial optimization, including logical characterizations of convex optimization problems solved by the ellipsoid method. There is a renewed interest in the use of probabilistic methods to establish 0-1 laws, while at the same time intriguing connection with the combinatorics of graph limits have emerged.

Two notable instances of new connections with FAMT are the field of knowledge representation, where an important role is played by description logics, and the field of dependence logic, which explores logical reasoning about various notions of dependence and independence arising in different scientific disciplines.

The principal aims of this Dagstuhl Seminar are the following.

  1. To identify fresh research challenges in FAMT, arising from the main application areas and to make new connections between core research in FAMPT and emerging application areas.
  2. To transfer knowledge from emerging techniques in core FAMT (algebraic methods, combinatorial optimization, random graphs) to the application areas.
  3. To strengthen the research community in FAMT, especially by integrating younger members into it.

  Creative Commons BY 3.0 DE
  Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick


  • Data Bases / Information Retrieval
  • Data Structures / Algorithms / Complexity
  • Verification / Logic


  • Finite model theory
  • Descriptive Complexity
  • Database Theory
  • Model Checking
  • Algorithms
  • Knowledge Representation
  • Independence Logic


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.