paperbot · PL 论文追踪

全部论文 待读 收藏

P2 From enhanced coinduction towards enhanced induction

从增强余归纳迈向增强归纳
POPL 6(POPL)2022匹配度 2/10 · 论文属于形式语义/并发理论,讨论归纳行为关系的证明增强与权重保持可靠性,未涉及 LLM/Agent、静态分析工具、浮点程序分析或贝叶斯程序分析,与用户核心的 PL 与 AI 交叉方向不匹配。引用 3 inbox
Davide Sangiorgi
crossref: 2026-09-10

AI 速览

一句话:为归纳行为关系建立类似余归纳增强的证明理论,并以权重保持条件保证增强函数的可靠性。

余归纳证明方法已有丰富的增强理论,广泛用于互模拟等行为关系。本文研究如何为归纳行为关系(由归纳可观测量定义)建立类似理论。与余归纳情形相同,理论使用半进展 R -> F(R):R 为进程关系,F 为关系函数,表示 R 中进程迁移可匹配且导数落入 F(R)。对给定预序,增强对应可靠函数,即 R -> F(R) 蕴含 R 包含于该预序;等价关系同理。作者为可观测量引入权重,并给出函数保持权重的条件以保证可靠性,证明该函数类包含非平凡函数且对若干函数构造子封闭,从而由简单可靠函数导出复杂证明技术。文中区分强语义与弱语义,并测试若干非平凡例子。

问题
如何为归纳定义的行为关系建立类似余归纳增强的通用证明理论,以系统获得复杂且可靠的证明技术。
方法
用半进展 R -> F(R) 和可靠函数刻画增强;为归纳可观测量引入权重,给出权重保持条件保证函数可靠,并研究该函数类的非平凡性与闭包性质;同时处理强语义和弱语义。
评估
在若干非平凡例子上测试所提出的增强技术。
原文摘要(Abstract)

There exist a rich and well-developed theory of enhancements of the coinduction proof method, widely used on behavioural relations such as bisimilarity. We study how to develop an analogous theory for inductive behaviour relations, i.e., relations defined from inductive observables. Similarly to the coinductive setting, our theory makes use of (semi)-progressions of the form R->F(R), where R is a relation on processes and F is a function on relations, meaning that there is an appropriate match on the transitions that the processes in R can perform in which the process derivatives are in F(R). For a given preorder, an enhancement corresponds to a sound function, i.e., one for which R->F(R) implies that R is contained in the preorder; and similarly for equivalences. We introduce weights on the observables of an inductive relation, and a weight-preserving condition on functions that guarantees soundness. We show that the class of functions contains non-trivial functions and enjoys closure properties with respect to desirable function constructors, so to be able to derive sophisticated sound functions (and hence sophisticated proof techniques) from simpler ones. We consider both strong semantics (in which all actions are treated equally) and weak semantics (in which one abstracts from internal transitions). We test our enhancements on a few non-trivial examples.

链接与引用

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

BibTeX
@article{paperbot1595,
  title = {From enhanced coinduction towards enhanced induction},
  author = {Davide Sangiorgi},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {6},
  number = {POPL},
  year = {2022},
  doi = {10.1145/3498679}
}