Enjoy the Silence, Part II: Probability-Based Queries on Stochastic Labelled Petri Nets

A stochastic process model combines control flow and stochasticity in a single representation. Answering queries on the behaviour and probabilities of such a model is essential not only for analysis and verification, but also towards stochastic process mining, in which the frequency of events and traces is explicitly taken into account. In this paper, we focus on probability-based queries on stochastic process models, dealing with questions like “what are the 10 most likely traces?" and "what are the traces with a probability higher than 1%?", and "what are the most likely traces that together cover 80% of the behaviour in the model?". We formalise these queries in the setting where the model is represented as a stochastic labelled Petri net with repeated labels and silent transitions. We provide a representation of the stochastic deterministic state space induced by the net suitable for answering probability-based queries, and introduce an algorithm to do so. Finally, we implement our approach and evaluate its applicability and feasibility on real-life event logs.