TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 20451

Logic and Random Discrete Structures Cancelled

( 01. Nov – 06. Nov, 2020 )

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/20451

Ersetzt durch
Dagstuhl-Seminar 22061: Logic and Random Discrete Structures (2022-02-06 - 2022-02-11) (Details)

Organisatoren

Kontakt

Motivation

The analysis of large random discrete structures, such as trees, graphs, or permutations, is a main research focus in contemporary discrete mathematics. The overall goal is to understand the “typical structure'' of objects from a given class by studying the behavior of a randomly chosen object from that class. Logic provides a useful and powerful formalism for classifying discrete structures and for expressing properties of discrete structures; for this reason, the lens of logic has also been used in the study of random discrete structures.

The connections between logic and random discrete structure trace their origin to the discovery of the zero-one law for first-order logic on finite structures under the uniform probability measure, a celebrated result due to Glebskii et al. and, independently, to Fagin. Since the discovery of this result five decades ago, logical limit laws or convergence laws have been established for several different models of random discrete structures and for various logics, including fragments of second-order logic and extensions of first-order logic with fixed-point constructs. Furthermore, fundamental algorithmic problems associated with the computation of asymptotic probabilities have been explored.

In recent years, connections between logic and random discrete structures have emerged in different frameworks that span a broad spectrum of areas, from extremal combinatorics to modeling uncertainty in data, and typically use distinct techniques. For example, the frameworks of graph limits and flag algebras are concerned with the study of asymptotic densities of structures, while the framework of probabilistic databases is concerned with the study of queries posed against inherently uncertain data. Logic has been successfully used in all these frameworks to provide a coherent viewpoint and to contribute to the establishment of unifying results.

The main aim of this Dagstuhl Seminar is to bring together researchers, both junior and senior, from different areas, such as logic, combinatorics, data uncertainty, and randomized algorithms, to share state-of-the-art advances in the interaction between these areas, present overviews of methods and techniques based on the combination of logic and discrete random structures, discuss open problems, and shape future directions of research in these fields.

Copyright Erich Grädel, Phokion G. Kolaitis, Tobias Müller, and Marc Noy

Teilnehmer
  • Erich Grädel (RWTH Aachen, DE) [dblp]
  • Tobias Müller (University of Groningen, NL) [dblp]
  • Marc Noy (UPC Barcelona Tech, ES) [dblp]

Klassifikation
  • data structures / algorithms / complexity
  • verification / logic

Schlagworte
  • Logic. Model theory. Random Graphs. Combinatorics. Complexity theory