LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.


Duality and limits of finite structures

10.12.2019, 11:00
Pavillon des Jardins
Luca Reggio (University of Bern)

A systematic approach to the study of limits of finite structures, motivated by investigations in graph theory, has been developed by Nešetřil and Ossona de Mendez starting in 2012. The basic construction, which goes under the name of Stone pairing, consists in embedding the set of finite structures into a space of probability measures which is complete, so that every Cauchy sequence of finite structures admits a limit. This limit point can be concretely realized as a measure. I will explain how a finer-grained variant of the Stone pairing corresponds — via duality — to enriching first-order logic with certain probability operators, and provide an axiomatisation of this logic. Further, I will indicate some potential applications of this approach to finite model theory (including, e.g., 0-1 laws), and relate it to first-order quantification in formal language theory. This talk is based on joint work with M. Gehrke and T. Jakl.

About LSV