paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A weakest pre-expectation semantics for mixed-sign expectations

混合符号期望的最弱前置期望语义
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 4/10 · 论文研究概率程序的最弱前置期望语义,属于形式语义与程序验证,与用户关注的贝叶斯程序分析/概率程序验证有间接关联,但未涉及 LLM/Agent、浮点程序分析或工业落地,因此匹配度有限。引用 30 inbox
Benjamin Lucien Kaminski, Joost-Pieter Katoen
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出可处理混合符号无界随机变量期望的概率程序最弱前置期望演算,保证语义总良定义且可靠。

本文为概率程序引入一种最弱前置条件风格的演算,用于推理程序执行后混合符号、无界随机变量的期望值(pre-expectations)。传统最弱前置期望演算通常依赖最小不动点,但混合符号期望可能不存在,标准论证不再适用。作者将 while 循环语义定义为对零元素迭代应用泛函的极限,并证明该语义总是良定义,即使相关期望值不存在。文中证明该演算具有可靠性并支持组合推理,还提出基于不变式的方法来推理循环的 pre-expectations。该工作扩展了概率程序最弱前置期望语义的适用范围。

问题
研究如何对概率程序执行后混合符号、无界随机变量的期望进行最弱前置条件式推理,尤其是传统基于最小不动点的语义不适用时。
方法
将 while 循环语义定义为对零元素迭代应用泛函的极限,给出最弱前置期望风格演算,并证明其可靠性与组合性,同时提出基于不变式的循环推理方法。
评估
评估以理论证明为主:证明语义始终良定义、演算可靠,并支持组合推理与不变式推理;摘要未报告工具实现或实验。
原文摘要(Abstract)

We present a weakest-precondition-style calculus for reasoning about the expected values (pre-expectations) of mixed-sign unbounded random variables after execution of a probabilistic program. The semantics of a while-loop is defined as the limit of iteratively applying a functional to a zero-element just as in the traditional weakest pre-expectation calculus, even though a standard least fixed point argument is not applicable in our semantics. A striking feature of our semantics is that it is always well-defined, even if the expected values do not exist. We show that the calculus is sound and allows for compositional reasoning. Furthermore, we present an invariant-based approach for reasoning about pre-expectations of loops.

链接与引用

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

BibTeX
@inproceedings{KaminskiK17,
  title = {A weakest pre-expectation semantics for mixed-sign expectations},
  author = {Benjamin Lucien Kaminski and Joost-Pieter Katoen},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005153}
}