Long-run average behaviour of probabilistic vector addition systems

T. Brázdil, S. Kiefer, A. Kučera, P. Novotny, in:, IEEE, 2015, pp. 44–55.


Conference Paper | Published | English
Author
; ; ;
Department
Series Title
LICS
Abstract
We study the pattern frequency vector for runs in probabilistic Vector Addition Systems with States (pVASS). Intuitively, each configuration of a given pVASS is assigned one of finitely many patterns, and every run can thus be seen as an infinite sequence of these patterns. The pattern frequency vector assigns to each run the limit of pattern frequencies computed for longer and longer prefixes of the run. If the limit does not exist, then the vector is undefined. We show that for one-counter pVASS, the pattern frequency vector is defined and takes one of finitely many values for almost all runs. Further, these values and their associated probabilities can be approximated up to an arbitrarily small relative error in polynomial time. For stable two-counter pVASS, we show the same result, but we do not provide any upper complexity bound. As a byproduct of our study, we discover counterexamples falsifying some classical results about stochastic Petri nets published in the 80s.
Publishing Year
Date Published
2015-07-01
Page
44 - 55
Conference
LICS: Logic in Computer Science
Conference Location
Kyoto, Japan
Conference Date
2015-07-06 – 2015-07-10
IST-REx-ID

Cite this

Brázdil T, Kiefer S, Kučera A, Novotny P. Long-run average behaviour of probabilistic vector addition systems. In: IEEE; 2015:44-55. doi:10.1109/LICS.2015.15
Brázdil, T., Kiefer, S., Kučera, A., & Novotny, P. (2015). Long-run average behaviour of probabilistic vector addition systems (pp. 44–55). Presented at the LICS: Logic in Computer Science, Kyoto, Japan: IEEE. https://doi.org/10.1109/LICS.2015.15
Brázdil, Tomáš, Stefan Kiefer, Antonín Kučera, and Petr Novotny. “Long-Run Average Behaviour of Probabilistic Vector Addition Systems,” 44–55. IEEE, 2015. https://doi.org/10.1109/LICS.2015.15.
T. Brázdil, S. Kiefer, A. Kučera, and P. Novotny, “Long-run average behaviour of probabilistic vector addition systems,” presented at the LICS: Logic in Computer Science, Kyoto, Japan, 2015, pp. 44–55.
Brázdil T, Kiefer S, Kučera A, Novotny P. 2015. Long-run average behaviour of probabilistic vector addition systems. LICS: Logic in Computer Science, LICS, 44–55.
Brázdil, Tomáš, et al. Long-Run Average Behaviour of Probabilistic Vector Addition Systems. IEEE, 2015, pp. 44–55, doi:10.1109/LICS.2015.15.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar