=Paper=
{{Paper
|id=Vol-3730/paper13
|storemode=property
|title=Process Mining Representation using Communication Structured Acyclic Nets (CSA-nets)
|pdfUrl=https://ceur-ws.org/Vol-3730/paper13.pdf
|volume=Vol-3730
|authors=Nadiyah Almutairi,Tuwailaa Alshammari,Mohammed Alahmadi
|dblpUrl=https://dblp.org/rec/conf/apn/AlmutairiAA24
}}
==Process Mining Representation using Communication Structured Acyclic Nets (CSA-nets)==
https://ceur-ws.org/Vol-3730/paper13.pdf
Process Mining representation using Communication
Structured Acyclic Nets (CSA-nets)
Dr. Nadiyah Almutairi1,2 , Tuwailaa Alshammari1 and Mohammed Alahmadi1,3
1 School of Computing, Newcastle University, Science Square, Newcastle upon Tyne, NE4 5TG, United Kingdom
2 Department of Science and Technology, University of Hafr Albatin, Hafr Al-Batin 39524, Kingdom of Saudi Arabia
3 Department of Software Engineering, University of Jeddah, Jeddah 21493, Kingdom of Saudi Arabia
Abstract
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.
Keywords
structured occurrence net, structured acyclic nets, communication structured acyclic net, labeled Petri nets,
model decomposition
1. Introduction
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 [2].
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 language-
based regions.
SON s is generalised in [3] as Communication Structure Acyclic Nets ( CSA -nets) which are
a Petri net-based formalism used to represent the behaviour of Complex Evolving Systems
(CESs). CSA-nets consist of sets of acyclic nets that communicate with each other through a set
of buffer places. These buffer places allow both asynchronous and synchronous communication
PNSE’24, International Workshop on Petri Nets and Software Engineering, 2024
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org)
217
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
between acyclic nets, and so can represent the concurrent behaviour of the system as well as
synchronisation behaviour. They are suitable tools for modelling and visualising the behaviour of
event-based systems.
In this paper, we focus on the outcome of the Petri net decomposition approach presented in
[1]. Essentially, we propose constructing a CSA-net model from the decomposed fragments of a
process model. That is accomplished by identifying each decomposite subnet as an individual
acyclic net and subsequently applying the proposed rules to establish communication via buffer
places.
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.
2. Related work
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, [4] developed a region-
based algorithm for discovering Petri nets from event logs, addressing the challenge of deriving
accurate process models in process mining. Their approach focuses on constructing a bounded
Petri net that encompasses the behaviour observed in event logs, prioritising the generation of
models with minimal behaviour while still capturing the essence of the logged events. This
method is notable for its ability to produce nets that accurately reflect the observed processes,
enhancing the precision of process discovery. The effectiveness of their algorithm is demonstrated
through implementation in a tool and validation on various examples, highlighting its potential
in improving the reliability and accuracy of process mining outcomes. Where in [5] , methods
for identifying workflow models are developed, starting with a "workflow log" that records the
actual execution of the workflow process. Additionally, a new algorithm is introduced to extract
a process model from the log and represent it through a Petri net. The authors demonstrate the
capability of the α-algorithm to effectively mine workflows described by a so-called SWF-net.
An important study in [1], presented a generic approach of decomposing Petri nets for process
mining has been introduced to address the challenges of complexity and scalability in analysing
large process models or event logs. In another words, a decomposition approach for process
mining problems was proposed, in particular, process discovery and conformance checking.
Basically, a process model is decomposed into smaller subnets and the conformance is preformed
to each subnet locally to reduce the computation time.
Generally, a large body of work exists in the literature about Petri nets decomposition and
218
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
composition. For instance, the authors in [6] present a method for increasing productivity in
system development through the use of Petri nets class input-output-place-transition (IOPT)
for modelling. They introduce a technique for partitioning Petri net models into concurrent
sub-models for distributed implementation, extending the model’s capabilities with directed
synchronous communication channels. This approach aims to propose a net-splitting operation
that allows centralised models to be transformed into distributed models suitable for heterogeneous
platforms. The operation includes specific rules for handling structural complexities and ensures
behavioural consistency through node duplication. The approach has been validated through
case studies demonstrating its applicability in co-design techniques. Moreover, [7] presents
a compositional approach for a new extension of ordinary Petri nets called open Petri nets
where the places are distinguished as open (input or output) to represent the interaction with
the environment. In their approach, two independent open nets which they agree on a common
subnet can be glued together to compose a new net. More precisely, a composition operation
pushout is introduced over open nets such that the common part of the component nets is
fused in the composed net. Their approach enables the systematic construction and analysis
of large and complex systems by composing smaller nets and understanding their interactions.
However, only the semantics of deterministic processes are considered. An extended version of
the compositional approach in [7] was introduced in [8]. Hence, non-deterministic processes
semantic is investigated in the compositional approach. Ranked open nets were defined (an
extension of open nets introduced in [7]) where the maximum number of allowed input and output
connections are specified. The composition operation is extended as well to non-deterministic
processes. Modal I/O-Petri Nets (MIOPNs) is introduced in [9] for asynchronous composition via
communication channels. More precisely, the interfaces are defined by labelled Petri nets which
distinguished input and output labels. In their composition approach, individuals components
are connected by channels for asynchronous communication. That is components with shared
input and output actions are connected together with a new place called communication channel.
Generally, the paper investigates how MIOPNs can be utilised to model asynchronous interactions
between components via compositional methodology.
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, [1] proposes
innovative methods for process discovery decomposition and conformance checking decomposi-
tion. In process discovery problem , the approach involves dividing the set of activities into partly
overlapping activity sets, discovering model fragments for each activity set, and then combining
these to form a complete process model. We utilised this approach to represent acyclic nets from
the decomposed sets (nets) identified.
3. Preliminaries
3.1. Acyclic Petri Nets
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.
219
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
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• ).
⋃︁ ⋃︁
init = {p ∈ P | • p = ∅} , Pfin = {p ∈ P | p• = ∅}are the initial places and final
Moreover, Pacnet acnet
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),
init ≜ Pinit is the default initial marking, and M fin ≜ Pfin is the final marking.
and Macnet acnet acnet acnet
• 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
Mi−1 [Ui ⟩acnet Mi , for every 1 ≤ i ≤ k.
• σ = 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 .
init , then σ ∈ sseq(acnet) is a step sequence, and M is a reachable mark-
• If M0 = Macnet k
ing of acnet. Also, if σ cannot be extended further, it is a maximal step sequence in
maxsseq(acnet).
A labeled acyclic Perti net ( [1] ), acnet = (P, T, F, l) is an acyclic Petri net (P, T, F) with
labeling function T ↛ UA where UA is some universe of activity labels. Let σv = {a1 , a2 , . . . an } ∈
UA ∗ be a sequence of activities. M0 [σv Mk iff there is a step sequence σ ∈ sseq(acnet) such
that M0 [σ ⟩acnet Mk and l(σ ) = σv . Also, dom(l) ⊆ T is the domain of l and the range of l denoted
by rng(l) is the set of the corresponding observable activities.
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) [1].
Example 1. Figure 1 shows a labelled acyclic Petri net (generated using ProM, a pro-
cess mining framework after modifying the event log used in [1]). The set of places are
P = {start, p1 , . . . , p9 , end}, and the transitions are T = {t1 ,t2 , . . . ,t11 }. t1 is enabled at the
initial marking Minit = {start}, so {start}[t1 ⟩. Hence, t1 can be fired and produce new mark-
ing M ′ = {p1 , p2 } denoted by {start}[t1 ⟩{p1 , p2 }. One of the maximal step sequences is
σ = {t1 ,t3 ,t4 ,t5 ,t10 }. The labelling function is dom(l) = {t1 ,t3 ,t4 ,t5 ,t8 ,t9 ,t10 } (visible tran-
sitions). with l(t1 ) = a, l(t3 ) = b, l(t4 ) = c, l(t5 ) = d, l(t8 ) = f , l(t9 ) = g, l(t10 ) = h such
that:
a = "register request" b = "examine file" c = "check ticket"
d = "decide" f = "send acceptance letter" g = " pay compensation"
h = "send reject letter".
220
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
p3 t10 end
h
p1 t2 t5 p4 t7 p6 p9
b d f t11
start t3 p7 t8 p10
a g
t1 p2 p5 t9
c
t4
Figure 1: A labelled acyclic net
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 [1].
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 [1]. There are some
work in the literature regarding decomposing process mining problems [1, 10, 11, 12, 13].
More precisely, if there is a system net SN = (acnet, Minit , Mfin ), then it is decomposed into
set of subnets SN = {SN 1 , SN 2 , . . . , SN n } such that SN i = (acneti , Minit
i , M i ) where acneti =
fin
i i i i
(P , T , F , l )[1].
221
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
The decomposition approach in [1] is valid if all the resulted subnets satisfy the original
labelling function. It means that each place belongs to only one subnet and each invisible
transition also belongs to only one subnet. Hence, only visible transitions can appear in different
subnets. However, if there are different visible transitions with the same label, then they must
belong to one subnet. Finally, each edge appears only in one subnet.
Example 2. Figure 3.1 shows the decomposition of the net in Figure 1 based on the de-
composition approach in [1]. Basically, the net in Figure 1 is decomposed into six subnets,
SN = {SN 1 , SN 2 , . . . , SN 6 }. Their approach of the decomposition produces a maximal partition-
ing of the overall process model. That means each subnet is as small as possible. Also, note that
only the visible transitions with unique labels appear in multiple subnets. Hence, their decom-
position approach is not only about the partitioning the edges, but it considered the transitions
labels.
p3
p1 t2
start t1 b d
a t1 t3 t5
a
SN1 SN2
p2
c p5
t1 t4 c d
a SN3 t4 SN4 t5
t10 end
h
t10
h t8 p9
t5 p4 t7 p6 t8 f
d f t11
p7 t9 t9 p10
SN5 g g SN6
Figure 2: The decomposition for the net in Figure 1 based on the decomposition approach defined in
[1].
4. Communication Structured Acyclic Nets (csa-nets)
Communication Structured Acyclic Nets (CSA-nets) are derived from Structured Occurrence Nets
(SON) which are a Petri net-based formalism and introduced in [14, 15] and elaborated in [16].
CSA -nets comprise of multiple acyclic nets that are linked through unique elements referred to
222
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
as buffer places. Buffer places are capable of modelling both asynchronous and synchronous
communication.
SON can be used as a framework for visualising and analysing behaviour of Complex Evolving
Systems (CESs). For example, in [17], SON were used to support the analysis of evidence related
to the activities of complex systems, including cybercrime and major accidents. The goal was to
indicate those responsible for cybercrime or identify the causes of accident. Also, SON were used
in [18] as a framework for modelling cybercrime investigation. Other work on SON are related to
events extraction [19, 20].
A recently designed and implemented tool SONCraft [21] (based on the WORKCraft plat-
form [22, 23] which is a flexible common underpinning for graph based models) provides an
extensive and powerful support for dealing with models of complex evolving systems based
on SON, including visualisation and verification. Generalising SON as CSA-nets, [24] verifies
its behavioural properties using SAT solver. Moreover, improving its visualisation aspects was
discussed in [25, 26, 27]. Equipping CSA-nets with probabilities was introduced in [28].
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 ) (n > 1)
such that:
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 .
2. Q is a finite set of buffer places disjoint from Pcsan ∪ Tcsan .
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) ≜ {z | (z, x) ∈ Fcsan ∪Wcsan } preacnet (X) ≜ {precsan (z) | z ∈ X}
⋃︁
postcsan (x) ≜ {z | (x, z) ∈ Fcsan ∪Wcsan } postcsan (X) ≜ {postcsan (z) | z ∈ X} .
⋃︁
223
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
acnet1 p2
p1 a b p4
p3
c d
q1 q2 q3
e f
p5 p6 p7
acnet2
Figure 3: Communication structured acyclic net csan.
4.1. Step sequence semantics
Definition 2 (step and marking [3]). Let csan be a CSA-net.
1. markings(csan) ≜ 2Pcsan ∪Qcsan are the markings.
init ≜ Pinit is the default initial marking.
2. Mcsan csan
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
init = M init ∪ M init · · · ∪ M init
acyclic nets. More precisely, Mcsan acnet1 acnet2 acnetn with an assumption that the
init
buffer places are always excluded from the initial marking Mcsan .
Definition 3 (enabled and executed step [3]). Let M be a marking of csan.
1. enabledcsan (M) ≜ {U ∈ steps(csan) | precsan (U) ⊆ M ∪ (postcsan (U) ∩ Q)} are the steps
enabled at M.
2. A step U enabled at M can be executed yielding a new marking M ′ ≜ (M ∪ postcsan (U)) \
precsan (U). This is denoted by M[U⟩csan M ′ . ♢
Definition 4 ( step sequence [3]). Let M0 , . . . , Mk (k ≥ 0) be markings and U1 , . . . ,Uk be steps
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 .
init [σ ⟩
2. sseq(csan) ≜ {σ | Macnet csan M} are the step sequences
3. maxsseq(csan) ≜ {σ ∈ sseq(csan) | ¬∃U : σU ∈ sseq(csan)} are the maximal step se-
quences.
4. reachable(csan) ≜ {M | Mcsan init [⟩
csan M} are the reachable markings.
5. finreachable(csan) ≜ {M | ∃σ ∈ maxsseq(csan) : Mcsan init [σ ⟩
csan M} are the final reachable
markings.
224
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
♢
If k = 0 then the corresponding step sequence σ is the empty sequence denoted by λ .
5. Composing a csa-net model from a decomposed process
model
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 indepen-
dently. [29] suggested establishing communication between decomposed sub-models. Basically,
they proposed an approach of composing a system model using the decomposed components.
Net Splitting operation was defined as a new Petri net operation. Using this operation, a Petri
net is split into several subnets. Then, directed synchronous communication channels are added
to represent the communication between the resulted components. Also, a Petri net model is
partitioned into disjoint sub-models using Split operation. These sub-models are associated with
component with independent execution. Then, the whole system model is composed by modelling
of communication channels among these components [30]. In the same vein, we would like to
reuse the decomposed subnets to compose a CSA-net model.
Next we introduce our approach of constructing a CSA-net model which is based on the result
of decomposing a system net defined in [1]. Basically, composing a CSA-net model requires
identify the overlapped visible transitions between the subnets and link them using asynchronous
communication and buffer places. Recall that the decomposition approach in [1] allows only
visible transitions to be shared between the subnets. These overlapped visible transitions are
always the last and first nodes of any two subnets. Basically, for two subnets SN i and SN j where
i < j and their sets of transitions are T i and T j respectively, if t ∈ T i ∩ T j then it is the first node
of SN j and the last node of SN i . Hence, for any two subnets SN i , SN j , let IntersectTran be the
set of these overlapped visible transitions. Also, let T i = {t1i , . . . ,tmi } be the set of transitions of
the subnet SN i . Similarly, let T j = {t1j , . . . ,trj } be the set of transitions of the subnet SN j . Then,
tmi = t1j ∈ IntersectTran. Then, to compose a CSA-net model from the decomposed subnets,
an asynchronous communication between the subnets using their overlapped visible transitions
is added. In this case, a buffer place q is added such that (tmi , q) , (q, (t • 1j )• ) ∈ W . Adding
asynchrounous communication and the buffer place q represents the global causality between the
subnets SN i and SN j .
The steps of composing a CSA-net model from the decomposed subnets are as follows:
Let SN be a system net and the set {SN 1 , . . . , SN n } be its maximal decomposed subnets. Then its
composed CSA-net model can be constructed as follows:
1. for each subnet SN i , an initial marking is added where 1 < i ⩽ n. Let the set of all new
initial markings be SN(Minit )
2. for each subnet SN i , a final marking is added where 1 ⩽ i < n. Let the set of all new added
final markings be SN(Mfin )
225
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
3. for each two subnets SN i , SN j where 1 ⩽ i < j ⩽ n and T i = {t1i , . . . ,tmi }, T j = {t1j , . . . ,trj }
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 = t1j ∈ IntersecTran. Finally, t1j ∈ T j is removed from T j .
In order to composing a CSA-net model from the decomposed subnets, we assume that each
subnet SN i is an acyclic net acnet.
SN1
start t1
a
q1
SN3
p2
c
t4
Figure 4: Composing two subnets SN1 and SN3 in Figure 2.
Example 3. Figure 4 shows an example of our approach. Subnets SN 1 and SN 3 in Figure 2
both have visible transition t1 , l(t1 ) = a. The presence of t1 in SN 3 captured the local causality
between t1 and other transitions of SN 3 . 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 SN 1 and SN 3 such that (t1 , q1 ) and (q1 ,t4 ). This asynchronous communication replaces
the local causality between t1 and t4 in SN 3 . Hence, t1 is removed from SN 3 , however its impact
is implicitly captured by the occurrence of t1 in SN 1 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 SN 1 only final
marking is added, however, subnet SN 3 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 [1].
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 [1]. A composed communication structured acyclic net
(or CCSA-net) is a tuple
ccsan = (SN 1 , . . . , SN n , Q,W ) (n > 1)
such that:
226
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
1. SN1 , . . . , SNn are subnets. We also denote:
Pcsan = P1 ∪ · · · ∪ Pn ∪ SN(Minit ) ∪ SN(Mfin )
Tcsan = T 1 ∪ · · · ∪ T n
Fcsan = F 1 ∪ · · · ∪ F n .
2. Q is a finite set of buffer places defined as in Definition 1.
3. for each two subnets SNi , SN j where 1 ⩽ i < j ⩽ n and T i = {t1i , . . . ,tmi }, T j = {t1j , . . . ,trj }
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 , t1j ∈ IntersecTran and they carry the same label.
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 SN 1 , so
it is the last node. However, it is first node in SN 2 . 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 SN i where 1 < i ≤ 6. Also, the new added final markings are for
the subnets SN i where 1 ≤ i < 6. The initial and final markings for SN 1 and SN 6 are those of
the original net in Figure 1 respectively. Hence, even though the subnets SN 2 , ..., SN 6 become
system nets, non of their visible transitions are fireable, their visible transitions are fireable when
the transitions of SN 1 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.
Then, for every maximal step sequence σ in ccsan, σ ∈ maxsseq(ccsan) there is a maximal step
sequence σ ′ in acnet, σ ′ ∈ maxsseq(acnet) such that σ ∩ T = σ ′ .
Our compositional approach and the compositional proposed in [7, 8] are different in several
aspects. In [7, 8], identifying a common subnet between two independent nets is required to
compose them into a new net. As the open places were classified into open and output, they were
227
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
SN1
start t1
a
SN2 q2
q1
SN3
t2 p3 t5 p2 t4
d c
p1
b
t3
q3
SN4
p5 t5
d
q4
q5
SN5
t10
h
p4 p6 t8
f
t7 p7 t9
g
q7 q6
SN6
p10 end
p9 t11
Figure 5: Composing csa-net model from the decomposed subnets in Figure 2.
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
228
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
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 [9]. Finally, the proposed compositional
technique is introduced in the context of process mining.
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 [31, 18, 19, 24, 26, 25, 32] was created manually. Our approach provides a
mechanism of constructing a CSA-net from an event log after decomposing the associated process
model. We believe that CSA-net is a suitable modelling representation for the context of process
mining. Due to the structure of CSA-net where each component is independent, employing it for
process mining would reduce the time computation for process mining related problems, specially
conformance checking and process discovery. In fact, performing conformance checking for a set
of small subnets is more efficient compared for a large model [1]. The motivation for process
mining originates from the presence of event data. Although event records can accumulate to
terabytes in size, performance becomes an increasingly important factor to consider. In order
to effectively ensure satisfactory response times , distributed the analysis across a network of
computers is the most feasible strategy [12, 10]. Moreover, utilisation CSA-net for the purpose
of process mining would not only be useful in terms of performance, but also provide localised
diagnostics and improve the visualisation.
6. Conclusion
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.
References
[1] W. M. P. van der Aalst, Decomposing petri nets for process mining: A generic approach,
Distributed Parallel Databases 31 (2013) 471–507. URL: https://doi.org/10.1007/s10619-
013-7127-5. doi:10.1007/S10619-013-7127-5.
[2] W. M. Van Der Aalst, B. F. Van Dongen, Discovering petri nets from event logs, in:
Transactions on Petri nets and other models of concurrency vii, Springer, 2013, pp. 372–
422.
[3] M. Alahmadi, S. Alharbi, T. Alharbi, N. Almutairi, T. Alshammari, A. Bhattacharyya,
M. Koutny, B. Li, B. Randell, Structured Acyclic Nets, Technical Report, School of Com-
puting, University of Newcastle upon Tyne, 2023.
229
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
[4] J. Carmona, J. Cortadella, M. Kishinevsky, A region-based algorithm for discovering petri
nets from event logs, in: Business Process Management: 6th International Conference,
BPM 2008, Milan, Italy, September 2-4, 2008. Proceedings 6, Springer, 2008, pp. 358–373.
[5] W. van der Aalst, T. Weijters, L. Maruster, Workflow mining: discovering process models
from event logs, IEEE Transactions on Knowledge and Data Engineering 16 (2004) 1128–
1142. doi:10.1109/TKDE.2004.47.
[6] A. K. H. da Costa, Petri net model decomposition - a model based approach supporting
distributed execution, Ph.D. thesis, Universidade NOVA de Lisboa (Portugal), 2010.
[7] P. Baldan, A. Corradini, H. Ehrig, R. Heckel, Compositional semantics for open petri nets
based on deterministic processes, Mathematical Structures in Computer Science 15 (2005)
1–35.
[8] P. Baldan, A. Corradini, H. Ehrig, B. König, Open petri nets: Non-deterministic processes
and compositionality, in: H. Ehrig, R. Heckel, G. Rozenberg, G. Taentzer (Eds.), Graph
Transformations, 4th International Conference, ICGT 2008, Leicester, United Kingdom,
September 7-13, 2008. Proceedings, volume 5214 of Lecture Notes in Computer Sci-
ence, Springer, 2008, pp. 257–273. URL: https://doi.org/10.1007/978-3-540-87405-8_18.
doi:10.1007/978-3-540-87405-8\_18.
[9] S. Haddad, R. Hennicker, M. H. Møller, Specification of asynchronous component systems
with modal i/o-petri nets, in: M. Abadi, A. Lluch-Lafuente (Eds.), Trustworthy Global
Computing - 8th International Symposium, TGC 2013, Buenos Aires, Argentina, August
30-31, 2013, Revised Selected Papers, volume 8358 of Lecture Notes in Computer Sci-
ence, Springer, 2013, pp. 219–234. URL: https://doi.org/10.1007/978-3-319-05119-2_13.
doi:10.1007/978-3-319-05119-2\_13.
[10] W. M. P. van der Aalst, Decomposing process mining problems using passages, in:
S. Haddad, L. Pomello (Eds.), Application and Theory of Petri Nets - 33rd International
Conference, PETRI NETS 2012, Hamburg, Germany, June 25-29, 2012. Proceedings,
volume 7347 of Lecture Notes in Computer Science, Springer, 2012, pp. 72–91. URL:
https://doi.org/10.1007/978-3-642-31131-4_5. doi:10.1007/978-3-642-31131-4\_5.
[11] W. M. P. van der Aalst, Distributed process discovery and conformance checking, in:
J. de Lara, A. Zisman (Eds.), Fundamental Approaches to Software Engineering - 15th
International Conference, FASE 2012, Held as Part of the European Joint Conferences on
Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012.
Proceedings, volume 7212 of Lecture Notes in Computer Science, Springer, 2012, pp. 1–25.
URL: https://doi.org/10.1007/978-3-642-28872-2_1. doi:10.1007/978-3-642-28872-
2\_1.
[12] C. Bratosin, N. Sidorova, W. M. P. van der Aalst, Distributed genetic process mining, in: Pro-
ceedings of the IEEE Congress on Evolutionary Computation, CEC 2010, Barcelona, Spain,
18-23 July 2010, IEEE, 2010, pp. 1–8. URL: https://doi.org/10.1109/CEC.2010.5586250.
doi:10.1109/CEC.2010.5586250.
[13] J. Carmona, J. Cortadella, M. Kishinevsky, Divide-and-conquer strategies for process min-
ing, in: U. Dayal, J. Eder, J. Koehler, H. A. Reijers (Eds.), Business Process Management,
7th International Conference, BPM 2009, Ulm, Germany, September 8-10, 2009. Proceed-
ings, volume 5701 of Lecture Notes in Computer Science, Springer, 2009, pp. 327–343.
230
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
URL: https://doi.org/10.1007/978-3-642-03848-8_22. doi:10.1007/978-3-642-03848-
8\_22.
[14] B. Randell, Occurrence nets then and now: The path to structured occurrence nets, in: L. M.
Kristensen, L. Petrucci (Eds.), Applications and Theory of Petri Nets - 32nd International
Conference, PETRI NETS 2011, Newcastle, UK, June 20-24, 2011. Proceedings, volume
6709 of Lecture Notes in Computer Science, Springer, 2011, pp. 1–16.
[15] B. Randell, M. Koutny, Failures: Their definition, modelling and analysis, in: C. B.
Jones, Z. Liu, J. Woodcock (Eds.), Theoretical Aspects of Computing - ICTAC 2007, 4th
International Colloquium, Macau, China, September 26-28, 2007, Proceedings, volume
4711 of Lecture Notes in Computer Science, Springer, 2007, pp. 260–274. URL: https:
//doi.org/10.1007/978-3-540-75292-9_18. doi:10.1007/978-3-540-75292-9\_18.
[16] M. Koutny, B. Randell, Structured occurrence nets: A formalism for aiding system failure
prevention and analysis techniques, Fundam. Informaticae 97 (2009) 41–91.
[17] B. Randell, M. Koutny, Structured Occurrence Nets: Incomplete, contradictory and uncertain
failure evidence, Technical Report 1170, School of Computing Science, University of
Newcastle upon Tyne, 2009.
[18] T. Alharbi, M. Koutny, Domain name system (DNS) tunneling detection using structured
occurrence nets (sons), in: D. Moldt, E. Kindler, M. Wimmer (Eds.), Proceedings of the
International Workshop on Petri Nets and Software Engineering (PNSE 2019), volume 2424
of CEUR Workshop Proceedings, CEUR-WS.org, 2019, pp. 93–108.
[19] T. Alshammari, Towards Automatic Extraction of Events for SON Modelling, CEUR
Workshop Proceedings 3170 (2022) 188–201.
[20] T. Alshammari, Integrating nlp and structured occurrence nets for crime modelling: A
pattern-based approach, in: M. Köhler-Bussmeier, D. Moldt, H. Rölke (Eds.), Petri Nets
and Software Engineering 2023 co-located with the 44rd International Conference on
Application and Theory of Petri Nets and Concurrency (PETRI NETS 2023), Lisbon,
Portugal, June 27th, 2023, volume 3430 of CEUR Workshop Proceedings, CEUR-WS.org,
2023. URL: https://ceur-ws.org/Vol-3430/poster2.pdf.
[21] B. Li, B. Randell, A. Bhattacharyya, T. Alharbi, M. Koutny, Soncraft: A tool for con-
struction, simulation, and analysis of structured occurrence nets, in: 18th International
Conference on Application of Concurrency to System Design, ACSD 2018, Bratislava,
Slovakia, June 25-29, 2018, IEEE Computer Society, 2018, pp. 70–74.
[22] Workcraft, https://workcraft.org/, 2018.
[23] I. Poliakov, V. Khomenko, A. Yakovlev, Workcraft - A framework for interpreted graph
models, in: G. Franceschinis, K. Wolf (Eds.), Applications and Theory of Petri Nets, 30th
International Conference, PETRI NETS 2009, Paris, France, June 22-26, 2009. Proceedings,
volume 5606 of Lecture Notes in Computer Science, Springer, 2009, pp. 333–342.
[24] N. Almutairi, M. Koutny, Verification of communication structured acyclic nets using SAT,
in: M. Köhler-Bussmeier, E. Kindler, H. Rölke (Eds.), Proceedings of the International
Workshop on Petri Nets and Software Engineering 2021 co-located with the 42nd Interna-
tional Conference on Application and Theory of Petri Nets and Concurrency (PETRI NETS
2021), Paris, France, June 25th, 2021 (due to COVID-19: virtual conference), volume 2907
of CEUR Workshop Proceedings, CEUR-WS.org, 2021, pp. 175–194.
231
Dr. Nadiyah Almutairi et al. CEUR Workshop Proceedings 217–232
[25] M. Alahmadi, Master channel places for communication structured acyclic nets, in:
M. Köhler-Bussmeier, E. Kindler, H. Rölke (Eds.), Proceedings of the International Work-
shop on Petri Nets and Software Engineering 2021 co-located with the 42nd Interna-
tional Conference on Application and Theory of Petri Nets and Concurrency (PETRI
NETS 2021), Paris, France, June 25th, 2021 (due to COVID-19: virtual conference), vol-
ume 2907 of CEUR Workshop Proceedings, CEUR-WS.org, 2021, pp. 233–240. URL:
https://ceur-ws.org/Vol-2907/paper13.pdf.
[26] M. Alahmadi, Parametrisation of csa-nets, in: M. Köhler-Bussmeier, D. Moldt, H. Rölke
(Eds.), Petri Nets and Software Engineering 2022 co-located with the 43rd International
Conference on Application and Theory of Petri Nets and Concurrency (PETRI NETS
2022), Bergen, Norway, June 20th, 2022, volume 3170 of CEUR Workshop Proceedings,
CEUR-WS.org, 2022, pp. 215–216. URL: https://ceur-ws.org/Vol-3170/poster3.pdf.
[27] M. Alahmadi, Parameterised csa-nets, in: M. Köhler-Bussmeier, D. Moldt, H. Rölke (Eds.),
Petri Nets and Software Engineering 2023 co-located with the 44rd International Conference
on Application and Theory of Petri Nets and Concurrency (PETRI NETS 2023), Lisbon,
Portugal, June 27th, 2023, volume 3430 of CEUR Workshop Proceedings, CEUR-WS.org,
2023, pp. 167–182. URL: https://ceur-ws.org/Vol-3430/paper10.pdf.
[28] N. Almutairi, Probabilistic communication structured acyclic nets, in: M. Köhler-Bussmeier,
D. Moldt, H. Rölke (Eds.), Petri Nets and Software Engineering 2022 co-located with the
43rd International Conference on Application and Theory of Petri Nets and Concurrency
(PETRI NETS 2022), Bergen, Norway, June 20th, 2022, volume 3170 of CEUR Workshop
Proceedings, CEUR-WS.org, 2022, pp. 168–187.
[29] A. K. H. da Costa, Petri net model decomposition-a model based approach supporting
distributed execution, Ph.D. thesis, Universidade NOVA de Lisboa (Portugal), 2010.
[30] A. Costa, L. Gomes, Partitioning of petri net models amenable for distributed execution,
in: 2006 IEEE Conference on Emerging Technologies and Factory Automation, 2006, pp.
1129–1132. doi:10.1109/ETFA.2006.355253.
[31] B. Li, Visualisation and Analysis of Complex Behaviours using Structured Occurrence Nets,
Ph.D. thesis, School of Computing, Newcastle University, 2017.
[32] S. Alharbi, Hierarchical simulation of timed behaviours of structured occurrence nets, in:
M. Köhler-Bussmeier, D. Moldt, H. Rölke (Eds.), Petri Nets and Software Engineering
2023 co-located with the 44rd International Conference on Application and Theory of
Petri Nets and Concurrency (PETRI NETS 2023), Lisbon, Portugal, June 27th, 2023,
volume 3430 of CEUR Workshop Proceedings, CEUR-WS.org, 2023, pp. 143–165. URL:
https://ceur-ws.org/Vol-3430/paper9.pdf.
232