Stochastic Process Trees: A Formal Framework for Stochastic Process Discovery

The inductive miner, a popular process discovery algorithm, issues a workflow net (WN) model by translation of an intermediate process tree (PT) representation, obtained from the considered event log. In this paper, we introduce the stochastic extension of the PT formalism, namely, stochastic process trees (SPT), by enriching basic PT operators with probabilistic parameters aimed at capturing the probabilistic characteristics of the traces stored in the considered log. In the context of stochastic process discovery, the introduction of SPTs allows for reducing the complexity of discovering the optimal instance of a stochastic model, as the parameter space induced by an SPT is inherently smaller than that of the corresponding (stochastic) WN. Based on the SPT formal semantics, we provide a stochastic simulation algorithm which allows for approximating the stochastic language issued by a SPT. By plugging it within an optimization framework, we demonstrate the efficacy of SPT-based stochastic process discovery through a number of experiments on real-life logs.