paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Positive First-order Logic on Words

字上的正一阶逻辑
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 2/10 · 该论文属于纯粹的逻辑与自动机理论研究,关注有限词上的 FO+ 可定义性与 Lyndon 保持定理,与用户核心方向(静态分析、Agentic/LLM、浮点或贝叶斯程序分析)几乎没有直接交集,仅在最宽泛的“形式化方法基础”层面有微弱关联。引用 0 inbox
Denis Kuperberg
crossref: 2026-09-12

AI 速览

一句话:给出 Lyndon 保持定理在有限结构上失败的简单证明,并证明正则语言的 FO+ 可定义性不可判定。

本文研究有限字上的一阶逻辑片段 FO+,其中一元谓词只能以正出现的方式使用。作者构造了一个在 FO 中可定义、且对一元谓词单调的语言,证明它不能用 FO+ 定义。这一结果说明 Lyndon 保持定理在有限结构上不再成立,并给出了一个简单的反例证明。此外,论文还考察 FO+ 可定义性的判定问题:给定一个正则语言,判定它是否可由 FO+ 定义是不可判定的。该工作揭示了正性限制与有限模型语义之间的张力,并为有限字上的描述复杂性与保持定理提供了新的边界结果。

问题
研究有限字上只允许一元谓词正出现的 FO+ 片段,厘清其表达能力及其与 FO、单调性和 Lyndon 保持定理的关系。
方法
构造一个 FO 可定义且对一元谓词单调、但不能用 FO+ 定义的语言,并证明给定正则语言判定其 FO+ 可定义性是不可判定的。
评估
以理论证明为主:给出反例证明保持定理失效,并通过不可判定性结果界定 FO+ 的判定边界;无实验评估。
原文摘要(Abstract)

We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is an FO-definable language that is monotone in monadic predicates but not definable in FO+. This provides a simple proof that Lyndon's preservation theorem fails on finite structures. We additionally show that given a regular language, it is undecidable whether it is definable in FO+.

链接与引用

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

BibTeX
@inproceedings{paperbot6172,
  title = {Positive First-order Logic on Words},
  author = {Denis Kuperberg},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470602}
}