Discovering discrete event processes through event clustering

This article deals with automated modelling of discrete-event processes. A novel process discovery method that builds workflow nets (WFN) by processing a multiset of event sequences or traces L is proposed; the discovered net may include silent transitions. In this method, an event clustering technique determines a partition of the event alphabet used in L ; every cluster, called Atomic Execution Block (AEB), gathers the events that always appear together in the same traces. Then, using the causal and concurrent event relations derived from L , relations between AEBs are classed as direct or indirect. Direct relations lead to net substructures related to traces that do not need the occurrence of silent transitions, whilst indirect relations involve the occurrence of silent transitions. Afterwards, the class of indirect relations is refined leading to four types of relations: direct, skip-indirect, redo-indirect, and switch-indirect relations. Finally, the WFN is synthesised; a Petri net sub-structure is built for every AEB based on the event relations. The sub-structures are composed in accordance with the block relation type. The procedures obtained from the proposed method have polynomial-time complexity; they have been implemented and tested based on a rediscovery scheme where test event sequences are obtained from reference test-nets of diverse size and structure.