.png){kind=icon}
返回
Structural Abstraction and Refinement for Probabilistic Programs
.png){kind=icon}
PRE
AI
DOI：10.1145/3763115.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
本文提出了一种结构抽象精化方法，这是一种用于验证概率程序阈值问题的新型框架。我们的方法通过抽象语句语义，将概率控制流自动机（PCFA）的结构表示为马尔可夫决策过程（MDP）。MDP的最大可达性自然地提供了一个适当的违反概率上界，称为结构上界。这引入了一种全新的结构化表征，揭示了PCFA与MDP之间的关系，与传统语义视角形成对比，在该视角下MDP反映的是语义。该方法的一个独特特点是将概率与计算语义的关注点进行清晰分离，其中抽象仅专注于概率计算，而精化仅处理语义方面，后者允许在不做修改的情况下采用非随机程序的验证技术。基于这一特点，我们提出了一种通用的反例引导抽象精化（CEGAR）框架，能够利用现有的非概率技术进行概率验证。我们使用轨迹抽象探索了其具体实现。该方法在一系列多样化的示例上与当前最先进的工具进行了比较评估，实验结果突显了其通用性以及快速处理更灵活结构的能力。
Keyword:
probabilistic programs
abstraction refinement
CEGAR
trace abstraction
期刊
P
IF:
2.8
论文数:
308
被引数:
4.7K
查看更多机构
.png){kind=icon}
