Analysis of probabilistic basic parallel processes. (English) Zbl 1405.68208

Bonnet, Rémi; Kiefer, Stefan; Lin, Anthony Widjaja

Muscholl, Anca (ed.), Foundations of software science and computation structures. 17th international conference, FOSSACS 2014, held as part of the European joint conferences on theory and practice of software, ETAPS 2014, Grenoble, France, April 5–13, 2014. Proceedings. Berlin: Springer (ISBN 978-3-642-54829-1/pbk). Lecture Notes in Computer Science 8412, 43-57 (2014).

Summary: 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.
For the entire collection see [Zbl 1284.68025].

MSC:

68Q85	Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
60J20	Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
68Q25	Analysis of algorithms and problem complexity
68Q87	Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)