03. – 08. September 2017, Dagstuhl Seminar 17361
Finite and Algorithmic Model Theory
Auskunft zu diesem Dagstuhl Seminar erteilen
Susanne Bach-Bernhard zu administrativen Fragen
Andreas Dolzmann zu wissenschaftlichen Fragen
Programm des Dagstuhl Seminars (Hochladen)
(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)
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 and Erich Grädel and Phokion G. Kolaitis and Thomas Schwentick
- Data Bases / Information Retrieval
- Data Structures / Algorithms / Complexity
- Verification / Logic
- Finite model theory
- Descriptive Complexity
- Database Theory
- Model Checking
- Knowledge Representation
- Independence Logic