On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KUČERA Antonín

Rok publikování 2015
Druh Článek ve sborníku
Konference Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings.
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
Doi http://dx.doi.org/10.1007/978-3-319-22177-9_2
Obor Informatika
Klíčová slova Vector Addition Systems; Markov chains
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.