paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Strong-separation Logic

强分离逻辑
TOPLAS 44(3)2022匹配度 3/10 · 该论文属于程序验证与形式语义领域的纯理论工作,研究分离逻辑的可判定性,与用户当前关注的 LLM/Agent 改进静态分析或形式化验证、以及浮点/贝叶斯程序分析与 LLM 交叉等方向没有直接关联。虽然形式验证是用户感兴趣的子领域之一,但本文不涉及 AI、LLM 或工业落地,匹配度较低。引用 2 inbox
Jens Pagel, Florian Zuleger
crossref: 2026-09-10

AI 速览

一句话:提出强分离逻辑,通过限制分离合取的语义,在保留魔法棒和归纳谓词的同时恢复可判定性。

大多数分离逻辑自动验证器基于符号堆片段,该片段不支持魔法棒算子,也不允许经典布尔算子作用于空间公式。这是因为支持魔法棒很快会导致不可判定性,尤其当与用于推理数据结构的归纳谓词结合时。为规避这些不可判定性结果,我们提出为分离合取赋予一种更严格的语义,由此得到强分离逻辑。我们论证,该逻辑可以像标准分离逻辑一样用于符号执行和溯因推理,同时在同时存在魔法棒和归纳谓词(我们考虑列表段谓词和树谓词)时仍保持可判定性——而这一特征组合在标准语义下会导致不可判定性。

问题
大多数分离逻辑验证器基于符号堆片段,因魔法棒和归纳谓词结合会导致不可判定性而受限。
方法
为分离合取赋予更严格的语义,定义强分离逻辑,并论证其可用于符号执行和溯因推理。
评估
证明该逻辑在同时包含魔法棒和归纳谓词(列表段和树谓词)时仍可判定,而标准语义下不可判定。
原文摘要(Abstract)

Most automated verifiers for separation logic are based on the symbolic-heap fragment, which disallows both the magic-wand operator and the application of classical Boolean operators to spatial formulas. This is not surprising, as support for the magic wand quickly leads to undecidability, especially when combined with inductive predicates for reasoning about data structures. To circumvent these undecidability results, we propose assigning a more restrictive semantics to the separating conjunction. We argue that the resulting logic, strong-separation logic, can be used for symbolic execution and abductive reasoning just like “standard” separation logic, while remaining decidable even in the presence of both the magic wand and inductive predicates (we consider a list-segment predicate and a tree predicate)—a combination of features that leads to undecidability for the standard semantics.

链接与引用

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

BibTeX
@article{paperbot1611,
  title = {Strong-separation Logic},
  author = {Jens Pagel and Florian Zuleger},
  journal = {ACM Transactions on Programming Languages and Systems},
  volume = {44},
  number = {3},
  year = {2022},
  doi = {10.1145/3498847}
}