Shrinking games and local formulas (Q1877096): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:01, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Shrinking games and local formulas |
scientific article |
Statements
Shrinking games and local formulas (English)
0 references
16 August 2004
0 references
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.
0 references
Ehrenfeucht-Fraïssé games
0 references
finite model theory
0 references
local formulas
0 references
quantifier rank
0 references