Long-run average behaviour of probabilistic vector addition systems

DOI10.1109/LICS.2015.15MaRDI QIDQ4635790zbMATH OpenOpenAlexFDO

Authors Tomáš Brázdil, Stefan Kiefer, Petr Novotný, Antonin Kučera

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.02655, https://dl.acm.org/citation.cfm?id=2876521

zbMATH Keywords

computational complexitystochastic processesPetri netsvectorsprobabilit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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 only 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.

Recommendations

• On the existence and computability of long-run average properties in probabilistic VASS
• Deciding fast termination for probabilistic VASS with nondeterminism
• Zero-reachability in probabilistic multi-counter automata
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Flat Petri nets (invited talk)

Cited in

(5)

• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• Qualitative analysis of VASS-induced MDPs
• On the existence and computability of long-run average properties in probabilistic VASS
• Long-Run Average Behavior of Vector Addition Systems with States
• Deciding fast termination for probabilistic VASS with nondeterminism

This page was built for publication: Long-run average behaviour of probabilistic vector addition systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635790)