The language-based theory of regions, stemming from the area of Petri net synthesis, forms a fundamental basis for Integer Linear Programming (ILP)-based process discovery. Based on example behavior in an event log, a process model is derived that aims to describe the observed behavior. Building on top of the existing ILP-formulation, we present a new ILP-based process discovery formulation that unifies two existing types of language-based regions and, additionally, we present a generalized ILP objective function that captures both region-types and helps us to find suitable process discovery results.
Process Mining [1] forms the connecting element between business process modeling and data analysis. Its main aim is to extract knowledge from business process execution data originating from a variety of data sources, e.g., enterprise information systems, social media, embedded systems etc. Within process mining, three main branches are distinguished being process discovery, conformance checking and process enhancement. Within process discovery the aim is to, given an event log, reconstruct a process model. Within conformance checking the aim is to assess, given a process model and an event log, the conformance of the event log to the process model. Within process enhancement the aim is to further improve and/or align existing process models by combining the two aforementioned disciplines, e.g., identification and removal of bottlenecks within business processes.
The area of Petri net synthesis [2] is concerned with deciding whether there exists a Petri net that exactly describes a given sequential behavioral system description. A subclass of synthesis techniques is the area of region theory which is both defined on transition systems, known as state-based region theory, and on languages, known as language-based region theory.
Language-based region theory forms a fundamental basis for ILP-based process discovery [3]. Within process discovery however, a process model is typically valued w.r.t. four essential process mining quality dimensions being replay-fitness, precision, generalization and simplicity [4]. Applying traditional Petri net synthesis techniques in a process discovery context will result in models that have perfect replay-fitness, maximal precision, low generalization and often low simplicity.
In this paper we propose a unified approach w.r.t. ILP-based process discovery, based on the newly introduced concept of hybrid variable-based regions. Hybrid variablebased regions unite two existing language-based region definitions and allow us to vary the number of variables used within the ILP problems being solved. Therefore, we assess the impact of using a different number of variables on the average computation time of solving ILPs during ILP-based process discovery. Additionally we present a new generalized ILP objective function that supports hybrid variable-based regions and show that the objective function yields correct process discovery results.
The outline of this paper is as follows. In Section 2 we present basic preliminaries. In Section 3 we present language-based regions. In Section 4 we show how to adopt language-based regions within process discovery using ILP. In Section 5 we present a brief evaluation of the performance of the approach. Section 6 covers related work. Section 7 concludes the paper. A sequence σ is a function relating positions to elements e ∈ S, i.e. σ : {1, 2, ..., k} → S. An empty sequence is denoted as . We write every non-empty sequence as e 1 , e 2 , ..., e k . The set of all possible sequences over a set S is denoted as S * . We define concatenation of sequences σ 1 and σ 2 as σ 1 • σ 2 , e.g., a, b • c, d = a, b, c, d . If we are given a set X of sequences over S, i.e., X ⊆ S * , we define X's prefix-closure as
Let S be a set on which we can pose some total order and let R ⊆ R be a range of values. Vectors are denoted as z ∈ R |S| , where z(e) ∈ R and e ∈ S. A vector z represents a column vector. For vector multiplication we assume vectors to agree on their indices. Thus, given a totally ordered set S = {e 1 , e 2 , ..., e n } and z 1 , z 2 ∈ R |S| we have z 1 z 2 = i∈{1,2,...,n} z 1 (e i ) z 2 (e i ). Parikh vectors represent the number of occurrences of a certain element within a sequence. A Parikh vector is a function p : S * → N |S| with p(σ) = (σ e1 , σ e2 , ..., σ en ) where σ ei = |{j | 1 ≤ j ≤ |σ|, σ(j) = e i }|. As an example consider S = {a, b, c, d}, σ 1 = a, b, d and σ 2 = a, c, d . We have p(σ 1 ) = (1, 1, 0, 1) and p(σ 2 ) = (1, 0, 1, 1). Note that σ 1 b = 1 whereas σ 2 b = 0. Given a Parikh vector p : S * → N |S| and a set Q ⊆ S, we define p Q : S * → N |Q| . Thus given S = {a, b, c, d} and σ 1 = a, b, d we have p {a,c,d} (σ 1 ) = (1, 0, 1).
The main goal of process discovery is to describe the observed behavior within an event log by means of a process model. Thus, event logs act as the input of process discovery whereas some process model acts as the output of process discovery. An abstract example of an event log is presented in Table 1. Often more data attributes are available in an event log, e.g., customer id, credit balance etc. In this paper we focus on the sequential ordering of activities w.r.t. cases, i.e. the control-flow perspective.
Definition 1 (Event log). Let A be a set of activities, an event log L is a bag of sequences over A, i.e., L : A * → N. 1A sequence of activities σ ∈ L is referred to as a trace. We assume that any given set of activities A is totally ordered (or we are able to trivially pose a total ordering on A).
We consider Petri nets to describe process models. A Petri net is a bipartite graph consisting of a set of vertices called places and a set of vertices called transitions. Arcs (directed edges) are connecting places and transitions and have an associated positive weight.
A Petri net is a 3-tuple N = (P, T, W ), where P is a set of places and T is a set of transitions with P ∩ T = ∅. W is the weighted flow relation of N , W : (P × T ) ∪ (T × P ) → N.
For a given node x ∈ P ∪ T , the pre-set of x in N is defined as •x = {y | W (y, x) > 0}. Correspondingly x• = {y | W (x, y) > 0} denotes the post-set of x in N . Graphically we represent places as circles and transitions as boxes. For every (x, y) ∈ (P × T ) ∪ (T × P ) with W (x, y) > 0 we draw an arc from x to y. If W (x, y) > 1 we denote the arc's weight W (x, y) on top of the arc from x to y. A Petri net is pure if it does not contain self-loops, i.e., if W (x, y) > 0 then W (y, x) = 0. An example (pure) Petri net is depicted in Figure 1.
Definition 3 (Marked Petri net). Let N = (P, T, W ) be a Petri net. A marking of N is a bag over N 's places, i.e. M : P → N. A marked Petri net is a pair (N, M 0 ), where M 0 represents N 's initial marking.
Let N = (P, T, W ) be a Petri net and let M be a marking of
Graphically we represent a marking by drawing exactly a place's marking-multiplicity number of dots inside the place (e.g. p 1 in Figure 1 with M 0 = [p 1 ]). If a transition t is enabled in (N, M ), t may fire, resulting in a new marking M . When t fires, denoted as (N, M )[t (N, M ), we have ∀ p∈P (M (p) = M (p) − W (p, t) + W (t, p)). For example in Figure 1 we have
Definition 4 (Firing sequences). Let N = (P, T, W ) be a Petri net and let (N, M 0 ) be a corresponding marked Petri net. Sequence σ = t 1 , t 2 , ..., t n ∈ T * is a firing sequence of (N, M 0 ), written as
Note that infinitely many firing sequences can exist given a Petri net. Some example firing sequences of the Petri net depicted in Figure 1
The set of all possible firing sequences in a Petri net N is called N s language, i.e., all sequences σ ∈ T * s.t. (N, M 0 )[σ (N, M i ). N 's language is denoted as L(N ) ⊆ T * and is prefixclosed.
Consider Figure 1 and event log L 1 = [ a, b, d, e, g 10 , a, c, d, e, g 9 , a, b, d, e, f, e, g 11 , a, c, d, e, f, e, g 8 ] over A 1 = {a, b, c, d, e, f, g}. Clearly we have L 1 ⊂ L(N 1 ), and thus replay-fitness of L 1 on N 1 is perfect. We will use N 1 , A 1 and L 1 throughout the paper as a running-example.
The concept of regions forms the basis of region theory within Petri net synthesis. Given an event log L over a set of activities A, language-based regions are used to represent
places in a resulting Petri net N = (P, A, W ). A language-based region maps every a ∈ A to an integer representing arc-weight. For such mapping over A to be a region we pose the restriction that the corresponding place p ∈ P should not block any σ ∈ L, i.e., σ ∈ L ⇒ σ ∈ L(N ). We identify two basic definitions of language-based regions which we classify as single variable-based regions and dual variable-based regions.
The main difference is the number of variables used to define a region.
Definition 5 (Single variable-based regions). Let L be an event log over a set of activities
Let R s (L) denote the set of all possible single variable-based regions of L. Equation 3.1 generates a set of linear inequalities, i.e. applying Equation 3.1 on L 1 yields: 1 which can be represented as a single variable-based region r = (m, ( v(a), v(b), ..., v(g))) = (0, (1, −1, −1, 0, 0, 0, 0)). Note that for each inequality generated by Equation 3.1, place p 2 has a value of at least 0 and hence is a member of R s (L).
Single variable-based regions only allow us to synthesize/discover pure Petri nets. As a consequence we can not find self-loops, i.e. we can not find a place p in a resulting net N = (P, A, W ) s.t. p ∈ •a∩a•, for any a ∈ A. A lot of workflow patterns [5] in fact exhibit places that include self-loops, e.g. milestone patterns, mutual-exclusion patterns, priority patterns etc. Hence, we define dual variable-based regions which explicitly allow us to distinguish between incoming and outgoing arcs.
Definition 6 (Dual variable-based regions). Let L be an event log over a set of activities A. Let m ∈ N and x, y ∈ N |A| . A triple r = (m, x, y) is a dual variable-based region iff:
Let R d (L) denote the set of all possible dual variable-based regions of L. Like Definition 5, Definition 6 generates a set of linear inequalities. Applying Definition 6 on L 1 yields:
Dual variable-based regions use two decision variables per a ∈ A, represented by x, y ∈ N |A| . The variables allow us to distinguish between incoming arcs and outgoing arcs when translating regions to Petri nets. Expressing a dual variable-based region r = (m, x, y) as a place p ∈ P in marked net (N, M 0 ) with N = (P, A, W ) is again straightforward. We have M 0 (p) = m, W (a, p) = x(a) and W (p, a) = y(a). Again consider place p 2 depicted in Figure 1 which can be represented as a dual variable-based region r = (m, ( x(a), x(b), ..., x(g)), ( y(a), y(b), ..., y(g))) = (0, (1, 0, 0, 0, 0, 0, 0), (0, 1, 1, 0, 0, 0, 0)). Verify that for each linear in-equality generated by Definition 6, place p 2 has a value of at least 0 and hence is a member of R d (L).
Using dual variable-based regions allows us to express non-pure places, i.e, self-loops, milestones etc. However, this type of regions uses roughly twice as many variables compared with single variable-based regions. To balance the number of variables used, though still enhance the possibility of finding non-pure Petri net structures, we introduce the new concept of hybrid regions, capturing both single and dual variable-based regions.
Definition 7 (Hybrid variable-based regions). Let L be an event log over a set of activities A. Let A s , A d ⊆ A be two sets of activities with
Equation 4.2 does not equal Equation 3.1, however, as p( ) = 0 and m ∈ N, the equations are equivalent in this context. Note that the set of hybrid variable-based regions, i.e. the set of variable assignments that adhere to Definition 7 depends on the hybrid partition of A into A s and A d . Therefore, we let A s act as a parameter for the set of feasible hybrid variable-based regions. Let R h As (L) denote the set of all possible hybrid variable-based regions of L where A s represent a hybrid partition of
. Region r = (0, 0, 0, 0) is deemed the trivial region.
All three language-based region definitions, i.e. single, dual and hybrid variablebased regions, provide means to accept and/or reject potential places in a to be constructed Petri net. In classical Petri net synthesis approaches, one keeps looking for feasible places until either L = L(N ), or if this is impossible, L(N ) \ L is minimized. Unfortunately, most models returned by classical Petri net synthesis techniques result in models that are unusable from a process discovery perspective. Hence, we need to relax the strict formal requirements posed on the relation between L and L(N ).
Note that if we choose β(σ) = 1 for all σ ∈ L, denoted β 1 , we instantiate the generalized objective function as the objective function proposed in [3]. We denote this objective function as z 1 , i.e. Equation 4.3.
To relate the behavior in a given event log to the objective function defined in Definition 9 we instantiate the scaling function β making use of the frequencies of the traces present in the event log, i.e. we let β(σ) = L(σ) leading to:
To assess the difference between z 1 and the newly proposed objective function z L , consider the Petri net depicted in Figure 2. Assume we are given some event log L = [ a, b, d 5 , a, c, d 3 ]. Let r 1 denote the hybrid variable-based region corresponding to place p 1 , let r 2 correspond to p 2 and let r 3 correspond to p 3 . In this case we have z 1 (r 1 ) = 1, z 1 (r 2 ) = 1 and z 1 (r 3 ) = 2. On the other hand we have z L (r 1 ) = z L (r 2 ) = z L (r 3 ) = 5 + 3 = 8. Thus, using z β L leads to more intuitive objective values compared to using z 1 as z L evaluates to the absolute number of discrete time-steps a token would remain in the corresponding place when replaying log L w.r.t. the place.
In [3] it is shown that the objective function used favors minimal regions. The proof cannot directly be adapted to hold for hybrid variable-based regions. Moreover it does not provide means to show that any arbitrary instantiation of z β favors minimal hybrid variable-based regions. Here we show that any instantiation of the generalized weighted prefix-closure-based hybrid region objective function with some scaling function β : L → R + favors minimal hybrid variable-based regions. We first show that the objective value of a non-minimal hybrid region equals the sum of the two minimal regions defining it after which we show that the given objective function maps each region to some positive real value, i.e. rng(z β ) ⊆ R + . Lemma 1 (Objective value composition of non-minimal regions). Let L be an event log over a set of activities A and let A s , A d ⊆ A be a hybrid partition. Let
As (L). Let z β : R h As (L) → R where z β is an instantiation of the generalized weighted objective function as defined in Definition 9, then z β (r 3 ) = z β (r 1 ) + z β (r 2 ).
Proof (By definition of z β ). Let us denote z β (r 3 ):
Lemma 1 shows that the value of z β for a non-minimal region equals the sum of the z β values of the two regions it is composed of. If we additionally show that z β can only evaluate to positive values, we show that z β favors minimal hybrid variable-based regions.
Lemma 2 (Range of z β is strictly positive). Let L be an event log over a set of activities A and let A s , A d ⊆ A be a hybrid partition. Let r = (m, v, x, y) be a non-trivial region, i.e., r ∈ R h As (L). If we let z β be any instantiation of the generalized weighted objective function as defined in Definition 9, then z β : R h As (L) → R + . Proof (By showing z β (r) > 0, ∀r ∈ R h As (L)). Let r = (m, v, x, y) be a non-trivial hybrid variable-based region, i.e. r ∈ R h As (L). Because r ∈ R h As (L) we have
Note that each Parikh value of an activity a ∈ A given a sequence σ, i.e. p(σ)(a), is greater or equal than the Parikh value of a, given σ's prefix, i.e.,:
Using Equation 4.7 we can substitute p A d (σ ) x with p A d (σ) x in Equation 4.6:
Combining rng(β) ⊆ R + , p( ) = 0 and m ∈ N with Equation 4.8 we find z β (r) ≥ 0:
If m > 0 then β( )(m+ p As ( ) v+ p A d ( ) ( x− y)) > 0. Combined with Equations 4.8 and 4.9 leads to z β (r) > 0.
Observe that if m = 0 then for r to be a non-trivial hybrid variable-based region, i.e. r ∈ R h As (L), either (I). ∃a ∈ A s s.t. v(a) > 0 or (II). ∃a ∈ A d s.t. x(a) > 0. (I). Let m = 0 and a ∈ A s s.t. v(a) > 0. We know ∃σ = σ • a ∈ L. Because r ∈ R h As (L) (using Equation 4.8) we have:
hence we deduce:
Combining this with Equations 4.8 and 4.9 yields z β (r) > 0.
If σ = we have (using Equation 4.8):
leads us to reformulate this to:
Combining this with Equations 4.8 and 4.9 yields z β (r) > 0.
(II) Let m = 0 and a ∈ A d s.t. x(a) > 0. We know ∃σ = σ • a ∈ L. Because r ∈ R h As (L) (using Equation 4.6) we have:
x + x(a) and thus:
Combining this with Equations 4.8 and 4.9 yields z β (r) > 0.
By combining Lemma 1 and Lemma 2 we can easily show that any instantiation of z β favors minimal regions.
As (L). For any z β : R h As (L) → R being an instantiation of the generalized weighted objective function as defined in Definition 9: z β (r 3 ) > z β (r 1 ) and z β (r 3 ) > z β (r 2 ).
Proof (By composition of Lemma 1 and Lemma 2). By Lemma 1 we know z β (r 3 ) = z β (r 1 ) + z β (r 2 ). By Lemma 2 we know that z β (r 1 ) > 0, z β (r 2 ) > 0 and z β (r 3 ) > 0. Thus we deduce z β (r 3 ) > z β (r 1 ) and z β (r 3 ) > z β (r 2 ). Consequently, any instantiation of the objective function as defined in Definition 9 favors minimal regions.
Both objective functions presented, i.e.z 1 and z L , are expressible in terms of the more general objective function z β as presented in Definition 9. As we have seen the two objective functions may favors different regions. Combining an objective function with the ILP-formulation presented in Definition 8 establishes means to find Petri net places. However, solving one ILP only yields one solution and hence we need means to find a set of places, which together form a Petri net that represents the input event log L.
The most apparent technique to find multiple places is the use of causal relations within an event log. Within the context of this paper we define a causal relation as follows.
Definition 10 (Causal relation). Let L be an event log over a set of activities A. A causal relation γ L is a function γ L : A × A → R where γ L (a, b) denotes the causality between activity a and b exhibited in L.
Several approaches exist to compute causalities hence we refer to [6] for an overview of the use of causalities within different process discovery approaches. As a consequence, γ L (a, b) can have different meanings w.r.t. the causality between a and b. Some approaches limit rng When adopting a causal-based ILP process discovery strategy, we try to find places which will be added in the resulting Petri net, each representing a causality found. A first step is to compute γ L values given some causal definition. Depending on the actual meaning of the γ L , whenever we find a causal relation from a to b (possibly because γ L (a, b) ≥ δ, where δ is some threshold value), we enrich the constraint body for the given causal constraint as follows: After the constraint body is enriched, we solve the ILP yielding a place having an optimal value for the specific objective function chosen. We repeat the procedure for every causal relation yielding a Petri net.
The hybrid variable-based ILP-formulation is implemented as a plug-in in the ProM-Framework (http://www.promtools.org) [7] 2 . The plug-in allows the user to specify parameters of ILP-based process discovery, e.g. several different objective functions, additional constraints and causality based mining.
To test the performance of hybrid variable-based ILP process discovery we have used the basic implementation within an experimentation framework 3 . The framework allows for generating random process models and from these models generate event logs. We have generated 40 models containing a minimum of 2 activities and a maximum of 12 activities. For each model we have generated 10 event logs, each containing 5000 traces. For each log we ran three different instantiations of the process discovery formulation, one purely single variable-based, one hybrid variant and one purely dual variable-based. The distribution of event classes in A over A s and A d is depicted in Table 2. For the hybrid variant the size of A s was kept constant and independent of the number of activities in A (as of |A| ≥ 3). We ran each instantiation 10 times per log using causal relations as a process discovery strategy. For each run of an instantiation we calculated the total time spend in solving all ILPs based on the causalities present in the event log. These times have been aggregated based on the number of activities present in an event log. The results of the experiment, plotted on a logarithmic scale, are depicted in Figure 3 4 .
As shown in Figure 3, the average time to solve the hybrid formulation is in-between the single and dual formulation. We additionally note the hybrid formulation to get slightly closer to the dual formulation when |A| increases. This is as expected as the number of single variables within the hybrid formulation is constant and hence the average time of solving the ILPs within the formulation increases with respect to the single variable formulation. Figure 3 shows that reducing the number of variables used within the ILP-formulation has an impact on the average time of solving ILPs. The differences are however marginal, which is to be expected as solving ILPs is exponential by nature. Therefore the experiments show that using ILPs for the aim of process discovery in 3 All framework files and results can be found at https://svn.win.tue.nl/repos/ prom/Packages/HybridILPMiner/Tags/papers/source_files/hybrid_ ilp_runtime_experiments.tar.gz 4 The experiments where distributed over four servers (Dell PowerEdge R520, Intel Xeon E5-2407 v2 2.40GHz, 10M Cache, 8 × 8GB RDIMM, 1600MT/s Memory), on each server a total of 10 models and corresponding logs where generated.
The concept of hybrid variable-based regions originates from language-based region theory, which in turn originates from the area of Petri net synthesis. We identify two main branches of language-based region theory within Petri net synthesis being the separating regions approach [8-10] and the minimal linear basis approach [11,12]. In the separating regions approach, which uses single-variable based regions, behavior not seen in a given prefix closed language is specified as being undesired. In the minimal linear basis approach, given a prefix closed language, a polyhedral cone of integer points is constructed based on dual variable-based regions. Using the cone a minimal basis of the set of regions is calculated which defines a minimal set of places to synthesized. Both approaches try to minimize L(N ) \ L, where N the resulting Petri net and L is a prefix-closed language. The approaches lead to Petri nets with perfect replay-fitness. Moreover precision is maximized. A side effect of this property is the fact that the synthesized net N scores low on both the generalization and the simplicity dimension.
In [3] a first design of an ILP-formulation was presented based on the concept of dual variable-based regions. The work presents objective function z 1 which we have further developed in this work to z L , and more generally, z β . The work also focuses on formulation of several different net-types in terms of linear in-equalities which even go beyond classical Petri nets, e.g. reset-and inhibitor arcs.
An alternative approach is to use the concept of state-based regions for the purpose of process discovery [13,14]. Within this approach an abstraction of the event log is computed in the form of a transition system. Regions are computed within the transition system where, like in language-based region theory, each region corresponds to a place in the resulting Petri net.
In [15] a process discovery algorithm is proposed based on the concept of numerical abstract domains using Parikh vectors as a basis. Based on an event log, a prefixclosed language is computed of which a convex polyhedron is approximated by means of calculating a convex hull. The convex hull is then used to compute causalities within the input log, by deducing a set of linear inequalities which represent places. The formulation used to calculate these causalities is in essence based the concept of single variable-based regions. The approach allows for finding pure Petri nets with arc weights and multiple marked places.
A multitude of other Petri net-based process discovery approaches exist. For a detailed description of these approaches we refer to [6].
We presented a new breed of language-based regions, i.e. hybrid variable-based regions, that captures the two existing region types being single and dual variable-based regions. Hybrid variable-based regions allow us to decide whether we want to use one or two variables for an activity present in the input event log. This allows us to achieve gains in terms of performance whilst maintaining the possibility to find complex (workflow) patterns. We have shown that within the hybrid variable-based ILP process discovery formulation, using only one variable per activity a ∈ A performs optimal in terms of the average time spent in solving the ILPs constructed.
We presented a generalized weighted objective function and showed that any instantiation of the objective function leads to ILPs that favor minimal regions. As a result, practitioners may vary the scaling function within the objective function under the guarantee that the objective function favors minimal regions. We presented a logbased scaling function that exploits trace frequencies available in the input log. Using the log based scaling function within the objective function assigns an objective value to each region equal to the token throughput of the corresponding place, given the event log. Hence, as we have shown using the new objective function leads to more intuitive objective values.
As an interesting direction for future work we identify the assessment of the impact of filtering, either a-priori or within the ILP itself, on the quality dimensions of the resulting nets, i.e. are we able to leverage the perfect repaly-fitness property? Also, an assessment of the impact of decomposition techniques [16] on the performance of ILP-based approaches is an interesting direction for future work.
Definition 8 (Hybrid variable-based process discovery ILP-formulation). Let L be an event log over a set of activities A and let A s , A d ⊆ A be a hybrid partition. Let M s , M d , M d be three matrices where M s is an |L| \ { } × A s matrix with M s (σ, a) = p(σ)(a) and
The hybrid variable-based process discovery ILP-formulation, denoted ILP h L , is defined as:
The ILP-fromulation presented in Definition 8 uses the set of linear in-equalities generated by Equation 4.1 within its constraint body. The formulation however binds v to {−1, 0, 1} |As| and x, y to {0, 1} |A d | , i.e. the formulation only allows for discovering Petri nets with arc weights restricted to {0, 1}. Additionally it defines an objective function, i.e. z = c m m + c v v + c x x + c y y, that maps each region to a real value, i.e. z : R h As (L) → R. In general we are free to choose whatever objective function we like, however, using different objective functions will lead to different process discovery results. Choosing c m = 0 and c v = c x = c y = 1 leads to arc minimization whereas maximizing the same objective leads to arc maximization, resulting in different places/regions found by the underlying ILP solver. The objective function proposed in [3], being a minimization function, tries to minimize the number of incoming arcs and maximize the number of outgoing arcs. The objective function can be defined in terms of c m , c v , c x and c y as c m = |L|, c v = σ∈L p As (σ), c x = σ∈L p A d (σ) and c y = − c x , i.e.:
The objective function used within [3], i.e. Equation 4.3 is less generic as the one proposed in Definition 8. As shown in [3], it favors minimal regions. A minimal region is a region that is not expressible as the sum of two other regions. The objective function is solely based on the set-representation of the prefix-closure of an event log. However, an event log is a bag of traces and thus consists of information on trace frequency. We propose a generalized prefix-closure-based objective function that incorporates a wordbased scaling function β. The scaling function β is required to map all sequences in the prefix-closure of the event log to some positive real value. The actual implementation is up to the user, although we present an instantiation of β that works well for process discovery. We show that the proposed generalized weighted prefix-closure-based hybrid region objective function favors minimal regions, given any scaling function β.