COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Lovász' Theorem and Comonads in Finite Model Theory

## Lovász' Theorem and Comonads in Finite Model TheoryAdd to your list(s) Download to your calendar using vCal - Tomas Jakl, University of Cambridge
- Friday 13 November 2020, 14:00-15:00
- Online.
If you have a question about this talk, please contact Jamie Vicary. https://us02web.zoom.us/j/177472153?pwd=MFgwd0EzY05QSGtpSDc2dU16aG9wdz09 In this talk I will present our joint work with Anuj Dawar and Luca Reggio. More than 50 years ago László Lovász showed that, in order to determine an isomorphism of two finite relational structures, it is enough to test that they both admit the same number of homomorphisms from any other finite structure. This result has been revisited recently by Zdeněk Dvořák and Martin Grohe. They showed that instead of an isomorphism we obtain a logical equivalence w.r.t a fragment of first-order logic, if we restrict the test structures to a given smaller category. We proved that all three of the above results can be captured in the framework of Samson Abramsky, Anuj Dawar, et al. The framework uses graded comonads to capture various combinatorial and logical properties of relational structures. Our new proofs make use of the graded comonads. As a byproduct we obtain a new result for modal logic simply by changing the graded comonad in question. This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series. ## This talk is included in these lists:- All Talks (aka the CURE list)
- Computer Laboratory talks
- Computing and Mathematics
- Interested Talks
- Logic and Semantics Seminar (Computer Laboratory)
- Online
- School of Technology
- Trust & Technology Initiative - interesting events
- bld31
- yk373's list
Note that ex-directory lists are not shown. |
## Other listsAccounting Seminars, CJBS Meeting the Challenge of Healthy Ageing in the 21st Century MedSin Cambridge## Other talksSpinning up planetary bodies by pebble accretion Bloodlines of the British Companion-disk interaction in exoplanetary systems, a (mostly) observational perspective Seeing like a welfare state: sickle cell disease, medical racism and patient advocacy in the National Health Service, 1975–1993 The Welcome Sanger Institute’s Scientific Plans 2021-2026 Rethinking the QCD axion |