Discovering Process Models With Long-Term Dependencies While Providing Guarantees and Handling Infrequent Behavior

In process discovery, the goal is to find, for a given event log, the model describing the underlying process. While process models can be represented in a variety of ways, Petri nets form a theoretically well-explored description language and are therefore often used in process mining. In this paper, we present an extension of the eST-Miner process discovery algorithm. This approach computes a set of Petri net places which are considered to be fitting with respect to a user-definable fraction of the behavior described by the given event log, by evaluating all possible candidate places using token-based replay. The set of replayable traces is determined for each place in isolation, i.e., they do not need to be consistent, which allows the algorithm to abstract from infrequent behavioral patterns. When combining these places into a Petri net by connecting them to the corresponding uniquely labeled transitions, the resulting net can replay exactly those traces that can be replayed by each of the inserted places. Thus, inserting places one-by-one without considering their combined effect may result in deadlocks and low fitness of the Petri net. In this paper, we explore adaptions of the eST-Miner, that aim to select a subset of places such that the resulting Petri net guarantees a definable minimal fitness while maintaining high precision with respect to the input event log. To this end, a new fitness metric is introduced and thoroughly investigated. Furthermore, various place selection strategies are proposed and their impact on the returned Petri net is evaluated by experiments using both real and artificial event logs.