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:Lovász' Theorem and Comonads in Finite Model Theor
y - Tomas Jakl\, University of Cambridge
DTSTART;TZID=Europe/London:20201113T140000
DTEND;TZID=Europe/London:20201113T150000
UID:TALK152596AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/152596
DESCRIPTION:https://us02web.zoom.us/j/177472153?pwd=MFgwd0EzY0
5QSGtpSDc2dU16aG9wdz09\n\nIn this talk I will pres
ent our joint work with Anuj Dawar and Luca\nReggi
o.\n\nMore than 50 years ago László Lovász showed
that\, in order to determine\nan isomorphism of tw
o finite relational structures\, it is enough to t
est\nthat they both admit the same number of homom
orphisms from any other\nfinite structure. This re
sult has been revisited recently by Zdeněk\nDvořák
and Martin Grohe. They showed that instead of an
isomorphism we\nobtain a logical equivalence w.r.t
a fragment of first-order logic\, if\nwe restrict
the test structures to a given smaller category.\
n\nWe proved that all three of the above results c
an be captured in the\nframework of Samson Abramsk
y\, Anuj Dawar\, et al. The framework uses\ngraded
comonads to capture various combinatorial and log
ical properties\nof relational structures. Our new
proofs make use of the graded\ncomonads. As a byp
roduct we obtain a new result for modal logic simp
ly\nby changing the graded comonad in question.
LOCATION:Online
CONTACT:Jamie Vicary
END:VEVENT
END:VCALENDAR