paperbot · PL 论文追踪

全部论文 待读 收藏

P2 When Locality Meets Preservation

当局部性与保持性相遇
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 0/10 · 该论文研究 Gaifman 正规形下局部句子的正布尔组合与局部初等嵌入保持性,属于纯模型论/有限模型理论,不涉及程序分析、静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析,与用户研究画像无实质关联。引用 1 inbox
Aliaume Lopez
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:刻画 Gaifman 正规形中局部句子的正布尔组合,证明其恰好对应局部初等嵌入下保持的一阶句子。

本文研究一阶逻辑中 Gaifman 正规形的一个片段,即基本局部句子的正布尔组合的表达力。作者证明该片段恰好刻画在局部初等嵌入下保持的一阶句子,从而给出新的一般保持定理,并推广 Łós-Tarski 定理。该完整保持结果在有限模型上通常失效,且相关判定问题不可判定。作为限制情形,作者研究扩展下保持,并证明扩展下保持当且仅当局部成立,由此得到若干具有良好性质的有限结构类。

问题
刻画一阶逻辑中局部句子的表达力,并在局部性概念下寻找新的保持定理。
方法
利用 Gaifman 正规形与局部初等嵌入,证明基本局部句子的正布尔组合与保持性之间的精确对应,并分析有限情形及相关判定问题。
评估
通过模型论证明建立保持定理,并给出相关判定问题的不可判定性结果;在扩展保持情形下导出具有良好性质的有限结构类。
原文摘要(Abstract)

This paper investigates the expressiveness of a fragment of first-order sentences in Gaifman normal form, namely the positive Boolean combinations of basic local sentences. We show that they match exactly the first-order sentences preserved under local elementary embeddings, thus providing a new general preservation theorem and extending the Łós-Tarski Theorem. This full preservation result fails as usual in the finite, and we show furthermore that the naturally related decision problems are undecidable. In the more restricted case of preservation under extensions, it nevertheless yields new well-behaved classes of finite structures: we show that preservation under extensions holds if and only if it holds locally.

链接与引用

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

BibTeX
@inproceedings{Lopez22,
  title = {When Locality Meets Preservation},
  author = {Aliaume Lopez},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3532498}
}