Multi-Structural Games and Number of Quantifiers
Multi-Structural Games and Number of Quantifiers
复制标题
多结构博弈和量词数量
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Nikhil Vyas
中科院分区：
文献类型：
--
作者：
Ronald Fagin;J. Lenchner;Kenneth W. Regan;Nikhil Vyas
我们研究多结构博弈，在两个结构集合${\mathcal{A}}$和${\mathcal{B}}$上进行。这些博弈推广了Escherichfeucht-Fraïssé博弈。Escherichfeucht-Fraïssé博弈捕获的是一阶句子的量词等级，而多结构博弈捕获的是量词的数量，在这个意义上，Spoiler赢得了r轮博弈，当且仅当有一个一阶句子最多有r个量词，其中${\mathcal{A}}$中的每个结构都满足n，而${\mathcal{B}}$中没有结构满足n。我们使用这些游戏，以提供一个完整的表征所需的量词的数量来区分不同大小的线性订单，并开发机器分析结构超出线性订单。
We study multi-structural games, played on two sets ${\mathcal{A}}$ and ${\mathcal{B}}$ of structures. These games generalize Ehrenfeucht-Fraïssé games. Whereas Ehrenfeucht-Fraïssé 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 ϕ with at most r quantifiers, where every structure in ${\mathcal{A}}$ satisfies ϕ and no structure in ${\mathcal{B}}$ satisfies ϕ. 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.