一句话：提出多结构博弈，以轮数精确刻画一阶句子的量词数量，并完全刻画区分不同大小线性序所需的最少量词数。
论文研究多结构博弈：该博弈在两个结构集合 A 与 B 上进行，是 Ehrenfeucht-Fraïssé 博弈的推广。经典 EF 博弈刻画一阶句子的量词秩，而多结构博弈刻画量词总数：Spoiler 在第 r 轮获胜，当且仅当存在一个至多含 r 个量词的一阶句子 φ，使得 A 中每个结构都满足 φ，而 B 中每个结构都不满足 φ。作者利用该博弈完整刻画了区分不同大小线性序所需的最少量词数，并发展了可用于分析线性序之外结构的机器。
We study multi-structural games, played on two sets $\mathcal{A}$ and $\mathcal{B}$ of structures. These games generalize Ehrenfeucht-Fra\"{i}ss\'{e} games. Whereas Ehrenfeucht-Fra\"{i}ss\'{e} games capture the quantifier rank of a first-order sentence, multi-structural games capture the number of quantifiers, in the sense that Spoiler wins the $r$-round game if and only if there is a first-order sentence $\phi$ with at most $r$ quantifiers, where every structure in $\mathcal{A}$ satisfies $\phi$ and no structure in $\mathcal{B}$ satisfies $\phi$. We use these games to give a complete characterization of the number of quantifiers required to distinguish linear orders of different sizes, and develop machinery for analyzing structures beyond linear orders.
@article{paperbot3451,
title = {Multi-Structural Games and Number of Quantifiers},
author = {Ronald Fagin and Jonathan Lenchner and Kenneth W. Regan and Nikhil Vyas},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:10)2025}
}