{'fraction_non_alphanumeric': 0.037674838321552113, 'fraction_numerical': 0.010527898932170252, 'mean_word_length': 4.54681960375391, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 23, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Automated Discovery of Process Models with True Concurrency and Inclusive Choices

Enterprise information systems allow companies to maintain detailed records of their business process executions. These records can be extracted in the form of event logs, which capture the execution of activities across multiple instances of a business process. Event logs may be used to analyze business processes at a fine level of detail using process mining techniques. Among other things, process mining techniques allow us to discover a process model from an event log -- an operation known as automated process discovery. Despite a rich body of research in the field, existing automated process discovery techniques do not fully capture the concurrency inherent in a business process. Specifically, the bulk of these techniques treat two activities A and B as concurrent if sometimes A completes before B and other times B completes before A. Typically though, activities in a business process are executed in a true concurrency setting, meaning that two or more activity executions overlap temporally. This paper addresses this gap by presenting a refined version of an automated process discovery technique, namely Split Miner, that discovers true concurrency relations from event logs containing start and end timestamps for each activity. The proposed technique is also able to differentiate between exclusive and inclusive choices. We evaluate the proposed technique relative to existing baselines using 11 real-life logs drawn from different industries.


Introduction
Enterprise information systems, such as Enterprise Resource Planning (ERP) systems, maintain detailed records of each execution of the business processes they support. These records can be extracted in the form of event logs. An event log is a set of event records capturing the execution of activities across a set of instances of a process.
Process mining techniques allow us to exploit event logs in order to analyze business processes at a fine level of detail. Among other things, process mining techniques allow us to discover a process model from an event log -an operation known as automated process discovery. Despite a rich body of research in the field, existing automated process discovery techniques do not fully capture the concurrency inherent in business processes. Indeed, the bulk of automated process discovery techniques operate under an interleaved concurrency model -a model of concurrency where two events are concurrent if they occur in either order. Specifically, existing techniques treat two activities A and B as concurrent if sometimes A completes before B and other times B completes before A. The interleaved concurrency model is suitable in systems where actions are atomic. However, in a business process, activities have a duration and the execution of two or more activities may overlap temporally. In other words, business processes contain true concurrency. The failure of existing automated process discovery techniques to take into account this true concurrency leads them to miss certain concurrency relations. For example, when an activity A always completes before activity B (because B takes longer) even though A and B overlap, existing techniques treat A and B as sequential. If A is then followed by C and C usually completes after B (but overlaps with it), they conclude that A, B and C are sequential, thus missing the observed concurrency.
This paper addresses this gap by presenting a refined version of an automated process discovery algorithm, namely Split Miner [6], capable of discovering true concurrency relations from event logs that record both the start and end timestamps of activity executions. The proposed technique, namely Split Miner 2.0, is also able to differentiate between exclusive and inclusive choices. The paper reports on an empirical evaluation that compares Split Miner 2.0 against existing baselines in terms of accuracy and model complexity measures.
The rest of the paper is structured as follows. Section 2 briefly reviews existing automated process discovery techniques. Section 3 introduces the approach to exploit true concurrency for automated process discovery. Section 4 presents the empirical evaluation while Section 5 summarizes the findings and further possible extensions.

Background and Related Work
An event log records information about a set of executions of a business processes (a.k.a. cases). Concretely, an event log is a chronological sequence of events, each one capturing a state change in the execution of an activity. As a minimum, each event in a log has three attributes: the identifier of the process execution (a.k.a. case ID); the label (i.e. the process activity the event refers to); and the timestamp (e.g. 10/07/2020 10.43). Optionally, an event may have other attributes such as the resource who triggered the event, their department, etc. In this paper, we require that at least one fourth attribute is attached to each event, namely the life-cycle transition. For a given event, this attribute indicates what state-change the referenced activity has undergone. The life-cycle of an activity captures all the states in an activity execution and their possible transitions. In general, one could observe very complex life-cycles, including states such as created, assigned, started, suspended, etc. In this paper, we adopt a simple life-cycle model wherein an activity execution can be in one of two states: start (i.e. the activity execution started); and end (i.e the activity execution ended).
Event logs can be exploited for different types of analysis including conformance checking, process performance mining, and automated process discovery [16]. In this paper, we focus on the latter. The goal of automated process discovery is to discover a process model (such as the one in Figure 1) by analysing an event log such as the one in Table 1 (the latter is just an extract and not a full log).
The quality of an automatically discovered process model is traditionally assessed over four dimensions: fitness -the amount of process behaviour recorded in the event log that can be replayed by the process model; precision -the amount of behaviour captured by the process model that can be found in the event log; generalization -the  amount of behaviour captured by the process model that even not being observed in the event log is likely to belong to the original process; and simplicity -quantifying how difficult is to understand the process model. Furthermore, a process model should be sound. The notion of soundness has been defined on Workflow nets [17] as a correctness criterion, and is also applicable to BPMN models. Formulated on BPMN models, soundness encompasses three properties: i) every process instance eventually reaches the end event (no deadlocks); ii) no end event is reached more than once during a process execution (proper completion); iii) each process activity is triggered in at least one process execution (no dead activities). A recent literature review of automated process discovery algorithms [5] showed that only few algorithms stand out for accuracy and performance among those outputting procedural process models. Specifically, Inductive Miner (IM) [10], Evolutionary Tree Miner (ETM) [7], and Split Miner (SM) [6]. IM and ETM are known to discover process models that are either highly fitting or precise, discovering simple, blockstructured and sound process models, while SM focuses on maximizing both fitness and precision at the cost of simplicity, structuredness, and in rare cases compromising the soundness of the process models [5,6]. However, of these three automated process discovery algorithms, only IM provides a variant that takes into account the activities' life-cycle when discovering a process model. IM life-cycle variant [11] analyses the activities' life-cycles to distinguish between concurrency and interleaving relations.
Past studies that investigated the problem of discovering control-flow relations between activities by leveraging life-cycle information or execution times include: (1) a simple algorithm [13] for discovering block-structured process models from complete and noise-free event logs; (2) an extension of the α-algorithm, i.e. the β algorithm [19]; (3) an extension of Heuristics Miner [8]; and (4) the work of Senderovich et al. which explores process performance modelling via temporal network representation [14]. The first one is limited to noise-free log. The second and third are based on underlying algorithms that produce unsound and inaccurate models when applied to real-life event logs, as shown in [5]. The fourth approach is not geared to discovering process models but rather targets the problem of performance mining.
In this paper, we extend the SM algorithm, which has been shown to produce accurate and (generally) sound process models over real-life logs. Figure 2 shows an overview of how SM discovers a process model from an event log. Given an input event log, SM operates over five steps: i) discover the directly-follows graph (DFG) and loops from the event log; ii) analyse the DFG for discovering concurrency rela-tions; iii) filter the DFG by removing the infrequent behaviour; iv) discover the split gateways; v) discover the join gateways. Each step is a standalone operation based on tailored algorithms [6], such a modular approach allows the replacement of any step with alternative methods. In this paper, we show how we updated the first, second, and fifth steps to discover true concurrency and inclusive choices, and reduce the chances of producing unsound process models via heuristics.

Approach
In this section, we describe how we redesigned the first two steps of the Split Miner original approach [6] and integrated in the last step two heuristics to repair models that are unsound due to improper completion and identify inclusive relations between activities, enabling the discovery of OR-splits.

Refined Directly-follows Graph Discovery
Given an event log, the first step performed by Split Miner is to sequentially read the events and build the directly-follows graph (DFG). Although this operation is straightforward, its output strictly depends on how the event log and the DFG are defined. Definitions 1, 2, and 3 capture the notion of DFG used in the original Split Miner.

Definition 1.
[Event Log as in [6]] Given a set of process activity labels A , an event log L is a multiset of traces, where a trace t ∈ L is a sequence of activity labels t = a 1 , a 2 , . . . , a k , with a i ∈ A , 1 ≤ i ≤ k. In addition, we use the notation a ∈ A to refer an activity a that belongs to a generic trace t ∈ L . 1 Definition 2. [Directly-Follows Relation as in [6]] Given an event log L and two process activities a x , a y ∈ A , we say that activity a y directly-follows activity a x , with notation a x a y , if and only if (iff) ∃ a 1 , a 2 , . . . , a k ∈ L | a i = a x ∧ a j = a y ∧ j = i + 1 ∧ 0 < i < n.

Definition 3.
[Directly-Follows Graph as in [6]] Given an event log L , its Directly-Follows Graph (DFG) is a directed graph G = (N, E), where N is the non-empty set of nodes, where each node represents a unique activity a ∈ L and there exists a bijective function λ : N → A such that λ (n) retrieves the activity n refers to; and E is the set of edges capturing the directly-follows relations of the activities observed in L , To capture the activities' lifecycle information, we refine the concept of event log.

Definition 4. [Refined Event
Log] Given a set of events E , a refined event log L ρ is a multiset of traces, where a trace t ∈ L ρ is a sequence of events t = e 1 , e 2 , . . . , e k , with e i ∈ E , 1 ≤ i ≤ k. Each event e ∈ E ρ is a tuple e = (l, p,t), where l ∈ A is the process activity the event refers to, retrieved with the notation e l ; p ∈ {start, end} is the state of the life-cycle of activity l, retrieved with the notation e p ; and t is the timestamp of the event, retrieved with the notation e t .
While redefining the event log to capture the activities' life-cycle information is intuitive and follows from its original definition [16], the same does not apply for the DFG. Indeed, more than one approach could be used to generate a DFG from a refined event log. The simplest approach would be to disregard all the events of a specific state of an activity life-cycle, for example, we could remove from L ρ all the events e ∈ L ρ | e p = start or all the events e ∈ L ρ | e p = end. Then, the refined event log would turn into an event log (Definition 1) and the DFG would be constructed according to Definition 3, but this would be equivalent to discarding the activities' lifecycle information.
An alternative approach was proposed by Leemans et al. [11] and incorporated into a variant of the Inductive Miner that takes into account lifecycle transitions, herein called Inductive Miner Lifecycle (IM-lc). According to [11], an activity a y directlyfollows an activity a x if any of the life-cycle states of activity a y is observed after any of the life-cycle states of activity a x in the same trace and between the two observations no activity completes the execution of its full life-cycle (see Definition 5).

Definition 5.
[Directly-Follows Relation as in [11]] Given a refined event log L ρ and two process activities a x , a y ∈ A , the relation a x a y holds iff ∃ e 1 , e 2 , . . . , According to Definition 5, a directly-follows relation would hold between two activities whose life-cycles overlap (i.e. the start-state of an activity is observed between the start-state and the end-state of another activity). While this is important and useful for IM-lc to discover concurrency relations [10], it would not be beneficial for Split Miner, since Split Miner requires to remove the directly-follows relations between activities that are considered concurrent [6]. Consequently, we are interested in discarding directly-follows relations of activities whose life-cycles overlap. We redefine the directly-follows relation of activities observed in a refined event log as follows. An activity a y directly-follows an activity a x if the start-state of the life-cycle of activity a y is observed after the end-state of the life-cycle of activity a x and no end-state of other activities are observed in between (see Definition 6).

Definition 6.
[Directly-Follows Relation] Given a refined event log L ρ and two process activities a x , a y ∈ A , the relation a x r a y holds iff ∃ e 1 , e 2 , . . . , e k ∈ L ρ | e l i = a x ∧ e l j = a y ∧ e p i = end ∧ e l j = start ∧ 1 ≤ i < j ≤ k ∧ n ∈ ] i, j [ | e p n = end.  The new version of Split Miner we propose in this paper relies on Definition 6. Depending on the definition of directly-follows relation that one adopts when generating the DFG, one may discover very different DFGs. As an example, let us consider the following refined event log (captured as a collection of traces, where each event is represented as the activity it refers to -including its life-cycle state as subscript, s standing for start and e standing for end):  Figure 3 shows the DFGs discovered from the L ρ x by applying Definition 2 (original Split Miner approach), Definition 5 (Inductive Miner life-cycle approach), and Definition 6 (this paper approach).

Refined Concurrency Discovery
The second step of the original Split Miner that we redesigned is the concurrency discovery. Split Miner relies on a simple heuristic to discover concurrency, precisely, given a DFG and two activities A, B ∈ A such that neither A nor B is a self-loop, A and B are assumed concurrent iff three conditions are true: A directly-follows B and B directlyfollows A (Relation 1); A and B do not form a short-loop (Relations 2 and 3); the frequency of the two directly-follows relations A B and B A is similar (Relation 2). 2 The simplicity of the concurrency oracle of Split Miner derives from the simplicity of the input event log (see Definition 1). However, when receiving as input a refined event log (Definition 4), it is possible to identify true concurrency by focusing on activities whose life-cycles overlap and are hence truly executed concurrently (e.g. by different process resources). Consequently, we redefine the concurrency discovery oracle as follows. Given two activities A, B ∈ A and a refined event log L ρ , we say A and B are concurrent if the following relation holds: where |A B| is the total number of observations of overlapping life-cycles of A and B in L ρ ; |A| and |B| are respectively the total number of complete life-cycle 3 observations of activity A and activity B in L ρ ; and ε is an arbitrary variable (given as input parameter) defining the minimum percentage of times that the two activities' lifecycles are required to overlap to assume the two activities concurrent. In particular, when ε = 1 our notion of concurrency is equivalent to the notion of strong simultaneousness defined by Van der Werf et al. [18] as well as Allen's interval relations [3] of overlaps, contains, starts, and is finished by. While for any other value of ε > 0 it is equivalent to a parametrized notion of weak simultaneousness [18]. Given that real-life event logs often contain noise and infrequent process behaviour, requiring ε = 1 would be very restrictive and may lead to the discovery of no concurrent activities.
Although both our approach and IM-lc infer concurrency relations between activities from the observation of overlapping life-cycles, we rely on an heuristic before validating the concurrency relations (i.e. Equation 5) -in-line with the original Split Miner; while IM-lc assumes the information contained in the log to be valid a priori (this is mitigated by another extension of IM-lc that embeds a filtering technique [11]).

Heuristic Improvement
Although Split Miner guarantees to discover sound acyclic process models and deadlock-free cyclic process models with no dead activities, for cyclic process models it does not guarantee proper completion. However, it is possible to reduce the chances to discover process models exhibiting improper completion by applying the following heuristic: for each AND-split gateway in a process model with an outgoing edge that is a loop-edge (leading to a topologically deeper node of the process model), we create a preceding XOR-split gateway and set this latter as source of the loop-edge. Figure 4 intuitively show how the heuristic operates, the loop-edge is highlighted in blue and, in general, activities could be present in the loop-edge.  Lastly, we integrated an heuristic to discern between concurrency and inclusive relations, in other words identifying when an AND-split gateway is a candidate ORsplit gateway. This second heuristic operates as follows. For each AND-split gateway in a process model, we consider all the successor activities and we check pairwise whether there exist traces where the pair of activities are mutually exclusive (i.e. one of the two activities is executed but not the other). Then, if the majority of the pairs of activities are both mutually exclusive and concurrent in different traces, 4 we turn the AND-split gateway into an OR-split gateway and we update accordingly the ORjoin gateway. As an example, let us consider the model in Figure 5a

Evaluation
In this section, we present an empirical evaluation that compares Split Miner 2.0 (SM 2.0 ) with three state-of-the-art automated process discovery algorithms: the original Split Miner [6] (SM), the Inductive Miner Lifecycle (IM-lc) [10] including its infrequent behaviour filter [11], and the most recent version of IM, namely IMfa [9].

Dataset and Setup
As testing dataset, we selected eleven real-life event logs (L1-L11) containing activity lifecycle information. The logs were sourced from companies operating in different fields (e.g. insurance, manufacturing, banking) and geographic areas (i.e. Europe and Australia). Given that these logs are not publicly available, we added a publicly available simulated event log known as the "Repair example" (R-Log), 5 which also contains activity lifecycle information. We did not include the BPIC12 and BPIC17 logs simply because the former does not have any overlapping lifecycle, and for the latter both SM and SM 2.0 produced the same model, which was analysed in previous studies [4,6,5]. Table 2 displays the characteristics of the event logs, highlighting their variety, with logs containing short to long traces (length 2 to 1,230), a wide range of distinct traces (0.28% to 96.55%) and distinct events (6 to 80), as well as notable differences in the total number of traces (37 to 70,512) and events (1, 156 to 830,522). The lifecycle information for each activity recorded in these event logs was complete, i.e. the start and end events were recorded for each activity.
From each log, we discovered a process model with SM 2.0 , SM, and IM-lc, and compared the quality of the discovered models over three quality measures: fitness, precision, and simplicity. Several methods have been proposed for measuring fitness and precision of an automatically discovered process model [15]. In this paper we use two methods, the one proposed by Adriansyah et al. [1,2] (alignment-based accuracy) and the one proposed by Augusto et al. [4] (Markovian accuracy). As proxy for simplicity we use the following three metrics [12]: Size -the total number of nodes of a process model; Control-flow complexity (CFC) -the amount of branching induced by the split gateways in the process model; Structuredness -the percentage of nodes located inside a single-entry single-exit fragment of the process model.
We implemented SM 2.0 as a Java command-line application, 6 and we ran the experiments on an Intel Core i7-8565U@1.80GHz with 32GB RAM running Windows 10 Pro (64-bit) and JVM 8 with 14GB of allocated RAM (10GB Stack and 4GB Heap). All the discovery algorithms (SM, SM 2.0 , and IM-lc) were executed using their default input parameters, and we set a timeout of 30 minutes for each algorithm execution and for each measurement.  Table 2: Descriptive statistics of the logs. Table 3 reports the fitness, precision, and simplicity measurements. Due to space limits, the table does not show the measurements for IMfa because they were either equal or worse than those for IM-lc, with the exception of those obtained on L9 (which reported a slight improvement). We can observe that SM 2.0 is less prone to discovering unsound models than SM, with the latter discovering an unsound model every three and the former only discovering sound models. This achievement reflects the effectiveness of our heuristics for removing improper completion.

Results
In terms of accuracy, the results obtained with the alignment-based accuracy and the Markovian accuracy are partially consistent in line with previous findings [4]. In fact, the two measuring methods agree on the best models in terms of fitness, precision, and F-score, respectively 100%, 66%, and 75% of the times.
As for fitness, IM-lc outperforms both SM and SM 2.0 as expected [5]. In terms of precision and F-score SM 2.0 and SM achieve the highest scores, with SM 2.0 performing better than SM, most of the times discovering more precise and fitting process models ultimately achieving a higher F-score. In fact, SM 2.0 accuracy scores are either higher than or equal to those of SM, the latter outperforming the former in fitness or precision only two times according to the alignment-based accuracy, and only three times according to the Markovian accuracy. Compared to IM-lc, SM 2.0 discovers eleven times more precise process models, indipendently of the measurement method.
As for simplicity, SM 2.0 stands out by producing smaller models than those discovered by both SM and IM-lc (9 times out of 12) and with a lower CFC (10 times out of 12). However, SM 2.0 and SM cannot systematically produce fully-structured process models as opposed to IM-lc which achieves this by design. Lastly, the execution times of IM-lc, SM, and SM 2.0 are negligible: all the process models were discovered within a minute (except for log L7, where IM-lc timed out). Figure 6 shows two qualitative examples of the improvements yielded by SM 2.0 . Considering the models from the L6 log (Figures 6a and 6b), SM 2.0 discovered the inclusive-OR relations between several activities of the process and removed the improper completion, while SM produced an unsound model. In the specific case of the L6 log, we also had the chance to validate the discovered model with the process analysts of the organization this log was extracted from, who confirmed that the activities were indeed in an inclusive-OR relation. Considering the models from the R-log (  ures 6c and 6d), only SM 2.0 discovers the concurrency relations between its activities, while SM mixes us the concurrency relations with loops.
(a) SM model discovered from L6.
(c) SM model discovered from R-Log.
(d) SM 2.0 model discovered from R-Log.

Conclusion
In this paper, we presented Split Miner 2.0 (SM 2.0 ), an extension of Split Miner (SM) [6] that exploits the activities' start and end timestamps recorded in an event log to discover true concurrency and inclusive choice relations between activities. This is achieved by redesigning the discovery of a directly-follows graph from an event log, adapting the concurrency notion of Van der Werf et al. [18], and introducing an intuitive heuristic to identify inclusive relations. Furthermore, given that SM cannot guarantee sound process models, we designed an heuristic that reduces the chances of discovering process models exhibiting improper completion. The empirical evaluation shows that SM 2.0 can discover more concurrent relations than SM, remove improper completion, and identify OR-splits, while preserving SM's model accuracy and reducing the complexity.
Although several studies have investigated the problem of automated process discovery from event logs [5], most of them operate on simple event logs with only three attributes: case id, timestamp, and activity label. Future research work in this area may focus on designing more sophisticated automated process discovery algorithms that can discover more complex BPMN process models by leveraging additional information that may be available in real-life event logs. Another direction for future work is to design accuracy measures such as fitness and precision that go beyond simple control-flow relations and include support for inclusive gateways, including the OR-join.