Efficient Analysis of Probabilistic Programs with an Unbounded Counter

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2011
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Computer Aided Verification, 23rd International Conference, CAV 2011
ISBN
978-3-642-22109-5
ISSN
—
e-ISSN
—
Number of pages
17
Pages from-to
208-224
Publisher name
Springer
Place of publication
Berlin
Event location
Snowbird, UT, USA
Event date
Jul 14, 2011
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)