Stochastic Process Discovery: Can It Be Done Optimally?

Process discovery is the problem of automatically constructing a process model from an event log of an information system that supports the execution of a business process in an organisation. In this paper, we study how to construct models that, in addition to the control flow of the process, capture the importance, in terms of probabilities, of various execution scenarios of the process. Such probabilistic aspects of the process are instrumental in understanding the process and to predict aspects of its future. We formally define the problem of stochastic process discovery, which aims to describe the processes captured in the event log. We study several implications of this definition, and introduce two discovery techniques that return optimal solutions in the presence and absence of a model of the control flow of the process. The proposed discovery techniques have been implemented and are publicly available. Finally, we evaluate the feasibility and applicability of the new techniques and show that their models outperform models constructed using existing stochastic discovery techniques.