Pebble games with algebraic rules

Abstract

We define a general framework of $\textit{partition games}$ for formulating two-player pebble games over finite structures. The framework we introduce includes as special cases the pebble games for finite-variable logics with and without counting. It also includes a $\textit{matrix-equivalence game}$, introduced here, which characterises equivalence in the finite-variable fragments of the matrix-rank logic of [Dawar et al. 2009]. We show that one particular such game in our framework, which we call the $\textit{invertible-map game}$, yields a family of polynomial-time approximations of graph isomorphism that is strictly stronger than the well-known Weisfeiler-Leman method. We show that the equivalence defined by this game is a refinement of the equivalence defined by each of the games for finite-variable logics.