Dagstuhl Seminar 17361
Finite and Algorithmic Model Theory
( Sep 03 – Sep 08, 2017 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/17361
Organizers
- 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)
Contact
- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
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.
- 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.
- To transfer knowledge from emerging techniques in core FAMT (algebraic methods, combinatorial optimization, random graphs) to the application areas.
- 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
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:
- 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.
- To transfer knowledge from emerging methods and techniques in core FAMT to application areas.
- 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).
Outcomes
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.
Anuj Dawar, Erich Grädel, Phokion G. Kolaitis, and Thomas Schwentick
- Faried Abu Zaid (TU Ilmenau, DE) [dblp]
- Albert Atserias (UPC - Barcelona, ES) [dblp]
- Christoph Berkholz (HU Berlin, DE) [dblp]
- Dietmar Berwanger (ENS - Cachan, FR) [dblp]
- Mikolaj Bojanczyk (University of Warsaw, PL) [dblp]
- Thomas Colcombet (University Paris-Diderot, FR) [dblp]
- Claire David (University Paris-Est - Marne-la-Vallée, FR) [dblp]
- Anuj Dawar (University of Cambridge, GB) [dblp]
- Arnaud Durand (Paris Diderot University, FR) [dblp]
- Kousha Etessami (University of Edinburgh, GB) [dblp]
- Ronald Fagin (IBM Almaden Center - San Jose, US) [dblp]
- Diego Figueira (University of Bordeaux, FR) [dblp]
- Joanna Fijalkow (University Paris-Diderot, FR) [dblp]
- Jakub Gajarský (TU Berlin, DE) [dblp]
- Erich Grädel (RWTH Aachen, DE) [dblp]
- Etienne Grandjean (Caen University, FR) [dblp]
- Martin Grohe (RWTH Aachen, DE) [dblp]
- Lauri Hella (University of Tampere, FI) [dblp]
- Sandra Kiefer (RWTH Aachen, DE) [dblp]
- Phokion G. Kolaitis (University of California - Santa Cruz, US) [dblp]
- Manfred Kufleitner (Universität Stuttgart, DE) [dblp]
- Dietrich Kuske (TU Ilmenau, DE) [dblp]
- Carsten Lutz (Universität Bremen, DE) [dblp]
- James F. Lynch (Clarkson University - Potsdam, US) [dblp]
- Jerzy Marcinkowski (University of Wroclaw, PL) [dblp]
- Martin Otto (TU Darmstadt, DE) [dblp]
- Wied Pakusa (University of Oxford, GB) [dblp]
- Svenja Schalthöfer (RWTH Aachen, DE) [dblp]
- Thomas Schwentick (TU Dortmund, DE) [dblp]
- Luc Segoufin (IINRIA & ENS Ulm, FR) [dblp]
- Sebastian Siebertz (University of Warsaw, PL) [dblp]
- Dan Suciu (University of Washington - Seattle, US) [dblp]
- Lidia Tendera (University of Opole, PL) [dblp]
- Wolfgang Thomas (RWTH Aachen, DE) [dblp]
- Szymon Torunczyk (University of Warsaw, PL) [dblp]
- Jouko Väänänen (University of Amsterdam, NL) [dblp]
- Jan Van den Bussche (Hasselt University, BE) [dblp]
- Victor Vianu (University of California - San Diego, US) [dblp]
- Heribert Vollmer (Leibniz Universität Hannover, DE) [dblp]
- Nils Vortmeier (TU Dortmund, DE) [dblp]
- Scott Weinstein (University of Pennsylvania, US) [dblp]
- Gregory Wilsenach (University of Cambridge, GB) [dblp]
- Thomas Zeume (TU Dortmund, DE) [dblp]
Related Seminars
- Dagstuhl Seminar 22051: Finite and Algorithmic Model Theory (2022-01-30 - 2022-02-04) (Details)
Classification
- data bases / information retrieval
- data structures / algorithms / complexity
- verification / logic
Keywords
- Finite model theory
- Descriptive Complexity
- Database Theory
- Model Checking
- Algorithms
- Knowledge Representation
- Independence Logic
