| Identifikační kód | RIV/00216224:14330/15:00081425 |
|---|
| Název v anglickém jazyce | Long-Run Average Behaviour of Probabilistic Vector Addition Systems |
|---|
| Druh | D - Článek ve sborníku |
|---|
| Jazyk | eng - angličtina |
|---|
| Obor - skupina | I - Informatika |
|---|
| Obor | IN - Informatika |
|---|
| Rok uplatnění | 2015 |
|---|
| Kód důvěrnosti údajů | S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
|---|
| Počet výskytů výsledku | 2 |
|---|
| Počet tvůrců celkem | 4 |
|---|
| Počet domácích tvůrců | 3 |
|---|
| Výčet všech uvedených jednotlivých tvůrců | Tomáš Brázdil (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 1762834)
Stefan Kiefer (státní příslušnost: DE - Spolková republika Německo)
Antonín Kučera (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 9872655)
Petr Novotný (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 2158507) |
|---|
| Popis výsledku v anglickém jazyce | 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 emph{patterns}, and every run can thus be seen as an infinitesequence 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. |
|---|
| Klíčová slova oddělená středníkem | Probabilistic Vector Addition Systems; Markov Chains |
|---|
| Stránka www, na které se nachází výsledek | - |
|---|
| DOI výsledku | 10.1109/LICS.2015.15 |
|---|