paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Alignment Completeness for Relational Hoare Logics

关系霍尔逻辑的对齐完备性
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 3/10 · 论文属于关系霍尔逻辑与程序验证的形式化理论,虽与形式化验证相关,但不涉及 LLM/Agent 改进验证、静态分析在 ML/Agentic 程序中的应用,也不涉及浮点或贝叶斯程序分析,与画像核心交叉方向匹配度低。引用 0 inbox
Ramana Nagasamudram, David A. Naumann
crossref: 2026-09-12

AI 速览

一句话:提出对齐完备性概念,用归纳断言法与乘积自动机刻画关系霍尔逻辑的规则完备性。

关系霍尔逻辑(RHL)用于推理程序之间的关系。已有若干 RHL 包含顺序乘积规则,可从普通霍尔逻辑(HL)的判定导出关系正确性判定;其他规则虽实用,但顺序乘积本身与 HL 已相对完备。为更合理地评价 RHL,本文引入“对齐完备性”,基于归纳断言方法与乘积自动机给出定义。作者对若干不同规则集给出了对齐完备性结果,说明这些规则组合能够覆盖哪些对齐模式下的关系推理,并讨论该概念对设计更丰富编程语言的 RHL 与关系验证器的指导意义。

问题
如何超越相对完备性,更令人满意地评估关系霍尔逻辑(RHL)中不同规则集的推理能力与完备性。
方法
引入基于归纳断言方法和乘积自动机的对齐完备性概念,并对若干不同 RHL 规则集证明相应的对齐完备性结果。
评估
以定义与理论证明的形式给出多组规则集的对齐完备性结果,分析其在不同对齐模式下的覆盖能力。
原文摘要(Abstract)

Relational Hoare logics (RHL) provide rules for reasoning about relations between programs. Several RHLs include a rule we call sequential product that infers a relational correctness judgment from judgments of ordinary Hoare logic (HL). Other rules embody sensible patterns of reasoning and have been found useful in practice, but sequential product is relatively complete on its own (with HL). As a more satisfactory way to evaluate RHLs, a notion of alignment completeness is introduced, in terms of the inductive assertion method and product automata. Alignment completeness results are given to account for several different sets of rules. The notion may serve to guide the design of RHLs and relational verifiers for richer programming languages and alignment patterns.

链接与引用

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

BibTeX
@inproceedings{paperbot6221,
  title = {Alignment Completeness for Relational Hoare Logics},
  author = {Ramana Nagasamudram and David A. Naumann},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470690}
}