Shrinking games and local formulas
type: Item
instance of: scholarly article
title: Shrinking games and local formulas
zbMATH Open document ID: 1055.03022
author: H. Jerome Keisler
author: Wafik Boulos Lotfallah
published in: Annals of Pure and Applied Logic
publication date: 2004-08-16T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03C13
zbMATH DE Number: 2091345
zbMATH Keywords: Ehrenfeucht-Fraïssé games
zbMATH Keywords: finite model theory
zbMATH Keywords: local formulas
zbMATH Keywords: quantifier rank
reviewed by: M. M. Arslanov
MaRDI profile type: Publication
full work available at URL: j.apal.2004.01.004
OpenAlex ID: W2140014237
cites work: An application of games to the completeness problem for formalized theories
cites work: Q3666827
cites work: Logics with counting and local properties
cites work: On winning Ehrenfeucht games and monadic NP
cites work: Q3836531
DOI: 10.1016/J.APAL.2004.01.004
description: scientific article; zbMATH DE number 2091345