https://www.dagstuhl.de/22051

30. Januar – 04. Februar 2022, Dagstuhl-Seminar 22051

Finite and Algorithmic Model Theory

Organisatoren

Albert Atserias (UPC Barcelona Tech, ES)
Christoph Berkholz (HU Berlin, DE)
Kousha Etessami (University of Edinburgh, GB)
Joanna Ochremiak (University of Bordeaux, FR)

Auskunft zu diesem Dagstuhl-Seminar erteilen

Christina Schwarz zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

Dokumente

Teilnehmerliste
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]

Motivation

The methods and tools of finite and algorithmic model theory (FAMT) have played an active role in the development of several areas of computer science. Besides the fact that finite or finitely representable structures are those that serve as inputs to computation, the study of the expressive power of logical languages on such structures has led to several fundamental insights. Some of these have found applications in areas as diverse as database theory, computational complexity, random structures and combinatorics, systems verification, automata theory, proof complexity, or algorithmic game theory.

Over the past four decades FAMT has established itself as a solid research field with a strong and evolving community of researchers with a shared research agenda. Much of the progress can be traced to the regular meetings of the community: the last such meeting was at Dagstuhl in 2017, and before that at Les Houches in 2012.

One of the main goals of this Dagstuhl Seminar is to capitalize on the progress and the potential impact of some of the latest developments in FAMT and related areas. Such developments include:

a) The recently established connections between symmetric models of classical computation and bounded-variable counting logics. The symmetric counterparts of classical models of computations include threshold circuits, linear and semidefinite programs, and algebraic circuits. These new results have already been used to establish new upper and lower bounds for large families of algorithms by FAMT tools.

b) The theories of homomorphism counts and limit structures in combinatorics. A recent trend of work establishes that distinguishing the structures by the number homomorphisms they admit from certain classes of patterns, or to certain classes of patterns, is a fruitful alternative to distinguishing them by the logic formulas they satisfy.

c) Enumeration and counting methods including their use in database query processing, among others. One of the goals of this line of research is to understand and classify the logical queries for which it is possible to compute a compact representation of the output from which the query results can be obtained, efficiently, and on demand.

The principal goals of the seminar are the following.

  • To identify fresh research challenges in the area of finite and algorithmic model theory, arising from the main application areas, including newly emerging ones.
  • To make new connections between core research in FAMT and other subfields of theoretical computer science, such as the theory of combinatorial and continuous optimization algorithms, and the theory of homomorphism counts and limit structures.
  • To transfer knowledge from emerging techniques in core FAMT back to the connecting subfields and application areas.
  • To strengthen the research community in FAMT, especially by integrating younger members into it.
  • To provide continuity to what has been a very successful model for building and consolidating a productive research community in FAMT.

Motivation text license
  Creative Commons BY 4.0
  Albert Atserias, Christoph Berkholz, Kousha Etessami, and Joanna Ochremiak

Related Dagstuhl-Seminar

Classification

  • Logic In Computer Science

Keywords

  • Finite model theory
  • Descriptive complexity
  • Random structures and combinatorics
  • Database theory
  • Automata and game theory

Dokumentation

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.

Publikationen

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