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

D 2015

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

KUČERA, Antonín

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

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

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 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

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/15:00081424

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-22176-2

ISSN

DOI

https://doi.org/10.1007/978-3-319-22177-9_2

EID Scopus

2-s2.0-84943634101

Klíčová slova anglicky

Vector Addition Systems; Markov chains

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 4. 2016 15:34, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 VaV

Název: Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů

Investor: Grantová agentura ČR, Teorie her jako prostředek pro formální analýzu a verifikaci počítačových systémů

Citovat

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. ISBN 978-3-319-22176-2. Dostupné z: https://doi.org/10.1007/978-3-319-22177-9_2.

@inproceedings{1323103,
   author = {Kučera, Antonín},
   address = {Heidelberg},
   booktitle = {Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings.},
   doi = {https://doi.org/10.1007/978-3-319-22177-9_2},
   editor = {Adrian Kosowski, Igor Walukiewicz},
   keywords = {Vector Addition Systems; Markov chains},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Heidelberg},
   isbn = {978-3-319-22176-2},
   pages = {12-24},
   publisher = {Springer},
   title = {On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS},
   year = {2015}
}

TY  - CONF
ID  - 1323103
AU  - Kučera, Antonín
PY  - 2015
TI  - On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS
PB  - Springer
CY  - Heidelberg
SN  - 9783319221762
KW  - Vector Addition Systems
KW  - Markov chains
N2  - 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.
ER  -

KUČERA, Antonín. On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS. In Adrian Kosowski, Igor Walukiewicz. \textit{Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gda\'nsk, Poland, August 17-19, 2015, Proceedings.}. Heidelberg: Springer, 2015, s.~12-24. ISBN~978-3-319-22176-2. Dostupné z: https://doi.org/10.1007/978-3-319-22177-9\_{}2.

Přehled o publikaci