Author(s):

Brázdil, Tomáš; Kiefer, Stefan; Kučera, Antonín; Novotný, Petr

Title: 
Longrun average behaviour of probabilistic vector addition systems

Affiliation 
IST Austria 
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 onecounter 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 twocounter 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.

Keywords: 
Polynomialtime; Polynomial approximation; Complexity bounds; Stochastic systems; Petri nets; Frequency vector; Probabilistic vector; Relative errors; Stochastic Petri Nets

Conference Title:

LICS: Logic in Computer Science

Conference Dates:

July 610, 2015

Conference Location:

Kyoto, Japan

ISBN:

9781479988754

Publisher:

IEEE

Date Published:

20150701

Start Page: 
44

End Page:

55

URL: 

DOI: 
10.1109/LICS.2015.15

Open access: 
yes (repository) 