Abstract

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.