paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On Logics and Homomorphism Closure

论逻辑与同态闭包
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 1/10 · 论文属于数理逻辑/有限模型论,研究逻辑句子模型类的同态闭包与可计算性,不涉及程序静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析。因此与用户研究方向基本无关。引用 1 inbox
Manuel Bodirsky, Thomas Feller, Simon Knauer, Sebastian Rudolph
crossref: 2026-09-12

AI 速览

一句话:系统研究逻辑句子模型类的同态闭包问题,并刻画一阶与二阶逻辑多片段的计算性质。

谓词逻辑是刻画关系结构类的首选形式,而同态用于描述关系结构间的对应。本文研究逻辑句子模型类的同态闭包(homclosure)所引发的若干基本问题:给定结构是否属于某句子的同态闭包、句子本身是否同态封闭、同态闭包能否在某一逻辑中被刻画,以及同态封闭句子在某些逻辑中是否有规范形式。作者针对一阶与二阶谓词逻辑的多种片段,系统澄清这些问题的可计算性质,给出相应的可判定性、复杂度或不可判定性结论,从而揭示逻辑表达力与同态闭包之间的相互依赖关系。

问题
研究逻辑句子的(有限或任意)模型类在同态闭包下的基本性质,包括成员判定、句子同态封闭性、逻辑可刻画性与规范形式。
方法
以模型论与逻辑片段分析为工具,对一阶和二阶谓词逻辑的广泛片段逐一考察上述同态闭包问题。
评估
通过可计算性与复杂度分类,厘清各逻辑片段中这些问题的可判定性、复杂度或不可判定性等计算性质。
原文摘要(Abstract)

Predicate logic is the premier choice for specifying classes of relational structures. Homomorphisms are key to describing correspondences between relational structures. Questions concerning the interdependencies between these two means of characterizing (classes of) structures are of fundamental interest and can be highly non-trivial to answer. We investigate several problems regarding the homomorphism closure (homclosure) of the class of all (finite or arbitrary) models of logical sentences: membership of structures in a sentence's homclosure; sentence homclosedness; homclosure characterizability in a logic; normal forms for homclosed sentences in certain logics. For a wide variety of fragments of first- and second-order predicate logic, we clarify these problems' computational properties.

链接与引用

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

BibTeX
@inproceedings{paperbot6192,
  title = {On Logics and Homomorphism Closure},
  author = {Manuel Bodirsky and Thomas Feller and Simon Knauer and Sebastian Rudolph},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470511}
}