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

Lovász' Theorem and Comonads in Finite Model Theory

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Jamie Vicary.

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity