Marie Skłodowska-Curie project D-FINED

From 1 February 2020 to 31 January 2022 I was a Marie Skłodowska-Curie fellow at the Department of Computer Science of the University of Oxford. My project D-FINED was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 837724.


Project synopsis

Finite model theory is the specialisation of model theory to finite structures, and has been called “the logic of computer science” since in the latter field the basic models of computation are finite. Many classical results of model theory, such as the compactness theorem, fail when restricted to finite models. For this reason, finite model theory has developed independently from model theory and the research communities, as well as the techniques, are almost disjoint. Finite model theory exemplifies a strand in the field of logic in computer science focussing on expressiveness and complexity (Power), as opposed to the one focussing on semantics and compositionality (Structure). The project D-FINED (Duality for finite models) aims to apply duality theory and categorical tools to bridge the gap between the semantics methods of model theory, and the combinatorial and complexity-theoretic methods of finite model theory, i.e., to relate Structure and Power.

The three main goals in this direction are to:

  1. Develop a structural approach to the study of spaces of finite structures, based on duality and categorical methods.
  2. Extend the applicability of these methods from finite structures to tame classes of infinite structures.
  3. Relate the duality approach to existing categorical semantics, such as Lawvere's hyperdoctrines and the game comonads recently introduced by Abramsky, Dawar and their collaborators.

This project may contribute to a more unified view of logic in mathematics and computer science, providing new tools for a structural approach to more algorithmic and complexity-oriented areas of logic such as finite model theory.


Scientific output

  1. Luca Reggio, Beth definability and the Stone-Weierstrass Theorem, Annals of Pure and Applied Logic, Vol. 172, Issue 8, 102990, 2021.
  2. Anuj Dawar, Tomas Jakl and Luca Reggio, Lovász-type theorems and game comonads, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LiCS), pp. 1-13, 2021.
  3. Samson Abramsky and Luca Reggio, Arboreal categories and resources, Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs Vol. 198, pp. 115:1-115:20, 2021.
  4. Mai Gehrke, Tomas Jakl and Luca Reggio, A duality theoretic view on limits of finite structures: Extended version, Logical Methods in Computer Science, Vol. 18, Issue 1, pp. 16:1-16:38, 2022.
  5. Luca Reggio, Polyadic sets and homomorphism counting, Advances in Mathematics, Vol. 410, Part A, 108712, 2022.
  6. Mai Gehrke, Tomas Jakl and Luca Reggio, A Cook’s tour of duality in logic. From quantifiers, through Vietoris, to measures, Samson Abramsky on Logic and Structure in Computer Science and Beyond, Outstanding Contributions to Logic, Vol. 25, Springer, 2023.
  7. George Metcalfe and Luca Reggio, Model completions for universal classes of algebras: Necessary and sufficient conditions, Journal of Symbolic Logic, Vol. 88, issue 1, pp. 381-417, 2023.
  8. Marco Abbadini and Luca Reggio, Barr-exact categories and soft sheaf representations, Journal of Pure and Applied Algebra, Vol. 227, issue 12, 107413, 2023.
  9. Samson Abramsky and Luca Reggio, Arboreal categories: An axiomatic theory of resources, Logical Methods in Computer Science, Vol. 19, Issue 3, pp. 14:1-14:36, 2023.
  10. Samson Abramsky and Luca Reggio, Arboreal categories and equi-resource homomorphism preservation theorems, Annals of Pure and Applied Logic, Vol. 175, Issue 6, 103423, 2024.

Preprints of all publications mentioned above are available through open access repositories, see the Publications page.


For more on game comonads, have a look at the Co-Wiki maintained by Tomáš Jakl.