论文标题
相对完整的概率程序验证
Relatively Complete Verification of Probabilistic Programs
论文作者
论文摘要
我们研究了用于指定定量“断言”的语法 - 函数映射程序为数字 - 用于概率程序验证。我们证明了我们的语法在以下意义上具有表现力：如果在我们的语法中表达函数$ f $的任何概率程序$ c $，则将每个初始状态$σ$映射到在$ c $ oon $ c $ on $ c $ on $ c $ on $ c $ oon $ cPect $ pree $ \ texteit $ \ texteit $ \ textep的最终状态中评估的每个初始状态$σ$的函数c $ c $ c $ c $ \ textect）是语法。 结果，我们获得了一个相对完整的验证系统，用于以库克的意义来推理预期值和概率：除了证明我们语言中的两个函数在我们的语言中给定的两个函数之间的单一不平等，给定$ f $，$ g $和$ c $，我们还可以检查$ g \ g \ preceq preceq \ preceq \ preceq \ preceq \ preceq \ textit {wp} wp {wp} [c] [c] $。
We study a syntax for specifying quantitative "assertions" - functions mapping program states to numbers - for probabilistic program verification. We prove that our syntax is expressive in the following sense: Given any probabilistic program $C$, if a function $f$ is expressible in our syntax, then the function mapping each initial state $σ$ to the expected value of $f$ evaluated in the final states reached after termination of $C$ on $σ$ (also called the weakest preexpectation $\textit{wp} [C](f)$) is also expressible in our syntax. As a consequence, we obtain a relatively complete verification system for reasoning about expected values and probabilities in the sense of Cook: Apart from proving a single inequality between two functions given by syntactic expressions in our language, given $f$, $g$, and $C$, we can check whether $g \preceq \textit{wp} [C] (f)$.
