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


Dagstuhl Report, Volume 7, Issue 9 Dagstuhl Report


Topic and Goals of the Seminar

Finite and Algorithmic Model Theory (FAMT) encompasses a number of research themes united around common methods for analysing the expressive power of logical formalisms on structures that are either finite or can be finitely represented. 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 decades the subject has developed through a close interaction between theoretical computer science and closely related areas of mathematics, including logic and combinatorics, and a strong research community has been forged, with a common research agenda which has influenced several important areas of computer science. The last Dagstuhl-like meeting of this research community before this seminar had been Aux Houches in 2012.

The principal goals of the seminar have been the following:

  1. To identify fresh research challenges in the area of finite and algorithmic model theory, arising from the main application areas and to make new connections between core research in FAMT and emerging application areas, such as logic and learning.
  2. To transfer knowledge from emerging methods and techniques in core FAMT to application areas.
  3. To strengthen the research community in FAMT, especially by integrating younger members into it.

Organisation and Activities

The organisers developed a schedule consisting of three invited one-hour survey talks, more focussed regular contributions proposed by the participants, an open problem session, and a final discussion about the state and perspectives on the future of FAMT. The three survey talks were given by

  • Wied Pakusa (Oxford) on recent achievements concerning the quest for a logic for polynomial time, focussing on Rank Logic and on Choiceless Polynomial Time,
  • Dan Suciu (Washington) on highlights of the connections between FAMT and databases.
  • Martin Grohe (Aachen) on new developments in machine learning and connections to FAMT.

In addition, 22 other participants gave regular talks on their recent work on topics of FAMT. A further social highlight was a superb concert on Thursday evening performed by Jan Van den Bussche (violin), Wolfgang Thomas (violin) and Jouko Väänänen (piano).


The seminar exceeded our expectations in achieving our principal goals. The invited talk by Pakusa gave an overview on the status of the ongoing pursuit for a logic for PTIME, and demonstrated the depth and technical sophistication that FAMT has reached. This talk was complemented by several insightful presentations on new and deep work on core topics of finite model theory. A particular highlight was the double presentation by Torunczyk and Siebertz, who brought in new methods from stability theory to the study of the finite model theory of sparse structures.

The invited talks by Grohe and Suciu explored new connections between the core methods of finite model theory and emerging areas of applications. These talks were also complemented by several other talks on new directions in FAMT and on interactions of FAMT with other areas. In particular, Grädel's talk focussed on new work in the area of database provenance, while Atserias' talk discussed a priori unexpected connections between constraint satisfaction and quantum information theory.

Overall, the presentations at the seminar were highly stimulating, and we know through discussions during and after the seminar that the new work presented has motivated others to take up the explorations of these questions. Based on the feedback received, we believe that this seminar will serve as a catalyst for new research directions in FAMT.

The organizers regard the seminar as very successful. As reflected in the final discussion, there was a consistent sentiment expressed by the participants that the FAMT community is in very healthy state. There are interesting new developments and exciting results in different directions, there is a strengthening of traditional connections to areas, such as databases and verification, but also new connections are emerging with such areas as knowledge representation, learning theory, logics for dependence and independence, and quantum information theory. Finally, and perhaps more importantly, there is an infusion of several outstanding young researchers who have the interest and hold the promise to advance FAMT in the years to come.

The participants clearly expressed the wish to a have a next meeting of the FAMT community, be it in Dagstuhl or elsewhere, within the next two to three years.

The organizers are grateful to the Scientific Directorate of the Center for its support of this workshop and the staff of Schloss Dagstuhl for the perfect organisation of our stay and their hospitality.

Summary text license
  Creative Commons BY 3.0 Unported license
  Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick

Related Dagstuhl-Seminar


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


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


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).

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.


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