Process mining using BPMN: relating event logs andprocess modelsKalenkova, A.A.; van der Aalst, W.M.P.; Lomazova, I.A.; Rubin, V.A.Published in:Software and Systems ModelingDOI:10.1007/s10270-015-0502-0Published: 01/10/2017Document VersionAccepted manuscript including changes made at the peer-review stagePlease check the document version of this publication: A submitted manuscript is the author's version of the article upon submission and before peer-review. There can be important differencesbetween the submitted version and the official published version of record. People interested in the research are advised to contact theauthor for the final version of the publication, or visit the DOI to the publisher's website. The final author version and the galley proof are versions of the publication after peer review. The final published version features the final layout of the paper including the volume, issue and page numbers.Link to publicationCitation for published version (APA):Kalenkova, A. A., van der Aalst, W. M. P., Lomazova, I. A., & Rubin, V. A. (2017). Process mining using BPMN:relating event logs and process models. Software and Systems Modeling, 16(4), 1019-1048. DOI:10.1007/s10270-015-0502-0General rightsCopyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright ownersand it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights. Users may download and print one copy of any publication from the public portal for the purpose of private study or research. You may not further distribute the material or use it for any profit-making activity or commercial gain You may freely distribute the URL identifying the publication in the public portal ?Take down policyIf you believe that this document breaches copyright please contact us providing details, and we will remove access to the work immediatelyand investigate your claim.Download date: 14. Jan. 2018

Softw Syst ModelDOI 10.1007/s10270-015-0502-0REGULAR PAPERProcess mining using BPMN: relating event logs and processmodelsAnna A. Kalenkova1 · Wil M. P. van der Aalst1,2 · Irina A. Lomazova1 ·Vladimir A. Rubin1Received: 11 March 2015 / Revised: 17 July 2015 / Accepted: 22 September 2015 Springer-Verlag Berlin Heidelberg 2015Abstract Process-aware information systems (PAIS) aresystems relying on processes, which involve human and software resources to achieve concrete goals. There is a need todevelop approaches for modeling, analysis, improvement andmonitoring processes within PAIS. These approaches includeprocess mining techniques used to discover process modelsfrom event logs, find log and model deviations, and analyzeperformance characteristics of processes. The representational bias (a way to model processes) plays an importantrole in process mining. The BPMN 2.0 (Business ProcessModel and Notation) standard is widely used and allows tobuild conventional and understandable process models. Inaddition to the flat control flow perspective, subprocesses,data flows, resources can be integrated within one BPMNdiagram. This makes BPMN very attractive for both processminers and business users, since the control flow perspecCommunicated by Prof. Ulrich Frank.This work is supported by the Scientific Fund of the NationalResearch University Higher School of Economics and is supported byRussian Fund for Basic Research (Project 15-37-21103).BAnna A. [email protected] can be integrated with data and resource perspectivesdiscovered from event logs. In this paper, we describe andjustify robust control flow conversion algorithms, which provide the basis for more advanced BPMN-based discoveryand conformance checking algorithms. Thus, on the basis ofthese conversion algorithms low-level models (such as Petrinets, causal nets and process trees) discovered from eventlogs using existing approaches can be represented in terms ofBPMN. Moreover, we establish behavioral relations betweenPetri nets and BPMN models and use them to adopt existingconformance checking and performance analysis techniquesin order to visualize conformance and performance information within a BPMN diagram. We believe that the resultspresented in this paper can be used for a wide variety ofBPMN mining and conformance checking algorithms. Wealso provide metrics for the processes discovered before andafter the conversion to BPMN structures. Cases for whichconversion algorithms produce more compact or more complicated BPMN models in comparison with the initial modelsare identified.Keywords Process mining · Process discovery · Conformance checking · BPMN (Business Process Model andNotation) · Petri nets · BisimulationWil M. P. van der [email protected] A. [email protected] A. [email protected] Research University Higher School of Economics,Moscow, Russia2Department of Mathematics and Computer Science,Eindhoven University of Technology, Eindhoven, TheNetherlands1 IntroductionProcess-aware information systems (PAIS) are the systemsdesigned to manage processes, operating in various domainsof human activity. There is a natural requirement to monitortheir work and analyze executed processes. In many cases,analysts are interested in a real system behavior, which maybe hidden from domain experts and system engineers. This123

A. A. Kalenkova et al.Table 1 An event log of a booking processCase IDEvent nameTimestampPriceClient IP1Book flight2014-12-24 08:30:00:232145188.44.42.451Get insurance2014-12-24 08:31:05:17123188.44.42.452Book flight2014-12-24 08:31:08:5439493.180.0.621Book hotel2014-12-24 08:32:08:703295188.44.42.453Book flight2014-12-24 08:32:11:534192188.44.50.1031Pay2014-12-24 08:34:17:456463188.44.42.451Confirm2014-12-24 08:35:17:537463188.44.42.45.real behavior can be reconstructed from the event logs. Forthat purpose, Data Science approaches can be applied. Theinterest in Data Science and Big Data signifies the growingimportance of evidence-based approaches. Process miningtechniques provide wide range of data-driven approachesthat are process-centric at the same time. Other data-drivenapproaches are often no process-centric.Process mining offers techniques for automatic discoveryof process models from event logs, checking compatibilityof process models and event logs (conformance checking)and enhancing discovered processes with additional data [1].Process mining has been successfully applied in a variety ofapplication domains such as healthcare [2], tourism [3] andeducation [4]. There is a IEEE process mining community,including more than 60 organizations [5]. Moreover, thereis a wide range of research and commercial tools availablein this area: ProM, Disco (Fluxicon), ARIS Process Performance Manager (Software AG), Perceptive Process Mining(Perceptive Software), ProcessAnalyzer (QPR) and Celonis.Today, BPMN 2.0 (Business Process Model and Notation) [6] is the de facto standard notation for modelingbusiness processes understandable by a wide audience ofpeople. Business analysts and product managers, technicaldesigners and developers, system and enterprise architectseffectively use this notation in their everyday job almosteverywhere where BPM is applied. An absolute majority offreeware and commercial BPM tools and Business Suites,like Oracle BPM Suite, IBM Business Process Manager,jBPM, Activiti, Appian BPM Suite, Bizagi BPM Suite,MagicDraw Enterprise Architect (Sparx), Mega Process(MEGA), Signavio Process Editor and others, either nativelysupport BPMN or provide conversion in order to stay compatible and up to date. BPMN applicability and best BPMNmodeling practices are presented in [7–9].The representational bias used for process mining is notonly relevant for the understandability of the results, it isalso vital to guide process discovery by setting a suitableclass of target models. Using the BPMN notation as a representational bias within process mining opens excellent123perspectives for applicability of process mining: Discoveredprocess models become available and understandable bythe majority of users, the models can be imported/exportedfrom/to any BPMN-aware modeling tool and executed,process mining techniques can be easily integrated to theexisting suites (BPMN serves as an interface in this case).Moreover, BPMN models allow for the combination of different perspectives varying from control flow (includingsubprocesses) to the perspective of resources.In this paper, we present methods for discovering thecontrol flow perspective of a process in terms of BPMN. Itshould be noted that process mining offers plenty of algorithms for the control flow discovery and each of them hasits own characteristics. The goal is not to invent new algorithms, but to benefit from the existing ones and to make themBPMN-compatible. Thus the discovery of the control flowrelies on conversion algorithms and existing process miningtechniques. To that end we firstly formalize the semanticsfor a subset of BPMN models and then present the conversion algorithms from well-known control flow modelingformalisms such as Petri nets (including non-free-choicePetri nets), causal nets [10] and process trees [11] to BPMN.The conversion algorithms presented in the paper are alsogiven the justifications in order to show that behavioral properties of process models discovered from an event log arepreserved. Moreover, we show relations between languagesof Petri nets and corresponding BPMN models, tacking intoaccount properties of the initial Petri nets.As a short introductory example, let us consider an eventlog1 reflecting a small portion of the history of a ticket booking process, which is presented in Table 1. In this process,people use a Web site to book a flight, a hotel, get insuranceand pay for the ticket. Different people in different casesexecute these activities in a different order. Beside case identifiers, event names and timestamps, an event log can contain1In order to give an intuitive example, we consider a simple and expressive synthetic event log. The analysis of process models discovered fromreal-life event logs is demonstrated in Sect. 9.

Process mining using BPMN: relating event logs and process modelsFig. 2 A BPMN model obtained by a conversion from the Petri netFig. 1 A Petri net constructed from the logadditional event properties, such as costs and resources (participants of the process); in this example, they are representedby prices and clients ip addresses.To discover a control flow, an event log is represented asa multiset of traces, each of which is a sequence of events,corresponding to a concrete case identifier: L book f light, get insurance, book hotel, pay, con f ir m 5 , book f light, book hotel, get insurance, pay, con f ir m 4 , book hotel, book f light, get insurance, pay, con f ir m 4 , book hotel, get insurance, book f light, pay, con f ir m 3 , get insurance, book hotel, book f light, pay, con f ir m 1 , get insurance, book f light, book hotel, pay, con f ir m 1 .A Petri net discovered from L by the Alpha mining algorithm [12] is presented in Fig. 1.With the help of a conversion algorithm, we construct aBPMN model from the Petri net, as shown in Fig. 2. ThisBPMN model is more compact than the initial Petri net. Thus,the result of process mining is available in a BPMN notationnow; this BPMN model can be easily imported and executedby any of BPM tools mentioned above.In order to estimate the advantages of using the BPMNnotation for mining, we additionally compare the complexityof the models produced by the existing control flow discoveryalgorithms and the complexity of the corresponding BPMNmodels. We use the various metrics, such as the numberof nodes, density and diameter for this evaluation. Correlations between the process metrics and the quality of processmodels are discussed in [13–16]. We present not only theoretical but also practical evaluations based on real-life eventlogs. Moreover, applied to these event logs, the metrics ofthe discovered BPMN models are compared to the metricsof the models designed manually with a BPMN-editor. Thishelps us to understand structural differences between models,which are created by process analysts and models discoveredfrom event logs.Since not only discovery but also conformance checkingand process enhancement are essential steps in process mining, this paper also shows how to enable them for BPMNmodels. A BPMN model is converted to a Petri net, and thenreplay techniques are applied [17] to retrieve performanceand conformance information. This information is used toenhance BPMN models. Theoretical observations presentedin this paper help us to relate states of a BPMN model withthe states of a corresponding Petri net. Thus, both conformance and performance information obtained for a Petri netcan be visualized using the initial BPMN model.A general scheme of using BPMN for process mining ispresented in Fig. 3. The user discovers a BPMN model byapplying discovery and BPMN conversions plugins. To showperformance and conformance information and to annotatethe BPMN diagram, the BPMN model is converted to a Petrinet, such that replay techniques can be used.The paper is organized as follows. Section 2 overviewsrelated work. Section 3 introduces basic definitions andnotions, including traces, Petri nets, system nets, (weak)Fig. 3 A general scheme of using BPMN for process mining123

A. A. Kalenkova et al.simulation and (weak) bisimulation relations. In Sect. 4,we propose algorithms for conversion from well-known formalisms such as Petri nets to BPMN and prove correctnessof these conversions. In Sect. 5, transformations of causalnets and process trees to BPMN are introduced. Section 6contains a set of BPMN simplification rules. In Sect. 7, atechnique for conformance checking and performance analysis on the basis of BPMN models is presented. A tool, whichimplements the proposed conversion and enhancement techniques, is presented in Sect. 8. Section 9 includes a case study,which shows the results of an application of the algorithmspresented in the paper to real-life event logs. Also the structural business-processes metrics are calculated and presentedin this section. Section 10 concludes the paper.2 Related workThis section surveys previous work on Petri net and workflowgraph conversions and includes an overview of existing discovery and conformance checking techniques dealing with“high-level” process models (e.g., BPMN models and models presented not only by the control flow, but also includingdata and resource perspectives as well).Algorithms for conversion of free-choice workflow nets[18] (a special subset of Petri nets) to workflow graphs (generalization concept for process modeling notations such asBPMN, UML Activity [19], EPC [20,21], etc) were proposedin [22,23]. In our paper, we will deal with arbitrary Petri netsstructures and arbitrary safe initial markings. Moreover, incontrast to the approaches proposed before [22,23], we provethat the target model will simulate (i.e., will be able to mimic)the behavior of the initial net and vice versa. These simulation relations give the possibility to prove important (in thecontext of process mining) propositions on the language relations. Another key result is that having simulation relationsbetween initial and target models allows us to project variousanalysis data (such conformance and performance information) obtained for one model to another.An approach for constructing BPMN models containingsubprocesses was presented in [24]. In contrast to our paper,this technique is mainly focused on deriving subprocessesfrom event logs. We present basic robust conversion algorithms, which help to construct flat control flow skeletons ofthe target BPMN models from the discovered Petri nets andother low-level models. We hope that our approach can be further used as a basis for discovering more advanced constructs.As [24] our approach is generic and can work with multiple discovery algorithms (such as [12,25,26]) in the processmining context. The approach presented in [27] demonstrates the possibility of mining BPMN models covering boththe control flow perspective and the resource perspective.Unfortunately, this approach is rather narrow in scope as it123presents very concrete algorithms for mining BPMN controlflow and resource elements. Algorithms for discovering dataand resources from event logs were proposed in [28–30],respectively. To evaluate the quality of BPMN models andmultiperspective process models obtained from the real eventlogs, an analysis of process quality metrics proposed in various studies, such as [13–16], can be applied. An approachfor finding deviations between an event log and a multiperspective process model was presented in [31].3 PreliminariesIn this section, we introduce basic notions, event logs, Petrinets, system nets and BPMN semantics.Multisets are used to present states of Petri nets and BPMNmodels, and also they are used to define event logs, in whichone trace can appear multiple times.B(A) is the set of all multisets over some set A. For somemultiset b B(A), b(a) denotes the number of times element a A appears in b. By b [a1 2 , a2 3 ] we denotethat elements a1 , a2 A appear in b two and three times,respectively.The sum of two multisets b and b over set A is definedas: (b b )(a) b(a) b (a) for all a from A. We say thatb b iff a A : b(a) b (a). For two multisets b and b over set A, such that b b , the difference function is definedas: (b\b )(a) b(a) b (a). The size of a multiset b over set A is denoted by b and defined as b a A b(a). Setswill be considered as a special case of multisets, where eachelement can appear 0 or 1 times. Thus, operations applicableto multisets can be applied to sets.Function f : X Y is a partial function withdomain dom( f ) X and range defined as r ng( f ) { f (x) x dom( f )} Y . f : X Y is a total function, i.e., dom( f ) X . Let f : X Y be a partialfunction, f can be applied to sequences of X using the recursive definition f ( ) and for some σ X andx X f ( x · σ ) f (x) · f (σ ), if x dom( f ) andf ( x · σ ) f (σ ) otherwise.3.1 Event logs and Petri netsDefinition 1 (Petri Net) A Petri net is a tuple PN (P, T, F) with P the set of places, T the set of transitions,P T , and F (P T ) (T P) the flow relation.Definition 2 (Marking) Let PN (P, T, F) be a Petri net.A marking M is a multiset of places, i.e., M B(P).Definition 3 (Safe Marking) A marking M of a Petri netPN (P, T, F) is safe iff p P : M( p) 1, i.e., eachplace contains not more than 1 token.

Process mining using BPMN: relating event logs and process modelsPictorially, places are represented by circles, transitions byboxes and the flow relation F by directed arcs. Places maycarry tokens represented by filled circles. A current markingM is designated by putting M( p) tokens into each placep P.For a node n P T , the set of input nodes and theset of output nodes are defined as n {x (x, n) F} andn {x (n, x) F}, respectively.A transition t T is enabled in a marking M of net PN,denoted as (PN, M) [t , iff p t : M( p) 1, i.e., eachof its input places contains at least one token.An enabled transition t may fire, i.e., one token is removedfrom each of the input places t and one token produced foreach of the output places t . Formally: M (M\ t) t is the marking resulting from firing enabled transition t inmarking M of Petri net PN. (PN, M) [t (PN, M ) denotesthat t is enabled in M and firing results in marking M .Let σ t1 , . . . , tn T be a sequence of transitions. (PN, M) [σ (PN, M ) denotes that there is a set of markings M0 ,M 1 , , Mn , such that M0 M, Mn M ,and (PN, Mi ) ti 1 (PN, Mi 1 ) for 0 i n. We saythat M is reachable from M if there exists σ , such that(PN, M) [σ (PN, M ).R(PN, M) denotes the set of all markings reachable inPN from the marking M.Definition 4 (Labeled Petri Net) A labeled Petri net PN (P, T, F, l) is a Petri net (P, T, F) with labeling functionl T U A where U A is some universe of activity labels.Let σv a1 , . . . , an U A be a sequence of activity labels.(PN, M)[σv (PN, M ) iff there is a sequence σ T suchthat (PN, M) [σ (PN, M ) and l(σ ) σv .If t / dom(l), transition t is called invisible. An occurrence of visible transition t dom(l) corresponds toobservable activity label l(t).In the context of process mining, we normally considerso-called complete firing sequences, and thus we deal withprocesses, which have well-defined initial and end states.Therefore, let us give a notion of a system net.Definition 5 (System Net) A system net is a triplet SN (PN, Minit , Mfinal ) where PN (P, T, F, l) is a labeled Petrinet, Minit B( p) is the initial marking and Mfinal B( p) isthe final marking.Fig. 4 A fragment of a non-free-choice Petri netDefinition 7 (Trace, Event Log) Let A U A be a set ofactivity labels. A trace σ A is a sequence of activitylabels. L B(A ) is an event log, i.e., a multiset of traces.Note that a trace can appear multiple times in an event log.Some conversion techniques presented in this paper dealwith free-choice nets. Let us define them.Definition 8 (Free-choice Nets) A system net SN (PN,Minit , Mfinal ) and a corresponding labeled Petri net PN (P, T, F, l) are called free-choice iff for any two transitionst1 , t2 T with t1 t2 holds t1 t2 .To illustrate the concept of a free-choice Petri net, let usconsider a fragment of a Petri net presented in Fig. 4. It isnot a free-choice Petri net, and t1 and t2 share an input place,but do not have identical sets of input places. Indeed, if placep1 contains tokens enabling t1 , while p2 is empty, there is“no free choice” between t1 and t2 , only t1 is enabled andmay fire. If an arc is added from p2 to t1 , then the net isfree-choice.3.2 BPMN semanticsIn this subsection, we will present an approach for the formalization of BPMN control flow semantics based on a conceptof token. This formalization will give an ability to justifythe conversion algorithms presented later in this paper. Werestrict ourselves to the core set of BPMN elements, whichincludes activities, start and end events, exclusive and parallelgateways. We hope that these initial results will give a basisfor formal description of more advanced BPMN modelingconstructs.Let us give a formal definition of a BPMN model.Definition 6 (Language of a System Net) Suppose thatSN (PN, Minit , Mfinal ) is a system net. Language L SNof SN will be defined as a set of all visible executionsequencesstarting in Minit and ending in Mfinal , i.e., L SN σv (PN, Minit )[σv (PN, Mfinal ) .Event logs are considered as a starting point in the contextof process mining, so let us give their formal definition.Fig. 5 Core BPMN modeling constructs123

A. A. Kalenkova et al.Fig. 6 Initial markingFig. 8 Firing exclusive gatewayDefinition 9 (BPMN Model) A BPMN model is a tupleBPMNmodel (N , A, G XOR , G AND , estart , E end , SF, λ),where– N is a set of flow nodes,– A N is a set of activities,– G XOR N , G AND N are sets of exclusive and parallelgateways,– estart N is a start event,– E end N is a set of end events,– sets A, G XOR , G AND , {estart }, E end form a partition of N ,– SF N N is a set of sequence flows,– λ : N U A is a labeling function, where U A is someuniverse of activity labels,– start event estart does not have incoming sequence flows,and has not more than one outgoing sequence flow,– end events from E end do not have outgoing sequenceflows.Figure 5 shows the core BPMN constructs used to modelprocesses.Let n N be an arbitrary BPMN model node, the preset n and the postset n are defined as sets of incoming andoutgoing sequence flows for the node n, respectively.To restrict the set of all possible BPMN models, we willconsider and discover well-formed BPMN models, which arerevealed as weakly connected graphs with a source and sinknodes.Definition 10 (Well-formed BPMN Model) A BPMN modelis called well-formed iff every node of this model is on a pathfrom the start event to some end event.Definition 11 (BPMN Model Marking) Let BPMNmodel bea BPMN model with a set of sequence flows SF. A markingM is a multiset over the set sequence flows, i.e., M B(SF).An initial marking Minit is a marking, such that for all sf from , and M (sf) 0, otherwise.SF Minit (sf) 1, if sf estartinitAn illustration for the initial marking is presented in Fig. 6.Each node independently of its type may be enabled, andan enabled node may fire. Let us consider an arbitrary BPMNFig. 7 Firing activity123model BPMNmodel (N , A, G XOR , G AND , estart , E end ,SF, λ) and define its firing rules:1. An activitya A is enabled in a marking M iff sf SF : a(sf) 1) (M sf 1 . Suppose activity ais enabled and this activity may fire, producing a newmarking M , such that M M\ sf 1 a . In otherwords, activity a is enabled in marking M iff it has anincoming sequence flow, which contains at least onetoken. When activity fires, it consumes one token froman incoming sequence flow and produces a token foreach outgoing sequence flow (Fig. 7).2. Exclusive gateways merge alternative paths: The incoming sequence flow token is routed to one of the outgoingsequence flows (Fig. 8).Similar to activities, exclusive gateway gXOR G XOR isenabled in marking M iff there is an incoming sequenceflow, which contains 1 M, at least one token in markingi.e., sf S F : gXOR (sf) 1) (M sf . Incontrast to activities, it produces a token to one of theoutgoing sequence flows. Suppose an exclusive gatewaygXOR consumes a token from an incoming sequence flowsf and produces a token to an outgoing sequence flow sf , and then a new model marking M will be defined as follows: M M\ sf 1 sf 1 .3. A parallel gateway gAND G AND is enabled in marking M iff sf gAND : M(sf) 1, i.e., each incomingsequence flow contains at least one token. An enabledparallel gateway gAND may fire and produce a new mark , i.e., aing: M , such that M M\ gAND gANDparallel gateway consumes a token from each incomingsequence flow and produces a token to each outgoingsequence flow (Fig. 9).4. The unique start event is never enabled, since it does nothave any incoming sequence flow.5. An end event eend E end is enabled in marking M iff sf SF : (sf eend ) (M(sf) 1). When end eventfires, it consumes a token from an incoming sequence flow sf, and yields in a new marking M M\ sf 1(Fig. 10).Fig. 9 Firing parallel gateway

Process mining using BPMN: relating event logs and process modelsexecutions, stopped in markings with tokens on sequenceflows. These sequences of activity labels correspond to theBPMN model deadlocks.Fig. 10 Firing end eventWhen node n N fires, we denote this firing as(BPMNmodel , M) [n (BPMNmodel , M ).We write (BPMNmodel , M) [σ (BPMNmodel , M ) forsome sequence of nodes σ n 1 , . . . , n k N iff thereare markings M0 , . . . , Mk , such that M0 M, Mk M , and for 0 i k the following statement holds(BPMNmodel , Mi ) n i 1 (BPMNmodel , Mi 1 ).Likewise in Petri nets marking M is reachable frommarking M iff there is a sequence σ N , such that(BPMNmodel , M) [σ (BPMNmodel , M ).For some sequence of activity labels σv U A , we write(BPMNmodel , M)[σv (BPMNmodel , M ), if there is σ , suchthat (BPMNmodel , M) [σ (BPMNmodel , M ) and λ(σ ) σv .By R(BPMNmodel , M), we will denote the set of all markings reachable in BPMNmodel from the marking M.To define the notion of language generated by a BPMNmodel, let us first give a definition of a final marking.Definition 12 (Final BPMN Model Marking) LetBPMNmodel be a BPMN model with an initial markingMinit and a set of nodes N . Mfinal is a final markingiff Mfinal R(BPMNmodel , Minit ) and n N M :(BPMNmodel , M) [n (BPMNmodel , M ).As it follows from this definition, the final marking of aBPMN model is the marking, in which no node can fire.Definition 13 (Language of a BPMN Model) Let BPMNmodelbe a BPMN model with an initial marking Minit and a set offinal markings Mfinal . The language of BPMNmodel is a setL BPMNmodel {σv (BPMNmodel , Minit )[σv (BPMNmodel , M) M Mfinal .Thus, we define the language of a BPMN model as a set ofall visible sequences starting in an initial marking and endingin some final marking.According to the BPMN 2.0 specification [6], BPMNmodel gets the status completed iff there is no token remaining. Following the specification, a language of a BPMNmodel can be considered as a union of two disjoint sets:L BPMNmodel VBPMNmodel IBPMNmodel .VBPMNmodel {σv ((BPMNmodel , Minit )[σv BPMNmodel ,M)) ( sf SF : M(sf) 0)} is a set of valid sequences,corresponding to the model executions, which lead to markings with no tokens remaining. Note that according to BPMNsemantics if no tokens remaining, no node is enabled.IBPMNmodel L BPMNmodel \VBPMNmodel stands for a set ofinvalid sequences, which are the traces of the BPMN model3.3 Transition systems, reachability graphs andsimulation relationsIn this subsection, some basic definitions, which are used forthe justification of the conversion algorithms, will be given.Definition 14 (Transition system) Let S and E be two disjoint non-empty sets of states and events, let τ E be aspecial silent event, and let B S E S be a transitionrelation. A transition system is a tuple TS (S, E, B, sin ),where sin S is an initial state. Elements of B are calledtransitions.eWe write s s , when (s, e, s ) B. Assume that s τS : s s, i.e., there is a transition from every state to itself,labeled by τ .A state s is reachable from a

everywhere where BPM is applied. An absolute majority of freeware and commercial BPM tools and Business Suites, like Oracle BPM Suite, IBM Business Process Manager, jBPM, Activiti, Appian BPM Suite, Bizagi BPM Suite, MagicDraw Enterprise Architect (Sparx), Mega Pro