Combinatorial Games for Quantifier Number

Rik Sengupta

11:00 - 11:35AM, Sat, Jun 24.
Abstract

Multi-structural (MS) games (Immerman 1981, Fagin et al 2021) are two-player games played using colored pebbles on two sets A and B of structures, by two idealized players called Spoiler and Duplicator. It is known that these games capture the number of quantifiers, in the sense that Spoiler wins the r-round game if and only if A and B are distinguishable by an r-quantifier FO sentence. However, if we restrict the number of variables we are allowed to use in these sentences, MS games or their natural variants no longer capture the number of quantifiers. In this talk, we develop a game called the quantifier-variable tree (QVT) game that precisely captures the number of quantifiers, given a fixed number k of variables.

[Back to Schedule]