Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F11%3A00054480" target="_blank" >RIV/00216224:14330/11:00054480 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1007/978-3-642-22110-1" target="_blank" >http://dx.doi.org/10.1007/978-3-642-22110-1</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-22110-1" target="_blank" >10.1007/978-3-642-22110-1</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Popis výsledku v původním jazyce
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. In particular, we show that the expected termination time can be approximated up to an arbitrarily small relative error with polynomially many arithmetic operations, and the same holds for the probability of all runs that satisfy a given omega-regular property.
Název v anglickém jazyce
Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Popis výsledku anglicky
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. In particular, we show that the expected termination time can be approximated up to an arbitrarily small relative error with polynomially many arithmetic operations, and the same holds for the probability of all runs that satisfy a given omega-regular property.
Klasifikace
Druh
D - Stať ve sborníku
CEP obor
IN - Informatika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2011
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Computer Aided Verification, 23rd International Conference, CAV 2011
ISBN
978-3-642-22109-5
ISSN
—
e-ISSN
—
Počet stran výsledku
17
Strana od-do
208-224
Název nakladatele
Springer
Místo vydání
Berlin
Místo konání akce
Snowbird, UT, USA
Datum konání akce
14. 7. 2011
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—