### Transcription

Process mining using BPMN : relating event logs and processmodelsCitation for published version (APA):Kalenkova, A. A., Aalst, van der, W. M. P., Lomazova, I. A., & Rubin, V. A. (2015). Process mining using BPMN :relating event logs and process models. (BPM reports; Vol. 1501). BPMcenter. org.Document status and date:Published: 01/01/2015Document Version:Publisher’s PDF, also known as Version of Record (includes final page, issue and volume numbers)Please check the document version of this publication: A submitted manuscript is the version of the article upon submission and before peer-review. There can beimportant differences between the submitted version and the official published version of record. Peopleinterested in the research are advised to contact the author for the final version of the publication, or visit theDOI 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 pagenumbers.Link to publicationGeneral 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.If the publication is distributed under the terms of Article 25fa of the Dutch Copyright Act, indicated by the “Taverne” license above, pleasefollow below link for the End User Agreement:www.tue.nl/taverneTake down policyIf you believe that this document breaches copyright please contact us at:[email protected] details and we will investigate your claim.Download date: 19. Jan. 2022

Noname manuscript No.(will be inserted by the editor)Process Mining Using BPMN:Relating Event Logs and Process ModelsAnna A. Kalenkova · W. M. P. van der Aalst · Irina A. Lomazova ·Vladimir A. RubinReceived: 03.2015 / Accepted: dateAbstract Process-aware information systems (PAIS) aresystems relying on processes, which involve human andsoftware resources to achieve concrete goals. There is a needto develop approaches for modeling, analysis, improvementand monitoring processes within PAIS. These approachesinclude process mining techniques used to discover processmodels from event logs, find log and model deviations, andanalyze performance characteristics of processes. The representational bias (a way to model processes) plays an important role in process mining. The BPMN 2.0 (BusinessProcess Model and Notation) standard is widely used and allows to build conventional and understandable process models. In addition to the flat control flow perspective, subprocesses, data flows, resources can be integrated within oneBPMN diagram. This makes BPMN very attractive for bothprocess miners and business users. In this paper, we describeand justify robust control flow conversion algorithms, whichprovide the basis for more advanced BPMN-based discovThis work is supported by the Basic Research Program of the NationalResearch University Higher School of Economics.Anna A. Kalenkova · Irina A. Lomazova · Vladimir A. RubinNational Research University Higher School of Economics, Moscow,RussiaE-mail: [email protected] M. P. van der AalstDepartment of Mathematics and Computer Science, EindhovenUniversity of Technology, Eindhoven, The NetherlandsBusiness Process Management Discipline, Queensland University ofTechnology, Brisbane, AustraliaE-mail: [email protected] A. LomazovaE-mail: [email protected] A. RubinE-mail: [email protected] and conformance checking algorithms. We believe thatthe results presented in this paper can be used for a widevariety of BPMN mining and conformance checking algorithms. We also provide metrics for the processes discoveredbefore and after the conversion to BPMN structures. Casesfor which conversion algorithms produce more compact ormore involved BPMN models in comparison with the initialmodels are identified.Keywords Process mining · Process discovery · Conformance checking · BPMN (Business Process Model andNotation) · Petri nets · Bisimulation1 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. For that purposeone of the promising approaches - process mining can beapplied.Process mining is a discipline connecting data miningand process modeling approaches. Process mining offerstechniques for automatic discovery of process models fromevent logs, checking compatibility of process models andevent logs (conformance checking) and enhancing discovered processes with additional data [4, 5]. Process mininghas been successfully applied in a variety of application domains such as healthcare, transportation, tourism and education. There is a IEEE process mining community, includingmore than 60 organizations [21]. Moreover, there is a widerange of research and commercial tools available in thisarea: ProM [35], Disco (Fluxicon), ARIS Process Performance Manager (Software AG), Perceptive Process Mining(Perceptive Software), ProcessAnalyzer (QPR) and Celonis.

2Anna A. Kalenkova et al.Case IDEventTimestampPriceClient IP1121311.book flightget insurancebook flightbook hotelbook flightpayconfirm.2014-12-24 08:30:00:2322014-12-24 08:31:05:1712014-12-24 08:31:08:5432014-12-24 08:32:08:7032014-12-24 08:32:11:5342014-12-24 08:34:17:4562014-12-24 42.45188.44.42.45.Table 1: An event log of a booking process.Today, BPMN 2.0 (Business Process Model and Notation) [30] is the de facto standard notation for modeling business processes understandable by a wide audienceof people. Business analysts and product managers, technical designers and developers, system and enterprise architects effectively use this notation in their everyday job almost everywhere where BPM is applied. An absolute majority of freeware and commercial BPM tools and Business Suites, like Oracle BPM Suite, IBM Business ProcessManager, jBPM, Activiti, Appian BPM Suite, Bizagi BPMSuite, MagicDraw Enterprise Architect (Sparx), Mega Process (MEGA), Signavio Process Editor and others, either natively support BPMN or provide conversion in order to staycompatible and up to date.The representational bias used for process mining isnot only relevant for the understandability of the results:it is also vital to guide process discovery by setting a suitable class of target models. Using the BPMN notation as arepresentational bias within process mining opens excellentperspectives 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 the existing suites (BPMN serves as an interface in this case). Moreover, BPMN models allow for the combination of differentperspectives varying from control flow to the perspective ofresources, thus a holistic view on a process model can beobtained.In this paper we present methods for discovering thecontrol flow perspective of a process in terms of BPMN.It should be noted that process mining offers plenty of algorithms for the control flow discovery, each of them hasits own characteristics. The goal is not to invent new algorithms, but to benefit from the existing ones and to makethem BPMN-compatible. Thus the discovery of the controlflow relies on conversion algorithms and existing processmining techniques. To that end we firstly formalize the semantics for a subset of BPMN models and then present theconversion algorithms from well-known control flow modeling formalisms such as Petri nets (including non-free-choicePetri nets), causal nets [6] and process trees [8] 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 eventlog reflecting a small portion of the history of a ticket booking process, which is presented in Tab. 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 cases execute these activities in a different order.Beside case identifiers, event names, and timestamps, anevent log can contain additional event properties, such ascosts and resources (participants of the process), in this example they are represented by prices and clients ip addresses(Tab. 1).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 hbook f light, get insurance, book hotel, pay, conf irmi5 , hbook f light, book hotel, get insurance, pay, conf irmi4 ,hbook hotel, book f light, get insurance, pay, conf irmi4 ,hbook hotel, get insurance, book f light, pay, conf irmi3 ,hget insurance, book hotel, book f light, pay, conf irmi1 ,hget insurance, book f light, book hotel, pay, conf irmi1 . A Petri net discovered from L by the Alpha mining algorithm [10] is presented in Fig. 1.book hotelbook flightpayconfirmget insuranceFig. 1: A Petri net constructed from the log

Process Mining Using BPMN: Relating Event Logs and Process ModelsWith 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 BPMNnotation now; this BPMN model can be easily imported andexecuted by any of BPM tools mentioned above.3Event logProcess discovery algorithmsPetri netCausal netProcesstreeConversions to BPMN(Section 3, Section 4)bookhotelbookflightBPMNpayconfirmBPMN to a Petri netconversion (Section 6)getinsurancePetri netFig. 2: A BPMN model obtained by a conversion from the Petri netIn order to estimate the advantages of using the BPMNnotation for mining, we additionally compare the complexity of the models produced by the existing control flow discovery algorithms and the complexity of the correspondingBPMN models. We use the various metrics, such as the number of nodes, density, and diameter [34] for this evaluation.We present not only theoretical but also practical evaluationsbased on real-life event logs. Moreover, applied to theseevent logs, the metrics of the discovered BPMN models arecompared to the metrics of the models designed manuallywith a BPMN-editor. This helps us to understand structuraldifferences between models, which are created by processanalysts and models discovered from 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 [7] 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 miningis presented in Fig. 3. The user discovers a BPMN modelby applying discovery and BPMN conversions plugins. Toshow performance and conformance information and to annotate the BPMN diagram the BPMN model is converted toa Petri net, such that replay techniques can be used.The paper is organized as follows. Section 2 introducesbasic definitions and notions, including traces, Petri nets,system nets, (weak) simulation and (weak) bisimulation relations. In Section 3 we propose algorithms for conversionfrom well-known formalisms such as Petri nets to BPMNand prove correctness of these conversions. In Section 4Evaluation of performanceand conformance infoPerformance andconformance infoEnhancement of theBPMN diagram(Section 6)AnnotatedBPMNFig. 3: A general scheme of using BPMN for process miningtransformations of causal nets and process trees to BPMNare introduced. Section 5 contains a set of BPMN simplification rules. In Section 6 a technique for conformance checking and performance analysis on the basis of BPMN modelsis presented. A tool, which implements the proposed conversion and enhancement techniques, is presented in Section 7.Section 8 includes a case study, which shows the results ofan application of the algorithms presented in the paper toreal-life event logs. Also the structural business-processesmetrics are calculated and presented in this section. Section9 concludes the paper.2 PreliminariesIn this section we introduce basic notions, event logs, Petrinets, system nets and BPMN semantics.Multisets are used to present states of Petri nets andBPMN models, also they are used to define event logs, inwhich one trace can appear multiple times.B(A) is the set of all multisets over some set A. Forsome multiset b B(A), b(a) denotes the number of timeselement a A appears in b. By b [a1 2 , a2 3 ] we denote

4Anna A. Kalenkova et al.that elements a1 , a2 A appear in b two and three timesrespectively.The sum of two multisets b and b0 over set A is definedas: (b ] b0 )(a) b(a) b0 (a) for all a from A. We say thatb b0 iff a A : b(a) b0 (a). For two multisets b andb0 over set A, such that b b0 , the difference function isdefined as: (b\b0 )(a) b(a) b0 (a). The size of aPmultisetb over set A is denoted by b and defined as b b(a).a ASets will be considered as a special case of multisets, whereeach element can appear 0 or 1 times. Thus, operations applicable to multisets can be applied to sets.Function f : X 9 Y is a partial function withdomain dom(f ) X and range defined as rng(f ) {f (x) x dom(f )} Y . f : X Y is a total function, i.e., dom(f ) X. Let f : X 9 Y be a partialfunction, f can be applied to sequences of X using the recursive definition f (hi) hi and for some σ X andx X f (hx · σi) hf (x)i · f (σ), if x dom(f ) andf (hx · σi) f (σ) otherwise.2.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.Pictorially, places are represented by circles, transitionsby boxes, and the flow relation F by directed arcs. Placesmay carry tokens represented by filled circles. A currentmarking M is designated by putting M (p) tokens into eachplace p 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 ) [ti, 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 isremoved from each of the input places t and one token produced for each of the output places t . Formally:M 0 (M \ t) ] t is the marking resulting from firing enabled transition t in marking M of Petri net PN.(PN, M ) [ti (PN, M 0 ) denotes that t is enabled in M andfiring results in marking M 0 .Let σ ht1 , ., tn i T be a sequence of transitions. (PN, M ) [σi (PN, M 0 ) denotes that there is a set ofmarkings M0 ,M1 ,.,Mn , such that M0 M , Mn M 0 ,and (PN, Mi ) [ti 1 i (PN, Mi 1 ) for 0 i n. We saythat M 0 is reachable from M if there exists σ, such that(PN, M ) [σi (PN, M 0 ).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 function l T 9 UA where UA is some universe of activity labels. Letσv ha1 , ., an i UA be a sequence of activity labels.(PN, M )[σv . (PN, M 0 ) iff there is a sequence σ T suchthat (PN, M ) [σi (PN, M 0 ) and l(σ) σv .If t / dom(l), transition t is called invisible. An occurrence of visible transition t dom(l) corresponds to observable activity label l(t).In the context of process mining we normally consider so-called complete firing sequences, 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.Definition 6 (Language of a System Net) Suppose thatSN (PN, Minit , Mfinal ) is a system net. Language LSNof SN will be defined as a set of all visible execution sequences starting in Minit and ending in Mfinal , i.e., LSN {σv (PN, Minit )[σv . (PN, Mfinal )}.Event logs are considered as a starting point in the context of process mining, so let us give their formal definition.Definition 7 (Trace, Event log) Let A UA 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 eventlog.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 netPN (P, T, F, l) are called free-choice iff for any two transitions t1 , t2 T with t1 t2 6 holds t1 t2 .2.2 BPMN semanticsIn this subsection we will present an approach for the formalization of BPMN control flow semantics based on a concept of token. This formalization will give an ability to justify the conversion algorithms presented later in this paper.

Process Mining Using BPMN: Relating Event Logs and Process Models5We restrict ourselves to the core set of BPMN elements,which includes activities, start and end events, exclusiveand parallel gateways. We hope that these initial results willgive a basis for formal description of more advanced BPMNmodeling constructs.Let us give a formal definition of a BPMN model.Definition 11 (BPMN Model Marking)Let BPMNmodel be a BPMN model with a set of sequenceflows SF. A marking M is a multiset over the set sequenceflows, i.e., M B(SF). An initial marking Minit is a marking, such that for all sf from SF Minit (sf) 1, if sf e start ,and Minit (sf) 0, otherwise.Definition 9 (BPMN Model)A BPMN model is a tuple BPMNmodel (N, A,GXOR , GAND , estart , Eend , SF, λ), whereAn illustration for the initial marking is presented inFig. 5.– N is a set of flow nodes,– A N is a set of activities,– GXOR N , GAND N are sets of exclusive and parallelgateways,– estart N is a start event,– Eend N is a set of end events,– sets A, GXOR , GAND , {estart }, Eend form a partition of N ,– SF N N is a set of sequence flows,– λ : N 9 UA is a labeling function, where UA is someuniverse of activity labels,– start event estart doesn’t have incoming sequence flows,and has not more than one outgoing sequence flow,– end events from Eend don’t have outgoing sequenceflows.Figure 4 shows the core BPMN constructs used tomodel . 5: Initial markingEach node independently of its type may be enabled, anenabled node may fire. Let us consider an arbitrary BPMNmodel BPMNmodel (N, A, GXOR , GAND , estart , Eend , SF, λ)and define its firing rules:1. An activity a A is enabled in a marking M iff sf SF : ( a(sf) 1) (M sf 1 ). Suppose activity a is enabled, this activity may fire,a new producing marking M 0 , such that M 0 M \ sf 1 ] a . In otherwords activity a is enabled in marking M iff it has anincoming sequence flow, which contains at least one token. When activity fires it consumes one token from anincoming sequence flow and produces a token for eachoutgoing sequence flow (Fig. 6).activitysequence flowastart eventaend eventFig. 6: Firing activityFig. 4: Core BPMN modeling constructsLet n N be an arbitrary BPMN model node, the presetn 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, whichare revealed as weakly connected graphs with a source andsink nodes. Definition 10 (Well-formed BPMN Model)A BPMN model is called well-formed iff every node of thismodel is on a path from the start event to some end event.2. Exclusive gateways merge alternative paths: the incoming sequence flow token is routed to one of theoutgoing sequence flows (Fig. 7). Similar to activities exclusive gateway gXOR GXOR is enabled inmarking M iff there is an incoming sequence flow,which contains at least one token in marking M , i.e., sf SF : ( gXOR (sf) 1) (M sf 1 ). Incontrast to activities it produces a token to one ofthe outgoing sequence flows. Suppose an exclusivegateway gXOR consumes a token from an incomingsequence flow sf and produces a token to an outgoing sequence flow sf', then a new model 1 marking 00M will be defined as follows: M M \ sf ] sf'1 .

6Anna A. Kalenkova et al.gXORgXORFig. 7: Firing exclusive gateway3. A parallel gateway gAND GAND is enabled in markingM 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 marking: M 0 , such that M 0 M \ gAND ] gAND, i.e., aparallel gateway consumes a token from each incomingsequence flow and produces a token to each outgoingsequence flow (Fig. 8).gANDgANDFig. 8: Firing parallel gateway4. The unique start event is never enabled, since it doesn’thave any incoming sequence flow.5. An end event eend Eend 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 0 M \ sf 1(Fig. 9).eendeend For some sequence of activity labels σv UAwe write(BPMNmodel , M )[σv . (BPMNmodel , M 0 ), if there is σ, suchthat (BPMNmodel , M ) [σi (BPMNmodel , M 0 ) and λ(σ) σv .By R(BPMNmodel , M ) we will denote the set of allmarkings 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 marking Minit and a set of nodes N . Mfinal is a final marking iff Mfinal R(BPMNmodel , Minit ) and n N @M 0 : (BPMNmodel , M ) [ni (BPMNmodel , M 0 ).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) LetBPMNmodel be a BPMN model with an initial markingMinit and a set of final markings Mfinal . The languageof BPMNmodel is a set LBPMNmodel {σv (BPMNmodel ,Minit )[σv . (BPMNmodel , M ) M Mfinal }.Thus, we define the language of a BPMN model as aset of all visible sequences starting in an initial marking andending in some final marking.According to the BPMN 2.0 specification [30] 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:LBPMNmodel 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 toBPMN semantics if no tokens remaining, no node is enabled.IBPMNmodel LBPMNmodel \VBPMNmodel stands for a set of invalid sequences, which are the traces of the BPMN modelexecutions, stopped in markings with tokens on sequenceflows. These sequences of activity labels correspond to theBPMN model deadlocks.Fig. 9: Firing end eventWhen node n N fires we denote this firing as(BPMNmodel , M ) [ni (BPMNmodel , M 0 ).We write (BPMNmodel , M ) [σi (BPMNmodel , M 0 ) forsome sequence of nodes σ hn1 , ., nk i N iff thereare markings M0 , ., Mk , such that M0 M , Mk M 0 , and for 0 i k the following statement holds(BPMNmodel , Mi ) [ni 1 i (BPMNmodel , Mi 1 ).Likewise in Petri nets marking M 0 is reachable frommarking M iff there is a sequence σ N , such that(BPMNmodel , M ) [σi (BPMNmodel , M 0 ).2.3 Transition systems, reachability graphs and simulationrelationsIn 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.

Process Mining Using BPMN: Relating Event Logs and Process ModelseWe write s s0 , when (s, e, s0 ) B. Assume thatτ s S : s s, i.e., there is a transition from every state toitself, labeled by τ .A state s is reachable from a state s0 iff there is a (possibly empty) sequence of transitions leading from s to s0 (de τnoted by s s0 ). The reflexive transitive closure of wille000 e000be denoted as . By s s we denote s s s s0 ,0i.e., s can be reached from s via e preceded and followedby zero or more τ transitions.A transition system must satisfy the following basic axiom: every state is reachable from the initial state: s S : sin s.Definition 15 (Simulation) For transition systems: TS (S, E, B, sin ) and TS' (S 0 , E, B 0 , s0in ) relation R S S 0is called a simulation iff:– (sin , s0in ) R,ee– (u, v) R e E: if u0 : u u0 then v 0 : v v 0and (u0 , v 0 ) R.Definition 16 (Weak simulation) Let us consider twotransition systems: TS (S, E, B, sin ) and TS' (S 0 , E, B 0 , s0in ). Relation R S S 0 is called a weak simulation iff:– (sin , s0in ) R,ee– (u, v) R e E: if u0 : u u0 then v 0 : v v0and (u0 , v 0 ) R.Definition 17 (Bisimulation) If R is a (weak) simulationrelation and R 1 is a (weak) simulation relation as well, thenrelation R is called a (weak) bisimulation.Definition 18 (Reachability Graph for a System Net) Areachability graph for a system net SN (PN,Minit , Mfinal ), where PN (P, T, F, l), and l T 9 UA , isa transition system TS (S, E, B, sin ), such that:– S R(SN, Minit ), i.e., the set of states is defined as aset of markings reachable from Minit ,– E rng(l) {τ }, i.e., the set of events is defined as aunion of the range of l and a silent event τ ,– B contains a transition (M, e, M 0 ) iff at least one thefollowing conditions holds:– t T : (SN, M ) [ti (SN, M 0 ), such that l(t) e, ift dom(l), or e τ , otherwise,– M M 0 and e τ , this holds for silent transitionsfrom states to itself.– sin Minit , i.e., the initial state in TS is the initial marking of SN.Definition 19 (Reachability graph for a BPMN model) Areachability graph for a BPMN modelBPMNmodel (N, SF, A, GXOR , GAND , estart , Eend , λ) withan initial marking Minit is defined as a transition systemTS (S, E, B, sin ), such that:7– S R(BPMNmodel , Minit ),– E rng(λ) {τ }, where τ is a special silent event,– (M, e, M 0 ) B iff at least one of the following conditions holds:– there exists n N , such that (BPMNmodel , M ) [ni(BPMNmodel , M 0 ), where λ(n) e, if n dom(λ),or e τ , otherwise,– M M 0 and e τ .– sin Minit .3 Converting process models into BPMNIn this section we will propose algorithms for the conversionfrom well-known formalisms such as Petri nets, causal netsand process trees to BPMN. These formalisms are widelyused within process mining as results of application of process discovery algorithms [9, 10, 12, 16, 20, 26, 36]. Having conversion algorithms to BPMN format will give an opportunity to discover control flow models, which could beintegrated with other process perspectives. The correctnessof the proposed system nets conversion algorithm will beproven.Algorithms for conversion of free-choice workflow nets[3] (a special subset of Petri nets) to workflow graphs (generalization concept for process modeling notations such asBPMN, UML Activity [31], EPC [25, 28], etc) were proposed earlier in [2] and [19]. In our paper we will deal witharbitrary system nets, which have arbitrary Petri nets structures and arbitrary safe initial markings. Also we prove thatthe target model will simulate the behavior of the initial netand vice versa, thus important (in the context of processmining) propositions on the language preservation will beproven.First, let us show that every system net with a safe initial marking can be transformed to an equivalent system net,which contains a unique source place.3.1 Adding a source place to an arbitrary system net with asafe initial markingIn most cases models discovered from event logs arearbitrary system

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