Paper deep dive
Monotonicity-Guided Bottom-Up Petri Net Discovery: The SPECpp Framework
Leah Tacke genannt Unterberg, Lisa L. Mannel, Wil M. P. van der Aalst
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Process discovery is one of the central challenges in process mining. Petri nets are particularly attractive because simple local constructs can express complex behavior, including concurrency. While their global behavior may be difficult to analyze, individual places can be efficiently characterized using monotonic properties, enabling bottom-up discovery. Unlike top-down approaches such as the Inductive Miner, which rely on predefined constructs for sequences, choices, loops, and concurrency, our approach allows such structures to emerge organically and can exploit the full expressive power of Petri nets, including free-choice constructs and long-term dependencies. The main challenge is the exponential number of candidate places and their combinations. We present the SPECpp framework which implements strategies to obtain high-quality models under time and resource constraints. SPECpp supports rapid experimentation and is used to evaluate these strategies using both synthetic and real-life event data.
Tags
Links
- Source: https://arxiv.org/abs/2608.09398v1
- Canonical: https://arxiv.org/abs/2608.09398v1
Trouble viewing inline? Open PDF directly →
Full Text
127,209 characters extracted from source content.
Expand or collapse full text
Monotonicity-Guided Bottom-Up Petri Net Discovery: The SPECpp Framework Leah Tacke genannt Unterberg Lisa L. Mannel Wil M. P. van der Aalst111Corresponding author wvdaalst@pads.rwth-aachen.de (Process And Data Science (PADS) RWTH Aachen University D-52074 Aachen, Germany) Abstract Process discovery is one of the central challenges in process mining. Petri nets are particularly attractive because simple local constructs can express complex behavior, including concurrency. While their global behavior may be difficult to analyze, individual places can be efficiently characterized using monotonic properties, enabling bottom-up discovery. Unlike top-down approaches such as the Inductive Miner, which rely on predefined constructs for sequences, choices, loops, and concurrency, our approach allows such structures to emerge organically and can exploit the full expressive power of Petri nets, including free-choice constructs and long-term dependencies. The main challenge is the exponential number of candidate places and their combinations. We present the SPECpp framework which implements strategies to obtain high-quality models under time and resource constraints. SPECpp supports rapid experimentation and is used to evaluate these strategies using both synthetic and real-life event data. Keywords: Bottom-up process discovery ⋅· Petri nets ⋅· Framework 1 Introduction Ever since the inception of process mining, process discovery has been the most researched task within the discipline [34, 28]. The automated, data-based inference of a process model that accurately portrays reality and lends itself to further analysis is immensely appealing. Understandably, process discovery is a key capability in the portfolio of process mining vendors like Celonis, SAP Signavio, Apromore, etc. Their increasing commercial success drives industry adoption, thereby opening up the field to new application domains and unseen levels of volume and variety, which again reinforces the need for further development of the core technologies. While simpler representations such as directly-follows graphs remain popular [36], there is a clear need for executable, precise, and human-readable process models able to express concurrency. Such models can serve as a basis for simulation, explainable prediction, and ultimately automated process improvement. From early work such as the Alpha Miner [33] to the ever popular Inductive Miner [11], all discovery algorithms directly and indirectly introduce representational and modeling biases in part by virtue of their structure. Some algorithms can be clearly categorized as functioning in a top-down or bottom-up manner [34, 39]. Informally, they either try to detect a global structure and subdivide the problem, or agglomerate atomic behavioral patterns. While there is no agreed-upon definition in the relevant literature, we use the following intuition. The inductive miner is an example of the former class, as it extracts the “outermost” behavior first, and recursively refines the inner behavior of the resulting independent sub models. This type of top-down specification provides ample structure which is useful for giving guarantees on the model level. However, it is also the reason for a major weakness: it is assumed that models are block-structured. Therefore, this divide-and-conquer style of independent sub problems introduces the limitation of not being able to discover dependencies spanning multiple sub models (blocks). We discuss related work further in Section˜6. In contrast to that, bottom-up approaches do not have to concern themselves with prior overall model structure specifications. The structure organically emerges from the agglomeration of minimal constructs. Put in another way: instead of attempting to detect structures in the input and translating it to the basic building blocks of the modeling formalism, we start with these basic building blocks and see which fit the input. For Petri nets, these minimal constructs are places. While their combination is intractable to analyze (Petri net reachability is EXPSPACE-hard [16]) and make general guarantees about without drastically limiting the expressiveness (e.g., block-structured models), individual places make for great candidates for efficiently reasoning on. Constraints on the whole model, like minimum fitness, are reflected on its individual places. By putting constraints on the individual places that eventually form the Petri net, multiple of the well-known model quality dimensions fitness, precision, simplicity and generalization [5] can be balanced starting from the low-level. We propose a conceptual framework named SPECpp that structures this kind of discovery into iterative candidate Proposal, Evaluation and Composition (PEC-cycle) followed by post-processing (p) for cleanup. The “S” of the acronym comes from the implementation which we detail in Section˜4. Figure˜1 provides a high-level overview. Essentially, we directly, and even better, indirectly, consider all possible places (like ILP-based approaches) and collect those passing an evaluation step in an intermediate result. This intermediate result can inform new place proposal, e.g., to guide the candidate search. The main strategy to combat intractability is exploiting monotonicity properties of places and place sets. A second, complementary strategy is to employ greedy search to further restrict the number of candidates considered. In our current base framework instantiation based on eST-Miner variants [19, 20, 21, 17, 18] by Mannel et al., we inherit the limitation of only supporting uniquely labeled transitions (so no silent/tau transitions either). However, we can use pre-processing approaches like [15] to address this. Figure 1: A high-level overview of the framework flow. An event log is taken as input to inform a proposal, evaluation and composition loop of candidate places. The final resulting Petri net is constructed after a post-processing step. To motivate the necessity of bottom-up approaches like this, we just need to turn our head to process control flows with complex dependencies that are not easily separated. For example, so-called long-term dependencies and short loops. We adapt a minimal example from Mannel et al. [19]. Imagine a delivery process where in the beginning either a regular or a VIP-customer’s order comes in (denoted by activities reg. order (o) and VIP order (vovo)). Then, a varying number of deliveries (delivery (d)) are made for that order. Finally, the customer is invoiced the regular price or the VIP special price (reg. invoice (i) and VIP invoice (vivi)). Of course, the invoice type is in accordance with the earlier order type. A sample event log of records of this process could be [⟨▶,o,d,d,i,■⟩,⟨▶,vo,d,d,d,vi,■⟩][ ,o,d,d,i, , ,vo,d,d,d,vi, ], with ▶ and ■ denoting the start and end of a process instance respectively. Figure˜2 shows the results of various established discovery algorithms on this input. Among existing approaches, only the eST-Miner correctly captures both the long-term dependency between order and invoice type and the delivery self-loop. (a) Base eST-Miner (b) Alpha Miner (c) Inductive Miner (d) ILP Miner Figure 2: Petri nets discovered by various algorithms on the input log [⟨▶,o,d,d,i,■⟩,⟨▶,vo,d,d,d,vi,■⟩][ ,o,d,d,i, , ,vo,d,d,d,vi, ]. The long-term (non-directly following) dependency between VIP or regular types, particularly with the looping activity delivery, provides a challenge for established discovery algorithms. It is important to emphasize that there is never “one correct” model. Model quality is informed by its purpose. The conceptual framework we present in this paper is highly flexible and configurable to be adaptable to the user’s needs to balance the aforementioned quality dimensions. Bottom-up discovery requires two key decisions: which candidate places to consider and how to combine accepted places into a model. We call these candidate proposal and candidate composition, respectively. Candidate composition is informed by candidate evaluation. Together, proposal, evaluation, and composition form the PEC cycle, which is followed by a post-processing stage. Next to the conceptual framework we present an extensive implementation (which we introduce in Section˜4) serving as a software framework for fast prototyping of varied metrics and constraint types that guide the discovery phase. The rest of this paper is structured as follows. We first provide a formal background in Section˜2, before we introduce our conceptual framework in Section˜3. Then, we go over the related implementation artifacts that we published in Section˜4. We then include a brief evaluation in Section˜5 to validate our approach. After positioning this framework among related work in Section˜6, we conclude the paper with some discussion and outlook on future work in Section˜7. 2 Background We use sets X=x1,x2,…X=\x_1,x_2,…\, multisets M=[x1f1,x2f2,…]M=[x_1^f_1,x_2^f_2,…] and finite ordered sequences σ=⟨s1,s2,…,sn⟩∈S∗σ= s_1,s_2,…,s_n ∈ S^* with the usual semantics. Elements in the support set of a multiset xi∈supp(M)x_i (M) have positive frequency fi∈ℕf_i and σ(i)=siσ(i)=s_i with i∈1,…,ni∈\1,…,n\ refers to the i-th element of a sequence. The elements of a sequence are set(σ)=σ(1),…,σ(n)set(σ)=\σ(1),…,σ(n)\. |⋅||·| denotes the cardinality, i.e., number of elements, in a set, multiset or sequence. We use k¯=1,…,k k=\1,…,k\ as a shorthand for integer index sets (with 0¯=∅ 0= ). The set of possible finite sequences over an alphabet Σ is Σ∗=⋃n∈ℕ0Σn ^*= _n _0 ^n, where Σn ^n denotes all sequences of length n∈ℕ0n _0. The powerset over X is denoted by (X)P(X) whereas ℬ(X)B(X) refers to all multisets over X. Further, we use permutations of sets S, π∈Perm(S)π (S) with π:S→|S|¯π:S→ |S| such that ∀i,j∈n¯:i≠j⇔π(i)≠π(j)∀ i,j∈ n:i≠ j π(i)≠π(j), i.e., π is bijective. A permutation uniquely maps a set to its ordered sequence by specifying element indices. A total ordering ≤ on X (a reflexive, antisymmetric and transitive relation) which further relates all elements, i.e., ∀x,y∈X:x≤y∨y≤x∀ x,y∈ X:x≤ y y≤ x, induces a permutation π≤ _≤ with ∀x,y∈X:π≤(x)≤π≤(y)⇔x≤y∀ x,y∈ X: _≤(x)≤ _≤(y) x≤ y. Additionally, we use predicate functions over sets X of the form f:X→True,Falsef:X→\True,False\. We usually define them with logical expressions ⇒,∨,∧,¬ , , , over the elements of X. They are used as filters on subsets S⊆XS X with the following notation: S↾f=s∈S∣f(s)=TrueS _f=\s∈ S f(s)=True\. Restrictions on functions restrict the domain, i.e., a function g:X→Yg:X→ Y is restricted by f to dom(g↾f)=X↾fdom(g _f)=X _f. In process mining, events are typically differentiated from their associated activity, however, we only care about event logs as sequences of activities in our setting. There are many opportunities for incorporating further event attributes into discovery or enriching the resulting models [22]. Though the implementation artifacts of this work support such extensions, particularly for heuristics, we leave this as future work. Definition 1 (Activities, Behaviors). A is the universe of activities (actions, tasks, etc.). ▶,■⊆\ , \ are unique start and end activities. A behavior is a sequence σ=⟨a1,…,an⟩∈∗σ= a_1,…,a_n ^* of activities that starts with ▶ and ends with ■ , i.e., a1=▶∧an=■a_1= a_n= and ∀1<i<n:ai∉▶,■∀ 1<i<n:a_i∉\ , \. The universe of possible behaviors is then given by =σ∈∗∣σ is a behaviorB=\σ ^* σ is a behavior\. Note that, while sequences can be empty, a behavior has at least length two. The fixed start/end activities pose no threat to generality, as sequences are trivially transformed to behaviors. We require them here to not have to deal separately with initially and finally occurring activities. It also simplifies the construction of the resulting Petri net. Definition 2 (Event Log). An event log L is represented as a multiset of behaviors, i.e., L∈ℬ()L (B). In this context, behaviors are also referred to as traces. For the notation of our resulting process model, we use a Petri net based formalism. Specifically, uniquely labeled Petri nets represented by sets of places. Transitions and places are the fundamental building blocks of Petri nets. We uniquely identify transitions with activities in this work, so we may use the terms interchangeably. Definition 3 (Places). ℙ=()×()P=P(A)×P(A) is the universe of all possible places. For p=(I,O)∈ℙp=(I,O) , we call ∙p=I p=I its preset and p∙=Op =O its postset. Transitions in both, i.e., the intersection ∙p∩p∙ p∩ p are called self-loops. Places ℙ!=(()∖∅)×(()∖∅)P^!=(P(A) \ \)×(P(A) \ \) with non-empty pre- and postset are called through places. An important structural relation on places which we will be using are preset and postset expansions. Definition 4 (Pre- & Postset Expansions). Let p,p′∈ℙp,p be places. p′p is called a preset expansion of p if and only if ∙p⊂∙p′ p⊂ p and p∙=p′∙p =p hold. It is direct if ∙p p and ∙p′ p differ by exactly one element. Postset expansions are defined symmetrically. As defined here, we only consider pure expansions, i.e., those where only either the pre- or postset changes. For an example, consider (a,b,c)(\a\,\b,c\) which is a direct postset expansion of (a,b)(\a\,\b\) and an indirect one of (a,∅)(\a\, ). Usually, the semantics of Petri net places are defined via markings, that is, counts of tokens on a place. When regarding a place and its adjacent transitions in isolation, the transitions in its postset are enabled whenever its number of tokens is positive. Of course, from the perspective of a transition, all of the places it is in the postset in need to have a positive number of tokens for it to be enabled. Enabled postset transitions can be executed to consume one token. The transitions exclusively in its preset (so non self-loops) are not constrained (by this particular place) and can fire at any time to produce a token. In our setting, this is equivalent to the property that for any prefix of a behavior, the number of activities in the preset up to the penultimate element of the prefix is greater or equal to that of those in the postset for the entire prefix. Additionally, they are equal for the entire behavior which implies equal token counts at the start and end of a trace, given the former condition holds. For our place fitness, we consider places as initially and finally unmarked. In our Petri net conversion, we add a marked start place and designated sink place, so this is not a restriction. This class is close to workflow nets without the requirement that all transitions lie on a path between start and end. Definition 5 (Fitness). Let p∈ℙp be a place and σ=⟨a1,…,an⟩∈σ= a_1,…,a_n a behavior. The behavior σ is fitting on p, i.e., □σ(p) _σ(p) if and only if non-neg(σ,p)∧balanced(σ,p)non-neg(σ,p) balanced(σ,p) holds. Where these properties are defined as follows. non-neg(σ,p) non-neg(σ,p) :⇔∀k∈n¯:non-negk(σ,p) : ∀ k∈ n:non-neg_k(σ,p) non-negk(σ,p) non-neg_k(σ,p) :⇔|i∈k−1¯∣σ(i)∈∙p|≥|i∈k¯∣σ(i)∈p∙| : |\i∈ k-1 σ(i)∈ p\|≥|\i∈ k σ(i)∈ p \| balanced(σ,p) balanced(σ,p) :⇔|i∈n¯∣σ(i)∈∙p|=|i∈n¯∣σ(i)∈p∙| : |\i∈ n σ(i)∈ p\|=|\i∈ n σ(i)∈ p \| The set of fitting behaviors on p is then given by (p)=σ∈∣□σ(p)fit(p)=\σ _σ(p)\. This notion of fitness intuitively corresponds to the classic token-based replay on Petri nets [24], e.g., during replay of behavior ⟨▶,a,b,a,b,■⟩ ,a,b,a,b, on place (a,b)(\a\,\b\), there are no missing tokens (non-neg), and at the end, there is no remaining token (balanced). While one place only constrains its adjacent activities, making it efficient to analyze and reason about, the behavior of a set of places is simply the intersection of its constituents. Definition 6 (Sets of Places). Let P⊆ℙP be a set of places and σ∈σ a behavior. σ is fitting on P if and only if □σ(P):⇔∀p∈P:□σ(p) _σ(P): ∀ p∈ P: _σ(p). The set of fitting behaviors on P is (P)=σ∈∣□σ(P)=⋂p∈P(p)fit(P)=\σ _σ(P)\= _p∈ Pfit(p). This definition implies that any trace is fitting on an empty set of places, which intuitively makes sense as places can be regarded as constraints. A set of places can be trivially translated to an equivalent Petri net with open-world semantics. That is, contrary to the typical closed-world semantics, an activity not contained in the model is unconstrained and can be executed at any time. Definition 7 (Petri net Conversion). Let P⊆ℙP be a set of places. The set of occurring activities is A=⋃p∈P∙p∪p∙A= _p∈ P p∪ p . Then N=(P′,A,F,Minit,Mfinal)N=(P ,A,F,M_init,M_final) with places P′=P∪pinit,pfinalP =P∪\p_init,p_final\ using pinit=(∅,▶)p_init=( , ) and pfinal=(■,∅)p_final=( , ) is a behaviorally equivalent marked Petri net under open-world semantics. The arcs are uniquely specified by the places F=(i,p),(p,o)∣p∈P′,i∈∙p,o∈p∙⊆(P′×A)∪(A×P′)F=\(i,p),(p,o) p∈ P ,i∈ p,o∈ p \ (P × A)∪(A× P ). The initial and final marking are simply Minit=[pinit]M_init=[p_init] and Mfinal=[pfinal]M_final=[p_final]. Note that, as pinitp_init and pfinalp_final have no fitting behavior according to □ , they are artificially added for marking-based semantics. Given a fixed set of activities, e.g., those considered possible in a process, the Petri net could also be extended with a concurrent “flower model gadget” to preserve the same fitting behavior under the closed-world semantics. In practice, this is not really a limitation as the given event log used for discovery is assumed to be complete in that regard. 3 Conceptual Framework We present a framework for bottom-up discovery of sets of places. There are two natural hooks for strategies: which places to consider and which combinations of places to consider. We term the strategy of which places to consider candidate proposal and which combinations to consider candidate composition. Composition strategies rely on a preceding candidate evaluation for their decision-making. Together, these three steps form the PEC-cycle. It is repeated until the proposal strategy is exhausted (no remaining candidates) but may also be stopped early, e.g., by specifying a time limit. After this loop terminates, we append a one-shot post-processing pipeline. This is also where we convert from sets of places, which we use formally and internally, to Petri nets. In this work, we focus mainly on the earlier stages, however, there is a lot of research and development potential in the latter stages that we want to support. Refer to Figure˜1 from the introduction for a high-level schematic overview. For this section, we fix a finite set of considered activities A⊆A and thus a set of possible places P=p∈ℙ∣∙p∪p∙⊆AP=\p p∪ p A\. In an application setting, this would typically be the set of activities occurring in the event log used as input. Then, the number of possible candidates |P||P| is in (2|A|)O(2^|A|) and the number of possible combinations of those candidates |(P)||P(P)| is in (2|P|)=(4|A|)O(2^|P|)=O(4^|A|). This makes a brute-force approach wholly intractable. By exhaustive enumeration, though infeasible even for small inputs, we could trivially guarantee finding the best possible solution according to any predefined quality metric. Luckily, there exist powerful monotonicity properties on places and place sets which enable us to drastically prune the search space. An evaluation of one candidate place can allow us to indirectly reason about a whole set of monotonically related places. Similarly, the conjunction of place properties on a place set may allow us to indirectly consider all its supersets. Additionally, we employ greedy decision-making and place set invariants (e.g., implicitness freedom). We first introduce our conceptual proposal strategy and then move over to evaluation together with composition and finally post-processing. 3.1 Proposal The primary method used in our framework for limiting the number of proposed candidates is the usage of a candidate tree in which the subtree relation is aligned to monotonicity properties on places. Further, we require a compact representation of that tree as it still has exponential size. We achieve this by using a locally computable child generation function instead of pre-computing the complete tree. The local computability allows us to incrementally unfold the tree while “forgetting” fully traversed nodes. Definition 8 (Efficient Candidate Tree). An efficient candidate tree T=(g,r)T=(g,r) is defined by a child generation logic g:P→(P)g:P (P) and a root node r∈Pr∈ P. The following properties of g are required so that T actually unfolds into a tree. Let g−1(p)=p′∈P∣p∈g(p′)g^-1(p)=\p ∈ P p∈ g(p )\ for p∈Pp∈ P be the inverse of g. The root has an empty set of parents, i.e., g−1(r)=∅g^-1(r)= . ∀p∈P ∀ p∈ P :p∉g(p) :p∉ g(p) (1) ∀p∈P∖r ∀ p∈ P \r\ :|g−1(p)|=1 :|g^-1(p)|=1 (2) Further, and most importantly, g has to be acyclic. For any sequence of at least two places ⟨p1,…,pn⟩∈P∗ p_1,…,p_n ∈ P^*, n≥2n≥ 2 which represents a path through T, i.e., ∀1≤i<n:pi+1∈g(pi)∀ 1≤ i<n:p_i+1∈ g(p_i), we require the start and end to be unique, i.e., p1≠pnp_1≠ p_n. The acyclicity condition already implies condition (1). Equation (2) states that each node, except the root, has to have a unique parent. Together with the finiteness of P, it follows that there must exist some leaf nodes without children. The places contained in a subtree rooted at a place p∈Pp∈ P under generation logic g are then well-defined by the following recursion. g(p)=p∪⋃p′∈g(p)g(p′)cand_g(p)=\p\∪ _p ∈ g(p)cand_g(p ) Note that the aforementioned leaf nodes form the terminal case in this definition. We additionally require candidate trees to be complete, i.e., the root r of a tree (g,r)(g,r) generates all possible places g(r)=Pcand_g(r)=P. In our setting, we may relax that to at least generating all through places, i.e., P!⊆g(r)⊆P^! _g(r) P. This is because non-through places can only have fitting behavior that does not intersect with them at all. Formally, set(σ)∩(∙p∪p∙)=∅set(σ)∩( p∪ p )= for place p∈ℙp and behavior σ∈(p)σ (p). That makes them uninteresting in our setting. Figure 3: An exemplary partial efficient candidate tree Tex=(g,r)T_ex=(g,r) rooted at place r=(a,)r=(\a\,\\). Consider Figure˜3 for a partial example of such a tree Tex=(g,r)T_ex=(g,r). Place r=(a,)r=(\a\,\\) is its root and it clearly fulfills the conditions of Definition˜8. Its candidate set g(r)cand_g(r) consists of all visible places. Note that it is not complete. The proposal step is simply a memory-efficient expansion of this tree. Potential candidates are proposed at most once. That is, only if they meet all constraints collected up to that moment. Constraints are how candidate evaluations and their indirect impact are incorporated into the candidate traversal. Definition 9 (Constraints). A constraint c:P→True,Falsec:P→\True,False\ is a predicate function over the set of possible places. A place p∈Pp∈ P meets constraint c, if and only if c(p)=Truec(p)=True. To lift this to sets of constraints C, we use an indicator function C(p):⇔∀c∈C:c(p)=TrueI_C(p): ∀ c∈ C:c(p)=True. We use it to filter sets of places S⊆PS P to those meeting the constraints S↾C=p∈S∣C(p) holdsS _I_C=\p∈ S _C(p) holds\. For sets of places S⊆PS P, we also have C(S):⇔∀p∈S:C(p)I_C(S): ∀ p∈ S:I_C(p) as an indicator whether all places meet all constraints. What we are really interested in are constraints that are aligned with the subtree relation of our candidate tree. This enables efficient pruning. Definition 10 (Subtree-Monotonicity). We call a set of constraints C subtree-monotonic w.r.t. generation logic g if for any p,p′∈Pp,p ∈ P with p′∈g(p)p _g(p), ¬C(p)⟹¬C(p′) _C(p) _C(p ) In other words, if C does not hold at p, it also does not hold on any place in its subtree. Note the contrapositive that if it holds at a descendant of p, it must also hold at p itself. With respect to the generation logic of the example tree TexT_ex, the set of constraints Cex=p↦a∉∙p,p↦a∉p∙C_ex=\p a∉ p,\,p a∉ p \, i.e., a neither occurs in the preset nor postset of a place p, is subtree-monotonic. A set of constraints C induces a restriction on a generation logic g as follows. For p∈Pp∈ P, gC(p)≔g(p)↾C.g_C(p) g(p) _I_C. That is, children not meeting the constraints are filtered out. This point-wise restriction of the child generation logic suffices for respecting the constraints. Theorem 1 (Constrained Child Generation). Let C be a subtree-monotonic set of constraints with respect to a child generation logic g. For any p∈Pp∈ P, it holds that g(p)↾C=gC(p)if C(p) holds,∅otherwise.cand_g(p) _I_C= casescand_g_C(p)&if I_C(p) holds,\\ &otherwise. cases Theorem˜1 states that the candidates meeting the constraints in the subtree rooted at p are exactly the candidates that the restricted generation logic gCg_C recursively generates. Simply said, a recursive traversal via gCg_C does not miss any places meeting the constraints. Figure 4: A schematic of how the subtree-monotonicity of a constraint set C interacts with a child generation logic and resulting candidate set rooted at a place p. A place like p p for which CI_C holds, cannot have an ancestor for which it does not and is thus included in gC(p)cand_g_C(p). Places like p~ p or p¯ p for which CI_C does not hold are either themselves directly filtered by gCg_C or an ancestor of theirs is. Therefore, they are also not included in the generated candidate set gC(p)cand_g_C(p). Proof. Let p∈Pp∈ P be a place, g a child generation logic and C a subtree-monotonic set of constraints. If C(p)I_C(p) does not hold, g(p)↾C=p′∈g(p)∣C(p′) holds=∅cand_g(p) _I_C=\p _g(p) _C(p ) holds\= immediately follows from subtree-monotonicity. So, assume C(p)I_C(p) holds. Figure˜4 provides an illustration of the following proof. As gCg_C is a point-wise restriction of g, i.e., ∀p∈P:gC(p)⊆g(p)∀ p∈ P:g_C(p) g(p), we have gC(p)⊆g(C)cand_g_C(p) _g(C). Trivially, we also have g(p)↾C⊆g(p)cand_g(p) _I_C _g(p), so it suffices to show for any p^∈g(p)∖p p _g(p) \p\ that C(p^)⇔p^∈gC(p)I_C( p) p _g_C(p). Let p^∈g(p)∖p p _g(p) \p\ be a descendant of p and let ⟨p1,…,pk⟩∈P∗ p_1,…,p_k ∈ P^*, k∈ℕk be the sequence (unique due to tree structure) of places from p to p p, i.e., p1=p_1=p, pk=p^p_k= p and pi+1∈g(pi)p_i+1∈ g(p_i) for all i∈k−1¯i∈ k-1. Assume C(p^)I_C( p) holds. Due to the contrapositive of subtree-monotonicity, it also holds for all pip_i on that path, and thus pi+1∈gC(pi)p_i+1∈ g_C(p_i) for all i∈k−1¯i∈ k-1. We therefore get p^∈gC(p) p _g_C(p). Assume C(p^)I_C( p) does not hold. Then, in particular, p p is not generated by the restricted generation logic gCg_C by its parent, i.e., p^∉gC(pk−1) p∉ g_C(p_k-1). So, we have p^∉gC(p) p _g_C(p). ∎ To allow general prioritized expansion, instead of hard-coding breadth- or depth-first traversal, we need to keep some additional state. The set of currently not fully expanded nodes as well as an indicator which of their children were already generated is necessary. Additionally, we keep a set of currently active subtree-monotonic constraints. Definition 11 (Tree State). A tree state TS=(S,C,ν)TS=(S,C,ν) of a tree T=(g,r)T=(g,r) is characterized by a set of active nodes S⊆PS P, a set of constraints C and a function ν:S→Pν:S→ P with ∀s∈S:ν(s)⊆g(s)∀ s∈ S:ν(s) g(s), indicating the already visited children of the active nodes. The canonical initial state of a candidate tree T=(g,r)T=(g,r) is (r,∅,(r,∅))(\r\, ,\(r, )\). The expansion can now be guided by an expansion strategy that selects the next active node of a tree state to be expanded. Note that the overall candidate ordering is still mainly dependent on the tree structure, as children cannot be traversed before their parents. Definition 12 (Expansion Strategy). An expansion strategy is a function n:(P)→Pn:P(P)→ P with ∀∅≠S⊆P:n(S)∈S∀ ≠ S P:n(S)∈ S that chooses one place out of a non-empty set of places. A tree state can be pruned by removing active nodes (and their mapping) in case their constraint-filtered children are exhausted, i.e., they become inactive. This is highly dependent on the expansion strategy. In the worst case, the tree state can grow to the maximum tree width, as is the case with breadth-first traversal. Depth-first traversal only needs to keep track of one path from the root node to the current node, and is thus bounded by the tree depth. This makes it the most memory efficient traversal. Another popular class of those strategies are heuristics, i.e., using a scoring function h:P→ℝh:P . Without loss of generality, we assume a preference for smaller values. Then h induces the strategy nh(S)=argminp∈Sh(p)n_h(S)=argmin_p∈ Sh(p) for ∅≠S⊆P ≠ S P. We call a h subtree-monotonic w.r.t. generation logic g if ∀p,p′∈P:p′∈g(p)⟹h(p)≤h(p′)∀ p,p ∈ P:p _g(p) h(p)≤ h(p ) holds. This is essentially a natural generalization of the constraint monotonicity from boolean implication to an ordering relation on the range of the heuristic. For example, the heuristic for place size, hex:p↦|∙p∪p∙|h_ex:p | p∪ p | is subtree-monotonic w.r.t. the example TexT_ex (from Figure˜3). Subtree-monotonic heuristics also induce subtree-monotonic threshold constraints, e.g., for a heuristic h and threshold t∈ℝt , ch,t(p):⇔h(p)≤tc_h,t(p): h(p)≤ t for p∈Pp∈ P. Note that, while we focus here on subtree-monotonic ordering and constraining strategies to guarantee completeness, more general strategies are possible and supported in our implementation. Dropping the completeness notion and letting greediness run wild can be empirically valid and is heavily employed on the composition side. There is also another prioritization opportunity within the expansion step. Namely, the child ordering m:P→⋃S⊆PPerm(S)m:P→ _S PPerm(S) w.r.t. the generation logic g that assigns to each place a permutation of its children under g, i.e., m(p)=π∈Perm(g(p))m(p)=π (g(p)) for p∈Pp∈ P. We use a static (place independent) child node permutation rule but it could be more sophisticated than that. For example, children with a heuristically determined high potential to improve the current result could be explored first. First, the next node to expand is picked from the active set according to the expansion strategy. Then, the constrained set of potential unvisited children is computed. If it is empty, we recurse after removing this exhausted place. Otherwise, the first place according to the child ordering is added to the active set and returned. With all of the previous definitions out of the way, we can define the tree expansion procedure in Algorithm˜1. Expansion fails (returns ⊥ ) if there are no more active nodes. Algorithm 1 expand 1:generation logic g 2:expansion strategy n 3:child ordering m 4:tree state TS=(S,C,ν)TS=(S,C,ν) 5:S≠∅S≠ 6:procedure expand(TSTS) 7: p←n(S)p← n(S) 8: N←gC(p)∖ν(p)N← g_C(p) ν(p) 9: if N=∅N= then ⊳ pruning if exhausted due to constraints 10: if |S|>1|S|>1 then 11: return expand((S∖p,C,ν↾S∖p)) expand((S \p\,C,ν _S \p\)) 12: else 13: return ⊥ 14: end if 15: else 16: π←m(p)π← m(p) 17: p′←argminp^∈Nπ(p^)p _ p∈ Nπ( p) 18: ν(p)←ν(p)∪p′ν(p)←ν(p)∪\p \ 19: if ν(p)⊇gC(p)ν(p) g_C(p) then ⊳ pruning if this was p’s last child 20: S←S∖pS← S \p\ 21: ν←ν↾Sν←ν _S 22: end if 23: S←S∪p′S← S∪\p \ 24: ν←ν∪(p′,∅)ν←ν∪\(p , )\ 25: return p′p 26: end if 27:end procedure The tree expansion is called within the proposal routine Algorithm˜2 to generate all constraint-satisfying candidates. Whenever a place is produced, it is handed over to the composition side which we describe in Section˜3.4. Due to the acyclicity (tree-structure) of the child node generation function g and children bookkeeping, expand never returns the same place twice when initialized with just the root node as an active node. This actually holds in general for sets of active nodes S with disjoint subtrees, i.e., ∀p≠p′∈S:p∉g(p′)∀ p≠ p ∈ S:p _g(p ). Consequently, propose will necessarily terminate after a finite number of steps. Algorithm 2 propose 1:efficient tree T=(g,r)T=(g,r) 2:initial constraints C 3:procedure propose 4: TS←(r,C,(r,∅))TS←(\r\,C,\(r, )\) 5: p←rif C(r),⊥otherwise.p← casesr&if I_C(r),\\ &otherwise. cases 6: while p≠⊥p≠ do 7: yield p 8: update C 9: p←expand(TS)p← expand(TS) 10: end while 11:end procedure After each candidate proposal, we allow the constraint set to change. The idea is that new constraints may be generated in response to the candidate. We require that the set of constraints is only ever updated in a monotone fashion. Definition 13 (Monotonic Constraint Strengthening). Let C,C′C,C be two subtree-monotonic constraint sets. C′C is a monotonic strengthening of C if and only if ∀p∈P:¬C(p)⟹¬C′(p)∀ p∈ P: _C(p) _C (p) holds, i.e., places for which C does not hold, C′C does neither. Most trivially this is the case if C⊆C′C C . A sequence of constraint sets is monotonic if every two directly following constraint sets are monotonic strengthenings. This follows from the transitivity of ⟹ . For example, the sequence of constraint sets \\, p↦a∉∙p∩p∙\p a∉ p∩ p \ (a is not a self loop of p), p↦a∉∙p\p a∉ p\ (a is not in the preset of p), p↦a∉∙p∪p∙\p a∉ p∪ p \ (a is neither in the preset nor postset of p) is monotonic. We want to note here that there is a difference between the formal constraints and their representation. Very local types of constraints only affect the subtree rooted in a single place and therefore have to be checked only once. Some constraints “touch” many subtrees and have to be constantly re-evaluated while other types of constraints can be efficiently summarized and thus incorporated with marginal impact on performance. This is an important aspect to consider on both the conceptual as well as implementation side. If we enforce the aforementioned monotonicity properties, we can guarantee a complete candidate traversal w.r.t. the final set of constraints C. If we further require the sequence of constraint sets to never exclude a previously returned candidate, the traversal is even minimal, i.e., we never consider a candidate that would later be filtered by new constraints. This is in particular the case for the local constraints mentioned above if they can be generated in response to the place they are local to. Proposition 1. Assuming constraint set updates are monotonic strengthenings, the set of returned places of the proposal routine Algorithm˜2, denoted here by M, contains all places for which all constraints in the final constraint set C hold, i.e., M⊇P↾CM P _I_C (completeness). Further, assuming an updated constraint set never excludes previously returned places, no more than those places are returned, i.e., M=P↾CM=P _I_C (minimality). Proof. Let (g,r)(g,r) be an efficient candidate tree and C0C_0 be the initial constraints. Assume propose terminates after T∈ℕ0T _0 executions of the loop (steps). For T=0T=0, we never return anything and as C0C_0 is subtree-monotonic, ¬C0(r)⟹P↾C0=∅ _C_0(r) P _I_C_0= . Let MtM_t be the set of returned candidates and CtC_t be updated constraint set after the t-th step for t∈T¯t∈ T. We first show completeness by contradiction. Assume p∈P↾CT∖MTp∈ P _I_C_T M_T exists. As the constraint sequence is monotonic, the set of places meeting all constraints can only shrink, i.e., ∀t<T:P↾Ct⊇P↾Ct+1∀ t<T:P _I_C_t P _I_C_t+1. So, for all t∈T¯t∈ T, p∈P↾Ctp∈ P _I_C_t holds. It can thus have never been filtered directly by the restriction of the child generation logic gCt(p)=g(p)↾Ctg_C_t(p)=g(p) _I_C_t at any timestep t. p also cannot be the root r as that is returned exactly if C0(r)I_C_0(r) holds. Then assume an ancestor p′p , i.e., p∈g(p′)p _g(p ), was filtered at step 0≤k≤T0≤ k≤ T instead. So, ¬Ck(p′) _C_k(p ). However, as CkC_k is subtree-monotonic, this directly implies ¬Ck(p) _C_k(p), i.e., p∉P↾Ckp∉ P _I_C_k. A contradiction. We show minimality Mt⊆P↾Ct−1M_t P _I_C_t-1 via induction over the timesteps. For t=1t=1, M1=r⊆P↾C0M_1=\r\ P _I_C_0 holds as we enter the loop the first time, i.e., C0(r)=TrueI_C_0(r)=True. For t+1>1t+1>1, Mt+1=Mt∪pM_t+1=M_t∪\p\ where p is the result of the expand call from the previous iteration. By construction, we have Ct(p)=Ct−1(Mt)=TrueI_C_t(p)=I_C_t-1(M_t)=True. If CtC_t does not constrain any place in MtM_t, i.e., Ct(Mt)I_C_t(M_t) holds, then it directly follows that Ct(Mt∪p)=TrueI_C_t(M_t∪\p\)=True. So, Mt+1M_t+1 is still a subset of all places meeting the updated constraints, i.e., Mt+1⊆P↾CtM_t+1 P _I_C_t. At the end after T steps, we thus inductively get MT⊆P↾CT−1M_T P _I_C_T-1. Finally, as the constraint sequence is monotonic and the algorithm terminated, there were no more unseen candidates left under CTC_T. Together with the assumption that it does not constrain an already returned candidate, we have exactly MT=P↾CTM_T=P _I_C_T, i.e., the set of proposed places is complete and minimal. ∎ This motivates choosing a good constraining strategy that generates constraints early enough for the selected generation logic. For example, consider the constraint sequence C0=∅,C1=…=CT=p↦a∉p∙C_0= ,C_1=…=C_T=\p a∉ p \ (where propose terminated after T steps), i.e., the constraint that a is not in the postset of a place p is added after the first proposed place. On a breadth-first traversal of the partial example tree TexT_ex, the left subtree (at p=(a,a)p=(\a\,\a\)) would be completely pruned. 3.1.1 Concrete Child Generation Logic In this section, we give our instantiation of a child generation logic. As the number of activities is the exponential factor in the runtime of this class of algorithms, we want to provide more fine-grained control over the selection of relevant activities. For this section, we thus fix a set of considered preset activities ∅≠Apre⊆A ≠ A_pre A and postset activities ∅≠Apost⊆A ≠ A_post A, making the set of possible places P=(Apre)×(Apost)P=P(A_pre)×P(A_post). Among these, only the through places P!=((Apre)∖∅)×((Apost)∖∅)P^!=(P(A_pre) \ \)×(P(A_post) \ \) are interesting. This allows us to naturally exclude places with the designated start/end activities ■ in their preset and ▶ in their postset which can never have any fitting behavior. The candidate tree is rooted at the empty place, i.e., r=(∅,∅)r=( , ). It is grown by extending the preset and postset until all considered activities are covered. That makes the depth of a place p∈Pp∈ P equal to the number of connected arcs, |∙p|+|p∙|| p|+|p |. This intuitive measure of place simplicity thus becomes a first class property in the emerging candidate ordering. Definition 14 (Incremental Pre- & Postset Expansions). Let p∈Pp∈ P be a place and <pre<_pre, <post<_post be strict total orderings on ApreA_pre and ApostA_post respectively. An incremental preset (postset) expansion of p=(I,O)p=(I,O) is an extension of p with one activity added to its preset (postset) which is larger than previously contained activities according to <pre<_pre (or <post<_post respectively). Formally, +(p) ^+(p) =(I∪a,O)∣a∈Apre,∀a′∈I:a′<prea =\(I∪\a\,O) a∈ A_pre,\,∀ a ∈ I:a <_prea\ +(p) ^+(p) =(I,O∪a)∣a∈Apost,∀a′∈O:a′<posta =\(I,O∪\a\) a∈ A_post,\,∀ a ∈ O:a <_posta\ Note that if I=∅I= (or O=∅O= , respectively), all considered activities meet the ordering constraint which is intuitively correct, as any element is then a valid extension of the empty set. The concrete child generation logic then simply concatenates these expansions under a condition on postset size to preserve the one-parent tree structure. Without it, we would have non-unique parents, as a through place is both a preset and a postset expansion of two different places. The choice of the postset size condition is related to pruning efficiency but could symmetrically be on the preset. For p=(I,O)∈Pp=(I,O)∈ P, g(p)≔+(p)if I=O=∅,+(p)if |I|+|O|=1,+(p)∪+(p)if |I|≥1∧|O|=1,+(p)if |I|≥1∧|O|>1g(p) casespost^+(p)&if I=O= ,\\ pre^+(p)&if |I|+|O|=1,\\ post^+(p) ^+(p)&if |I|≥ 1 |O|=1,\\ post^+(p)&if |I|≥ 1 |O|>1 cases These cases are disjoint and well defined on all places eventually generated by g starting at the empty root r=(∅,∅)r=( , ). It is important to note here that g does not generate non-through places except for in the first two layers, where all places have either ∙p=∅ p= or p∙=∅p = . This can also be modeled as an initial constraint c(p):⇔(∙p=p∙=∅)∨(∙p=∅∧|p∙|=1)∨(∙p≠∅∧p∙≠∅)c(p): ( p=p = ) ( p= |p |=1) ( p≠ p ≠ ) that exactly excludes P∖g(r)P _g(r), leaving g(r)=P!∪r∪+(r)cand_g(r)=P^!∪\r\ ^+(r). Our child ordering permutation m merely lifts <pre<_pre and <post<_post to the extensions constructed with them. That is, let m(p)=πm(p)=π, then π((I∪a,O))<π((I∪a′,O)):⇔a<prea′π((I∪\a\,O))<π((I∪\a \,O)): a<_prea and π((I,O∪a))<π((I,O∪a′)):⇔a<posta′π((I,O∪\a\))<π((I,O∪\a \)): a<_posta hold. Further, postset expansions are ordered before preset expansions, i.e., ∀pI∈+(p),pO∈+(p):π(pO)<π(pI)∀ p_I ^+(p),p_O ^+(p):π(p_O)<π(p_I), because they can lead to earlier pruning. This is related to the choice of the condition on the postset size above. An example candidate subtree according to the instantiations given in this section is presented in Figure˜5. It is rooted at (▶,a)(\ \,\a\), so it starts at depth two. Blue edges indicate postset expansions, red ones preset expansions. The activity orderings used in g are ▶<prea<preb<prec <_prea<_preb<_prec and a<postb<postc<post■a<_postb<_postc<_post . Note that the selected sets of possible activities for the preset ApreA_pre and postset ApostA_post differ. Any place p with ■∈∙p ∈ p and ▶∈p∙ ∈ p can never have any fitting behavior, so they can readily be excluded from the candidate tree. This example subtree illustrates the emerging asymmetrical structure with the earlier and more homogeneous postset expansion subtrees. The over/underfedness constraints can cut off child subtrees in which only one of the two colors occurs. So, this postset (blue) first structure prioritizes underfedness. Constraint generation enabling pruning is enabled by candidate evaluation and performed within the composition logic. Figure 5: An example of the candidate subtree rooted at (▶,a)(\ \,\a\) generated by our given child generation logic g, child permutation m and activity orderings ▶<prea<preb<prec <_prea<_preb<_prec and a<postb<postc<post■a<_postb<_postc<_post . Blue edges indicate postset expansions, red ones preset expansions. The emerging structure has more homogeneous postset expansion subtrees which are also ordered earlier (according to breadth-first traversal). 3.2 Evaluation Any proposed candidate place is evaluated with arbitrary metrics to provide a basis for the composition logic. We divide the evaluations of candidates into individual and relative. Individual evaluations are defined on individual places, i.e., :ℙ→Eeval^ind:P→ E^ind with evaluation co-domain E^ind, whereas relative evaluations are always relative to a given set of places, i.e., :ℙ×(ℙ)→Eeval^rel:P×P(P)→ E^rel with evaluation co-domain E^rel. Individual evaluations are computable locally, i.e., independently of the previously proposed candidates. They may use static parameters, such as the input event log, however. Typical for this type are log-fitness evaluations (based on place fitness from Definition˜5) and generally place-local heuristics. Relative evaluations on the other hand explicitly consider a candidate place together with an intermediate result (set of places). This allows testing model-level/global properties, such as deadlock-freedom of the resulting Petri net or place implicitness. These functions tend to be more expensive to compute due to being defined on the (place) set level, as they may scale super-linearly or even exponentially in the number of elements. 3.3 Concrete Evaluations In the following, we present two types of concrete evaluations used in our instantiation of the framework: place fitness and place implicitness. Place Fitness Recall the definition of □σ(p) _σ(p) on individual places and place sets (Definition˜5). If we want the resulting set of places to be fitting for the entire input log, we can translate that into the constraint that every individual place needs to be fitting for the entire log. Closely related to the tree structure we gave before is the notion of under- and overfedness extensively discussed by van der Aalst in [35]. Definition 15 (Under- & Overfedness). Let p∈ℙp be a place and σ∈σ a behavior. We call p overfed (underfed) on σ if and only if △σ(p) _σ(p) (or △σ(p) sideways sideways $ $ sideways sideways_σ(p), respectively), with △σ(p) _σ(p) :⇔¬balanced(σ,p) : \,balanced(σ,p) △σ(p) sideways sideways $ $ sideways sideways_σ(p) :⇔¬non-neg(σ,p) : \,non-neg(σ,p) Note that these properties are not mutually exclusive. They are also not entirely symmetric. Overfedness corresponds to a non-empty marking at the end of token-based replay, i.e., an excess of token production, and underfedness corresponds to a negative marking during token-based replay, i.e., a deficiency in token production. The relation to fitness □σ(p) _σ(p) is trivially □σ(p)⇔¬△σ(p)∧¬△σ(p) _σ(p) _σ(p) sideways sideways $ $ sideways sideways_σ(p). For place evaluation, we are interested in the event log-level. Luckily, behavior-level properties can be lifted to multisets of behaviors via aggregation by counting. Definition 16 (Multiset-level Lifting). For a non-empty event log []≠L∈ℬ()[\,]≠ L (B), a place p∈ℙp and a behavior-level property R:×ℙ→True,FalseR:B×P→\True,False\ on places and behaviors we can count the fraction of behaviors it holds on as follows. #L,pR=|[σ∈L∣R(σ,p)=True]||L|\#^R_L,p= |[σ∈ L R(σ,p)=True]||L| This also lifts behavior-level monotonicity to the log-level. Theorem 2 (Lifted Monotonicity). Let []≠L∈ℬ()[\,]≠ L (B) be a non-empty event log, p∈ℙp be a place, and R:×ℙ→True,FalseR:B×P→\True,False\ be a behavior-level property. For any p′∈ℙp where R(σ,p)⟹R(σ,p′)R(σ,p) R(σ,p ) holds for all σ∈Lσ∈ L, the following holds. #L,pR≤#L,p′R\#^R_L,p≤\#^R_L,p Proof. Every behavior counted in the denominator of the left hand side of the inequality is also counted on the right, as R(σ,p)⟹R(σ,p′)R(σ,p) R(σ,p ) for all σ∈Lσ∈ L. ∎ In other words, if a behavior-level property R is monotonic with respect to some ordering on places, e.g., the child generation function of our candidate tree, the fractions will also be monotonic. This will be the basis of our constraint generation which we introduce in Section˜3.4.1. We define a fitness evaluator that counts the fractions of fitting, underfed, and overfed behaviors. □,△,△:ℙ ^ind_ , sideways sideways $ $ sideways sideways, :P →[0,1]×[0,1]×[0,1] →[0,1]×[0,1]×[0,1] p p ↦(#L,p□,#L,p△,#L,p△) (\# _L,p,\,\# sideways sideways $ $ sideways sideways_L,p,\,\# _L,p) Place Implicitness The implicitness evaluation checks whether a place is redundant, i.e., does not change the fitting behavior of an intermediate result. An additional place can of course at most reduce the fitting behavior, and never increase it. Adding an implicit place to the solution set would just increase the complexity of the resulting model, so it is beneficial to filter it out. The corresponding evaluator can look as follows. global implicitness:ℙ×(ℙ) ^rel_global implicitness:P×P(P) →True,False →\True,False\ (p,S) (p,S) ↦(S)=(p∪S) (S)=fit(\p\∪ S) This property can be computed via linear programming based on Petri net theory [9]. However, this is relatively expensive. Given a fixed set of behaviors B⊆B , e.g., those occurring within an input event log, we can check the implicitness somewhat heuristically by only considering whether p is redundant on this sample of all possible behavior: replay implicitness:ℙ×(ℙ) ^rel_replay implicitness:P×P(P) →True,False →\True,False\ (p,S) (p,S) ↦(S)∩B=(p∪S)∩B (S)∩ B=fit(\p\∪ S)∩ B This implicit place filtering also has huge computational advantages as it restricts the solution set space, i.e., all combinations of possible places, dramatically and keeps the intermediate result small, thus speeding up all relative evaluations. Mannel et al. introduced this technique as “replay-based implicit place removal”. For more details, refer to [17]. To facilitate efficient application of a suite of evaluators, it is up to the composing side to dynamically call them as needed. This allows for short-circuiting of composition logic, e.g., discarding a candidate place after it does not meet a particular threshold on a cheap-to-calculate heuristic. The following section introduces the generalized composition logic, and our greedy instantiation. 3.4 Composition The handling of proposed candidates and the constraining strategy, i.e., the system by which to generate constraints, is implemented on the composing side. Constraints usually derive from desired properties of the possible solution sets and are discovered by evaluation of candidate places. In general, our framework is intended to support arbitrary composition strategies that internally update a state, making use of the aforementioned evaluations. In particular, we see a lot of opportunities in mirroring the efficient candidate traversal of the proposal side. We give the general structure in Algorithm˜3. The procedure compose is called after propose yields a place. The candidate place is incorporated into an internal state by update-state, then, if possible, candidate constraints are generated. Only after calling get-result is the state collapsed to a concrete resulting set of places. However, with existing approaches, we are limited to greedy or at most relaxed greedy approaches to curb the huge exponential blowup of candidate combinations. Essentially, the composition routine turns into an online algorithm that has to make local decisions and trust the candidate generation process with a “good” ordering of candidates. Algorithm˜4 shows this simplified interface implementation. Instead of an arbitrary state, we directly manage a result set. The core strategy, in addition to generate-constraints as before, now lies in deliberate-acceptance which determines the manner in which the evaluated candidate is incorporated into the intermediate result. In the following, we describe the quintessential constraint generation strategy that fits nicely into this online setting. Secondly, we give an overview of composition state updating. Algorithm 3 general composing 1:current state S∈SPS∈ SP, with state-space SPSP 2:individual evaluators (k)k∈N(eval^ind_k)_k∈ N^ind, N=n¯N^ind= n^ind 3:relative evaluators (k)k∈N(eval^rel_k)_k∈ N^rel, N=n¯N^rel= n^rel 4:subroutine evaluate 5:subroutine update-state 6:subroutine generate-constraints 7:subroutine generate-result: SP→(ℙ)SP (P) 8:procedure compose(p) 9: ←evaluate(p,(ek)k∈N,(ek)k∈Np)evs← evaluate(p,\,(e^ind_k)_k∈ N^ind,\,(e^rel_k)_k∈ N^relp) 10: update-state(p,)(p,evs) 11: C←generate-constraints(p,)C← generate-constraints(p,evs) 12: yield constraints C 13:end procedure 14:procedure get-result 15: return generate-result(S)(S) 16:end procedure Algorithm 4 greedy composing 1:set of previously accepted places I⊆ℙI 2:subroutine deliberate-acceptance 3:procedure evaluate(p,(k)k∈N,(k)k∈Np,\,(eval^ind_k)_k∈ N^ind,\,(eval^rel_k)_k∈ N^rel) 4: for k∈Nk∈ N^ind do 5: ek←k(p)e^ind_k ^ind_k(p) 6: end for 7: for k∈Nk∈ N^rel do 8: ek←k(p,I)e^rel_k ^rel_k(p,I) 9: end for 10: return (ek)k∈N,(ek)k∈N)(e^ind_k)_k∈ N^ind,\,(e^rel_k)_k∈ N^rel) 11:end procedure 12:procedure update-state(p,p,evs) 13: ←deliberate-acceptance(p,)decision← deliberate-acceptance(p,evs) 14: if =Acceptdecision=Accept then 15: I←I∪pI← I∪\p\ 16: else if =ReplaceExisting(p^)decision=ReplaceExisting( p) then 17: I←I∖p^∪pI← I \ p\∪\p\ 18: else if =Rejectdecision=Reject then 19: I←I← I 20: end if 21:end procedure 22:procedure generate-result(I) 23: return I 24:end procedure 3.4.1 Concrete Constraint Generation As we have already mentioned in the proposal and evaluation sections, simple fitness constraints drive the constraint generation. The final connection to make from the previously introduced under/overfedness notions is to the preset and postset expansions used in our child generation logic g, which we fix for the following considerations. We first state the central theorem which expresses how these fitness notions align to our tree structure. Theorem 3 (Under/Overfedness Monotonicity). Let p,p′∈ℙp,p be places such that p′p is a postset expansion of p, i.e., ∙p=∙p′ p= p and p∙⊂p′∙p ⊂ p . For any behavior σ∈σ , it holds that △σ(p)⟹△σ(p′) sideways sideways $ $ sideways sideways_σ(p) sideways sideways $ $ sideways sideways_σ(p ). This is analogous for △ and preset expansions. In words, if p is underfed (overfed) on σ, any postset (preset) expansion of p is also underfed (overfed) on σ. Intuitively, a place that is underfed can only become more underfed by adding token consumers. As a concrete example, consider behavior σ=⟨▶,b,■⟩σ= ,b, and place p=(a,b)p=(\a\,\b\). p is underfed on σ and any postset expansion of p, e.g., (a,b,c)(\a\,\b,c\), must also be underfed on σ. To be able to generate subtree-monotonic constraints from this, they have to be consistent on all places in the subtree rooted at some place p, i.e., the entirety of g(p)cand_g(p). Lemma 1 (Underfedness Subtree-Monotonicity). Let p∈ℙp with |∙p|+|p∙|≥2| p|+|p |≥ 2 be a place of depth at least two and p′∈+(p)p ^+(p) be a direct postset expansion of it. For any σ∈σ , it holds that: △σ(p)⟹∀p^∈g(p′):△σ(p^) sideways sideways $ $ sideways sideways_σ(p) ∀ p _g(p ): sideways sideways $ $ sideways sideways_σ( p) Proof. To see this, recall the case distinction in our definition of g. If p′p is a postset expansion of p with depth at least two and thus |p∙|≥1|p |≥ 1, we have |p′∙|>1|p |>1. Which implies that there are no preset expansions in g(p′)cand_g(p ) as we never shrink places. Formally, ∀p^∈g(p′):∙p=∙p′=∙p^∧p∙⊂p′∙⊆p^∙∀ p _g(p ): p= p = p p ⊂ p p . As all places in g(p′)cand_g(p ) are postset expansions of p′p , Theorem˜3 directly implies the claim. ∎ Due to our design decision to prefer postset expansions in our definition of g, the overfedness subtree-monotonicity is a lot more restricted. Lemma 2 (Overfedness Subtree-Monotonicity). Let p∈ℙp be a place with +(p)=∅post^+(p)= and p′∈+(p)p ^+(p) be a direct preset expansion of it. For any σ∈σ , it holds that: △σ(p)⟹∀p^∈g(p′):△σ(p^) _σ(p) ∀ p _g(p ): _σ( p) Proof. A place p with non-expandable postset, i.e., +(p)=∅post^+(p)= , can only have preset expansions in its subtree. The claim then follows directly from Theorem˜3. ∎ Note that the only places p in an unconstrained tree that have a non-expandable postset but still have preset children to prune are those with p∙=xp =\x\ where x∈Apostx∈ A_post is the maximal element of ApostA_post, i.e., ∀a∈Apost∖x:a<postx∀ a∈ A_post \x\:a<_postx. We showed that these behavior-level properties △ and △ satisfy the desired monotonicity. Using Theorem˜2, we can thus conclude the following property of the counted fractions. Lemma 3 (Lifted Under/Overfedness Monotonicity). Let []≠L∈ℬ()[\,]≠ L (B) be a non-empty event log and p∈ℙp be a place of depth at least 2. For all places in the candidate sets of its postset expansions, i.e., ⋃p′∈+(p)g(p′) _p ^+(p)cand_g(p ), it holds that: #L,p△≤#L,p′△\# sideways sideways $ $ sideways sideways_L,p≤\# sideways sideways $ $ sideways sideways_L,p This is analogous for △ and preset expansions. Proof. Use Theorem˜2 with the △ as the behavior-level property, which is monotonic for the considered places according to Lemma˜1. ∎ We can now use the log-level lifting of the place fitness evaluator □,△,△eval^ind_ , sideways sideways $ $ sideways sideways, to filter places and generate constraints. Specifically, we use thresholds to convert the fractions back again into truth values. It is clear to see that □L(p)⇔#L,p□=1 _L(p) \# _L,p=1. Additionally, we have the following relation to over- and underfedness: #L,p□≤1−#L,p△\# _L,p≤ 1-\# sideways sideways $ $ sideways sideways_L,p and #L,p□≤1−#L,p△\# _L,p≤ 1-\# _L,p. That is, if a place should fit a certain fraction τ∈[0,1]τ∈[0,1] of behavior in a log, it can be underfed (and overfed) on at most (1−τ)⋅100%(1-τ)· 100\% of the traces. Given a threshold τ∈[0,1]τ∈[0,1] and an evaluation result (#L,p□,#L,p△,#L,p△)(\# _L,p,\# sideways sideways $ $ sideways sideways_L,p,\# _L,p) of a place p on log L, we can then generate the following constraints in generate-constraint. If #L,p△>1−τ∧|∙p|+|p∙|≥2\# sideways sideways $ $ sideways sideways_L,p>1-τ | p|+|p |≥ 2 holds, return constraint prune-postset-subtreep(p^):⇔p^∉⋃p′∈+(p)g(p′)prune-postset-subtree_p( p): p∉ _p ^+(p)cand_g(p ) Otherwise, if #L,p△>1−τ∧+(p)=∅\# _L,p>1-τ ^+(p)= holds, return constraint prune-preset-subtreep(p^):⇔p^∉⋃p′∈+(p)g(p′)prune-preset-subtree_p( p): p∉ _p ^+(p)cand_g(p ) These constraints might seem expensive to check, however, due to our choice of g, they only affect the subtrees of p, i.e., they are local. Thus, they can trivially be represented such that g(p)↾prune-postset-subtree=g(p)∖+(p)g(p) _I_prune-postset-subtree=g(p) ^+(p), or respectively g(p)↾prune-preset-subtree=g(p)∖+(p)g(p) _I_prune-preset-subtree=g(p) ^+(p), takes no additional checks by simply marking these children as already visited in the tree state via ν. To visualize this, consider the candidate subtree presented in Figure˜5 and event log L=[⟨▶,a,b,■⟩4,⟨▶,a,a,■⟩6]L=[ ,a,b, ^4, ,a,a, ^6]. Assume the root place r=(▶,a)r=(\ \,\a\) is being proposed. On behavior ⟨▶,a,b,■⟩ ,a,b, , r is fitting, not underfed, and not overfed, and on ⟨▶,a,a,■⟩ ,a,a, , it is not fitting, underfed, and not overfed. Thus, #L,r□=0.4\# _L,r=0.4, #L,r△=0.6\# sideways sideways $ $ sideways sideways_L,r=0.6 and #L,r△=0\# _L,r=0. Given the threshold τ=0.5τ=0.5, we can discard r, as no Petri net that contains r could replay more than 40% of L. Furthermore, we can generate the constraint prune-postset-subtreer(p^):⇔p^∉⋃p′∈+(r)g(p′)prune-postset-subtree_r( p): p∉ _p ^+(r)cand_g(p ). That means, we can prune all the descendants of r that are connected purely along blue edges (postset expansions). In this case (▶,a,b)(\ \,\a,b\), (▶,a,c)(\ \,\a,c\), (▶,a,■)(\ \,\a, \) and their children (left side of the tree). We can easily verify that none of the affected places p could ever have an underfed fraction smaller than 0.6, i.e., we know #L,p△≥0.6\# sideways sideways $ $ sideways sideways_L,p≥ 0.6 and thus #L,p□≤1−#L,p△≤0.4\# _L,p≤ 1-\# sideways sideways $ $ sideways sideways_L,p≤ 0.4. At the same time, we can see that places that are descended via a red edge (preset expansion), e.g., p′=(▶,a,a,■)p =(\ ,a\,\a, \) cannot easily be pruned. Both behaviors of L fit on p′p . We expect that many desirable final model properties can be encoded into similar evaluations to keep intermediate results invariant regarding that property. Another example are uniwired Petri nets [20]. Two activities a,a′∈a,a are wired by a place p∈ℙp if and only if a∈∙p∧a′∈p∙a∈ p a ∈ p . Uniwired Petri nets have the property that for any two activities, they contain at most one place that wires them. This can easily be translated into a subtree-monotonic constraint. Specifically, if we accept a candidate p into our intermediate solution, we can generate the constraint not-biwiringp(p^):⇔(∙p^∩∙p)=∅∨(p^∙∩p∙)=∅not-biwiring_p( p): ( p∩ p)= ( p ∩ p )= . Note that this constraint is not as “pretty” (local) as the fitness-derived constraints, as it can exclude previously proposed candidates and is highly sensitive to ordering. However, it is very strong, i.e., it shrinks the candidate space dramatically, because it touches multiple disjoint subtrees. 3.4.2 Concrete Composition State Update In the following, we briefly discuss what can be done in the update-state procedure of Algorithm˜3. As mentioned earlier, the general version is very expressive with its arbitrary state but not yet fully utilized by existing instantiations. Currently, as we rely on existing eST-Miner variants, we are closer to the greedy simplification given in Algorithm˜4. We want to note here that some variants [20, 21] are actually what we would call relaxed greedy as they have the ability to postpone this acceptance decision and collect postponed candidates in a heuristically-ordered priority queue. We refer the interested reader to the primary literature. Greedy composition relies heavily on place-local evaluations. However, there is, of course, a gap between place-local evaluations and model-level properties. For example, while the place fitness evaluation □,△,△eval^ind_ , sideways sideways $ $ sideways sideways, can successfully be used for filtering candidates and generating constraints, it is not sufficiently strong to guarantee fitness of the set of all accepted places in the case of τ<1τ<1. Naive application could easily produce even a deadlocked model, if only disjoint partitions of the log behavior are fitting on the constituent places. Refer to [21] by Mannel et al. and the therein introduced “Delta Variant”. Furthermore, evaluation relative to the intermediate result is useful for ensuring invariants or final properties of result sets. One such invariant is the absence of implicit places described before in Section˜3.3. Assuming an evaluation oracle, e.g., global implicitness:ℙ×(ℙ)→True,Falseeval^rel_global implicitness:P×P(P)→\True,False\, it is trivially incorporated into the framework. In our implementation, we provide an LP (linear program)-based and replay-based evaluator for global implicitnesseval^rel_global implicitness and replay implicitnesseval^rel_replay implicitness respectively. When this entire proposal, evaluation, and composition cycle terminates, either due to candidate exhaustion or otherwise signaled by time limit or surpassed quality threshold, we initiate one round of post-processing. Within this algorithmic framework, and particularly greedy composition, there are some areas where unwanted local structures can build up such that a “cleanup” step becomes integral to the overall discovery quality. 3.5 Post-Processing We make post-processing a first class member of this discovery framework to provide an opportunity for fixing quirks that can come up in bottom-up discovery. Basically, allowing a last global look over after being stuck in local decision-making for efficiency. In particular, we intend for this step to be pipelined with sequential execution of reusable transformations. From thorough structural implicit place removal after, e.g., a heuristic application during PEC-cycling, to place merging for increasing simplicity when the tree traversal depth is limited. As we allow graceful premature cancellation of the PEC-cycling stage, it can also be used to fix artifacts that occur when not all possible places have been directly or indirectly considered. The aforementioned place merging is an example of that. Lastly, some technical aspects like model conversion can now be easily incorporated. Generally, any model repair strategy and particularly, existing implementation of it, could be applied here. This way, existing work can be easily reused and combined, which is one of the major goals of our framework implementation that we present in the next section. 4 Implementation In this section, we introduce our extensive implementation of the conceptual framework. The full development repository is available on GitHub222https://github.com/leah-tgu/specpp. Additionally, we have published a bundled plugin with an interactive GUI frontend in the package SPECpp on the ProM nightly build333https://w.promtools.org/doku.php?id=nightly. This frontend is also included in the GitHub repository. A basic overview of the components is shown in Figure˜6. The software components largely correspond to the elements we described in the previous section. On the proposal (left) side, we have the Proposer which uses the Candidate Tree. The tree is made up of its Expansion Strategy, and the crucial Child Generation Logic which is responsible for efficiently incorporating constraints. Proposed candidates are handed over to the Composer component that internally manages a Composition which stands in for the internal state that is updated using the Individual and Relative Evaluators. The composer may generate constraints for the proposer in response to a candidate. Figure 6: An overview of the main PEC components, their dependencies and their main responsibility. They mimic the conceptual structure with the addition of Supervision. Additionally, there is the more framework implementation relevant supervision, shared global data storage and component communication linking service. Particularly the Supervision system is of note here. In this setting, where heuristic ordering, greedy decision making, constraints and unforeseen combinations of the former are abound, we consider it a first-class requirement to be able to inspect in some manner how a particular result came together. The internal execution, data and communication flow is so dynamic that in order to know what happened during execution, it is of great benefit to allow developers to define custom descriptive events in their algorithm variants. These are asynchronously collected and handled flexibly in the supervision system. Arbitrary supervisors can be implemented to inspect the behavior even at runtime. For example, this system is used for a live discovery view in the interactive ProM plugin. More basic usage would be logging to a log file and/or the console. Particularly important for evaluating new proposal, evaluation or composition strategies is also a view on performance. It is detailed to individual executions for future uses, however, even the aggregated average per task timing and occurrence frequency are massively useful in finding bottlenecks. Supervision, as well as the other mentioned framework facilities, are realized by a requirement management system that permits dynamic at-runtime provisioning and requesting of data and functions across components. As we developed this software framework with the intention to support a high degree of flexibility, interfaces are very minimal and general. To make up for this, we provide the aforementioned systems to ease coordination and monitoring. Furthermore, the software framework facilitates quick prototyping through reuse via its focus on interoperability of different variants/implementations. Ideally, new implementations are split into separable components such that parts of these approaches can be reused and combined. 4.1 Available Component Instantiations We fitted our framework implementation with some base components for the instantiations we described in Section˜3. It explicitly supports heuristic expansion strategies, including the scoring metrics introduced in [18]. Basic depth-first, which is most memory efficient, and breadth-first expansion are available as well. The aforementioned paper also introduces activity ordering strategies for computing <pre<_pre and <post<_post using metrics derived from the input log. We include these as well as lexicographic and random orderings. Our child generation logic implementation supports the crucial preset/postset expansion cutoff constraints, depth limiting, wiring constraints and transition blacklisting. In contrast to our conceptual framework, we can permit non subtree-monotonic constraints at the cost of incomplete traversal. This occurs for example when we allow wiring constraints to be deleted after the wiring place is retroactively removed from the intermediate result set. Another avenue that is technically possible, is restarting the candidate tree traversal with the current constraints to get closer to completeness in these cases. On the side of composers, we included the pattern of recursion/nesting. After applying their own decision making logic, recursive composers delegate the candidate handling to a child component. This allows reuse of “partial” composition strategies like fitness filtering. The main implemented strategies are the aforementioned fitness filtering corresponding to the base eST-Miner (refer to [19]), a uniwired composer as introduced in [20], the delta composer from [21] and an implementation for concurrent implicit place removal from [17] supporting both the replay-based version as well as the linear-programming based structural version. Similarly, this nesting is supported for compositions to allow an outer composition to internally manage other compositions. For evaluators, there is a standard and a parallelized version of token-based replay fitness which supports computation on log-subsets. Additionally, there is a facility for computing place token counts over traces which is used in replay-based implicit place removal. Implicit place checkers (both kinds) are also available as relative evaluators. There are two ways to access the framework. For one, there is the headless package (i.e., not depending on ProM) in the repository. It contains main classes for command line access to simple “event log in – Petri net out” execution, experimentation execution with lots of output and logging, and a command line interface for batch execution of freely configurable parameter variations. The latter also contains documentation and a usage guide for file-based component configuration. The other way to access at least a part of the capabilities of the framework is the ProM plugin. 4.2 The ProM Plugin The accompanying ProM plugin is layered on top of the framework implementation itself. It serves the purpose of providing a visual and interactive interface to advanced process mining users who merely want to access already implemented variants. Moreover, the ProM infrastructure enables combining this approach with more than 1500 other plugins. Due to the extensive configuration options and their importance, it may not be very accessible to people not familiar with the research behind it. Even though we do provide presets, some deeper understanding is required for a proper interpretation of the results. The plugin and the ProM platform in general are not really geared towards “true process mining end users”. In the following, we go into detail about its usage. After selecting an event log input and calling the Interactive SPECpp plugin, the user is presented with an interactive GUI that sequentially guides them through configuration and execution of the underlying SPECpp discovery. The procedure is divided into the stages Pre-Processing, Configuration, Discovery and Results. Dynamic indicator buttons on the top row indicate the current, as well as currently enabled, stages. The active stage is marked in pink and its label is underlined. Accessible stages are marked in blue, whereas inaccessible ones are greyed out. This is exemplified in Figure˜7. The user is in the discovery stage and can at any time go back to pre-processing and configuration but cannot skip ahead to the results because the computation is still running. Selecting a previous (to the left of the current stage) stage, resets the internal progress to that stage. For the stages concerning configuration, the last executed configuration is restored. This enables fast experimentation with parameters and settings. Pre-Processing This stage gives an opportunity to preview the loaded data after applying an event classifier and an activity ordering strategy. It is further possible to select only a subset of activities to consider for place presets or postsets respectively. Configuration This view has a dynamic list of options categorized into each of the framework’s major components, as well as a section for parameterization. The first section offers presets for the eST-Miner variants proposed by Mannel et al. [19, 20, 21]. Additionally, supervision can be turned off (or reduced) for increased performance if no insight into the execution specifics is required. Generally, only a simplified, manually designed component implementation selection is possible via this interface, however, the post-processing remains as generic as the underlying framework itself. The reason for this abstraction is usability. The full feature set is accessible to developers via code-based and .json file-based configuration. We recommend interested researchers to preferably check out the GitHub page. Discovery The discovery view presented in Figure˜7 is constantly asynchronously updated while the PEC-cycling is performed. The left panel displays the currently accepted places either as a list or graph. The user can select the update frequency. For a high number of places, graph layouting becomes useless (and slow), so it is disabled. The right hand side is separated into four sections which are also all continuously updated. From top to bottom, there are sub panels for the search space, execution progress, performance, and monitored events. Figure 7: The discovery view of the ProM plugin. The left split shows the currently accepted places in a list view. A graph visualization is available as well. The right side provides real-time information about the computation regarding candidate space traversal, performance, and events. The search space panel gives an overview of the maximum number of candidate places, as well as the as-of-now computed fraction of those. The indicator of the last candidate’s tree depth can additionally give a hint towards the remaining processing time. The elapsed time for the main PEC-cycling (place discovery) and final post-processing computation is displayed on the execution progress panel. If time limits were configured, they are shown as well. There is additionally the option to manually cancel the computation at any time. Cancellation of the first stage is graceful, i.e., the current intermediate result can be used for further post-processing. When both steps terminate successfully, the “continue to result” button is enabled. The performance panel consists of a table that summarizes all currently observed (via the supervision system) performance events. The columns are selected summary statistics such as mean, min, max and frequency. Any developer-defined custom events are caught here as well. So, for example a newly implemented heuristic’s performance can be instrumented as well. Similar to the performance table, the event table lists all currently observed descriptive events generated by the components and their frequencies. This helps with understanding how often certain paths are taken in proposal or composition decisions, e.g., how many underfed places are detected or how many implicit places were rejected. Any custom developer-defined events can be displayed here. If supervision was disabled or reduced, the corresponding tables remain empty. Results The final resulting Petri net, as well as potentially visualizable intermediate post-processing results are displayed. Fitness for the entire model, as well as individual places in the initially resulting place set can be displayed. Additionally, overall alignment-based fitness and ETC precision are calculated. From the export panel, the user can export the final resulting Petri net and used algorithm configuration. 5 Evaluation To evaluate our approach, we performed automated experiments on synthetic as well as real-life event logs. The intent is to demonstrate the capabilities of the basic instantiations of conceptual components to achieve acceptable results on popular evaluation datasets. Furthermore, we highlight features of our implementation. We use the synthetic Repair, Reviewing and Teleclaims event logs from [34], and real-life logs HospitalBilling444https://doi.org/10.1007/978-3-319-59536-8_34, Sepsis [23] and Road Traffic Fine Management (RTFM) [7]. As well as some past BPI challenge logs of 2012555https://doi.org/10.4121/uuid:3926db30-f712-4394-aebc-75976070e91f and the Domestic Declarations (DomDecl) log from the challenge’s 2020666https://doi.org/10.4121/uuid:52fb97d4-4588-43c9-9d04-3604d4613b51 rendition. This selection of evaluation targets is diverse in its structure and represents staples in this discipline. Table˜1 gives an overview. A high number of variants slows down fitness evaluation but most importantly, the number of occurring activities determines the number of possible candidate places. We can already see that BPIC12 presents an almost adversarial input. We applied the batch execution feature of our implementation to perform discovery over a range of parameterizations. Table 1: The event logs used for our evaluation. The real-life event logs contain considerable variation. 80% of traces in the Sepsis event log are unique. Whereas our artificial logs are quite small, the RTFM log contains over half a million events. Also, the BPI challenge logs sport a high number of activities. Event Log #Traces #Variants #Activities #Events Teleclaims 3,512 12 11 24,825 Repair 1,104 77 8 11,855 Reviewing 100 96 14 2,278 HospitalBilling 100,000 1,020 18 451,359 Sepsis 1,050 846 16 15,214 RTFM 150,370 231 11 561,470 BPIC12 13,087 4,366 24 262,200 BPIC20.DomDecl 10,500 99 17 56,437 For the component configuration, we chose the AverageFirstOccurrenceIndex activity ordering from [18], the therein defined eventually-follows interest score for heuristic tree traversal and τ-thresholding composition with concurrent implicit place removal from [17]. As post-processing, we selected LP-based implicit place removal from [19] and Self-loop place merging. These transformations merely simplify the model and do not change its supported behavior. Due to the not fully characterized nature of replay-based implicitness checking from [17] in the τ<1τ<1 regime (i.e., log and model not exhibiting the same language), we forego using it as a pre-filtering step before the thorough LP-based version. This would be very beneficial for performance but as we discovered, it does not consistently underestimate implicitness. This selection of components is one of the simplest and nicely showcases the use-case of plugging together methods that were originally proposed in separate works. The parameters were varied according to Table˜2. The actual files, code and results are available on the project’s GitHub page777https://github.com/leah-tgu/specpp/releases/tag/paper_eval. τ is the threshold for the fraction of fitting traces as an acceptance criterion (#L,p□\# _L,p), as well as constraint generation in case the place is under/overfed on more than (1−τ)⋅100%(1-τ)· 100\% of traces (as introduced in Section˜3.4.1). The tree depth limit almost determines runtime by severely limiting the exponential activity combinations. As the replay-based implicit place removal comes with no formal guarantees for most of our parameterizations as mentioned above, it turns into a mere heuristic. So, we test both versions RegionBased (replay_implicitnesseval^rel_replay\_implicitness) and LPBased (global_implicitnesseval^rel_global\_implicitness) as our relative implicitness oracle during composition. We want to emphasize that limiting the tree depth to these low values compared to the full depth of 2⋅#2·\#Activities is a reasonable choice as places with more than, e.g., six arcs connected to them, are detrimental to visual simplicity. The place depth acts as a very natural low-level complexity measure. Additionally, restricting control-flow dependencies to such few arcs is still very powerful. Few manually designed models will connect more than six activities to a place. Table 2: The varied parameters and their ranges. They were varied independently over their entire ranges resulting in 6⋅5⋅2=606· 5· 2=60 combinations. The exact configuration files and code are available on the project’s GitHub page. Decreasing τ and increasing the max tree depth increases the number of possible fitting places in the search space. Parameter Range τ 1.0,0.9,0.8,0.7,0.6,0.5\1.0,0.9,0.8,0.7,0.6,0.5\ max tree depth 2,3,4,5,6\2,3,4,5,6\ implicitness calculator RegionBased, LPBased\RegionBased, LPBased\ We limited the execution time to 10 minutes for PEC-cycling, after which we gracefully stopped the loop and initiated post-processing which was also limited to 10 minutes before the computation was canceled. The LP-based post-processing in its current naive implementation has to solve quadratically many quadratically sized LPs (in the number of collected places), so if it does not terminate timely, it is a good indication that the resulting model would contain hundreds (or thousands in some cases) of places, making it thoroughly impractical to use and evaluate. Table˜3 gives some summary statistics on the recorded runtimes. Note that timeouts are not sharp because they rely on cooperative termination, thus the recorded execution times can exceed the set limits slightly. PEC timeouts are not that problematic as they are soft/graceful cancellations, i.e., the result is still being used. The total timeouts, i.e., those where a hard cancellation occurred, are more common among the bigger real-life logs. Particularly logs with high numbers of unique activities are problematic. Table˜4 illustrates that for executions that did not finish (DNF), the number of collected places in the intermediate result, i.e., those meeting the τ threshold which were not identified as implicit to the rest, is indeed immense. It is not a loss to not consider such models. Rather, this points out the need for more sophisticated filters and candidate acceptance rules which are already being investigated by Mannel et al. A recent result is [10]. Table 3: Summary of the algorithm runtimes over all 60 attempted parameterizations. BPIC20 executions often ran into the hard-cancellation timeout due to the high number of fitting places. Event Log Timeouts PEC-cycling [s] Post-Processing [s] Total [s] PEC Total 10%-pcrtl avg 90%-pcrtl std 10%-pcrtl avg 90%-pcrtl std avg Teleclaims 0.0% 3.3% 0.02 14.30 28.98 48.71 0.01 28.52 4.68 118.13 42.82 Repair 0.0% 0.0% 0.02 1.13 2.35 2.56 0.00 1.28 0.55 8.08 2.41 Reviewing 0.0% 1.7% 0.14 9.31 28.16 16.67 0.00 10.68 1.58 77.40 19.99 HospitalBilling 33.3% 25.0% 1.79 293.34 600.04 269.42 0.15 181.76 600.00 255.08 475.09 Sepsis 11.7% 18.3% 1.64 174.38 600.01 215.16 0.08 129.61 600.00 228.42 303.99 RTFM 0.0% 15.0% 0.19 15.89 55.73 31.48 0.05 103.82 600.00 215.49 119.71 BPIC12 56.7% 18.3% 17.85 407.49 600.71 244.93 0.16 202.00 600.00 245.41 609.49 BPIC20.DomDecl 31.7% 25.0% 0.81 253.26 600.15 265.78 0.94 179.29 600.00 219.73 432.55 Table 4: Overview of the median number of collected places in the intermediate and final results. The intermediate result size for canceled runs (DNF) where post-processing timed out reveal that in these cases, basic τ-filtering and implicitness checking are simply not sufficient to handle the noise and complexity. Event Log #Collected Places (median) #Collected Places (DNF) (median) #Places after Post-Processing (median) Teleclaims 43 1247 14 Repair 22 - 10 Reviewing 36 675 13 HospitalBilling 111 4072 27 Sepsis 60 2437 16 RTFM 45 2710 14 BPIC12 99 907 26 BPIC20.DomDecl 95 6826 24 Further, we appended an automatic evaluation of alignment-based fitness and ETC precision [5]. We also computed their harmonic mean, the F1-score. As alignment computation on huge models with low fitness can take prohibitively long, we also limited the execution time to 10 minutes for that task. Similar to the post-processing above, an exceeded timeout is a good indication for an undesirable model—either due to its complexity or inadequate fitness. Consider Figure˜8, Figure˜9 and Figure˜10 that show the trade-offs between the metrics fitness, precision, and number of places (stand-in for complexity, so lower is better) for the models with a top 25% F1-score. We see that acceptable fitness and precision are achievable on any input log. However, we immediately notice that on the complex and noisy real-life logs, these scores come at the cost of large models. We rediscover the above finding that for these inputs, many feasible non-implicit places are found. This is also a consequence of the exponential increase in possible activity combinations with higher numbers of activities, which these logs tend to contain. For example, we should expect a log with 24 possible activities to require more places to constrain its model’s behavior than for 8. Figure 8: The distribution and Pareto front of fitness vs. precision of the best models (in terms of top 25% F1-score). Figure 9: The distribution and Pareto front of fitness vs. #places (lower is better) of the best models (in terms of top 25% F1-score). Figure 10: The distribution and Pareto front of precision vs. #places (lower is better) of the best models (in terms of top 25% F1-score). We want to emphasize that, naturally, a decrease in τ and increase in max tree depth lead to more feasible places and in turn longer running times. It is thus nice to see in Figure˜11 that the best scoring models can at least also be discovered in the faster runs. As we can see in Figure˜12, maximal fitness and also precision are usually reached even on low tree depths (and thus fast executions), which is in line with the previous observation. It also makes sense that, for higher precision, more constraining places are needed, while high fitness can be achieved with sufficient places to form a connected model. For example, on Teleclaims, the best results with an F1-score of 1 were achieved in, e.g., 0.5s (depth limit 3), 8.3s (depth limit 4) or 48.67s (depth limit 6). This phenomenon is mainly caused by the implicitness evaluation, as at some point, almost every new candidate is implicit to one in the intermediate result. This highlights the importance of incorporating model property invariants like implicitness-freedom into constraint generation. We point to [35] and the notion of redundancy as another possible monotonic pruning property. Making this ordering agnostic for formal guarantees is not trivial, however. A practical remedy would be the detection of intermediate model quality improvement stagnation in a future composition strategy. This is manually achievable in our ProM live discovery interface previously shown in Figure˜7. The graph or list visualization of the as-of-now accepted places makes it easy to see when they are not changing anymore. For example, when running the RTFM discovery interactively for τ=0.7τ=0.7, we can notice that the result stops changing after about three minutes, even if the full traversal (≈ 6mil evaluations) takes 47 minutes. Next, we turn our attention towards the effect of the τ and max tree depth parameterizations on the resulting model quality. Figure˜13 shows the Spearman rank correlation coefficient (it assesses how monotonic the relationship between two variables is) between these parameters and fitness/precision. To look at their effect independently, we computed these for each of these two separately while controlling for the other, i.e., computing the correlation per controlled group and averaging them. There exists an interesting inversion in the relationship between τ and fitness for the smaller synthetic logs and the larger more noisy logs. While an increased τ has a positive impact on the former, it has a negative on the latter. That means for the more simplistic inputs, a higher τ leads to higher fitness, while complex logs require more less-than-perfectly locally fitting places to achieve an overall fitting model. Precision always requires lowered τ values. Probably because there are too few high-fitness places to properly constrain the resulting model otherwise. For the maximum tree depth, an increase seems to always have a positive influence on fitness and precision, though to varying degrees. On the synthetic logs, it is mostly important for precision, while on the real-life logs, fitness really benefits from more candidate space exploration. Figure 11: The percentile rank of the fastest execution to reach a model scoring in the top 10% according to fitness/precision/F1-score. These fractions express that even the best models the algorithm can find for any parameterization are (also) discovered on the faster runs. It is clear to see that both in terms of fitness and precision, the best achievable results are consistently also achievable in the shortest possible time. As one might expect, to maximize them jointly (F1-score), more time is necessary. For example, on BPI20. DomDecl maximal fitness was reached by a run in the 6.7%-percentile of runtimes, while to achieve maximal F1-score, a run in the 24.4%-percentile was necessary. Figure 12: The average minimal max tree depth at which the model quality metrics are already maximized at. The average is over the different values of τ, as it has a big impact on the achievable metric. We see that, especially on the smaller synthetic logs, a high model fitness can be achieved with very low tree depth, thus saving running time. Precision appears to require more tree levels on average on these logs, and particularly to maximize both at the same time (F1-score), more candidate places are required. (a) The average spearman correlation efficient between τ and the fitness/precision of the resulting models controlled by max tree depth. (b) The average Spearman correlation efficient between max tree depth and the fitness/precision of the resulting models controlled by τ. Figure 13: The correlation between the varied parameters and model metrics. Lastly, we take a look at some of the concrete models we were able to discover during this evaluation. On the synthetic log Teleclaims, the model shown in Figure˜14 with a fitness of 0.91 and precision of 1 shows on the one hand the tendency to discover more complex models but also the ability to provide high precision. Long-term dependencies like determine likelihood of claim and initiate payment, which are usually not discovered by other popular approaches, do complicate the model but may also provide some new insights. As the model was discovered for τ=0.8τ=0.8, we have the guarantee that each constraint represented by a place is applicable to at least 80% of the observed behavior. On RTFM which is a log with varied behavior, three executions with τ=0.7τ=0.7, max tree depth ∈3,4,5∈\3,4,5\ and LPBased implicit place removal produced an interesting model that is shown in Figure˜15. It has an alignment-based fitness of 0.93, precision of 1 and perfectly fits 68% of the log. We also see some of the quirks of the used basic τ threshold, as the activity Appeal to Judge can never occur in a model trace due to its connected self-loop place. As that behavior apparently occurs in less than 70% of traces, the place passes the filter. This strictly-said dead part could rather be regarded as an approximation. Figure 14: One of the best models for Teleclaims, discovered for τ=0.8τ=0.8 and depths 4 and 5. It contains many long-term dependencies, e.g., between determine likelihood of claim and initiate payment. Its scores are 0.91 for fitness and 1 for precision. Figure 15: One of the best models for the RTFM log. It was discovered on three different runs with τ=0.7τ=0.7 in 1.8s (depth limit 3), 10.4s (depth limit 4) and 45.3s (depth limit 5). It has a fitness of 0.93, precision of 1 and perfectly fits 68% of the log. 6 Related Work As process discovery has provided a long-standing challenge in process mining [31, 25, 32], many different approaches have been proposed [34, 39, 1]. Historically, it is predated by the Petri net synthesis problem concerned with creating a Petri net that precisely covers a behavioral specification [3]. From this line of research stems a vast family of region-based approaches on languages by Carmona et al. [6], Werf et al. [40], van der Aalst et al. [30] and van Zelst et al. [43, 42]. They mostly use (mixed) Integer Linear Programming (ILP) on a specifically designed optimization problem where solutions correspond to Petri net places. These approaches are very similar to ours in their aim to directly synthesize places that fit the observed behavior, thus constructing a Petri net in a bottom-up manner. They also avoid introducing restrictive modeling/representation bias and can therefore model non-free choice constructs. Historically, they struggle with noise and scalability issues. In contrast to our proposed framework, noise is typically tackled by pre-filtering as a consequence of the “global” view on place fitness. Whereas we can adaptively evaluate each candidate place locally and in dependence of the existing intermediate solution. There is also genetic process discovery [29, 41, 27, 8] which similarly has performance issues and cannot provide any guarantees about the resulting model. Another early bottom-up work is the Alpha Miner by van der Aalst et al. in [33] which has seen many proposed variants [15, 45, 46, 38] which address noise handling and other limitations of the initial work. While the approach does synthesize individual places, and combines them into a full Petri net, the places themselves are derived based on extracted activity relations and not the full behavior of the log. Because of this, the approach effectively underlies stronger modeling bias as the patterns which are detectable in the activity relations are not perfectly expressive. Additionally, due to the simplicity of the algorithm—all places are discovered at once—places can also not be evaluated relative to each other, e.g., leading to deadlocked models. The very successful and popular Inductive Miner by Leemans et al. [11] and its variants [12, 13, 4] can almost be viewed as a prototypical top-down approach. Working with the directly-follows graph of the given log, the idea is to recursively divide and conquer (solve) the discovery on sub graphs, and then collecting the sub problem solutions in the emerging tree structure. Strong representational bias is introduced in this step as the formalism used, process trees, only captures block-structured Petri nets. Additionally, as the patterns for high-level structure by which to split into sub problems are manually defined, modeling bias is introduced as well. Apart from the inability to discover non-free choice constructs or long-term dependencies, these approaches tend to underfit, providing low precision models. However, an important advantage is their support of silent (tau) transitions. Building on the inductive miner framework, an algorithm that includes a bottom-up subroutine, precisely to address lacking precision, has also been proposed [14]. The so-called Indulpet Miner is also process tree based, so it inherits the same representational bias as mentioned above. The bottom-up recursion tries to identify fitting partial cuts, essentially checking whether certain activity relations between the partial cut partitions are satisfied. Petri net places are more expressive than such predefined patterns but there are of course fewer cut candidates. Still, the authors mention the very high cost of full log traversal and the exponential complexity incurred in this step. As these points are precisely what our framework tries to address, it may be worthwhile to investigate an application of this concept to that technique, using partial cuts as candidates instead of places. There are also discovery algorithms focusing on non-Petri net models. For one, there is the Split Miner proposed by Augusto et al. [2]. It directly discovers simple BPMN models (using OR, XOR and AND-gateways) which are equivalent to block-structured Petri nets. They thus purposely introduce the same representation bias as the above mentioned inductive miner to keep the resulting models easily interpretable. However, their discovery of the BPMN gateways (splits and joins) is global and not fundamentally limited by the division into independent sub problems. The heuristic miner by Weijters et al. [44] discovers causal nets (C-nets) for example. The algorithm can deal with noise and provides slider-based abstraction to generate simple models. However, C-nets do not posses imperative semantics like the otherwise popular Petri nets and are thus not directly comparable. Beyond our setting of case-centric event logs and control-flow models, bottom-up methods are also being investigated. For example, Agent System Mining [26], a technique that composes multi agent systems from individual agent models, has been proposed by Tour et al. To lift the traditional case-centric process notion to a multi-agent one, they propose to mine for sub models and infer their interaction patterns. Similar to the object-centric paradigm [37], a richer modeling formalism is required. One might consider such techniques to operate on a “higher level”, as in, their candidates are models instead of relatively atomic constructs such as Petri net places. Lastly, as amply mentioned, the works of Mannel et al. [19, 20, 17, 18, 21] on the so-called eST-Miner laid the groundwork for our approach. Our framework is a slight generalization of the former algorithms into this prototypical bottom-up setting. 7 Conclusions In this paper, we presented SPECpp, a framework for bottom-up Petri-net discovery that casts discovery as the problem of efficiently identifying promising candidate places and composing them into a high-quality model. We formalized this process as a Proposal–Evaluation–Composition (PEC) cycle followed by post-processing. A key advantage of bottom-up discovery is that it does not require the model to conform to a predefined block structure and can therefore discover complex constructs, including non-free-choice behavior and long-term dependencies. At the same time, the flexibility of the framework and implementation does facilitate encoding restrictive design choices, e.g., uniwiring, in a seamless manner. The advantage directly leads into its biggest weakness: exponential complexity and thus running time. To address the resulting exponential search space, we introduced a memory-efficient recursive representation of the candidate space that supports rigorous pruning using monotone constraints. This allows large sets of candidate places to be considered indirectly while only a fraction need to be evaluated explicitly. Specifically, we used the locally (individual place) testable property, fitness, and aligned its monotonicity to our constraint system. Complementary to pruning are the candidate ordering prioritization mechanisms like heuristics. On the side of candidate composition, we presented our general composition routine in which candidate places are evaluated and incorporated into an internal state, with the additional opportunity to generate constraints for future candidates. Further, we briefly described a greedy procedure that is based on relative evaluations to the intermediate result and candidate filtering based on existing eST-Miner procedures. To accompany the conceptual framework, we provide a software framework for development as well as tool support with an interactive user interface inside the ProM ecosystem. A practical feature being the possibility to set a time limit, as the intermediate result can always be utilized. In our evaluation, we demonstrated the applicability of the framework to synthetic as well as real-life event data. The evaluation demonstrates that the framework can discover high-quality models on both synthetic and real-life event logs, although its current runtime is not yet competitive with established discovery algorithms. Importantly, good models were often obtained long before exhaustive traversal of the candidate space, indicating that effective ordering and pruning strategies can make incomplete traversals practically useful. We envision that this kind of discovery approach should be tuned to the user’s needs. If there is enough time, a thorough traversal which actually provides some guarantees can be configured, otherwise a more heuristically guided instantiation can be used. The appeal lies in the sense of completeness that a well constrained candidate space traversal can provide. Directions for future work emerge naturally from the structure of our conceptual framework. Starting with proposal, more complex heuristics that incorporate more log information and allow monotonic pruning of places would be a great start. Even slightly extending the τ threshold to relative fitness [35] may have potential. Further, an extended constraining strategy based on precision or other quality dimension metrics could improve candidate pruning speed in this first step while providing additional guarantees. Supporting discovery of silent transitions or non-uniquely labeled transitions would be a huge improvement. Moving over to the less developed composition side, even more impactful improvements could be made. From defining a useful subclass of Petri nets that naturally provides subtree-monotonic constraints which would permit new guarantees on the final model (like uniwiring), to relaxing the current greedy strategy to combat running into local optima. The latter could be achieved by mirroring the tree structure of places for sets of places. That is, multiple compositions could be directly and indirectly considered. With monotone properties, scoring metrics, and at least approximate guiding heuristics, this extension would drastically improve the completeness of this approach. In general, this framework benefits from both rigorous provable candidate pruning and candidate composition space restrictions for model quality, as well as approximate heuristics used for ordering prioritization in incomplete traversals. Acknowledgements We thank the Alexander von Humboldt (AvH) Stiftung for supporting our research. Additionally, we thank the Ministry of Culture and Science of the German State of North Rhine-Westphalia (MKW) and the Excellence Strategy of the Federal Government and the Länder for supporting our research. References [1] A. Augusto, J. Carmona, and E. Verbeek (2022) Advanced Process Discovery Techniques. In Process Mining Handbook, W. M. P. van der Aalst and J. Carmona (Eds.), Lecture Notes in Business Information Processing, Vol. 448, p. 76–107. Cited by: §6. [2] A. Augusto, R. Conforti, M. Dumas, M. La Rosa, and A. Polyvyanyy (2019) Split miner: automated discovery of accurate and simple business process models from event logs. Knowl. Inf. Syst. 59 (2), p. 251–284. Cited by: §6. [3] É. Badouel, L. Bernardinello, and P. Darondeau (2015) Petri net synthesis. Texts in Theoretical Computer Science. An EATCS Series, Springer. Cited by: §6. [4] D. Brons, R. Scheepens, and D. Fahland (2021) Striking a new balance in accuracy and simplicity with the probabilistic inductive miner. CoRR abs/2109.06288. External Links: Link Cited by: §6. [5] J. C. A. M. Buijs, B. F. van Dongen, and W. M. P. van der Aalst (2012) On the role of fitness, precision, generalization and simplicity in process discovery. In On the Move to Meaningful Internet Systems: OTM 2012 - Confederated International Conferences: CoopIS, DOA-SVI, and ODBASE 2012, R. Meersman et al. (Eds.), Lecture Notes in Computer Science, Vol. 7565, p. 305–322. Cited by: §1, §5. [6] J. Carmona, J. Cortadella, and M. Kishinevsky (2008) A region-based algorithm for discovering Petri nets from event logs. In Business Process Management, 6th International Conference, BPM 2008, M. Dumas, M. Reichert, and M. Shan (Eds.), Lecture Notes in Computer Science, Vol. 5240, p. 358–373. Cited by: §6. [7] M. de Leoni and F. Mannhardt (2015) Road traffic fine management process. Cited by: §5. [8] A. K. A. de Medeiros, A. J. M. M. Weijters, and W. M. P. van der Aalst (2007) Genetic process mining: an experimental evaluation. Data Min. Knowl. Discov. 14 (2), p. 245–304. Cited by: §6. [9] F. García-Valles and J. M. Colom (1999) Implicit places in net systems. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, PNPM 1999, p. 104–113. Cited by: §3.3. [10] F. C. Groß, L. L. Mannel, and W. M. P. van der Aalst (2023) Enhancing the applicability of the est-miner: efficient precision-guided implicit place avoidance. In 5th International Conference on Process Mining, ICPM 2023, p. 121–128. Cited by: §5. [11] S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst (2013) Discovering block-structured process models from event logs - A constructive approach. In Application and Theory of Petri Nets and Concurrency - 34th International Conference, Petri NETS 2013, J. M. Colom and J. Desel (Eds.), Lecture Notes in Computer Science, Vol. 7927, p. 311–329. Cited by: §1, §6. [12] S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst (2013) Discovering block-structured process models from event logs containing infrequent behaviour. In Business Process Management Workshops - BPM 2013 International Workshops, M. La Rosa and P. Soffer (Eds.), Lecture Notes in Business Information Processing, Vol. 171, p. 66–78. Cited by: §6. [13] S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst (2018) Scalable process discovery and conformance checking. Softw. Syst. Model. 17 (2), p. 599–631. Cited by: §6. [14] S. J. J. Leemans, N. Tax, and A. H. M. ter Hofstede (2018) Indulpet miner: combining discovery algorithms. In On the Move to Meaningful Internet Systems. OTM 2018 Conferences, H. Panetto et al. (Eds.), Lecture Notes in Computer Science, Vol. 11229, p. 97–115. Cited by: §6. [15] J. Li, D. Liu, and B. Yang (2007) Process mining: extending alpha-algorithm to mine duplicate tasks in process logs. In APWeb/WAIM Workshops, Cited by: §1, §6. [16] R. J. Lipton (1976) The reachability problem requires exponential space. Technical report Technical Report 62, Department of Computer Science, Yale University. Cited by: §1. [17] L. L. Mannel, R. Bergenthum, and W. M. P. van der Aalst (2020) Removing implicit places using regions for process discovery. In Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data 2020, CEUR Workshop Proceedings, Vol. 2625, p. 20–32. Cited by: §1, §3.3, §4.1, §5, §6. [18] L. L. Mannel, Y. Epstein, and W. M. P. van der Aalst (2020) Improving the state-space traversal of the est-miner by exploiting underlying log structures. In Business Process Management Workshops - BPM 2020 International Workshops, A. del-Río-Ortega, H. Leopold, and F. M. Santoro (Eds.), Lecture Notes in Business Information Processing, Vol. 397, p. 334–347. Cited by: §1, §4.1, §5, §6. [19] L. L. Mannel and W. M. P. van der Aalst (2019) Finding complex process-structures by exploiting the token-game. In Application and Theory of Petri Nets and Concurrency - 40th International Conference, Petri NETS 2019, S. Donatelli and S. Haar (Eds.), Lecture Notes in Computer Science, Vol. 11522, p. 258–278. Cited by: §1, §1, §4.1, §4.2, §5, §6. [20] L. L. Mannel and W. M. P. van der Aalst (2019) Finding uniwired Petri nets using est-miner. In Business Process Management Workshops - BPM 2019 International Workshops, C. D. Francescomarino, R. M. Dijkman, and U. Zdun (Eds.), Lecture Notes in Business Information Processing, Vol. 362, p. 224–237. Cited by: §1, §3.4.1, §3.4.2, §4.1, §4.2, §6. [21] L. L. Mannel and W. M. P. van der Aalst (2022) Discovering process models with long-term dependencies while providing guarantees and handling infrequent behavior. In Application and Theory of Petri Nets and Concurrency - 43rd International Conference, Petri NETS 2022, L. Bernardinello and L. Petrucci (Eds.), Lecture Notes in Computer Science, Vol. 13288, p. 303–324. Cited by: §1, §3.4.2, §3.4.2, §4.1, §4.2, §6. [22] F. Mannhardt, M. de Leoni, and H. A. Reijers (2015) The multi-perspective process explorer. In Proceedings of the BPM Demo Session 2015, CEUR Workshop Proceedings, Vol. 1418. Cited by: §2. [23] F. Mannhardt (2016) Sepsis cases - event log. Cited by: §5. [24] A. Rozinat and W. M. P. van der Aalst (2008) Conformance checking of processes based on monitoring real behavior. Inf. Syst. 33 (1), p. 64–95. Cited by: §2. [25] A. Tiwari, C. J. Turner, and B. A. Majeed (2008) A review of business process mining: state-of-the-art and future trends. Bus. Process. Manag. J. 14 (1), p. 5–22. Cited by: §6. [26] A. Tour, A. Polyvyanyy, and A. A. Kalenkova (2021) Agent system mining: vision, benefits, and challenges. IEEE Access 9, p. 99480–99494. Cited by: §6. [27] C. Tsai, H. Jen, and I. Chen (2010) Time-interval process model discovery and validation - A genetic process mining approach. Appl. Intell. 33 (1), p. 54–66. Cited by: §6. [28] W. M. P. van der Aalst and J. Carmona (Eds.) (2022) Process mining handbook. Lecture Notes in Business Information Processing, Vol. 448, Springer. Cited by: §1. [29] W. M. P. van der Aalst, A. K. A. de Medeiros, and A. J. M. M. Weijters (2005) Genetic process mining. In Applications and Theory of Petri Nets 2005, 26th International Conference, ICATPN 2005, G. Ciardo and P. Darondeau (Eds.), Lecture Notes in Computer Science, Vol. 3536, p. 48–69. Cited by: §6. [30] W. M. P. van der Aalst, V. A. Rubin, H. M. W. Verbeek, B. F. van Dongen, E. Kindler, and C. W. Günther (2010) Process mining: A two-step approach to balance between underfitting and overfitting. Softw. Syst. Model. 9 (1), p. 87–111. Cited by: §6. [31] W. M. P. van der Aalst, B. F. van Dongen, J. Herbst, L. Maruster, G. Schimm, and A. J. M. M. Weijters (2003) Workflow mining: A survey of issues and approaches. Data Knowl. Eng. 47 (2), p. 237–267. Cited by: §6. [32] W. M. P. van der Aalst and B. F. van Dongen (2013) Discovering Petri nets from event logs. Transactions on Petri Nets and Other Models of Concurrency 7, p. 372–422. Cited by: §6. [33] W. M. P. van der Aalst, A. J. M. M. Weijters, and L. Maruster (2004) Workflow mining: discovering process models from event logs. IEEE Trans. Knowl. Data Eng. 16 (9), p. 1128–1142. Cited by: §1, §6. [34] W. M. P. van der Aalst (2016) Process mining: data science in action. Springer, Berlin, Heidelberg. Cited by: §1, §1, §5, §6. [35] W. M. P. van der Aalst (2018) Discovering the “glue” connecting activities - exploiting monotonicity to learn places faster. In It’s All About Coordination - Essays to Celebrate the Lifelong Scientific Achievements of Farhad Arbab, F. S. de Boer, M. M. Bonsangue, and J. Rutten (Eds.), Lecture Notes in Computer Science, Vol. 10865, p. 1–20. Cited by: §3.3, §5, §7. [36] W. M. P. van der Aalst (2019) A Practitioner’s Guide to Process Mining: Limitations of the Directly-Follows Graph. In International Conference on Enterprise Information Systems (Centeris 2019), Procedia Computer Science, Vol. 164, p. 321–328. Cited by: §1. [37] W. M. P. van der Aalst (2019) Object-centric process mining: dealing with divergence and convergence in event data. In Software Engineering and Formal Methods - 17th International Conference, SEFM 2019, P. C. Olveczky and G. Salaün (Eds.), Lecture Notes in Computer Science, Vol. 11724, p. 3–25. Cited by: §6. [38] W. M. P. van der Aalst (2022) Discovering directly-follows complete Petri nets from event data. In A Journey from Process Algebra via Timed Automata to Model Learning, Lecture Notes in Computer Science, Vol. 13560, p. 539–558. Cited by: §6. [39] W. M. P. van der Aalst (2022) Foundations of Process Discovery. In Process Mining Handbook, W. M. P. van der Aalst and J. Carmona (Eds.), Lecture Notes in Business Information Processing, Vol. 448, p. 37–75. Cited by: §1, §6. [40] J. M. E. M. van der Werf, B. F. van Dongen, C. A. J. Hurkens, and A. Serebrenik (2008) Process discovery using integer linear programming. In Applications and Theory of Petri Nets, 29th International Conference, Petri NETS 2008, K. M. van Hee and R. Valk (Eds.), Lecture Notes in Computer Science, Vol. 5062, p. 368–387. Cited by: §6. [41] M. L. van Eck, J. C. A. M. Buijs, and B. F. van Dongen (2014) Genetic process mining: alignment-based process model mutation. In Business Process Management Workshops - BPM 2014 International Workshops, F. Fournier and J. Mendling (Eds.), Lecture Notes in Business Information Processing, Vol. 202, p. 291–303. Cited by: §6. [42] S. J. van Zelst, B. F. van Dongen, W. M. P. van der Aalst, and H. M. W. Verbeek (2018) Discovering workflow nets using integer linear programming. Computing 100 (5), p. 529–556. Cited by: §6. [43] S. J. van Zelst, B. F. van Dongen, and W. M. P. van der Aalst (2015) Avoiding over-fitting in ILP-based process discovery. In Business Process Management - 13th International Conference, BPM 2015, H. R. Motahari-Nezhad, J. Recker, and M. Weidlich (Eds.), Lecture Notes in Computer Science, Vol. 9253, p. 163–171. Cited by: §6. [44] A. J. M. M. Weijters and J. T. S. Ribeiro (2011) Flexible heuristics miner (FHM). In 2011 IEEE Symposium on Computational Intelligence and Data Mining, CIDM 2011, p. 310–317. Cited by: §6. [45] L. Wen, W. M. P. van der Aalst, J. Wang, and J. Sun (2007) Mining process models with non-free-choice constructs. Data Min. Knowl. Discov. 15 (2), p. 145–180. Cited by: §6. [46] L. Wen, J. Wang, W. M. P. van der Aalst, B. Huang, and J. Sun (2010) Mining process models with prime invisible tasks. Data Knowl. Eng. 69 (10), p. 999–1021. Cited by: §6.