Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Efficient Analysis of Probabilistic Programs with an Unbounded Counter
复制标题
使用无界计数器对概率程序进行有效分析
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Kucera
中科院分区：
文献类型：
--
作者：
T. Brázdil;S. Kiefer;A. Kucera
我们表明，一个子类的无限状态的概率程序，可以建模的概率一计数器自动机（pOC）承认一个有效的定量分析。我们首先建立了一个强大的联系pOC和鞅理论，这导致了基本的观察定量性质的运行pOC。特别是，我们提供了一个“发散间隙定理”，它的界限是一个积极的非终止概率pOC远离零。使用这些观察，我们表明，预期的终止时间可以近似到一个任意小的相对误差在多项式时间，这同样适用于所有运行，满足一个给定的ω-正则性质编码的确定性拉宾自动机的概率。
We show that a subclass of infinite-state probabilistic programs that can be modeled by probabilistic one-counter automata (pOC) admits an efficient quantitative analysis. We start by establishing a powerful link between pOC and martingale theory, which leads to fundamental observations about quantitative properties of runs in pOC. In particular, we provide a “divergence gap theorem”, which bounds a positive non-termination probability in pOC away from zero. Using these observations, we show that the expected termination time can be approximated up to an arbitrarily small relative error in polynomial time, and the same holds for the probability of all runs that satisfy a given ω-regular property encoded by a deterministic Rabin automaton.
Rabinizer 2：LTL â GU 的小型确定性自动机
DOI：
10.1007/978-3-319-02444-8_32
发表时间：
2013
期刊：
影响因子：
--
作者：
Křetínský;Ruslán Ledesma
通讯作者：
Ruslán Ledesma
Rabinizer：LTL(F, G) 的小型确定性自动机
DOI：
10.1007/978-3-642-33386-6_7
发表时间：
2012
期刊：
影响因子：
--
作者：
Andreas Gaiser;Jan Křetínský;Javier Esparza
通讯作者：
Javier Esparza
准生死过程、树状 QBD、概率 1 计数器自动机和下推系统
影响因子：
2.2
作者：
Etessami K
通讯作者：
Etessami K