BRÁZDIL, Tomáš, Stefan KIEFER and Antonín KUČERA. Efficient Analysis of Probabilistic Programs with an Unbounded Counter. In Ganesh Gopalakrishnan, Shaz Qadeer. Computer Aided Verification, 23rd International Conference, CAV 2011. Berlin: Springer, 2011, p. 208-224. ISBN 978-3-642-22109-5. Available from: https://dx.doi.org/10.1007/978-3-642-22110-1. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{962615, author = {Brázdil, Tomáš and Kiefer, Stefan and Kučera, Antonín}, address = {Berlin}, booktitle = {Computer Aided Verification, 23rd International Conference, CAV 2011}, doi = {http://dx.doi.org/10.1007/978-3-642-22110-1}, editor = {Ganesh Gopalakrishnan, Shaz Qadeer}, keywords = {one-counter machines; probabilistic systems; model-checking}, language = {eng}, location = {Berlin}, isbn = {978-3-642-22109-5}, pages = {208-224}, publisher = {Springer}, title = {Efficient Analysis of Probabilistic Programs with an Unbounded Counter}, year = {2011} }
TY - JOUR ID - 962615 AU - Brázdil, Tomáš - Kiefer, Stefan - Kučera, Antonín PY - 2011 TI - Efficient Analysis of Probabilistic Programs with an Unbounded Counter PB - Springer CY - Berlin SN - 9783642221095 KW - one-counter machines KW - probabilistic systems KW - model-checking N2 - 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. ER -
BRÁZDIL, Tomáš, Stefan KIEFER and Antonín KUČERA. Efficient Analysis of Probabilistic Programs with an Unbounded Counter. In Ganesh Gopalakrishnan, Shaz Qadeer. \textit{Computer Aided Verification, 23rd International Conference, CAV 2011}. Berlin: Springer, 2011, p.~208-224. ISBN~978-3-642-22109-5. Available from: https://dx.doi.org/10.1007/978-3-642-22110-1.
|