BCTCS 2021

Regular Talk
Logics Game Theory Language Theory

Partition Games, Compositionally: Structure & Power of Linear Algebraic Games

Adam Ó Conghaile

on  Mon, 15:30 ! Live for  30min

For a long-time, Spoiler-Duplicator games have been a crucial tool for proving expressibility upper bounds on logical languages. In the last 5 years, beginning with a seminal paper of Abramsky, Dawar and Wang[1] on the pebbling comonad, a large body of recent work has exposed a fascinating compositional structure lying beneath the surface of many of these games, relating games to each other and to relevant structural parameters such as treewidth. Recent work in this area of so-called game comonads has helped to better understand the pebble game [1], modal bisimulation game [2] and games for generalised quantifiers [3]. One class of games whose category theoretic structure is not yet understood is that of partition games. As explored in the thesis of Bjarki Holm[4], partitions give a rich grammar for constructing Spoiler-Duplicator games for various logics including the matrix equivalence and invertible maps games for linear algebraic logics. In my talk, I will briefly review recent developments in game comonads before introducing partition games and describing where they might fit into this compositional picture. The latter part of this talk is based on ongoing work with Anuj Dawar.

 Overview  Program