http://www.dagstuhl.de/17361

03. – 08. September 2017, Dagstuhl Seminar 17361

Finite and Algorithmic Model Theory

Organisatoren

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 erteilen

Susanne Bach-Bernhard zu administrativen Fragen

Andreas Dolzmann zu wissenschaftlichen Fragen

Dagstuhl Reports

Wir bitten die Teilnehmer uns bei der notwendigen Dokumentation zu unterstützen und Abstracts zu ihrem Vortrag, Ergebnisse aus Arbeitsgruppen, etc. zur Veröffentlichung in unserer Serie Dagstuhl Reports einzureichen über unser
Dagstuhl Reports Submission System.

Dokumente

Teilnehmerliste
Gemeinsame Dokumente

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

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

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

Publikationen

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.