BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:A duality theoretic view on limits of finite struc
tures - Tomáš Jakl\, Computer Lab
DTSTART;TZID=Europe/London:20200228T140000
DTEND;TZID=Europe/London:20200228T150000
UID:TALK139981AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/139981
DESCRIPTION:A systematic theory of structural limits for finit
e models has been developed by Nešetřil and Ossona
de Mendez. It is based on the insight that the co
llection of finite structures can be embedded\, vi
a a map they call the Stone pairing\, in a space o
f measures\, where the desired limits can be compu
ted. We show that a closely related but finer grai
ned space of measures arises -- via Stone-Priestle
y duality and the notion of types from model theor
y -- by enriching the expressive power of first-or
der logic with certain "probabilistic operators".
We provide a sound and complete calculus for this
extended logic and expose the functorial nature of
this construction.\n\nThe consequences are two-fo
ld. On the one hand\, we identify the logical gist
of the theory of structural limits. On the other
hand\, our construction shows that the duality-the
oretic variant of the Stone pairing captures the a
dding of a layer of quantifiers\, thus making a st
rong link to recent work on semiring quantifiers i
n logic on words. In the process\, we identify the
model theoretic notion of types as the unifying c
oncept behind this link. These results contribute
to bridging the strands of logic in computer scien
ce which focus on semantics and on more algorithmi
c and complexity related areas\, respectively.
LOCATION:Computer Laboratory\, room SS03
CONTACT:Jean Pichon-Pharabod
END:VEVENT
END:VCALENDAR