http://www.dagstuhl.de/17361

September 3 – 8 , 2017, Dagstuhl Seminar 17361

Finite and Algorithmic Model Theory

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)

For support, please contact

Susanne Bach-Bernhard for administrative matters

Andreas Dolzmann for scientific matters

Documents

List of Participants
Shared Documents

Motivation

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.

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

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

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support