The paper presents Trace Language, a language for compact encoding of process trace sets. Thirteen micro-configurations are proposed and tested over a few process mining algorithms to identify success and failure points of the latter. Trace expressions are developed for the micro-configurations using Trace Language. 1. Introduction ‖ represents trace set with two possible traces {ab, ba} A process is a progression of activities, and its exe- and ‖ represents trace set {abpq, apbq, apqb, pqab, cution stamps footprints in form of series of triggered pabq, paqb}. In the operators below, the operands can be transitions as the process progresses. These footprint individual transitions or composites defined by chronicle trails are known as traces, which together form a trace orderings. Chronicle Ordering is the default operator if set corresponding to the set of traces generated out of there is no operator specified, as in trace abcd, which multiple executions of the process. Process Mining algo- represents → → → . rithms routinely use trace sets to recover or build process Swapper (∦) It operates on chronicle orderings as models from them. We observed that there are certain in- operands, treating them as atomic (indivisible) substrings. herent patterns among processes which we call as micro- It concatenates them in both permutations to represent configurations, that get over-passed by process mining two possible traces. For example, ∦ represents trace algorithms and stand as fracture points for them. At this set {ab, ba} and ∦ represents trace set {abcpqr, stretch, realizing the need of a language that can repre- pqrabc}. The operator is commutative but not associative. sent trace sets compactly, help in automating implemen- Bowtie operator (◁▷) This operator represents a genertations and serve as basis for refinements and improve- ator of two particularly fashioned traces that are strucments in mining algorithms, we propose a compact novel tured as ordered and pairwise concatenations of trantrace language. It serves the purpose of trace set genera- sition sequences sandwiching the common transition tor when used for representing micro-configurations. sequence. The common transition sequence is written The paper first expounds the operators of the Trace as superscript on the operator symbol. For example, Language, followed by a discussion of results enlist- < , >◁▷< , > produces two traces {acd, bce}. ing Trace Language expressions for thirteen micro- The operator is neither commutative nor associative. configurations which were tested over five process min- m-Subsequence Operator (S) This operator repreing algorithms in the Python (pm4py) framework [1]. sents all valid subsequences of length m for the given The algorithms tested are Alpha Mining [2], Alpha(+) unary operand that represents a sequence of chronicle miner [3], Heuristics Miner [4], Inductive Miner [5] and orderings. The subsequences are valid if they are in growDirectly-Follows Graphs (DFG) [6]. ing sequence of chronicles. For example, S2 < > 2. Trace Language Operators represents traces {xy, xz, yz}. With m as 1, the operator Chronicle Ordering (→), Alternative (⋊), Concur- functions as a shredder that creates all traces of length 1. rent (‖) These are basic operations of sequence, choice For example, S1 < > represents traces {x, y, z}. and parallel composition. For example, → → any-Subsequence Operator (S) This unary operarepresents trace set with single trace {abc}, ⋊ rep- tor represents all subsequences that are in growing seresents trace set with two possible traces {a, pqr}, and quence of chronicle orderings of the operand. For example, S < > represents trace set { x, y, xy}. There are no empty or null subsequences. Floating Operator (F) It represents insertion of an indivisible floating operand as prefixed, in-fixed or sufixed subsequence into the divisible host (i.e. base) operand provided as superscript in the operator symbol. For example, < >F<> forms traces cab, acb and abc. Similarly,
International Workshop on Petri Nets and Software Engineering 2022, PNSE’22 $ karnika@cse.iitb.ac.in (K. Shivhare); rkj@cse.iitb.ac.in (R. K. Joshi) https://www.cse.iitb.ac.in/~karnika/ (K. Shivhare); https://www.cse.iitb.ac.in/~rkj/ (R. K. Joshi)
© 2022 Copyright for this paper by its authors. Use permitted under Creative CPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g CCoEmmUoRns LWiceonsrekAstthribouptionP4r.0oIncteerenadtiionnagl s(CC(CBYE4U.0)R.-WS.org) → → where, = ( ⋊ ⋊ ) → → ( ‖ ) where, = ( → ) ⋊
∦ < > <> → (< , >◁▷< , >) < , >◁▷< , > < → >
D()
D<,>() B</,/>()
D<,>()
2 < > B</>() ⋊B</>() < >F<> creates {cdab, acdb, abcd}. This does not include any trace involving d before or before since the floating operand is indivisible. The operator is neither commutative nor associative. References Substring Bypass Operator (B) This ternary opera- [1] A. Berti, S. J. van Zelst, W. van der Aalst, Process mintor operates on one host operand and a bypass pairing, ing for python (pm4py): Bridging the gap between which is a pair of chronicle orderings (substrings). In process- and data science, 2019. host trace, an occurrence of pair’s former substring is [2] W. Aalst, A. Weijters, L. Maruster, Workflow mining: replaced to generate another trace. Substring bypass op- Discovering process models from event logs, IEEE ebryartoeprlgaecneemreantets. Fhoorstetxraamcepalen,dBals/oa<bypass >trarceepfroersmenetds [3] TAr.aWnse.iKjtnerosw,lPerdogceeassndmDinaitnagE: nEgxitneenedriinngg (t2h0e0a4l)p.ha{Bayz/,x,y/z}. <A com p>acttonroetparteiosennfto{rxbyuz,lkaybzy,pxabszs}.results is algorithm to mine short loops (2004). [4] A. Weijters, W. Aalst, A. A. K. Medeiros, Process minSubstring Drop Operator (D) A special case of Sub- ing with the HeuristicsMiner algorithm, Technische string Bypass Operator, it bypasses substring in host Universiteit Eindhoven, 2006. operand with an empty substring, i.e., it drops the speci- [5] S. Leemans, D. Fahland, W. Aalst, Discovering blockifed substring from the host to generate a new trace. For structured process models from event logs - a coneaxnadmDpl,e,D< <>re>prceosnensttrsutcrtascetrsaecte{pseqtrs{,pqqrrss,,pqsr}.s} TsthrueoctriyveoafpPpNroaancdh,Cionn:cInutr.rCenocnyf,. oSpnrAinpgpelri,ca2t0i1o3n. and 3. Results Table 1 shows trace expressions for mi- [6] W. Aalst, Process discovery from event data: Relating croconfigurations (elementary nets in Fig. 1), and suc- models and logs through abstractions, 2018. cess/failures of Alpha (A), Alpha+ (A+), Heuristics (H), Inductive (I) and DFG (D) algorithms in Pm4Py[1] library.