Affiliations: [a] Inria Rennes-Bretagne Atlantique, Campus de Beaulieu, F35042 Rennes, France. eric.badouel@inria.fr | [b] Department of Computing Science, Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany. uli.schlachter@informatik.uni-oldenburg.de
Correspondence:
[*]
Address for correspondence: Inria Rennes-Bretagne Atlantique, Campus de Beaulieu, F35042 Rennes, France
Note: [†] Supported by DFG (German Research Foundation) through grant Be 1267/15-1 ARS (Algorithms for Reengineering and Synthesis).
Abstract: Process discovery aims at constructing a model from a set of observations given by execution traces (a log). Petri nets are a preferred target model in that they produce a compact description of the system by exhibiting its concurrency. This article presents a process discovery algorithm using Petri net synthesis, based on the notion of region introduced by A. Ehrenfeucht and G. Rozenberg and using techniques from linear algebra. The algorithm proceeds in three successive phases which make it possible to find a compromise between the ability to infer behaviours of the system from the set of observations while ensuring a parsimonious model, in terms of fitness, precision and simplicity. All used algorithms are incremental which means that one can modify the produced model when new observations are reported without reconstructing the model from scratch.
Keywords: Region theory, Petri net synthesis, process discovery
