paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A note on first-order spectra with binary relations

关于带二元关系的一阶谱的注记
LMCS vol.Volume 14, Issue 22018匹配度 1/10 · 论文研究一阶谱与 Asser 猜想,属于有限模型论/逻辑与自动机理论,与用户关注的静态分析、LLM/Agent 程序分析、浮点程序分析及贝叶斯程序分析均无直接交叉。引用 0 inbox
Eryk Kopczynski, Tony Tan
crossref: 2026-09-10

AI 速览

一句话:证明多变量二元关系一阶句子的谱可线性归约到单一对称二元关系,且模型均为二部图,从而简化 Asser 猜想。

论文研究一阶句子的谱,即其有限模型基数集合,特别关注使用至少三个变量、仅含二元关系的句子。作者给出构造性归约:对任意此类句子 Φ,构造同变量数的句子 Φ',它只使用一个对称二元关系,并使其谱与 Φ 的谱线性成正比;同时 Φ' 的所有模型都是二部图。基于该结果,作者得到推论:要判定谱类是否对补集封闭(Asser 猜想),只需考虑仅用三个变量且模型限于无向二部图的句子。这为 Asser 猜想提供了更受限的判定对象,并连接有限模型论与二部图结构。

问题
研究一阶谱(有限模型基数集合)在二元关系与至少三变量情形下的结构,以及 Asser 猜想(谱类是否对补集封闭)可否归约到更简单的句子类。
方法
通过构造性翻译/归约:从任意至少三变量、二元关系的一阶句子 Φ 构造同变量数但仅含一个对称二元关系的句子 Φ',并分析其模型为二部图且谱线性成比例。
评估
以数学证明和构造性归约作为评估方式;关键结果是谱的线性比例保持及二部图模型限制,并由此得到 Asser 猜想的充分归约。
原文摘要(Abstract)

The spectrum of a first-order sentence is the set of the cardinalities of its finite models. In this paper, we consider the spectra of sentences over binary relations that use at least three variables. We show that for every such sentence $\Phi$, there is a sentence $\Phi'$ that uses the same number of variables, but only one symmetric binary relation, such that its spectrum is linearly proportional to the spectrum of $\Phi$. Moreover, the models of $\Phi'$ are all bipartite graphs. As a corollary, we obtain that to settle Asser's conjecture, i.e., whether the class of spectra is closed under complement, it is sufficient to consider only sentences using only three variables whose models are restricted to undirected bipartite graphs.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot411,
  title = {A note on first-order spectra with binary relations},
  author = {Eryk Kopczynski and Tony Tan},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 2},
  year = {2018},
  doi = {10.23638/lmcs-14(2:4)2018}
}