BRÁZDIL, Tomáš, Stefan KIEFER a 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. s. 208-224, 17 s. ISBN 978-3-642-22109-5. doi:10.1007/978-3-642-22110-1.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Efficient Analysis of Probabilistic Programs with an Unbounded Counter
Autoři BRÁZDIL, Tomáš (203 Česká republika, domácí), Stefan KIEFER (276 Německo) a Antonín KUČERA (203 Česká republika, garant, domácí).
Vydání Berlin, Computer Aided Verification, 23rd International Conference, CAV 2011, od s. 208-224, 17 s. 2011.
Nakladatel Springer
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Obor Computer sciences, information science, bioinformatics
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Kód RIV RIV/00216224:14330/11:00054480
Organizační jednotka Fakulta informatiky
ISBN 978-3-642-22109-5
Doi http://dx.doi.org/10.1007/978-3-642-22110-1
UT WoS 000347051200008
Klíčová slova anglicky one-counter machines; probabilistic systems; model-checking
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 17. 12. 2011 17:01.
Anotace
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.
Anotace česky
V článku je dokázáno, že kvantitativní analýzu nekonečně-stavových programů popsatelných automatem s jedním čítačem lze provádět algoritmicky a efektivně. Zejména je možné aproximovat střední čas ukončení těchto programů.
Návaznosti
P202/10/1469, interní kód MUNázev: Formální metody pro analýzu a verifikaci komplexních systémů
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 18. 10. 2019 03:46