Communication Structured Acyclic Nets (CSA-nets) are derived from Structured Occurrence Nets SON which are a Petri net-based formalism used to represent the behaviour of Complex Evolving Systems (CESs). It consists of sets of Acyclic Nets ANs that communicate with each other through a set of buffer places. It supports the analysis and visualisation of activities of CESs. In this work, we use SONs formalism to represent processes that have been decomposed using approaches in [1], we used SONs to compose the subnets and use its robust representation to analyse and visualise the same model, however, without any existing cycles. Our approach provides a mechanism for composing a SON model by using the decomposed subnets. We argue that the resulting model exhibits similar behaviour to the original model.
Process mining is a technique that combines data mining and process analysis to extract valuable
insights from event logs generated by information systems. Its aim is to discover, monitor,
and improve real processes by extracting knowledge related to these processes from event
logs recorded during the execution of business operations. Process mining utilises various
techniques, including process discovery, which involves deriving process models from event logs;
conformance checking, which compares the actual processes to predefined models; and process
enhancement, which improves processes based on insights gained from event logs [
Petri nets are one of the popular models for representing processes in process mining. Petri nets can effectively capture concurrency, conflict, and synchronisation aspects of process flows between processes or activities. Specifically, different techniques and algorithms can be used to generate Petri nets from event logs such as the α -algorithm, state-based regions, and languagebased regions.
SONs is generalised in [
In this paper, we focus on the outcome of the Petri net decomposition approach presented in
[
The remainder of this paper is organised as follows: Section 2 summarise some of the existing knowledge and related work. Basic properties of acyclic nets are introduced in the preliminaries Section 3. Section 4 introduces CSA-nets and some of the definitions, while Section 5 discusses the steps taken to compose SON models from decomposed process model. Section 6 concludes our study summarising our findings.
Various algorithms utilise Petri nets as representations for process mining. Region-based process
discovery techniques and α-algorithm are examples of such techniques. Basically, α-algorithm
can be used to construct a Petri net process model to describe behaviour from an event log,
which consists of a set of traces (sequence of events). This is known as process discovery
problem. Also, measuring the differences between the observed behaviour (captured by the
traces in the event log) and the modelled behaviour (firing sequence of a Peti net) for a given
event log and Petri net is known as conformance checking problem. In the context of process
mining, these two problems are formulated using Petri nets. For instance, [
An important study in [
Generally, a large body of work exists in the literature about Petri nets decomposition and
composition. For instance, the authors in [
Despite the fact that there exists an extensive literature on the approaches of net composition
and decomposition, yet difficulties dealing with large event log still an issue. Hence, [
This section provides basic concepts related to acyclic Petri nets and event logs. Acyclic nets can represent alternative ways of interpreting what has happened, and so may exhibit (backward and forward) non-determinism.
An acyclic net is a triple acnet = (P, T, F), where P and T are disjoint finite sets of places and transitions respectively, and F ⊆ (P × T ) ∪ (T × P) is a flow relation such that: (i) P is nonempty and F is acyclic; and (ii) for every t ∈ T , there is p ∈ P such that pFt. Graphically, places are represented by circles, transitions by boxes, and arcs between the nodes represent the flow relation If needed, we denote P by Pacnet, etc. For all x ∈ P ∪ T , • x = preacnet (x) ≜ {z | zFx} and x• = postacnet (x) ≜ {z | xFz} (and similarly for sets of nodes • X = ⋃︁x∈X • x and X • = ⋃︁x∈X x• ). Moreover, Paincnitet = {p ∈ P | • p = ∅} , Pafincnet = {p ∈ P | p• = ∅}are the initial places and final places respectively.
Given an acyclic net, its execution proceeds by the occurrence (or firing) of sets of transitions. Let acnet = (P, T, F) be an acyclic net.
• markings(acnet) ≜ {M |⊆ P} are the markings (shown by placing tokens within the circles), ifn ifn and Maincintet ≜ Paincnitet is the default initial marking, and Macnet ≜ Pacnet is the final marking. • steps(acnet) ≜ {U ⊆ T | U ̸= ∅ ∧ ∀t ̸= u ∈ U : • t ∩ • u = ∅} are the steps. • enabledacnet(M) ≜ {U ∈ steps(acnet) | • U ⊆ M} are the steps enabled at a marking M, and a step U enabled at M can be executed yielding a new marking M′ ≜ (M ∪ U • ) \ • U . This is denoted by M[U ⟩acnet M′.
Let M0, . . . , Mk (k ≥ 0) be markings and U1, . . . ,Uk be steps of an acyclic net acnet such that
• σ = U1 . . .Uk is a step sequence from M0 to Mk
denote by M0[σ ⟩acnet Mk, and M0[⟩acnet Mk denotes that Mk is reachable from M0. • If M0 = Maincintet, then σ ∈ sseq(acnet) is a step sequence, and Mk is a reachable marking of acnet. Also, if σ cannot be extended further, it is a maximal step sequence in maxsseq(acnet).
A labeled acyclic Perti net ( [
For each transition t ∈ T , t is called invisible if it is without a label, t ∈/ dom(l), however, it is
visible when l(t) ∈ dom(l). Note that occurrence of visible transition t corresponds to observable
activity l(t) [
Example 1. Figure 1 shows a labelled acyclic Petri net (generated using ProM, a
process mining framework after modifying the event log used in [
b = "examine file" c = "check ticket" f = "send acceptance letter" g = " pay compensation" start a t1 p1 p2 t2 b t3 c t4 p3 p5
end t11
Whereas, the invisible transitions are t2,t7,t11 which are unlabelled transitions (silent action). Finally, for the sequence of activities σv = {a, b, c, d, f , g}, then {start}[σv {end} because there is a step sequence σ = {t1,t3,t4,t5,t7,t8,t9,t11} where l(σ ) = σv
Note that a labelled acyclic Petri net acnet with maximal step sequences (starting from the initial marking and ending in final marking) is called system net and denoted by SN = (acnet, Minit, Mfin ).
Event log are the key concept in the context of process mining. Basically, any event log,
denoted by L, consists of multiset of sequence of events called traces. A trace captures the
evolution (from start to end) of a case, which is a process instance, according to the executed
activities. Note that it is possible for different cases to have the same traces. Hence, one can say
that an event log is multiset of traces [
As indicated earlier, conformance checking and process discovery are related process mining problems. Conformance checking approaches examine to what extend an event log L and a system acyclic net SN = (acnet, Minit, Mfin ) fit together. Basically, it quantifies the consistency between observed behaviour stored in L and the modelled behaviour represented by SN. There are different techniques of conformance checking and exploring them here is out of the scope of this paper.
Performing conformance checking may take long time as a lot of different traces need to be
conformed with a process model which might include an exponential number of traces. For
example, when an event log contains millions of events, the entire event log must be checked in
order to do conformance checking, which is in fact time consuming. To reduce time required for
conformance checking, Petri net and event log are decomposed into smaller fragments. Basically,
after generating a Petri net process model based on the activities in the event log, decomposing
the process model into smaller subnets and performing conformance checking for each subnet
locally reduces the computation time needed for the conformance checking [
More precisely, if there is a system net SN = (acnet, Minit, Mfin ), then it is decomposed into
set of subnets SN = {SN1, SN2, . . . , SNn} such that SNi = (acneti, Miinit, Mifni ) where acneti =
(Pi, T i, Fi, li)[
The decomposition approach in [
Example 2. Figure 3.1 shows the decomposition of the net in Figure 1 based on the
decomposition approach in [
p2 SN3
SN2 p5 end p9 p10
t11 SN6 p3 d t5
Communication Structured Acyclic Nets (CSA-nets) are derived from Structured Occurrence Nets
(SON) which are a Petri net-based formalism and introduced in [
SON can be used as a framework for visualising and analysing behaviour of Complex Evolving
Systems (CESs). For example, in [
A recently designed and implemented tool SONCraft [
Figure 3 depicts a simple CSA-net, which comprises two acyclic nets: acnet1 and acnet2. Asynchronous communication between the two acyclic nets is represented by arrows, as seen between the transitions c and a in different acyclic nets linked through a single buffer place q1. Thus, transition a will never be executed before c in any execution sequence. A synchronous communication is represented by arrows pointing in both directions, using buffer places q2 and q3, as observed between transitions b and d. Thus, these two transitions have to be executed simultaneously.
Definition 1 ( CSA-net). A communication structured acyclic net (or CSA-net) is a tuple csan = (acnet1, . . . , acnetn, Q,W ) 1. acnet1, . . . , acnetn are acyclic nets with disjoint sets of nodes (i.e., places and transitions).
We also denote:
Pcsan = Pacnet1 ∪ · · · ∪ Pacnetn Tcsan = Tacnet1 ∪ · · · ∪ Tacnetn
Fcsan = Facnet1 ∪ · · · ∪ Facnetn .
3. W ⊆ (Q × Tcsan) ∪ (Tcsan × Q) is a set of arcs. 4. For every buffer place q: (i) there is at least one transition t such that tW q; and (ii) if tW q and qWu then transitions t and u belong to different component acyclic nets. ♢ That is, in addition to requiring the disjointness of the component acyclic nets and the buffer places, it is also required that buffer places pass tokens between different acyclic nets. To indicate relationships between different nodes, for all x ∈ Pcsan ∪ Tcsan ∪ Qcsan and X ⊆ Pcsan ∪ Tcsan ∪ Qcsan, we denote the directly preceding and directly following nodes as follows: precsan (x) ≜ postcsan (x) ≜ {z | (z, x) ∈ Fcsan ∪ Wcsan} {z | (x, z) ∈ Fcsan ∪ Wcsan} preacnet (X ) ≜ ⋃︁{precsan (z) | z ∈ X } postcsan (X ) ≜ ⋃︁{postcsan (z) | z ∈ X } . acnet1 acnet2 p1 p5 a c e p2 p3 p6
Definition 2 (step and marking [
3. steps(csan) ≜ {U ∈ 2Tcsan \ {∅} | ∀t ̸= u ∈ U : precsan (t) ∩ precsan (u) = ∅} are the steps.
♢
The initial marking of a CSA-net is the union of the initial markings of all the component acyclic nets. More precisely, Mcinsaitn = Maincintet1 ∪ Maincintet2 · · · ∪ Maincintetn with an assumption that the buffer places are always excluded from the initial marking Mcinsaitn.
Definition 3 (enabled and executed step [
enabled at M.
of a CSA-net csan such that Mi− 1[Ui⟩csan Mi, for every 1 ≤ i ≤ k.
1. σ = U1 . . .Uk is a step sequence from M0 to Mk, it is denoted by M0[σ ⟩csan Mk. Moreover,
M0[⟩csan Mk denotes that Mk is reachable from M0. 2. sseq(csan) ≜ {σ | Maincintet[σ ⟩csan M} are the step sequences 3. maxsseq(csan) ≜ {σ ∈ sseq(csan) | ¬∃U : σU ∈ sseq(csan)} are the maximal step sequences. 4. reachable(csan) ≜ {M | Mcinsaitn[⟩csan M} are the reachable markings. 5. finreachable (csan) ≜ {M | ∃σ ∈ maxsseq(csan) : Mcinsaitn[σ ⟩csan M} are the final reachable markings. If k = 0 then the corresponding step sequence σ is the empty sequence denoted by λ .
Composing a CSA-net model from the decomposed subnets is based on the technique of Petri
net model decomposition with distributed execution. This technique can tackle the difficulties
involved in the analysis and modelling of large-scale systems. That is because complex systems
can be decomposed into interconnected subsystems that can be analysed and executed
independently. [
Next we introduce our approach of constructing a CSA-net model which is based on the result
of decomposing a system net defined in [
The steps of composing a CSA-net model from the decomposed subnets are as follows: Let SN be a system net and the set {SN1, . . . , SNn} be its maximal decomposed subnets. Then its composed CSA-net model can be constructed as follows: 1. for each subnet SNi, an initial marking is added where 1 < i ⩽ n. Let the set of all new initial markings be SN(Minit) 2. for each subnet SNi, a final marking is added where 1 ⩽ i < n. Let the set of all new added ifnal markings be SN(Mfin ) 3. for each two subnets SNi, SN j where 1 ⩽ i < j ⩽ n and T i = {t1i, . . . , tmi}, T j = {t1, . . . , trj} j are their set of transitions respectively. Let IntersecTran = T i ∩ T j be the set of their overlapped visible transitions. Then, a buffer place q is added such that (tmi, q), (q, (t• 1j )• ) ∈ W where tmi = t1 ∈ IntersecTran. Finally, t1j ∈ T j is removed from T j.
j
In order to composing a CSA-net model from the decomposed subnets, we assume that each subnet SNi is an acyclic net acnet.
SN1
start SN3 q1 t1 a p2
Example 3. Figure 4 shows an example of our approach. Subnets SN1 and SN3 in Figure 2 both have visible transition t1, l(t1) = a. The presence of t1 in SN3 captured the local causality between t1 and other transitions of SN3. This local causality can be represented globally at the level of subnets. In this case, the buffer place q1 and asynchronous communication are added between SN1 and SN3 such that (t1, q1) and (q1,t4). This asynchronous communication replaces the local causality between t1 and t4 in SN3. Hence, t1 is removed from SN3, however its impact is implicitly captured by the occurrence of t1 in SN1 and captured by buffer place q1 and its arcs. As in CSA-net each acyclic net is independent and it has its own initial and final places, therefore initial and final markings are added for each subnet. In particular, for subnet SN1 only final marking is added, however, subnet SN3 initial marking and final marking are added, which are the gray shaded nodes as depicted in Figure 4 ♢
Therefore, we would like to redefine Definition 1 to be based on the decomposition approach
defined in [
Definition 5 ( CCSA-net). Let SN be a system net , and its maximal decomposition is the set of
the subnets {SN1, . . . , SNn} as defined in [
Pcsan Tcsan Fcsan = = =
P1 ∪ · · · ∪ T 1 ∪ · · · ∪ F1 ∪ · · · ∪
Pn ∪ SN(Minit) ∪ SN(Mfin ) T n
Fn . 2. Q is a finite set of buffer places defined as in Definition 1. 3. for each two subnets SNi, SNj where 1 ⩽ i < j ⩽ n and T i = {t1i, . . . , tmi}, T j = {t1, . . . , trj} j are their set of transitions respectively. Let IntersecTran = T i ∩ T j be the set of their overlapped transitions which carry the same label. Then, a buffer place q is created such that (tmi, q), (q,t1j) where tmi, t1 ∈ IntersecTran and they carry the same label.
j 4. W ⊆ (Q × Tcsan) ∪ (Tcsan × Q) is a set of arcs. ♢ Example 4. Figure 5 shows the result of the CSA-net model composition. Basically, all the decomposed subnets in Figure 2 are reused with additional buffer places between the subnets connecting them using their overlapped visible transitions. For instance, in Figure 2 the subnets SN1 and SN2 both include transition t1 with a label. Note that t1 is only transition in SN1, so it is the last node. However, it is first node in SN2. So, buffer place q2 is added such that (t1, q2) ∪ (q2,t2) ∪ (q2,t3) ∈ W . The rest of the subnets are treated similarly. Worth noticing that in the composed CSA-net model in Figure 5 the initial markings with auxiliary transitions are added for the subnets SNi where 1 < i ≤ 6 (which are the gray shaded nodes). Similarly, final markings are added for the subnets SNi where 1 ≤ i < 6. ♢
Worth to notice that the decomposed subnets in Figure 2 have no initial nor final markings. However, initial and final markings are added when composing them together in the composed CSA-net in Figure 5. Hence, they become system nets. More precisely, the new added initial markings are for the subnets SNi where 1 < i ≤ 6. Also, the new added final markings are for the subnets SNi where 1 ≤ i < 6. The initial and final markings for SN1 and SN6 are those of the original net in Figure 1 respectively. Hence, even though the subnets SN2, ..., SN6 become system nets, non of their visible transitions are fireable, their visible transitions are fireable when the transitions of SN1 are fired. In fact, by removing all the added initial and final markings, we obtain the decomposed subnets in Figure 2. More important, adding the initial and final markings does not change the original behaviour.
Regarding the behaviour preservation of the original net, we would like to point that the composed csan in Definition 5 and the original acyclic net have closely related behaviour. This is formulated in the next result.
Theorem 5.1. Let acnet = (P, T, F, l) be a labelled acyclic net and ccsan be as in Definition 5.
Our compositional approach and the compositional proposed in [
SN5 t2 b t3
SN1 start p3
q4 p4 SN6 t1 a t5 d t10 h t7
p7
p10
p9
t11
p6
q7
end
q1
p2
p5
q3
q5
t4
c
t5
d
used as interfaces between the net and the environment whereas in our compositional approach
the transitions are the interfaces. Also, in our case, there is no need to define the common subnets
between the components to be able to construct the compositional model. Instead, we connect
the subnets which shared the same visible transitions via buffer places. Hence, there is no need to
define a composition operation as we utilise the buffer places to connect the subnets and compose
the CSA-net which is similar to the composition in [
Composing a CSA-net using the decomposed subnets allows us to construct a CSA-net from
a database(i.e., an event log in this case), which has not been addressed so far. CSA-net in all
the previous work [
In this work, we proposed a method to construct CSA-net from decomposed subnets. We argue that CSA-net is a suitable representation for process mining analysis. That is because CSA-net allows individually and locally diagnosis for each acyclic net. Hence, conformance checking can be performed efficiently using CSA-net representation. In future, we plan to implement our approach as a SONCraft plug-in. Furthermore, an experiment will be conducted for conformance checking problem after constructing a CSA-net process model and compare the results with some results exist in the literature. Related formal proofs will be discussed as well.