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. A Petri net describes the underlying process well if it allows for all relevant behavior (fitness) and, at the same time, restricts other process executions not contained in the event log (precision). A process discovery algorithm aiming to balance these often conflicting requirements is the eST-Miner. To this end, the approach employs a user-definable parameter which indicates a lower bound for the fraction of behavior in the event log that each place in the Petri net must be able to replay. As the eST-Miner is restricted to uniquely labeled transitions, i.e., it does not return silent or duplicate transitions, there are inputs where precision is decreased for the purpose of guaranteeing minimal fitness. An example is the situation where part of the process is optional and can be skipped, which is usually modeled by using a silent transition. Being constraint to uniquely labeled transitions, the eST-Miner models such behavior using a place with a loop. On the one hand this correctly allows to skip the looping behavior (maintains fitness), on the other hand precision is decreased drastically by allowing the behavior to be repeated arbitrarily often. Thus, the models returned by the eST-Miner often contain imprecise substructures, most prominently, ”flower-like” places (places with one-loops). In this paper, we aim to replace such places by more meaningful and precise submodels that include silent transitions, while preserving desirable structures existing in the input uniquely labeled Petri net. We describe an approach to distill the behavior related to a specific, imprecise place from the event log such that the resulting log projection can be used to discover and insert a more precise Petri net. Furthermore, extensions of the approach to more complex imprecise structures are discussed.
Today’s organizations collect increasing amounts of data corresponding to processes they handle, so-called event data. Every event corresponds to the execution of an activity within the run of an instance of the process. From such event data one can extract an event log, which groups the events into cases, i.e., the sequences of activities sequentially recorded for one process instance. While additional data attributes may be stored for events, they are not considered in this work. nEvelop-O ∗Corresponding author. An area that provides methods for gaining insights and extract information and value from such data is the field of process mining, which connects data mining and process science.
The sub-field of process discovery applies discovery algorithms to an event log to find a process model that describes the relations of the occurrences of activities. Such relations include conditionality, concurrency or choice between activities in a process and are reflected in the behavior of the event log. A good process model can help to better understand and subsequently improve the process, e.g., by reducing ineficiencies or detecting quality issues. An ideal discovery algorithm returns a process model for an input event log that represents all process executions in the event log (fitness ) while not allowing for behavior not contained in the event log (precision), is easy to understand (simplicity) and, finally, is likely to also include future process executions similar to the examples given in the event log, i.e., is not overfitting the log (generalization). For real-life event logs, these goals are usually in conflict with each other and it is impossible to perfectly satisfy all of them simultaneously.
The discovery algorithm eST-Miner (eficient Statespace Traversal-Miner) [
In this work, we aim to remedy this issue by introducing a framework that combines the eST-Miner’s ability to discover complex control-flows with the added expressiveness of silent transitions. Based on a uniquely labeled Petri net discovered by the eST-Miner, the goal of the framework is to introduce silent transitions to improve precision while preserving fitness. The approach first identifies imprecise structures in the given Petri net and computes the corresponding parts of the event log. Based on each sublog, it discovers a new, non-uniquely labeled Petri net and replaces the imprecise structure with this model without impacting the behavior expressed by the surrounding parts of the model.
A technique for the computation of the sublog and for the replacement of the imprecise structure are both presented in this paper. Considering the identification of imprecise structures, in this work, we focus on easily detectable candidate imprecise structures such as loops.
The proposed framework is related to ideas presented in the field of incremental process
discovery techniques. In particular, the work in [
In this work we focus on Petri nets discovered by the eST-Miner. However, the ideas and
concepts can be extended to Petri nets produced by other approaches. In particular, approaches
rooted in region theory [
The framework described in this paper was inspired by a master thesis [
The remainder of this work is structured as follows. In Section 2, we present the mathematical notations and concepts used in this work. Section 3 introduces the eST-Miner. Section 4 presents the approach to obtain a more precise process model by replacing imprecise structures. Section 5 applies the approach presented on real-life logs. In Section 6, we conclude this paper and give an outlook for future work.
We use of the following definitions and notations: A set, e.g. {, , , } , contains every element once, while a multiset can contain an element more than once, e.g. [, , , , , ] = [ 3, 2, ] . Set union, intersection and diference are defined as usual. By ℙ( ) we refer to the power set of the set , and ( ) is the set of all multisets over the set . In contrast to sets and multisets, a sequence is ordered. It can contain an element more than once, e.g., ⟨, , , , , ⟩ . We denote the number of elements of a set, multiset or sequence as | | . A projection of a sequence ∈ ∗ on a subset of activities ⊆ is denoted by ↾ . For example, ⟨, , , , ⟩↾ {,} = ⟨, , ⟩ . Further, we uplift all functions that are applicable to single elements of a sequence to be applicable to the full sequence, i.e., for a function ∶ → and a sequence ⟨ 1, 2, … , ⟩ we write (⟨ 1, 2, … , ⟩) = ⟨ ( 1), ( 2), … , ( )⟩. By we denote the universe of all possible activities (e.g., actions or operations). A trace is a finite sequence where each element is an activity from the universe of activities . The universe of such traces is denoted by . A log ∈ ( ) is a multiset of traces. We aim to represent the behavior described by an event log using a Petri net with transitions labeled according to the activities in the event log. A sequence of transitions fired describes a trace corresponding to the sequence of the transition labels. A so-called silent transition is labeled with the silent activity label and adds no activity to a trace. Definition 2.1 (Labeled Petri Net) We define a labeled Petri net as a quintuple = (, , , , ) where is a finite set of places, is a finite set of transitions such that ∩ = ∅ , ⊆ ( ×)∪( ×) is a set of directed arcs, ⊆ with ∉ is a set of non-silent activity labels, and ∶ → ∪ { } is a labeling function assigning to each transition a (possibly silent) activity label.
We define the preset and postset of places and transitions as usual, i.e., given a Petri net = (, , , , ) and a place or transition ∈ ∪ , the preset of is • = { ∈ ∪ ∣ ( , ) ∈ } and the postset of is • = { ∈ ∪ ∣ (, ) ∈ } . The current state of a labeled Petri net is described by its marking. A marking is a mapping function ∶ → ℕ 0 for a set of places and describes the number of tokens that each place holds. An accepting Petri net is a labeled Petri net having an initial marking and a final marking, which we use to define its behavior. Definition 2.2 (Accepting Petri Net) An accepting Petri net is defined as a triplet = (, i, f), where = (, , , , ) is a labeled Petri net and i ∶ → ℕ 0 an initial marking and f ∶ → ℕ 0 a final marking.
The behavior of an accepting Petri net is based on the firing rule for transitions. A transition is enabled, if all ingoing places in • hold at least one token in the current marking , i.e., if ∀∈• ∶ () ≥ 1 holds. An enabled transition can fire , consuming a token from each place in it’s preset and producing a token in each place in its postset. Thus, firing a transition changes the current marking to marking ′, denoted as [⟩ ′, where for ′ it holds that ′() = () − 1, if ∈ (•\•) or () + 1, if ∈ (•\•) or () otherwise. The behavior of an accepting Petri net is given by the set of its valid firing sequences, which are sequences of transitions that can be fired conclusively to lead from the initial marking to the final marking. Definition 2.3 (Valid Firing Sequences) Let = (, i, f) with = (, , , , ) be an accepting Petri net and let = ⟨ 1, 2, … , ⟩ with ∈ ∗ be a sequence of transitions. We call a firing sequence in from marking 0 if we have 0[ 1⟩ 1[ 2⟩ 2 … −1 [ ⟩ . This is denoted as 0 [⟩ . We call a valid firing sequence in if 0 = i and = f.
The non-silent transition labels of a valid firing sequence describe a trace that can be replayed using this firing sequence.
Definition 2.4 (Replayable Traces) Consider an accepting Petri net = (, i, f) with = (, , , , ) and a trace ∈ ∗. We say that is replayable on if and only if there exists a valid firing sequence = ⟨ 1, 2, … , ⟩ such that the projection of on its non-silent transition labels equals , i.e., = ⟨( 1), ( 2), … , ( )⟩↾ = .
The approach presented in this paper aims to improve a given accepting Petri net based on an event log , such that fitness is preserved while precision is ideally increased. Various metrics have been introduced for measuring or approximating fitness and precision with diferent advantages and disadvantages. In this work, we abstract from concrete metrics as we are interested only in the relation between these quality aspects when comparing two accepting Petri nets and ′. To this end, we compare the traces replayable by both nets. Definition 2.5 (Comparing Fitness and Precision) Consider an event log and two accepting Petri nets and ′. ′ is at least as fitting as , if every trace ∈ replayable on is also replayable on ′. ′ is at least as precise as , if every trace ∈ replayable on ′ is also replayable on . ′ is more precise than , if additionally a trace ′ ∈ \ exists that is replayable on but not replayable on ′.
Several variants and extensions of the eST-Miner have been proposed in the past years [
As input, the algorithm takes a log and returns an accepting Petri net as output. Inspired
by language-based regions, the basic strategy of the approach is to begin with a Petri net whose
transition labels correspond exactly to the activities used in the given log. From the finite set
of unmarked, intermediate candidate places, the subset of all fitting places is computed and
inserted by connecting them to their uniquely labeled ingoing and outgoing transitions. Such
places are uniquely identifiable by their sets of ingoing and outgoing transitions, thus there are
|ℙ() × ℙ()| candidate places. The eST-Miner is able to filter infrequent behavior by deeming a
place to be fitting even if it does not allow for replaying the complete event log. However, in this
paper, we require it to accept places as fitting only if all traces in the event log are replayable
(feasible places). Places are evaluated using token-based replay. To avoid replaying the log on
all candidate places (exponential in the number of activities), it organizes the potential places as
a set of trees. When traversing these trees, their special structure allows to cut of subtrees, and
thus candidates, based on the replay result of their parent [
To facilitate further computations and human readability, implicit places are identified and
removed [
We emphasize the following details since they become relevant in the context of this work. Note that the eST-Miner adds designated start and designated end activities to the input event log, which are reflected by correspondingly labeled start and end transitions. A source place, marked in the initial marking, is added as the preset of the start transition, and a sink place, marked in the final marking, forms the postset of the final transition. In the context of this work, we relabel the start and end transitions of each model discovered using the eST-Miner as silent transitions. Furthermore, the eST-Miner variant used here is restricted to only discover accepting Petri nets that have perfect fitness for the input log, i.e., all log traces are replayable. Thus, with the start and end transitions relabeled to be silent, the input log without added artificial start and end activities has perfect fitness on the discovered net.
As an example, consider the accepting Petri net shown in Figure 1a discovered on the log = [⟨, ⟩, ⟨, ⟩, ⟨, , , ⟩, ⟨, , , ⟩] using the eST-Miner. illustrates the discovery of complex control-flow structures and is perfectly fitting and precise with respect to as it does not replay any trace not in . Nevertheless, undesired places which are decreasing readability are inserted due to the limitation of the eST-Miner to not use silent transitions for the representation of skippable behavior such as the activities and being skippable.
Consider = [⟨, ⟩, ⟨, ⟩, ⟨, , ⟩, ⟨, , ⟩] as a similar log, for which the eST-Miner discovers
the accepting Petri net shown in Figure 1b. allows for arbitrarily many occurrences of
between and or between and respectively. Such a looping structure, which allows for a
transition to be fired arbitrarily often (or not at all) and in arbitrary order, is commonly referred
to as a flower construct [
The eST-Miner frequently returns Petri nets that over-approximate optional behavior using rather imprecise looping structures. Specifically, we refer to -loops as candidate imprecise structures.
Definition 4.1 ( -Loops) Let = (, , , , ) be a Petri net that contains a sequence of unique nodes ⟨ 1, 2, … , ⟩ ∈ ( ∪ ) ∗ of length , which are forming a directed cycle from and to a place ∈ , i.e., ∈ (• 1 ∪ •) ∧ ∀∈[1,−1] ∶ ∈ • +1 and ∀,∈[1,] ∶ = ⇒ = holds. We refer to such a sequence as a -loop of the place , where denotes the number of transitions in the node sequence.
Given an accepting Petri net, the so-called Projection Discovery with the eST-Miner presented in the following replaces a place that has one-looping transitions with a more precise accepting Petri net while preserving fitness, i.e., all traces from the input log remain replayable. Replayable behavior outside of the event log is never increased, with the goal being to reduce it.
0 eST-Miner
L e l b a y a l p e r 0
Optional: Pre-Processing
Case 2 only: -Loop Merge merge all places in the -loop into a single place ∈ with ↺ ≠ ∅
Par oning of One-Looping Transi ons split a place ∈ with ↺ ≠ ∅ into several places ↺ that partition ↺
(compare Sec on 4.4) SN = (wNi,th , ) 12.. Tp ↺i∈s ≠seax∅fie,s,ts, where: N = (P, T, F, A, l) 3. ∀t1,t2∈T↺: l t1 ≠ ∧ where: l t1 = l t2 ⇒ t1 = t2
Place Projection
Projection Discovery with the eST-Miner
Post-Processing Reduce Silent Transitions , compute the place projection log L↾ (compare Sec on 4.1)
L↾ Empty Trace Stable eST-Miner Discovery L↾ (compare Sec on 3)
L↾ ,
, , Recursion?
‘ Place Replacement replace and ↺ with (compare Sec on 4.2)
The overall algorithmic framework is outlined in Figure 2. Initially, a log and an accepting Petri net with perfect fitness on this log are given. The projection discovery starts with the procedure detailed in Section 4.1, for each safe place with uniquely labeled and non-silent one-loops we compute a place projection log representing the behavior of the place with respect to the input log and one-looping transitions. Notably, this projected log will contain the empty trace in case the looping transitions reflect optional behavior. Based on the place projection log, we use the eST-Miner to discover a new subnet and insert it into replacing and its one-looping transitions. The replacement technique is detailed in Section 4.2. Note, that the projection discovery can be applied recursively to the discovered subnets until no improvement can be found. Further, we enable the eST-Miner to discover a more precise model by removing all occurrences of the empty trace from the projected event log before starting the discovery. If such traces indeed exist, then we add a silent transition to the discovered , making the complete net skippable.
Our input of the projection discovery can be refined by pre-processing such that -loops are considered or such that better results are obtained by using a place partitioning technique. For a -loop contained in , we merge all places in the -loop into a single place as detailed in Section 4.3. This reduces the -loops to one-loops. Place partitioning splits into a set of places to be handled individually and to find more meaningful logs, as detailed in Section 4.3.
Note that in our implementation and presented examples, we reduce silent transitions in the ifnal accepting Petri net while preserving its behavior [ 16] to improve readability.
The approach guarantees to preserve fitness and precision, as detailed in Section 4.4.
As input, the place projection expects an accepting Petri net = (, i, f) with = (, , , , ) , a firing sequence on the accepting Petri net and a safe place ∈ that is unmarked in i and f and that has a non-empty set of uniquely labeled, non-silent one-looping transitions ⟲ . As a result, the place projection of on returns a place projection log satisfying the following properties: Property 1 holds a trace for each non-extendable subsequence of for which holds a token during firing of on and Property 2 for all ∈ ⟲ fired while a token is contained in , their label (if non-silent) is appended to the same trace of , and for no ′ ∉ ⟲ their label is added.
In the following, we give further explanation for a place projection log to satisfy the two criteria. As we replace the place and its one-looping transitions ⟲ with an accepting Petri net discovered on the log , we do not want to model behavior that is modeled by other transitions (Property 2). Further, for our replacement technique, we expect the replacing accepting Petri net to be able to reach its final marking from its initial marking when sequentially firing the activities corresponding to the one-looping transitions contained in a subsequence of , for which is non-empty when firing on (Property 1, Property 2). As our used discovery algorithm returns a perfectly fitting Petri net on its input log, we conclude Property 1 and Property 2 to be strongly influential towards the behavior of an accepting Petri net discovered on a place projection log. If both properties hold for a place projection function, we expect an accepting Petri net discovered on the place projection log to cover the same behavior from as the place to be replaced.
To detect increments and decrements in the number of tokens of a place between two subsequent markings, we introduce the token sequence of a place and a valid firing sequence as a new concept.
Definition 4.2 (Token Sequence of a Place and a Valid Firing Sequence) Let = (, i, f) with = (, , , , ) be an accepting Petri net, ∈ be a place and = ⟨ 1, 2, … , ⟩ be a valid firing sequence in . We define the sequence of token states of and as the sequence (, ) = ⟨ i(), 1(), 2(), … , −1 (), f()⟩ , where i [ 1⟩ 1 [ 2⟩ 2 [ 3⟩ … [ −1 ⟩ −1 [ ⟩ f holds.
We use the concept of the token sequences to construct a projection function satisfying Property 1 and Property 2 described above. Definition 4.3 gives the projection of a valid firing sequence on a safe place as the multiset of all non-extendable subsequences for which is non-empty during firing of .
Definition 4.3 (Projection of a Valid Firing Sequence on a Safe Place) Let = (, i, f) be an accepting Petri net with = (, , , , ) , ∈ be a safe place in the Petri net where i() = 0 ∧ f() = 0 holds, ⟲ = • ∩ • ≠ ∅ the set of non-silent and uniquely labeled onelooping transitions of the place , i.e., ∀ 1, 2∈ ⟲ ∶ ( 1)≠∧( 1)=( 2)⇒ 1= 2, a trace, = ⟨ 1, 2, … , ⟩ a valid firing sequence of replaying and (, ) = ⟨ 0, 1, 2, … , ⟩ a token sequence with ∈ ℕ . The projection ↾ of the firing sequence on the safe place is the multiset of sequences ↾ = [(⟨ +1 , +2 , … , ⟩↾ ⟲ ) ∣ , ∈ [2, − 1] ∧ < ∧ − = 0 ∧ +1 = 0 ∧ ∀ ∈ [, ] ∶ > 0].
In the context of this work, we expect the firing sequence of a trace to be non-ambiguous. This holds trivially for the eST-Miner as it discovers uniquely labeled accepting Petri nets only.
We uplift the concept of the place projection to logs to obtain a place projection log ↾ by considering the union of all projections of firing sequences on corresponding to each trace in the log, i.e., ↾ = ⋃ ∈ ↾ . In Table 1, examples of token sequences and place projections are shown for 4 of the accepting Petri net shown in Figure 3b.
The next step in our framework is to discover an accepting Petri net = ( , , , , ) with = ( , , , , ) on the projection log ↾ . Note that if the log contains the empty trace, i.e., ⟨⟩ ∈ ↾ , that an empty trace stable eST-Miner used in this work then discovers an accepting Petri net on ↾ \{⟨⟩} and inserts a skipping silent transition , i.e., ( ) = ∧ • = { ∈ ∣ , ( ) > 0} ∧ • = { ∈ ∣ , ( ) > 0}.
Considering our running example, we obtain the place projection log 2 = 1↾ 3 = [⟨⟩2, ⟨⟩ 2, ⟨, ⟩ 2, ⟨, ⟩ 2]. We discover the accepting Petri net 2 shown in Figure 4a with the empty trace stable eST-Miner on 2. Here, we apply the projection discovery recursively with the place 2 in 2 and 2 as input. We obtain the place projection log 3 = 2↾ 2′ = [⟨⟩2, ⟨ ⟩ 2, ⟨⟩ 2] and discover the accepting Petri net 3 shown in Figure 4b. Here, no further recursion is applied. At this point, place replacement is applicable. Intuition on the replacement of a place with an accepting Petri net and corresponding desired properties are given in the next section.
In this section, we describe the replacement of a place with an accepting Petri net = ( , , , , ) discovered on the place projection log ↾ . First, the place and all its onelooping transitions ⟲ = • ∩ • are removed (Step 1). Further, we connect all other ingoing (respectively outgoing) transitions of as ingoing (respectively outgoing) to each place that holds a token in the initial marking , (Step 2) (respectively, final marking , ) (Step 3). Lastly, we convey all restrictions that a transition ∈ ⟲ has to all inserted transitions that share the label with the transition (Step 4).
Steps (1)-(3) aim to replace the place and its one-looping transitions ⟲ with the accepting Petri net such that, with respect to the replay of all traces in the log, a token is produced in all places marked by , whenever a token was produced in and to consume a token from all places marked by , whenever a token was consumed from . Step (4) aims to convey all restrictions on the former one-looping transitions that are not imposed by itself. We formalize these replacement steps in Definition 4.4.
Definition 4.4 (Replacing a Place with an Accepting Petri Net) Let = (, i, f) with = (, , , , ) be an accepting Petri net, ∈ a place with its one-looping transitions e t2' p2' t2' g t3' t4' ● p1' t1' p2' t5' p3' t6' ■ p4' ● p2 a t2 b t3 p2' t5' e t2' (a) Accepting Petri net 2,3, which is the result of (b) Accepting Petri net 1,2,3, which is the result of the accepting Petri net 3 in Figure 4b. replacing the place 2′ in
replacing the place 3 in
( ′, ′, ′, ′, ′), where the following holds: = ( , , , , ). This results in an accepting Petri net ⟲ = • ∩ • ≠ ∅ to be replaced with the accepting Petri net = ( , , , , ) with ′ = ( ′, i′, f′
) with ′ = p2' p5 f t2' g ′ = ( ∪ )\(• × {} ∪ {} × •) ∪
{( , ) ∈ (•\ ⟲ ) × ∣ , ( ) > 0} ∪ {( , ) ∈ × (•\ ⟲ ) ∣ , ( ) > 0} ∪ ⋃ ({( , ) ∈ (• \{}) × ∣ ( ) = ( )} ∪ ∈ ⟲ {( , ) ∈ × ( •\{}) ∣ ( ) = ( )}).
In the following we continue our example from Figure 3a and Figure 4. In Figure 5a, we show the accepting Petri net be replayed on 2,3 while precision is improved compared to 3. The accepting Petri net 2,3 resulting from replacing 2′ in 2 with 3. Here, 2 can still 1,2,3 shown in Figure 5b results from replacing 3 in 1 with 2,3. All traces occurring in 1 are replayable on 1,2,3 and no other. Thus, fitness is preserved and precision is improved compared to 1 . quality of the results.
In the following section we introduce pre-processing steps that can be applied optionally in our framework to also consider -loops as candidate imprecise structures and to improve the
In this section, we are going to discuss how to make place projection feasible for -loops and an approach on how to handle the case where we discover an accepting Petri net that does not improve precision when being replaced. First, we have a look on the place projection on -loops.
Place Projection on k-Loops So far, we limited our method to project a log on a single place with one-looping transitions. Nevertheless, the eST-Miner and other discovery algorithms p3' f t3' p4 p2' e t2' p2' g t ' 3 t2' p3' frequently return Petri nets that include -loops. Therefore, we extend our approach to also allow for the projection of a log on multiple places.
Consider a -loop in an accepting Petri net = (, i, f) with = (, , , , ) that contains a set of places ⟲ ⊆ . Combining all places into a single place , where • = ⋃ ′∈ ⟲ • ′ and • = ⋃ ′∈ ⟲ ′• holds, does not restrict the behavior of the accepting Petri net . Further, the framework is applicable as the combined place has a non-empty set of one-looping transitions. An example of this approach is given for discovered on from our example shown in Figure 3b. Here, we merge 4 and 7 into a single place resulting in an accepting Petri net equivalent to 1 shown in Figure 3a. The result of the projection discovery on 1 with is shown in Figure 6.
In the following, we present that splitting a place into several places and partitioning the one-looping transitions can be applied to improve precision when the discovered accepting Petri net does not improve precision.
Partitioning of One-Looping Transitions Let = (, i, f) with = (, , , , ) be
an accepting Petri net and let ∈ be a place with one-looping transitions ⟲ = • ∩ • ≠ ∅ .
Splitting the place into a set of parallel places ⟲ , where ⋃ ′∈ ⟲ • ′ ∩ ′• = ⟲ ∧ ∀ ′∈ ⟲ ∶ • ′ =
• ∧ ′• = • holds, does not decrease fitness. The place projection log for each place ′ ∈ ⟲ is
diferent from the place projection log for the place . Thus, we conclude diferent accepting
Petri nets to be discovered which we can insert. Therefore, we can apply this technique when
our framework does not further improve precision. Heuristic strategies for partitioning the
transitions are explored in [
In the following section we formalize the guarantees on fitness and precision preservation and sketch the corresponding proofs.
In this section, we give a more detailed view on the guarantees provided by our framework. The framework guarantees to preserve fitness and precision as formalized in Theorem 4.1 and Theorem 4.2.
Theorem 4.1 (Preservation of Fitness) Let be an event log and let = (, i, f) with = (, , , , ) be an accepting Petri net on which each trace ∈ has a unique valid firing sequence . Further, let ∈ be a safe place that has a set of uniquely labeled non-silent onelooping transitions ⟲ = • ∩• ≠ ∅ with ∀ 1, 2∈ ⟲ ∶ ( 1) ≠ ∧( 1) = ( 2) ⇒ 1 = 2 that does not a hold a token in the initial or final marking, i.e., i() = f() = 0 . Let ′ = ( ′, ′, ′) with ′ = ( ′, ′, ′, ′, ′) be the accepting Petri net obtained by applying the projection discovery. For such an accepting Petri net ′, it holds that all traces ∈ have a valid firing sequence ′ and therefore fitness to be preserved.
Proof. For any ∈ that has a valid firing sequence = ⟨ 1, 2, … , ⟩ on , we conclude a valid firing sequence ′ = ⟨ 1′, 2′, … , ′ ⟩ to exist on ′ where , ∈ ℕ and which replays on ′. Recall, that for the place projection to be unambiguous and for our replacement technique to be applicable, we expect each trace to be replayed by the same firing sequence throughout the whole framework. We consider the token sequence (, ) = ⟨ 0, 1, … , ⟩. If every token state is equal to zero, we conclude the firing sequence ′ to be equal to as the replacement technique does not influence the token movement and the transitions fired.
Next, we consider a token sequence where a value is non-zero. We are interested in the first non-extendable subsequence ⟨ , +1 , … , ⟩ where ∀∈[,] ∶ = 1 with ∈ [2, ] and ∈ [1, −1] .
Consider the prefix of , with = ⟨ 1, 2, … ⟩ and = ⟨ +1 , +2 , … , −1 ⟩. Since does not consume a token from , we conclude it to be exceptionable on ′ and ′ to start with . Considering the sequence = ⟨ +1 , +2 , … , −1 ⟩, we distinguish for each transition whether its in the set of shared transitions \ ⟲ (1) or in the set ⟲ (2).
In Case (1), we know that such a transition 1 ∈ \ ⟲ is neither ingoing nor outgoing to as 1 reproduces a non-zero token state and as it is not a one-looping transition of . Therefore, all ingoing places of are in . Thus, we conclude such a transition to be fired as well in ′ when ifred in . We conclude the transition to be enabled in ′ considering Property (4) of Definition 4.4 if each preceding transition in has a transition with the same labeling being added to ′.
The same arguing holds in Case (2) for all ingoing places of a transition ′ ∈ ⟲ . Nevertheless, we cannot add ′ directly to ′ as it is replaced in ′ and as a transition with the same label has other ingoing places than . If we consider to only contain transitions in ⟲ , i.e., = ↾ ⟲ , we identify this firing sequence to be considered for the place projection according to Definition 4.3. Therefore, we conclude that for each ′ a transition with the same label exists and is enabled in ′. Further, according to Definition 4.4, we preserve exiting transitions of being correspondingly enabled in ′ as we connect outgoing non-looping transitions with the places containing a token in the final marking of the replacing subnet. Similarly, according to Definition 4.4, we preserve the transitions corresponding to the one-looping transitions to be enabled accordingly as we connect the places containing a token in the initial marking of the replacing subnet as outgoing places to all ingoing transitions of .
We can continue our argument on the alternating subsequences of all-zero and all-one token sequences for following. Considering those arguments, we conclude for each replaying on that a corresponding ′ on ′ also replaying exists. Thus, we conclude fitness being preserved. □ Theorem 4.2 (Preservation of Precision) Let be an event log and let = (, i, f) with = (, , , , ) be an accepting Petri net on which each trace ∈ has a unique valid ifring sequence . Further, let ∈ be a safe place that has a set of uniquely labeled non-silent onnote-alohooplidnga ttroaknesnitiinonths e ⟲ini=tia•l∩or• fin≠al∅marwkiinthg,∀i .1e,.2,∈ ⟲ ∶i( )( =1) ≠ f(∧)(= 10) =.L(et2 ) ⇒′ =1=( 2′,tha ′t, doe′s) with ′ = ( ′, ′, ′, ′, ′) be the accepting Petri net obtained by projection discovery. For such an accepting Petri net ′, it holds that any traces that is replayable in ′ is also replayable by ′. This implies, that the proposed method does not increase the behavior of the model, i.e., preserves precision.
Proof. We consider the set of places that only occur in ′, i.e., = ′\ . According to Definition 4.3, we can conclude that it is possible to merge all places into a single place resulting in an accepting Petri net , i.e., • = ⋃ ′∈ • ′ ∧ • = ⋃ ′∈ ′• holds. Such a modification does not reduce behavior. Considering Definition 4.3, Definition 4.4 and the qualities of the eST-Miner that we apply to the place projection logs, we can directly conclude such an accepting Petri net to be equal to , i.e., = holds. Thus, every trace replayable on ′ is replayable on and therefore precision preserved. □
In the following, we apply our framework to real-life event logs to evaluate its capacities.
In this section, we apply the framework presented in Figure 2 to one artificial event log and three real-life event logs. First, there is the ’Road Trafic Fine Management’ log [ 17] which contains the log of an information system managing road trafic fines. In order to find more meaningful Petri nets, we split the log into two logs RTFM+ and RTFM-, based on the presence of the appeal attribute of a trace. The second log used is the ’Sepsis’ log [18] describing the pathway of a patient with a sepsis through a hospital. We filtered this log for the nine most frequent activities. The third log is a subset of the BPI Challenge log of 2017 [19] which describes a loan application process of a Dutch financial institution that is filtered for all accepted application ofers. We provide an overview of the main properties of the logs in Table 2.
For each of the four logs, we give accepting Petri nets discovered by the eST-Miner and discovered by our framework each. Comparing both the input and the result of our framework, we want to show that precision improves while fitness is preserved. However, existing automated precision metrics fail to show the improvement of precision numerically as they are negatively impacted in our framework when silent transitions are added. Therefore, we show that the application of our framework is reducing the possible behavior. The resulting accepting Petri nets discovered by the eST-Miner and invidually online. (Click here: Link our framework on to GitLab instance) the evaluation logs.
The models nets are shown in Table 3. The diferent colors in the accepting Petri nets discovered by our framework each represent a projection place replacement.
Our framework is implemented in ProM as the so-called ProjectionMiner plugin. For the application of the eST-Miner within our framework, we limited the maximal search depth of the candidate tree to a depth of six as experience has shown that most interesting places are covered already even though we do not traverse the full candidate tree. This limits each place discovered to contain in sum at most six arcs ingoing and outgoing. In our evaluation, we applied the full framework except for the -loop merge. As there is currently no heuristic implemented for the partitioning of one-looping transitions, it is applied manually. Nevertheless, the framework is able to discover the models on the R T F M - , S e p s i s and B P I 1 7 event log without user guidance.
As a result, for all accepting Petri nets discovered by our framework that are shown in Table 3, we can conclude their one-looping transitions to be meaningful as they model activities that appear repeatedly in traces of the original log. Further, our evaluation shows that our framework extends the eST-Miner to find more meaningful constructs than flower models. In the investigated examples, precision is improved for all inputs while fitness is preserved. In conclusion, there are real-life event logs and artificial logs that our framework can be applied to and where our framework extends the eST-Miner to achieve higher precision by adequately modeling optional behavior without hampering its ability to discover complex control-flow structures or reducing fitness.
In this paper, we introduced a framework which uses place projection techniques to replace imprecise loop-structures in eST-Miner models, stemming from the algorithm’s inability to discover silent transitions, with more precise subnets suitably modeling optional behavior. In addition to the projection and replacement methods we have extended the approach to loops of arbitrary length and considered a partitioning technique for one-looping transitions. As proven, the framework guarantees to preserve fitness and precision. As expected, for our investigated example logs we identify precision to be improved. In particular, our application to real-life event logs has shown that our framework is capable of finding accepting Petri nets containing silent transitions with the eST-Miner that are more precise than those discovered using the standard eST-Miner.
We conclude our framework to be a promising step towards improving discovery algorithms
unable to return silent transitions, e.g. many region-based approaches, and towards the
enhancement of process models containing flower structures. Nevertheless, further research has
to be done. In [
Any of these ideas can be taken as starting point for further research. Nevertheless, the concept of place projection is promising as it is not limited to eST-Miner models only and as it thus extends our view on process discovery and process enhancement. Moreover, our introduced techniques extend the general toolset of incremental process discovery. Notably, it already significantly extends the capabilities of the eST-Miner to make it more applicable to real-life logs.
We thank the Alexander von Humboldt (AvH) Stiftung for supporting our research (grant no. 1191945). The authors gratefully acknowledge the financial support by the Federal Ministry of Education and Research (BMBF) for the joint project Bridging
AI (grant no. 16DHBKI023). models from event logs - A constructive approach, in: J. M. Colom, J. Desel (Eds.), PETRI NETS 2013, Proceedings, volume 7927 of LNCS, Springer, 2013, pp. 311–329. [16] T. Murata, Petri nets: Properties, analysis and applications, Proc. IEEE 77 (1989) 541–580. [17] M. de Leoni, F. Mannhardt, Road Trafic Fine Management Process (2015). [18] F. Mannhardt, Sepsis Cases - Event Log (2016). [19] B. van Dongen, BPI Challenge 2017 - Ofer log (2021).