KUČERA, Antonín. On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS. In Adrian Kosowski, Igor Walukiewicz. Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings. Heidelberg: Springer, 2015. s. 12-24, 13 s. ISBN 978-3-319-22176-2. doi:10.1007/978-3-319-22177-9_2.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS
Autoři KUČERA, Antonín (203 Česká republika, garant, domácí).
Vydání Heidelberg, Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings. od s. 12-24, 13 s. 2015.
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í
Forma vydání tištěná verze "print"
Impakt faktor Impact factor: 0.402 v roce 2005
Kód RIV RIV/00216224:14330/15:00081424
Organizační jednotka Fakulta informatiky
ISBN 978-3-319-22176-2
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-22177-9_2
Klíčová slova anglicky Vector Addition Systems; Markov chains
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: RNDr. Pavel Šmerk, Ph.D., učo 3880. Změněno: 28. 4. 2016 15:34.
Anotace
We present recent results about the long-run average properties of probabilistic vector additions systems with states (pVASS). Interestingly, for probabilistic pVASS with two or more counters, long-run average properties may take several different values with positive probability even if the underlying state space is strongly connected. This contradics the previous results about stochastic Petri nets established in 80s. For pVASS with three or more counters, it may even happen that the long-run average properties are undefined (i.e., the corresponding limits do not exist) for almost all runs, and this phenomenon is stable under small perturbations in transition probabilities. On the other hand, one can effectively approximate eligible values of long-run average properties and the corresponding probabilities for some sublasses of pVASS. These results are based on new exponential tail bounds achieved by designing and analyzing appropriate martingales. The paper focuses on explaining the main underlying ideas.
Návaznosti
GA15-17564S, projekt VaVNázev: Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů
Investor: Grantová agentura ČR, Standardní projekty
VytisknoutZobrazeno: 24. 10. 2019 07:21