paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Successor-Invariant First-Order Logic on Classes of Bounded Degree

有界度类上的后继不变一阶逻辑
LMCS vol.Volume 17, Issue 32021匹配度 1/10 · 该论文属于纯逻辑与描述复杂性方向，研究有界度结构上后继不变一阶逻辑的表达能力，与用户关注的静态分析、LLM/Agent 结合、浮点程序分析或贝叶斯程序分析均无直接关系。引用 2 inbox
Julien Grange
逻辑与自动机
crossref: 2026-09-10

AI 速览

一句话：证明在有界度结构类上，后继不变一阶逻辑的表达能力不超过普通一阶逻辑。

本文研究后继不变一阶逻辑（successor-invariant FO）的表达能力。该逻辑在一阶逻辑基础上允许使用结构上的一个额外后继关系，但要求公式在有限结构上的有效性不依赖于具体后继关系的选择。作者考察有界度结构类，证明在这一限制下，后继不变一阶逻辑并不比普通一阶逻辑表达更多性质。该结果刻画了辅助后继关系在低度结构上的作用边界，将不变性与一阶表达力联系起来。

问题
后继不变一阶逻辑允许在有限结构上引入辅助后继关系，只要公式的有效性独立于该关系选择；本文关注它相对普通一阶逻辑是否严格更强，尤其是在有界度结构类上。
方法
通过对有界度结构类上的逻辑表达力进行分析，比较后继不变 FO 与 FO 的可定义性质。
评估
以理论证明的方式给出表达力结果：在有界度类上，后继不变 FO 不超出 FO；不涉及实验评估。
原文摘要（Abstract）

We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of an additional successor relation on the structure is allowed, as long as the validity of formulas is independent of the choice of a particular successor on finite structures. We show that when the degree is bounded, successor-invariant first-order logic is no more expressive than first-order logic.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@article{paperbot1284,
  title = {Successor-Invariant First-Order Logic on Classes of Bounded Degree},
  author = {Julien Grange},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 3},
  year = {2021},
  doi = {10.46298/lmcs-17(3:20)2021}
}