Report

Behavioral Comparison of Process Models Based on Canonically Reduced Event Structures Paolo Baldan Marlon Dumas Luciano García Abel Armas Behavioral comparison of process • Explain the differences between a pair of process models using simple and intuitive statements • Abstract representations based on binary behavioral relations – Event structures, e.g., PES and AES • More expressive formalisms can give smaller representations – AES can provide smaller representations than PES Comparison based on reduced AES • Folding technique does not ensure canonicity – Canonical graph labeling technique a a • Process models can represent infinite behavior. I.e., cyclic behavior. – Error tolerant graph matching techniques – Categorization of discrepancies b Arrange pickup Arrange appt. pickup appt. Arrange delivery Arrange appt. delivery appt. d d Produce ship. Produce notice ship. notice c c – Unfolding technique for computing a finite representation • Provide understandable feedback about behavioral discrepancies b Prepare transp. Prepare quote transp. quote b b Arrange Arrange pickup pickup appt. appt. Arrange a a Prepare Prepare transp. transp. quote c b quote Arrange Arrange delivery delivery appt. appt. c c Arrange delivery delivery appt. appt. c b Arrange Arrange pickup pickup appt. appt. d d Produce Produce ship. ship. notice notice a b Background. Petri nets Prepare transp. quote c b a c b Arrange delivery appt. d Produce ship. notice Arrange delivery appt. Arrange pickup appt. Prepare transp. quote c Arrange pickup appt. Arrange delivery appt. Arrange pickup appt. d Produce ship. notice p7 c b p0 d p6 pc0 p7 cp b a pd7 6 d b b p6 p7 p1 p6 p7 a p0 p3c τc1 p5 τ3 p3 τ1 p5 τ3 p3 τ1 p5 τ3 p5 τ3 pp22 ττ00 Place dp7 p7 c b p1 pp44 p1a p0 c p3 τ1 p5 ττ22 c pp00 b pp11 a d pp66 p0 pp77 p0 c pp33 ττ11 p2 τ2 p4 p pp55 dp7 b p6 pd p7 a a p0 p p1 p d 0 1 a b c b b d d c d a p0 ττ33 p4 τ2 • τ0 Markings: {{p0}, {p1}, {p2}, …} p2 pτ0 p4 p τ2 τ τ • Firing sequence: {{a,b,b…}, …} 2 0 p2 4 τ 2 p4 aτ 0 2 b τ2c • Executions: d {{a,b,c,d}, …} cb b p3c b a p7 p0 c Silent transition Transition p1 a p0 p1 Background. Petri nets τ1 3 p1 a p0 p6 p 6 c a b c p7 p d7 b d d c p0 a c apb0 b0 p1 c ad d p16 b b d b a c dp6 d b p0a p1 ac pd7 c c b cc p0 c b p1 p d p6 d b p1 p6 d p7 c b p7 c ba c d a c d p0 c ad b d ab ddc c c d bb d pd3c τ1 dp5 dτ3 c p b b p0 p1 c a p p 6 7 c pb1 pp6 7 d p7 p6 p1p0 c p0 c d pb3d τ1 p5 cτ3 c b d p p5 τ3 τ 3 c p 1 τ 5 b d 1 3 c p3 τ1 p5 τ3 ab ac c d d c b d d d d τ1 b pp35 ττ3 p5 τ p3 d d cddb b d p3 cτ1 p5b τ3c 1 3 a c b a b b d d c d c d d d b c b d 0 τ p4 p4τ2 τ p2 τa 0 c p4 a d d ac 0 2 p22 d τ00 p44b τ22 d b c d pd a τ0 c p 2 p2 τ0 p4 bτ2 a c d b a b a b b d b ba bb c b d p p 2 3 c b b p1 d pd p b c pc0d a b c c 2 3 d c ddd c c cd c b b b d bd bc c c d a ca a d c d c ad d b d c d d a b d c a d d c a d c d b b b p6 pa dp7 ap7 p0 c a pd1 d ca b d d b d c b d c b 6 b c b p p p p p c 0 1 6 d c b p1 d 0 1 6 7 7 b d d p0 b b d a p7 c b a c p6 b d c d c b d a c b b c c ddd b c d cd c b p d d d 5 p τ3 d c b d c d 1 p p5d τ 3 d d 1 τ3 3 τ1 5 p33 τ11 p55 τ33 c d c d d c b d p p τ 3 1d b d p3 τ1 pd5 τ3 c d c d a d d d p2 τ0 p4 τ2 b d d d d c a a τ0 p4 τ2 b p p τ τ 2 4 0 2 c d p2 τ0 p4 τ2 p2 τ0 a p2 τ0 d p4 bτ2 b d b b dd p p τ0 4 τ2 2 a b b p2 τ0 p4 τ2c b c b b b d d b c c c d d c b ada b c b d d bd c c c c c b p0 c p1 d a p p a 6 7 a d d c b c b d c b d a d c ab b b c p0 p6 c da c d dp7 p1 d d b b p6 p7 a a c p p p p a d b d 0 1 6 7 bd p p b 0 1 c b a pd7b a d c b d p6 b d d b d d c b pb p6 c c0 c d p3 τp16 p5 τp37 d b c b d p7 dcd p1 d p1 c d c d c c d d p5 τ3 c 3 τ1 pd p 3 τc1 p3 τ1 5 p5τ3 d τ a d 3 p3 τ1 c c d p3 τ1 p5 τ3 a d d p p τ3 b d 3 τ1 5 a p3 τ1 p5 τ3 b d a a b a b d{a,b,c}, …} c d Configurations: {{a}, {a,b}, {a,c}, b d c p2 τ0 p4 τ2 a b c b b add d c b c c b c d c db b c c d a ab p2 τ0 p4 aτ2 bdc c d c b a b c b d a c b ba d b b dd dc bd dc d d b a d d d c c b bd b c d d b b d Background(2). Branching process and PES Background(3). PES and AES • AES is a more expressive formalism than PES – Same configurations as PES, but fewer events – Reduction technique (folding) • hp-bisimilarity – Non-canonicity Canonical graph labeling technique • Canonical graph algorithm) labeling techniques (McKay‘s – Associates a graph with a canonical label • Largest lexicographical exemplar representation) adjacency matrix of the (string linear • Keep the order given to the vertices in the largest exemplar • Compute the canonical graph labeling for PES • Weight of the events Canonical folding • Folding of events 1. Lexicographic order on the event’s label 2. Largest set of events 3. Largest weights w.r.t. the canonical graph labeling c a Cyclic process models b c τ1 p1 p0 a d p2 b a τ3 p3 d c • Infinite number of events in branching process d • Infinite number of events in PES c b d • Finite complete prefix unfoldings a c d b c d d b b 0 b 2 c a b d Finite completeb prefix unfolding d b bc c d p0 c d τ1 a τ3 a p2 b p3 b0 d b1 b b5 a d b3 b c c • McMillan d band Esparza – b4 cc c b a c b2 p1 b0 d b c b c based on markings d Truncating techniques d c c c c • Does not areflect all dthe possible causal predecessors d i a b b for any event o b Customized complete prefix unfolding • Khomenko et al. proposes a framework to define a customized complete prefix unfolding • Order for configurations • Set of configurations • Equivalence • Equivalence for capturing causal dependencies – Same markings – The marking was generated by the firing of the same transitions Customized complete prefix unfolding(2) τ0 b • Cyclic behavior: – A transition c is part of cyclic behavior if there is pa configuration with two occurrences of c – Transition c is repeated 0 or more times if it does not occur in all runs c b c p0 τ1 a b d b d b τ1 p2 d c b p3 b p3 d c c c d b dc b e1 c e4 e0 d a d a a τ3 a p1 p2 τ2 c τ3 a p1 0 – Transition c is repeated 1 or more times if it occurs in all runs τ2 a c a τ0 b c d c d b d e11 b e6 b e2 c d c e14c b c c d d c c e5 d i c d b a b b b i a o o c c c c c c Not canonical unfoldingd i a i a o o i d b i b a a o o • It does not guarantee a canonical complete prefix unfolding for equivalent models (pomset-trace equivalence) Comparison a b Prepare transp. quote c b a c b c Arrange delivery appt. Produce ship. notice Arrange delivery appt. Arrange pickup appt. Prepare transp. quote d Arrange pickup appt. Arrange delivery appt. Arrange pickup appt. d Produce ship. notice a b Prepare transp. quote c b a Produce ship. notice Arrange delivery appt. Arrange pickup appt. c b Prepare transp. quote d Arrange pickup appt. Arrange delivery appt. d Produce ship. notice Relations among matched events Mismatchingevents Unmatched repetitive behavior • In model 2, there is a state after the execution of task c where d and c are mutually • There Task bismay an additional occur many occurrence times in of model task b 2;after whereas c in model in model 2 1, it is not repeated exclusive; whereas in model 1, there is a state afterc the execution of b where c can any time occur before d, or c can be skipped • There is an additional occurrence of task c after b in model 2 • Task c may occur many times in model 2; whereas in model 1, it is not repeated any • In model 2, there is a state after the execution of task a where c can occur before d, time or c can be skipped; whereas in model 1, there is a state after the execution of a where c precedes d Arrange delivery appt. Arrange pickup appt. Conclusions • Technique for a behavioral comparison of process models using AES – Canonical folding of AES – Finite representation using Petri net unfoldings • Characterization of cyclic behavior according to task repetitions – Categorization of discrepancies for offering a more understandable feedback Future work • Visualization of discrepancies in the models • Empirical evaluation of the usefulness of diagnostics using real-world process models • Test if a more refined feedback can be given by using other models of concurrency Comparison 1. Consider only common behavior (common labels of tasks) 2. One model can have more behavior than other – Error tolerant graph matching techniques 3. Discrepancies 1. Mismatching relations among matched events (approximate context) 2. Mismatching repetitive behavior 3. Unmatched events (approximate context)