BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:A duality theoretic view on limits of finite structures - Tomáš 
 Jakl\, Computer Lab
DTSTART:20200228T140000Z
DTEND:20200228T150000Z
UID:TALK139981@talks.cam.ac.uk
CONTACT:Jean Pichon-Pharabod
DESCRIPTION:A systematic theory of structural limits for finite models has
  been developed by Nešetřil and Ossona de Mendez. It is based on the ins
 ight that the collection of finite structures can be embedded\, via a map 
 they call the Stone pairing\, in a space of measures\, where the desired l
 imits can be computed. We show that a closely related but finer grained sp
 ace of measures arises -- via Stone-Priestley duality and the notion of ty
 pes from model theory -- by enriching the expressive power of first-order 
 logic with certain "probabilistic operators". We provide a sound and compl
 ete calculus for this extended logic and expose the functorial nature of t
 his construction.\n\nThe consequences are two-fold. On the one hand\, we i
 dentify the logical gist of the theory of structural limits. On the other 
 hand\, our construction shows that the duality-theoretic variant of the St
 one pairing captures the adding of a layer of quantifiers\, thus making a 
 strong link to recent work on semiring quantifiers in logic on words. In t
 he process\, we identify the model theoretic notion of types as the unifyi
 ng concept behind this link. These results contribute to bridging the stra
 nds of logic in computer science which focus on semantics and on more algo
 rithmic and complexity related areas\, respectively.
LOCATION:Computer Laboratory\, room SS03
END:VEVENT
END:VCALENDAR