Shrinking games and local formulas (Q1877096): Difference between revisions

The authors introduce shrinking Ehrenfeucht-Fraïssé games in which the players move in neighborhoods whose radii shrink at a rate which depends on a sequence \({\mathbf s}=\{s_0,s_1,\ldots,s_{n-1}\}\) of scattering parameters. By definition the sequence \({\mathbf s}\) shrinks rapidly if \(2r_m\leq s_m\) for all \(m<n\). Here the sequence \(\{r_m\}\), with \(r_0=1\) and \(r_{n+1}=2r_n+s_n\), consists of the so-called ``local radii''. In the paper under review the authors consider Ehrenfeucht-Fraïssé games by two players, Spoiler and Duplicator. The main result of the paper is the following: if the sequence \({\mathbf s}\) shrinks rapidly and Duplicator has a winning strategy for the \(n\)-round shrinking game on two structures, then Duplicator has a winning strategy for the \(n\)-round Ehrenfeucht-Fraïssé game. The authors consider also some applications of this result.