Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Analysis of Probabilistic Basic Parallel Processes


Rémi Bonnet, Stefan Kiefer, and Anthony W. Lin. Analysis of probabilistic basic parallel processes. Technical report,, January 2014. Available at


Basic Parallel Processes (BPPs) are a well-known subclass of Petri Nets. They are the simplest common model of concurrent programs that allows unbounded spawning of processes. In the probabilistic version of BPPs, every process generates other processes according to a probability distribution. We study the decidability and complexity of fundamental qualitative problems over probabilistic BPPs – in particular reachability with probability 1 of different classes of target sets (e.g. upward-closed sets). Our results concern both the Markov-chain model, where processes are scheduled randomly, and the MDP model, where processes are picked by a scheduler.

Suggested BibTeX entry:

    author = {R{\'e}mi Bonnet and Stefan Kiefer and Anthony W. Lin},
    institution = {},
    month = {January},
    note = {Available at},
    title = {Analysis of Probabilistic Basic Parallel Processes},
    year = {2014}

See ...
Conference version