一句话：精细分析多结构博弈，并引入量词–变量树博弈与语法博弈，同时刻画一阶逻辑的量词数和变量数。
本文研究多结构（MS）博弈与 Ehrenfeucht–Fraïssé（EF）博弈的精细比较。MS 博弈在两组结构上进行且 Duplicator 可复制结构；作者指出结构集合的使用至关重要，并说明在结构对上玩时它刻画固定量词数一阶句子的布尔组合。通过分析博弈中实现的类型，论文刻画了 Spoiler 不在先前着法上叠置这一变体的表达力。第二部分关注同时刻画一阶逻辑的量词数与变量数：自然 MS 变体无法做到；作者引入量词–变量树博弈，并推广为语法博弈族，以同时刻画合理的语法度量与变量数。
Multi-structural (MS) games are combinatorial games that capture the number of quantifiers of first-order sentences. On the face of their definition, MS games differ from Ehrenfeucht-Fraisse (EF) games in two ways: first, MS games are played on two sets of structures, while EF games are played on a pair of structures; second, in MS games, Duplicator can make any number of copies of structures. In the first part of this paper, we perform a finer analysis of MS games and develop a closer comparison of MS games with EF games. In particular, we point out that the use of sets of structures is of the essence and that when MS games are played on pairs of structures, they capture Boolean combinations of first-order sentences with a fixed number of quantifiers. After this, we focus on another important difference between MS games and EF games, namely, the necessity for Spoiler to play on top of a previous move in order to win some MS games. Via an analysis of the types realized during MS games, we delineate the expressive power of the variant of MS games in which Spoiler never plays on top of a previous move. In the second part we focus on simultaneously capturing number of quantifiers and number of variables in first-order logic. We show that natural variants of the MS game do *not* achieve this. We then introduce a new game, the quantifier-variable tree game, and show that it simultaneously captures the number of quantifiers and number of variables. We conclude by generalizing this game to a family of games, the *syntactic games*, that simultaneously capture reasonable syntactic measures and the number of variables.
@article{paperbot2696,
title = {Multi-Structural Games and Beyond},
author = {Marco Carmosino and Ronald Fagin and Neil Immerman and Phokion Kolaitis and Jonathan Lenchner and Rik Sengupta},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 4},
year = {2024},
doi = {10.46298/lmcs-20(4:27)2024}
}