Representing Block-structured Process Models as Order Matrices: Basic Concepts, Formal Properties, Algorithms [original]

Representing Block-structured Process Models

as Order Matrices:

Basic Concepts, Formal Properties, Algorithms

Chen Li1?, Manfred Reichert2, and Andreas Wombacher3

1Information Systems Group, University of Twente, The Netherlands

[email protected]

2Institute of Databases and Information Systems, Ulm University, Germany

[email protected]

3Database Group, University of Twente, The Netherlands

[email protected]

Abstract. In various cases we need to transform a process model into a

matrix representation for further analysis. In this paper, we introduce the

notion of Order Matrix, which enables unique representation of block-

structured process models. We present algorithms for transforming a

block-structured process model into a corresponding order matrix and

vice verse. We then prove that such order matrix constitutes a unique

representation of a block-structured process model; i.e., if we transform

a process model into an order matrix, and then transform this matrix

back into a process model, the two process models are trace equivalent;

i.e., they show same behavior. Finally, we analyze algebraic properties

of order matrices.

1 Introduction

In various cases we need to transform a process model into a matrix represen-

tation for further analysis. For example, in graph theory adjacency matrices

are often used for various kinds of graph analysis (e.g., reachability analysis or

derivation of minimal spanning tree [25]). In process mining, causal matrices are

used to represent the relationship between transitions in Petri nets. Causal ma-

trices are further applied in genetic process mining to discover a process model

which covers the execution traces of a collection of process instances best [7]. In

the field of data mining, matrices are used to classify, cluster or associate data

[26, 20]. However, all these techniques are focusing on the nodes and edges of a

graph or process model, and cannot be applied in respect to the management of

process changes [12].

In this paper, we introduce the notion of order matrix, which represents all

transitive relations between the activities of a block-structured process model.

In the context of managing process variants [8], for example, we have already

?This work was done in the MinAdept project, which has been supported by the

Netherlands Organization for Scientific Research under contract number 612.066.512.

applied this kind of matrix for measuring the structural similarity between two

process models [13]. We have further used order matrices for mining structurally

different process variants. Here, we aim at discovering a process model that

structurally covers a collection of process variants best [11, 14]. The present paper

focuses on basic concepts, algorithms and formal properties of order matrices,

and less on their use.

The remainder of this paper is organized as follows: Section 2 introduces some

basic definitions needed for understanding this paper. Section 3 then provides the

formal definition of an order matrix and gives an illustrative example. Section 4

presents an algorithm for transforming a block-structured process model into an

order matrix. Section 5 presents an algorithm for transforming an order matrix

back into a block-structured process model. In Section 6, we prove that there

exists a one-to-one mapping between a process model and its order matrix, i.e.,

if one transforms a process model into an order matrix, and then transform

this matrix back into a process model, the two models will be same. Finally, we

present algebraic properties of order matrices in Section 7.

2 Backgrounds

We first introduce basic notions needed in the following:

Process Model: Let Pdenote the set of all sound (i.e., correct) process

models. We denote a process model as sound if there are no deadlocks or un-

reachable activities in the process model [21, 28]. In our context, a particular

process model S= (N, E, . . .)4∈ P is defined in terms of an Activity Net [21].

Nconstitutes the set of activities and Ethe set of control edges (i.e., precedence

relations) linking them. More precisely, Activity Nets cover the following funda-

mental process patterns: Sequence, AND-split, AND-join, XOR-split, XOR-join,

and Loop [27].5These patterns constitute the core set of any workflow specifica-

tion language (e.g., WS-BPEL [3] and BPMN [4]) and cover most of the process

models we can find in practice [36, 15]. Furthermore, based on these patterns

we are able to compose more complex ones if required (e.g., an OR-split can

be mapped to XOR- and AND- splits [19]). Finally, when restricting process

modeling to these basic process patterns, we obtain models that are better un-

derstandable and less erroneous [18, 16]. A simple example of an Activity Net is

depicted in Fig. 1a. For a detailed description and correctness issues we refer to

[21].

Block Structuring: To limit the scope, we assume Activity Nets to be

block-structured, i.e., sequences, branchings (with aforementioned split and join

semantics), and loops are specified as blocks with well-defined start and end

nodes. These blocks may be nested, but must not overlap, i.e., the nesting must

4A Well-structured Activity Net contains more elements than only node set Nand

edge set E, which can be ignored in the context of this paper.

5These patterns can be mapped to other languages as well. For example in Business

Process Execution Language (BPEL), XOR-Split / -join can be represented by ’If’

or ’Pick’, AND-Split / -Join by ’Flow’, and Loops by ’While’ or ’RepeatUntil’ [3].

be regular [21, 10]. A block in a process model Scan be a single activity, a

self-contained part of S, or even Sitself. As example consider process model

Sfrom Fig. 1. Here {A},{A,B},{C,F}, and {A,B,C,D,E,F,G}describe pos-

sible blocks contained in S. Note that we can represent a block Bas activ-

ity set, since the block structure itself already becomes clear from the process

model S. For example, block {A,B}corresponds to the parallel block with corre-

sponding AND-split and AND-join nodes in S. The concept of block-structuring

can be found in languages like WS-BPEL [3]. When compared with non-block-

structured process models, block-structured ones are easier understandable for

users and have less chances of containing errors [23, 16–18]. If a process model is

not block-structured, in most practically relevant cases we can transform it into

a block-structured one (see [31, 18, 10]).

Definition 1 (Trace). Let S= (N, E, . . .)∈ P be a process model. We define

tas a trace of Siff:

–t≡< a1, a2, . . . , ak>(with ai∈N) constitutes a valid and complete exe-

cution sequence of activities considering the control flow defined by S. We

define TSas the set of all traces that can be produced by process instances

running on process model S.

–t(a≺b)is denoted as precedence relationship between activities aand bin

trace t≡< a1, a2, . . . , ak>iff ∃i < j :ai=a∧aj=b.

We only consider traces composing ’real’ activities, but no events related

to silent activities, i.e., nodes in a process model having no associated action

and only existing for control flow purpose [13]. At this stage, we consider two

process models as being the same if they are trace equivalent, i.e., S≡S0iff

TS≡ TS0. Like most process mining approaches [30, 7, 34], the stronger notion

of bi-similarity [9] is not considered in our context.

3 Basic Definition of an Order Matrix

One key feature of our ADEPT change framework is to maintain the struc-

ture of the unchanged parts of a process model [21, 6, 33]. For example, when

deleting an activity this neither influences successors nor predecessors of this

activity, and therefore also not their order relations [24, 22]. To incorporate this

feature in our approach, rather than only looking at direct predecessor-successor

relationships between activities (i.e. control edges), we consider the transitive

control dependencies for each pair of activities; i.e., for a given process model

S= (N, E, . . .)∈ P, for activities ai, aj∈N,ai6=ajwe examine their structural

order relations (including transitive order relations). Logically, we determine or-

der relations by considering all traces in trace set TSproducible by model S.

Fig. 1a shows an example of a process model S. This model comprises process

patterns like Sequence, AND-block, XOR-block, and Loop-block [27]. Here, trace

set TSof Sconstitutes an infinite set due to the presence of the loop-block in S

(cf. Fig. 1b). Such infinite number of traces precludes us to perform any detailed

analysis of the trace set. Therefore we need to transform such infinite trace sets

into a finite representation for further analysis.

3.1 Simplification of Infinite Trace Sets

One common approach to represent a string with infinite length is to represent

it as finite set of n-gram lists [5]. The general idea behind an n-gram list is to

represent a single string by an ordered list of substrings with length n(so-called

n-grams). In particular, only the first occurrence of an n-gram is considered, while

later occurrences of the same n-gram are omitted in the n-gram list. Thus, an

n-gram list represents a collection of strings with different length. In particular,

an infinite language can be represented as finite set of n-gram lists. For example,

a string < abababab > can be represented as 2-gram <$a, ab, ba, b#>, where

(#) represents the start (end) of the string. Such approach is commonly used

for analyzing loop structures in process models [35, 2], or - more generally - in

the context of text indexing for substring matching [1]. Inspired by the n-gram

approach, we define the notion of Simplified Trace Set as follows:

Definition 2 (Simplified Trace Set).

Let Sbe a process model and TSdenote the trace set producible on S. Let Bk,

k= (1, . . . , K)be Loop-blocks in S, and TBkdenote the set of traces producible on

Bk. Let further (tBk)mbe a sequence of m(m∈N) traces < t1

Bk, t2

Bk, . . . , tm

Bk>

with tj

Bk∈ TBk,j∈ {1, . . . , m}. We additionally define (tBk)0=<> as an

empty sequence. If we only consider the activities corresponding to Bk, in any

trace t∈ TSproducible on S,teither has no entries 6or must have structure

< t∗

Bk,(tBk)m>, with t∗

Bk∈ TBkrepresenting the first loop iteration and m∈N0

being the number of additional iterations loop-block Bkis executed in trace t.

We can simplify this structure by using < tBk, τk>instead, where τkrefers to

(tBk)m. When simplifying trace set TSthis way, we obtain a finite set of traces

S, denoted as Simplified Trace Set of process model S.

In our representation of a trace t∈ TS, we only consider the first occurrence

of trace t∗

Bkproducible by block Bkwhile omitting others that occur later within

trace t. Instead, we represent such repetitive entries by a silent activity τk, which

has not associated action but solely exists to indicate omission of other tBk

appearing later in trace t, i.e., τkrepresents the iterative execution of loop-block

Bkcaptured in trace t.7When omitting repetitive entries within trace set TS,

we obtain a finite trace set T0

Sthat we can use for further analysis. Note that

when dealing with nested loops (e.g., a loop-block Bkcontains another loop-

block Bj), we first need to analyze Bjand then Bk; i.e., we need to first define

τjto represent the iterative execution of loop-block Bjas captured in trace t

and then define τkto represent loop-block Bk.

As example consider process model Sin Fig. 1a. Loop-block B, which is

surrounded by a loop-backward edge, is the block comprising activities Cand

6i.e., the loop-block Bkhas not been executed at all.

7Though this approach is inspired by n-gram, it is different from n-gram representa-

tion of a string. In n-gram the length of the sub-string is a fixed number n, while

in our approach we use τkto represent traces producible by the Loop-block Bk.

Obviously, traces producible by Bkdo not necessarily have same length.

Order matrix AProcess model S

AND-Split AND-Join

XOR-Split XOR-Join

Control Flow Loop

B C D E F G

11 1 1 1

1 1 1 1 1

1 1

1 1 1 1

0 0 0

0 0

0 0 0

0 0

0 0 0 0

- -

10 0 0L L

‘0’ : successor ‘1’ : predecessor

‘+’ : AND-block ‘-’ : XOR-block

‘L’ : Loop

<A,B,D,E,G>;

<B,A,D,E,G>;

<A,B,D,C,F,

G>;

<B,A,D,C,F,

D G

Trace set

Simplified trace set

<A,B,D,E,G>;

<B,A,D,E,G>;

<A,B,D,C,F,G>;

<B,A,D,C,F,G>;

<A,B,D,C,F,C,F,G>;

<B,A,D,C,F,C,F,C,F,G>;

……

(

a) (b) (c)

Fig. 1. a) Process model and b) related order matrix

F; consequently the trace set this block can produce is {<C,F>}. Therefore,

any trace t∈ TSproducible on Shas structure <C,F,(C,F)m>with m∈N0

depending on the number of times the loop iterates. For example, <C,F >,

<C,F,C,F >and <C,F,C,F,C,F >are all valid traces producible by the

loop-block. Let us define a silent activity τcorresponding to block B. Then

we can simplify these traces by <C,F, τ > where τrefers the to the sequence

of the traces producible on B. This way, we can simplify infinite trace set TS

to finite set T0

S={<A,B,D,E,G >, < B,A,D,E,G >, < A,B,D,C,F,τ, G>, <

B,A,D,C,F,τ, G>}(cf. Fig. 1b).

3.2 Defining an Order Matrix

For process model S, the analyzing results of its trace set TSare aggregated in

an order matrix A, which considers five types of order relations (cf. Def. 3):

Definition 3 (Order matrix). Let S= (N, E, . . .)∈ P be a process model

with activity set N={a1, a2, . . . , an}. Let further TSdenote the set of all traces

producible on Sand let T0

Sbe the simplified trace set of S(cf. Def. 2). Let Bk,

k= (1, . . . , K)denote loop-blocks in S. For every Bk, we define silent activity

τk,k= (1, . . . , K)to represent the iterative structure producible by Bkin T0

Then:

Ais called order matrix of Swith Aaiajrepresenting the order relation

between activities ai,aj∈NS{tk¯

¯k= 1, . . . , K},i6=jiff:

–Aaiaj= ’1’ iff (∀t∈ T 0

Swith ai, aj∈t⇒t(ai≺aj))

If for all traces containing activities aiand aj,aialways appears BEFORE

aj, we denote Aaiajas ’1’, i.e., aialways precedes of ajin the flow of control.

–Aaiaj= ’0’ iff (∀t∈ T 0

Swith ai, aj∈t⇒t(aj≺ai))

If for all traces containing activities aiand aj,aialways appears AFTER

aj, we denote Aaiajas a ’0’, i.e. aialways succeeds of ajin the flow of

control.

–Aaiaj= ’+’ iff (∃t1∈ T 0

S, with ai, aj∈t1∧t1(ai≺aj))∧(∃t2∈ T 0

S, with

ai, aj∈t2∧t2(aj≺ai))

If there exists at least one trace in which aiappears before ajand another

trace in which aiappears after aj, we denote Aaiajas ’+’, i.e. aiand ajare

contained in different parallel branches.

–Aaiaj= ’-’ iff ( ¬∃t∈ T 0

S:ai∈t∧aj∈t)

If there is no trace containing both activity aiand aj, we denote Aaiajas ’-’,

i.e. aiand ajare contained in different branches of a conditional branching.

–Aaiaj= ’L’, iff ((ai∈Bk∧aj=τk)∨(aj∈Bk∧ai=τk))

For any activity aiin a Loop-block Bk, we define order relation Aaiτkbetween

it and the corresponding silent activity τkas ’L’.

The first four order relations {1,0,+,-}specify the precedence relations be-

tween activities as captured in the trace set, while the last order relation ’L’

indicates loop structures within the trace set. Fig. 1c presents the order ma-

trix of process model S. Since Scontains one Loop-block, a silent activity τ

is also added to this matrix. This order matrix contains all five order relations

as described in Definition 3. For example, activities Eand Cwill never appear

in same trace belonging to the simplified trace set since they are contained in

different branches of an XOR block. Therefore, we assign ’-’ to matrix element

AEC. Further, since in all traces which contain both activities Band G,Balways

appears before G, we can obtain order relation ABG = ’1’ and order relation AGB

= ’0’. Special attention should be paid to the order relations between the silent

activity τand the other activities. The order relation between τand activities

Cand Fis set to ’L’, since both Cand Fare contained in the Loop-block; for all

remaining activities, τhas same order relations with them as activities Cor F

have. Note that the main diagonal of the order matrix is empty, since we do not

compare an activity with itself.

As one can see, elements Aaiajand Aajaican be derived from each other. If

activity aiis a predecessor of activity aj, (i.e. Aaiaj= 1), we can always conclude

that Aajai= 0 holds and if Aaiaj∈ {’+’,’-’, ’L’}, we obtain Aajai=Aaiaj.

4 Transforming a Process Model into an Order Matrix

Clearly, it is not realistic to first enumerate all traces of a process model and

analyze the order relation based on them. The trace set of a process model can

be extremely large particularly if the model contains several AND-blocks or even

infinite if there are loop-blocks. In the following, we introduce Algorithm 1 to

compute the order matrix for a process model in polynomial time. Note that

this algorithm is also able to cope with loop structures.

In Algorithm 1, we first define set P(ai) for each activity ai∈N, which

contains all (direct and indirect) predecessors of ai(Line 1). An activity ajis

input : A process model S= (N, E, . . .)

output: Its order matrix A

For each activity ai∈N, i = (1,...,n), define P(ai) as the predecessor set of ai;1

Define Set Cas the set of activities which are already parsed;2

Define Las the set of Loop-blocks Bk;3

P(ai) = ∅for i= (1,...,n), C=∅and L=∅/* initial state */;4

Set parseModel (Node tstart, Node tend, Set C)begin5

/* Compute predecessor sets for activities between node tstart and

tend. Returns a new C’ */

while (tstart 6=tend)do6

if (Sequence) then7

P(tstart) = P(tstart).addAll(C) ;8

C0=C.add(tstart) ;9

tstart =tstart.nextNode;10

else if (XOR-block) then11

foreach branch iin XOR-split, i= (1,...,m)do12

ni= XOR-split.nextNode in branch i;13

i=parseModel (ni, XOR-join, C) ;14

C0=C.addAll(Sm

i=1 C0

i) ;15

tstart = XOR-join.nextNode;16

else if (AND-block) then17

foreach branch iin AND-split, i= (1,...,m)do18

ni= XOR-split.nextNode in branch i;19

i=parseModel (ni, XOR-join, C) ;20

foreach branch kin AND-split, k= (1,...,m)do21

Ck=Sm

i=1,i6=kC0

parseModel (AND-split, AND-join, Ck);23

C0=C.addAll(Sm

i=1 C0

i) ;24

tstart = AND-join.nextNode;25

else if (Loop-block) then26

L.add (parseModel (Loop-start.nextNode, Loop-end, ∅)) ;27

C’ = C.addAll (parseModel (Loop-start,Loop-end, C)) ;28

tstart = Loop-end.nextNode;29

return C0;30

end31

computeOrderRelationBasedOnPredecessorSets () begin32

/* Compute order relation based on predecessor sets */ ;

foreach ai, aj∈N, i 6=jdo33

if P(ai)contain(aj)∧ ¬P(ai)contain(aj)then Aij = ’1’;34

else if ¬P(ai)contain(aj)∧P(ai)contain(aj)then Aij = ’0’;35

else if P(ai)contain(aj)∧P(ai)contain(aj)then Aij = ’+’;36

else if ¬P(ai)contain(aj)∧ ¬P(ai)contain(aj)then Aij = ’-’;37

end38

addSilentActivitiesForLoopStructure (Set L, OrderMatrix A)begin39

/* Add loop on order matrix */ ;

foreach Bk∈ L do40

Define silent activity τk;N=N0S{τk};41

foreach ai∈N0do42

if (ai∈Bk)then43

Aaiτk= ’l’ ; Aτkai= ’l’ ;44

else if (ai∈N0\Li)then45

Let aj∈Li;46

Aaiτk=Aaiaj;Aτkai=Aajai;47

end48

Algorithm 1: Computing order matrix for process model

a predecessor of aiiff ∃t∈ T 0

S:t(aj≺ai). In addition, we define set Lwhich

contains all Loop-blocks Bkof the process model. Following that, three functions

are specified. Function parseModel (Lines 5 to 31) first parses the process model

Sand computes the predecessor sets P(ai) for each activity of the model. Fur-

ther, it determines set Lwhich contains all Loop-blocks Bkof S. Then function

computeOrderRelationBasedOnPredecessorSets (lines 32 to 38) calculates the

order relations for every pair of activities of model Sbased on their predecessor

sets. Finally, function addSilentActivitiesForLoopStructure (lines 39 to 48)

specially handles the loop structures of process model S.

Function parseModel has three input parameters: Nodes tstart and tend mark

the start and the end of the block Biwe need to analyze; set Ccorresponds to

the set of activities already been analyzed. After computing predecessor sets and

Loop-blocks for the activities from block Bi, we obtain new set C’ comprising

original set Cand all activities of Bi. Initially, tstart is set to the start-flow of S,

tend to the end-flow of S, and Cto an empty set (Line 5).

In our analysis, we consider four process patterns:

– Sequence. This pattern is analyzed in Lines 7 to 10 in Algorithm 1. Assume

that blocks Bi,Bjand Bkare three blocks of process model S, where Bi

precedes Bjand Bjprecedes Bk. Let ai∈Biand aj∈Bj. For any trace

t∈ TScontaining both aiand aj, we obtain t(ai≺aj). Therefore, for every

aj∈Bj, we need to add Bito its predecessor set P(aj). Similarly, for every

ak∈Bk, we need to add both Biand Bjto its predecessor set P(ak). In

Algorithm 1, we first add Bito set C, and then add Cto every P(aj)∈Bj.

Finally we add Bjto C(lines 7-9). We repeat same procedure when analyzing

Bk, i.e., we add Cto every P(ak) with ak∈Bk, and then add Bkto C.

– XOR-block. This pattern is analyzed in Lines 10 - 15 in Algorithm 1. Since

the activities in one branch of an XOR-block can never appear in trace t

together with activities of another branch of same XOR-block, we analyze

each branch of an XOR-block separately. Every branch iis considered as

block of S, which can be analyzed independently by the parseModel func-

tion. In this case, tstart shall point to the first node on branch iand tend to

the XOR-join node. Further we need to use same set Cfor analyzing each

branch iin the XOR-block (line 14). This way, we can ensure that activities

from a particular branch do not appear in the predecessor sets of activities

from another branch of the XOR-block. After every branch is analyzed, we

add all activities of this XOR-block to new set C’ (Line 15).

– AND-block. This pattern is analyzed in Lines 17 - 25 of Algorithm 1. Sim-

ilarly to XOR-blocks, we analyze each branch of an AND-block separately.

For every branch i,tstart shall point to the first node in branch iand tend

to the AND-join node. Further we use same set Cfor every branch iin the

AND-block (Line 20). Obviously, an AND-block differs from an XOR-block,

since all its branches are executed concurrently. Therefore, for two activities

aiand ajfrom two different branches in such AND-block, aican appear

before ajin one trace but appear after ajin another trace. Let BAND rep-

resents the AND-block, and BAND

ibe the block representing branch iof

BAND. As reflecting on the predecessor set P(ai) for each ai∈BAND

i, we

need to add all activities from other branches BAND \BAND

ito its prede-

cessor set. In Algorithm 1, Line 22 computes set BAND \BAND

iand Line

23 adds them to the predecessors sets P(ai), ai∈BAND

i. This way, we can

ensure that two activities from different branches of an AND-block always

appear in the predecessor sets of each other.

– Loop-block. This pattern is analyzed in Lines 26 - 29 in Algorithm 1.

We first determine which activities are contained in Loop-block Bby call-

ing function parseModel and adding Bto set L(Line 27). Then, we con-

tinue parsing the model using function parseModel to analyze the activi-

ties inside this Loop-block (Line 28). Note that the analysis of the prede-

cessor sets is based on the simplified trace set (cf. Def. 2), i.e., we only

consider the first appearance of trace tB∈ TBproducible by block B,

while later appearances of tB(caused by the iterative executions of this

Loop-block) are not considered any longer. It will handled later by function

addSilentActivitiesForLoopStructure.

Since blocks may be arbitrarily nested, function parseModel in Algorithm 1

is realized as recursive function. We consider sequence structures as basic ele-

ments of a process model. Whenever there is an AND- or XOR-block, we consider

its branches as blocks and analyze them separately. This division continues until

all AND- and XOR-blocks are resolved into blocks which only contains sequence

structures with elementary activities. This way we are able to compute prede-

cessor set P(ai) of each activity aiin a straightforward way (Lines 7 - 10 in

Algorithm 1). Complexity of function parseModel, therefore, is O(n2), where n

equals the number of activities in process models.

As example take process model Sin Fig. 1. Table 1 shows analysis results

after every step of function ParseModel from Algorithm 1. It indicates which

node function parseModel points to, which activities are processed, which pro-

cess patterns it belongs to, to which set Cchanges afterwards, and what are

the predecessor sets or loop-blocks obtained in this step. For example, Step 1

shows initial state of this function. Steps 2 and 3 analyze the two branches of the

AND-block separately, and results are merged in Step 4. After processing activ-

ity Din Step 5, the algorithm handles the XOR-block in Steps 6-12. Note the

differences between Step 4 and Step 12 when dealing with XOR- and AND-joins

respectively: additional changes are performed on predecessor sets for activi-

ties corresponding to an AND-block. The Loop-block in S, in turn, is handled

in Steps 8 - 11, during which we identify which activities are included in this

Loop-block.

After obtaining predecessor sets P(ai) for every activity ai∈Nusing func-

tion parseModel, we can determine order relations between two activities as

follows:

–If ((ai∈P(aj)) ∧ ¬(aj∈P(ai))), Aaiaj= ’1’, i.e., aialways precedes aj.

–If (¬(ai∈P(aj)) ∧(aj∈P(ai))), Aaiaj= ’0’, i.e., aialways succeeds aj.

–If ((ai∈P(aj)) ∧(aj∈P(ai))), Aaiaj= ’+’, i.e., aiappears before ajin

some traces while it succeeds ajin other traces.

Step Node Processed Workflow Parsed activity Predecessor set P(ai)

pointing at activities pattern set C/ Loop-block set Bk

1 AND-split AND-block ∅

2A A Sequence ∅P(A)=∅

3B B Sequence ∅P(B)=∅

4 AND-join A,B AND-block {A,B}P(A)={B}

P(B)={A}

5D D Sequence {A,B,D}P(D)={A,B}

6 XOR-split XOR-block {A,B,D}

7E E Sequence {A,B,D,E}P(E)={A,B,D}

8 Loop-start Loop-block {A,B,D}

9C C Sequence {A,B,D,C}P(C)={A,B,D}

10 F F Sequence {A,B,D,C,F}P(F)={A,B,D,C}

11 Loop-end Loop-block {A,B,D,C,F}Bk={C,F}

12 XOR-join E,C,F XOR-block {A,B,D,E,C,F}

13 G G Sequence {A,B,D,E,C,F,G}P(G)={A,B,D,E,C,F}

Table 1. Analysis result for process model Sfrom Fig. 1 when applying parseModel

in Algorithm 1

–If (¬(ai∈P(aj)) ∧ ¬ (aj∈P(ai))), Aaiaj= ’-’, i.e., aiand ajnever appear

together.

The abovementioned method is described by function computeOrderRelationBasedOnPredecessorSets

in lines 32 - 38 in Algorithm 1. The computation of these four order relations

{1,0,+,-}is straightforward since it directly matches with the definition of an

order matrix (cf. Def. 3).

As discussed in Section 3, if a process model Scontains Loop-blocks, its

trace set TSbecomes infinite. Therefore we need to reduce TSto simplified

trace set T0

Sfor further analysis (cf. Def. 2). We can achieve this reduction

by defining one silent activity τkfor every Loop-block Bkto represent the it-

erative behavior of the traces producible by Bk(cf. Section 3). After adding

activity τkto the order matrix, the challenge is to determine order relations

between τkand the other activities. In the following, we introduce function

addSilentActivitiesForLoopStructure (Lines 39 - 48 in Algorithm 1) to de-

termine order relations between τkand others. In principle, we can divide activ-

ities into two groups:

–ai∈Bk. If aiis contained in the Loop-block, order relation between aiand

τkis straightforward. According to Definition 3, Aaiτk=0L0and Aτkai=0L0

must hold.

–ai∈N\Bk. In this case, we need to determine order relation between τk

and activity aiwhich is outside the loop block Bk. Since our process model

is block-structured, we can consider whole Loop-block Bkas single ”process

step” in this context. Therefore, ”process step” should have unique order

relations with the remaining activities. This implies that all activities be-

longing to block Bk, including silent activity τk, should have same order

relation in respect to the activities located outside this block. We can there-

fore determine relation between τkand ai∈N\Bkby considering another

activity aj∈Bk. Since both τkand ajbelong to a same Loop-block, Aaiτk

can be assigned to A0

aiaj. Similarly, we obtain Aτkai=A0

ajai.

For example take Sfrom Fig. 1. Table 1 depicts predecessor set P(ai) of

each activity ai, and the set Lfor Loop-blocks which we obtain when applying

function parseModel in Table 1. Based on this, we can compute order ma-

trix Ausing functions computeOrderRelationBasedOnPredecessorSets and

addSilentActivitiesForLoopStructure. The result is shown in Fig. 1b. Spe-

cial attention should be paid to the order relations between silent activity τand

the other activities: except the order relations between τon the one hand and C

and Fon the other hand are ’L’, the order relations between τand the remaining

activities are same as the ones Cand Fhave.

Complexity of Algorithm 1 is O(2n2) where nequals the number of activ-

ities the process model has. To be more precise, the complexity of function

parseModel is O(n2) and complexity of the other two functions corresponds to

O(n2) in total. This polynomial complexity allows us to quickly transform a

(large) process model into its order matrix for further analysis.

5 Transforming an Order Matrix back into a Process

Model

In Section 4, we have introduced an algorithm for transforming a process model

Sinto its corresponding order matrix A. In this section, we show how such an

order matrix Acan be transformed back into a process model S. This approach

is described by Algorithm 2.

Algorithm 2 starts with defining a hashtable which maps activities from the

order matrix (the key of the hashtable) to their corresponding blocks (the value

of the hashtable). Initially, every activity from the order matrix constitutes a

block itself (Line 2). The key idea of Algorithm 2 is to merge such blocks. More

precisely, two blocks can form a bigger one iff they have same order relations

in respect to all remaining blocks within the order matrix (Lines 6 - 9). If two

blocks Biand Bjcan be merged into a bigger block Bij, we can build the new

block based on these two smaller blocks and their order relation (Lines 11 - 12).

The newly created block Bij replaces Biand Bjin the hashtable. We can then

map such block to activity aiin the order matrix and remove the corresponding

row and column for ajin A(Lines 13 - 15). Therefore, in every iteration, we

reduce one row and one column of the order matrix. Merging blocks continues

iteratively until there are only two blocks remaining in the order matrix. We

merge these two blocks in the last step (Line 23).

Function createModel(Block Bi, Block Bj, OrderRelation 3) creates a pro-

cess model by merging two blocks Biand Bjbased on their order relation 3

(Lines 19 - 35 in Algorithm 2). If 3represents a predecessor or successor relation,

we just need to add one edge between start and end of these two blocks. If the

input : An order matrix A

output: A process model S= (N, E, . . .)

Define Hashtable Map;1

Define each activity aias a block Bi;Map.put(ai,Bi)i= (1,...,n);2

iteration = 0; /* initial state */ ;

while iteration < n −2do3

foreach ai, aj∈N, ai6=ajdo4

merge = True ;5

for ak∈N\ {ai, aj}do6

if Aaiak6=Aajakthen7

merge = False;8

/* two blocks can merge into a bigger one, iff they

have same order relations to the others */ ;

break ;9

if merge then10

createModel (Map.getValue(ai), Map.getValue(ai), Aaiaj)11

/* create a new block based on the two blocks and their

order relation */ ;

Bij =buildBlock (Map.getValue(ai), Map.getValue(ai), Aaiaj) ;12

/* Merge these two block based on their order relation */ ;

Map.remove(ai); Map.remove(aj)/* change the blocks */ ;13

A.remove(aj)/* change order relations */ ;14

Map.put (ai, Bij ) ;15

break;16

iteration ++;17

S=createModel (Map.getValue(a1), Map.getValue(a2), Aa1a2)/* Merge last18

two blocks */ ;

createModel (Block Bi, Block Bj, OrderRelation 3)begin19

if 3= ’0’ then20

/* Merge block Biand Bjbased on their order relation 3*/

addEdge (Bj.end, Bi.start);

else if 3= ’1’ then21

addEdge (Bi.end, Bj.start);22

else if 3= ’+’ then23

addNode (AND-split); addNode(AND-join) ;24

addEdge (AND-split, Bi.start); addEdge (AND-split, Bi.start);25

addEdge (Bj.end, AND-join); addEdge (Bj.end, AND-join) ;26

else if 3= ’-’ then27

addNode (XOR-split); addNode(XOR-join);28

addEdge (XOR-split, Bi.start); addEdge (XOR-split, Bi.start);29

addEdge (Bj.end, XOR-join); addEdge (Bj.end, XOR-join) ;30

else if 3= ’l’ then31

Let Bi=τ; addNode (loop-start); addNode(loop-end) ;32

addEdge (loop-start, Bj.start); addEdge (Bj.end,loop-end);33

addEdge (loop.end, loop-start, loop) ;34

end35

Algorithm 2: Transforming an order matrix into a process model

two blocks have order relation ’+’ or ’-’, we add them to different branches of

an AND- or XOR-block. If order relation 3corresponds to ’L’, there must be a

Loop-block in the process model and either Bior Bjcorrespond a silent activity

τ. Reason is that any silent activity τcan only be clustered with Loop-block

Bthat it corresponds to. If Biequals τ, we only need to surround Bjwith a

loop-backward edge.

As example take order matrix Afrom Fig. 1. Since activities Aand Bhave

same order relations in respect to the remaining activities, we are able to merge

these two activities to an AND-block. After creating this block, we remove ac-

tivity Bfrom order matrix A. For example, the block containing Aand Bcan be

merged with activity Din order to create a bigger block. If we repeat this process

of merging blocks, we finally obtain process model Sas depicted in Fig. 1.

6 One-to-one Mapping between a Process model and its

Order Matrix

Section 4 has introduced Algorithm 1 for transforming a process model into its

order matrix. In Section 5, we have further provided Algorithm 2 for transforming

an order matrix back into its corresponding process model. Generally, it is critical

to prove that such transformation constitutes a one-to-one mapping, i.e., if we

first transform a process model Sinto its order matrix A, and then transform

Aback to a process model S0,S0should be same as S.

When transforming a process model into an order matrix (cf. Algorithm

1), we recursively analyze each block of the process model from start to end.

However, when transforming an order matrix back into a process model (cf.

Algorithm 2), the order in which we merge blocks is more or less arbitrary, i.e.,

we merge two blocks together whenever this is possible. Therefore, it is important

to know whether the order relation satisfies the associative law, i.e., whether the

order to merge small blocks into bigger ones can influence the result.

Let us first consider predecessor-successor order relations ’0’ and ’1’. Assume

process model Scontains three blocks Bi,Bjand Bkwith Bipreceding Bj

and Bjpreceding Bk. Obviously, we obtain ABiBj=010and ABjBk=010.

Representing this as mathematical equation, we obtain Bi3Bj3Bkwith 3being

’1’. If we need to transform order matrix Ainto a process model S0, it does not

matter whether we first merge Biand Bjor we first merge Bjand Bk, i.e.,

(Bi3Bj)3Bk=Bi3(Bj3Bk). It is obvious from Algorithm 2 that we only need

to add control edges between the end of the preceding block and the start of

the succeeding one. Therefore the order of adding edges does not influence the

resulting model. Clearly, such rule also applies if order relation 3corresponds

to ’0’.

For order relations ’+’ and ’-’, let us re-assume that there are three blocks Bi,

Bjand Bkwith same order relation ’-’ among each other, i.e., Bi3Bj3Bkwith

3being ’-’. Fig. 2a shows two models Sand S0that result when merging these

three blocks together. To be more precise, Scan be obtained by first merging Bi

and Bjand then merging the intermediate block with Bk(S= (Bi3Bj)3Bk),

while S0can be obtained by first merging Bjand Bkand then merging the

resulting block with Bi(S0=Bi3(Bj3Bk)).

AND-Split

AND-Join

XOR-Split

XOR-Join

S S’

S, S’ and S’’ are trace equivalent

S’’

Fig. 2. Trace equivalence for AND and XOR blocks

Obviously, process models Sand S0are structurally different. However, S

and S0are trace equivalent despite their structural difference, i.e., trace sets

TSand TS0producible on Sand S0respectively are the same: TS=TS0=

TBiSTBjSTBk. Note that the two process models are trace equivalent to S00

as well. Regarding S00,Bi,Bjand Bkare located in three different branches of

the same XOR-block. In the context of our research, we consider S,S0and S00

being the same, since the corresponding process models have same trace set and

therefore show same behaviors.8This indicates that order relation ’-’ satisfies the

associative law, and consequently the order in which blocks are merged is not

relevant. When first transforming a process model (e.g., S00) into order matrix A,

and then transforming Aback into a process model (e.g., S0), the original and the

newly derived process models are trace equivalent. In our context, we consider

these two models being same. Thus the transformation between process model

and order matrix constitutes a one-to-one mapping. Obviously, same results are

obtained if the order relations between them are ’+’ (cf. Fig. 2b).

For order relation ’L’, the associative law is not applicable in the given context

because Bi3Bj3Bk(with 3= ’L’) is not possible for an order matrix. If Bi3Bj

holds with 3= ’L’, either Bior Bjmust be τ. This, in turn, indicates that in

expression Si3Sj3Sk, two out of the three blocks constitute silent activities

τ. Let us assume that Bjand Bkare these two silent activities. Thus such

expression means that block Biis surrounded by a loop-backward edge to form

a loop-block B0

iand this Loop-block B0

iis immediately surrounded by another

loop-backward edge to form another Loop-block B00

i, i.e., Biis surrounded by

two loop-backward edges. In this case, B0

iand B00

iare trace equivalent, and

8Like most process mining techniques (e.g. [30, 7, 34]), the stronger notion of bi-

similarity are not considered in our context [9]

therefore expression Si3Sj3Skwould be simplified to Si3Sjwith 3being ’L’.9

This implies that the condition to analyze the associative law does not hold.

Although associative law is not applicable to order relation ’L’, it cannot

influence the one-to-one mapping between a process model and its order matrix.

Reason is that whenever two blocks have order relation ’L’, one of them must

be a silent activity τ, and this silent activity can only be merged with the

block surrounded by a loop-back edge. Assume that block Bis surrounded by a

loop, i.e., has order relation ’L’ with silent activity τ(cf. Def. 3). For any block

Biwhich is different from B, there are only two situations: either Bcontains

activities not in Bior Biis a sub-block of B. In the first scenario, for any activity

ai/∈B,aimust have different order relation in respect to τthan activities in B

have, therefore Bicannot be clustered with τ; in the second scenario, there must

be an activity ai∈B\Bihaving different order relation to τwhen compared to

an activity aj∈Bi. Therefore Bican not be clustered with τ. This indicates that

the silent activity τcan only be clustered with the Loop-block it corresponds to.

Consequently, the order of clustering also does not influence results.

7 Algebraic Properties of Order Relations

In addition to associativity of order relations, we have analyzed their algebraic

properties. Let Si, Sj, Sk∈ P be three sound process models. In this context,

we denote a process model as sound if there are no deadlocks or unreachable

activities in the process model [21, 28]. Let further 3={0,1,+,−, L}be the

order relations as set out by Definition 3. Then, the algebraic system <P,3>

has the properties depicted in Table 2:

Algebraic property Order relation 3

Name Mathematical expression 0 1 + - L

Closure Si3Sj∈ P Yes Yes Yes Yes Yes

Commutativity Si3Sj=Sj3SiNo No Yes Yes Yes

Transitivity Si3Sj∧Sj3Sk⇒Si3SkYes Yes No No Yes

Associativity (Si3Sj)3Sk=Si3(Sj3Sk) Yes Yes Yes Yes - 10

Identity element I Si3I=SiI=∅I=∅I=∅None I=∅11

Table 2. The algebraic properties of order relation

9We can easily identify such situation from the process model or the order matrix. If

a block is surrounded by two loop-back edges in a process model, we only need to

keep one of them so that the model is still trace equivalent to the original one. In an

order matrix, we can easily identify such situation by checking whether two silent

activities τis able to merge or not. If yes, then we can remove one of them.

9According to the analysis in Section 6, conditions for analyzing associative law does

not exist

11 If two blocks Siand Sjhave order relation ’L’, at least one of them must be silent

activity τ. Therefore, we consider the identity element also being existent for order

In details, Table 2 summarizes 5 algebraic properties of the order matrix,

namely, closure, commutativity, transitivity, associativity and identity element.

The analysis is based on function createModel as defined in Algorithm 2. Using

this function we can merge two process models Siand Sj(a process model is

also a block) into another process model Sij based on order relation 3.

– Closure. For all five order relations, the closure property is satisfied, i.e., if

we merge two sound process model Siand Sjbased on any of the five order

relations 3={0,1,+,−, L}, we obtain another sound process model Sij.

This is a very important property since it guarantees soundness of the re-

sulting model when merging two process models using function createModel

(cf. Algorithm 2). Consequently, when transforming an order matrix into a

process model using Algorithm 2, the resulting process model must be sound

as well, since the algorithm constructs a process model by merging blocks

(cf. Algorithm 2). The theoretical background to guarantee soundness of

the resulting model when merging two blocks can also be found in ADEPT

change framework [21] (or see also inheritance rule in Petri Nets [29]).

– Commutativity. Commutativity is represented by the relation of the el-

ements in an order matrix. If Aaiaj=3with 3∈ {+,-,L}holds, we will

obtain Aajai=Aaiaj(since the respective order relations satisfy commuta-

tive law). On the contrary, if Aaiaj= ’0’ holds, we can obtain Aajai= ’1’

and vice verse. This implies that, in most cases it is sufficient to only analyze

the upper or lower part of the triangle in the order matrix.

– Transitivity. Transitive law applies to order relations ’0’, ’1’ and ’L’, but

not to the others. This property is important for Algorithm 1 because the

key construct in this algorithm is a sequence structure with start- and end-

node. Since order relations ’0’ and ’1’ are transitive, but not commutative,

for a given process model Swith finite number of activities, there must

be a start- and end-node. Reason is that if an algebraic system with finite

number of elements is transitive, but not commutative, this algebraic system

must be bounded [25], i.e., there must be an element which does not have

predecessors (the start of process model) and an element which does not

have any successor (the end of process model).

– Associativity. The associative law has been discussed in Section 6. This

property guarantees that when transforming a process model Sinto an order

matrix A, and then transforming resulting order matrix back to a process

model S0,Sand S0are trace equivalent. This property is important in order

to guarantee the one-to-one mapping between a process model and its order

matrix.

– Identity element. The identity element is important for dealing with silent

activities in a process model. Since silent activities constitute the identity ele-

ment for order relations ’0’, ’1’, ’+’ and ’L’, we do not need special treatment

for them (i.e., they will not influence the result). This property is important,

relation ’L’, since an ”empty” process model remains an ”empty” process model,

even after surrounding it within a loop structure.

especially when changing a process model and its corresponding order ma-

trix. Note that such changes often introduce silent activities [13, 29, 21, 32].

The only exception is provided by order relation ’-’. When merging a process

model Siwith a silent activity based on order relation ’-’, we obtain a new

block Sj. Consequently, we need to add one more empty trace t(producible

by the silent activity, i.e., a trace contains no activity) into trace set TSiin

order to obtain trace set TSj. Therefore, if t /∈ TSi, we obtain TSi6=TSj. We

refer to [13] for an approach to handle silent activities for order relation ’-’.

8 Conclusion

This paper provides a matrix representation of a process model, which we denote

as order matrix. We have presented an algorithm to transform a process model

into its order matrix, and an algorithm to transform an order matrix back to a

process model. We have further shown that the mapping between process model

and its order matrix is one-to-one, i.e., we basically obtain same process model

when transforming a process model into an order matrix and then transforming

the resulting order matrix back to a process model. Finally, we have discussed

algebraic properties of order relations and their influences on the algorithms as

well.

References

1. R. A. Baeza-Yates. Text-retrieval: Theory and practice. In Proceedings of the IFIP

12th World Computer Congress on Algorithms, Software, Architecture - Informa-

tion Processing ’92, Volume 1, pages 465–476, Amsterdam, The Netherlands, The

Netherlands, 1992. North-Holland Publishing Co.

2. R. P. Jagadeesh Chandra Bose and W. M. P. van der Aalst. Context aware trace

clustering: Towards improving process mining results. In SDM’09, pages 401–412.

SIAM, 2009.

3. BPEL. http://docs.oasis-open.org/wsbpel/2.0/wsbpel-v2.0.pdf.

4. OMG BPMI.org. Business Process Modeling Notation Specification. Object Man-

agement Group, 2006. available at: http://www.bpmn.org.

5. P. F. Brown, V. J. Della Pietra, P. V. de Souza, J. C. Lai, and R. L. Mercer. Class-

based n-gram models of natural language. Computational Linguistics, 18(4):467–

479, 1992.

6. P. Dadam and M. Reichert. The ADEPT project: A decade of research and de-

velopment for robust and flexible process support - challenges and achievements.

Computer Science - Research and Development, 23(2):81–97, 2009.

7. A.K. Alves de Medeiros. Genetic Process Mining. PhD thesis, Eindhoven Univer-

sity of Technology, NL, 2006.

8. A. Hallerbach, T. Bauer, and M. Reichert. Capturing variability in business process

models: the provop approach. Software Process: Improvement and Practice, page

to appear, 2009.

9. J. Hidders, M. Dumas, W.M.P. van der Aalst, A.H.M. ter Hofstede, and J. Verelst.

When are two workflows the same? In CATS ’05:, pages 3–11, Darlinghurst, Aus-

tralia, 2005.

10. B. Kiepuszewski, A. H. M. ter Hofstede, and C. Bussler. On structured workflow

modelling. In CAiSE’00, pages 431–445. LNCS 1789, Springer, 2000.

11. C. Li, M. Reichert, and A. Wombacher. Discovering reference process models by

mining process variants. In ICWS’08, pages 45–53. IEEE Computer Society, 2008.

12. C. Li, M. Reichert, and A. Wombacher. Mining process variants: Goals and issues.

In IEEE SCC (2), pages 573–576. IEEE Computer Society, 2008.

13. C. Li, M. Reichert, and A. Wombacher. On measuring process model similarity

based on high-level change operations. In ER ’08, pages 248–262. Springer LNCS

5231, 2008.

14. C. Li, M. Reichert, and A. Wombacher. Discovering reference models by mining

process variants using a heuristic approach. In BPM’09, LNCS 5701, pages 344–

362. Springer, 2009.

15. J. Mendling. Metrics for Process Models: Empirical Foundations of Verification,

Error Prediction and Guidelines for Correctness, volume 6 of LNBIP. Springer,

2008.

16. J. Mendling, G. Neumann, and W. M. P. van der Aalst. Understanding the oc-

currence of errors in process models based on metrics. In CoopIS’07, LNCS 4803,

pages 113–130, 2007.

17. J. Mendling, H. A. Reijers, and J. Cardoso. What makes process models under-

standable? In BPM’07, pages 48–63. LNCS 4714, Springer, 2007.

18. J. Mendling, H. A. Reijers, and W. M. P. van der Aalst. Seven process modeling

guidelines (7pmg). Information & Software Technology, 52(2):127–136, 2010.

19. J. Mendling, B. F. van Dongen, and W. M. P. van der Aalst. Getting rid of or-joins

and multiple start events in business process models. Enterprise IS, 2(4):403–419,

2008.

20. J. Ross Quinlan. C4.5: programs for machine learning. Morgan Kaufmann Pub-

lishers Inc., USA, 1993.

21. M. Reichert and P. Dadam. ADEPTflex -supporting dynamic changes of workflows

without losing control. Journal of Intelligent Information Systems, 10(2):93–129,

1998.

22. M. Reichert, S. Rinderle-Ma, and P. Dadam. Flexibility in process-aware informa-

tion systems. LNCS Transactions Petri Nets and Other Models of Concurrency,

2:115–135, 2009.

23. H. A. Reijers and J. Mendling. Modularity in process models: Review and effects.

In BPM’08, pages 20–35. LNCS 5240, Springer, 2008.

24. S. Rinderle-Ma, M. Reichert, and B. Weber. On the formal semantics of change

patterns in process-aware information systems. In ER’08, pages 279–293. LNCS

5231, Springer, 2008.

25. K.H. Rosen. Discrete Mathematics and Its Application. McGraw-Hill, 2003.

26. P.N. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-

Wesley, 2005.

27. W. M. P. van der Aalst, A. H. M. ter Hofstede, B. Kiepuszewski, and A. P. Barros.

Workflow patterns. Distributed and Parallel Databases, 14(1):5–51, 2003.

28. W. M. P. van der aalst and K. van Hee. Workflow Management: Models, Methods,

and Systems. The MIT Press, 2002.

29. W.M.P. van der Aalst and T. Basten. Inheritance of workflows: an approach to

tackling problems related to change. Theor. Comput. Sci., 270(1-2):125–203, 2002.

30. W.M.P van der Aalst, T. Weijters, and L. Maruster. Workflow mining: Discov-

ering process models from event logs. IEEE Trans. on Knowl. and Data Eng.,

16(9):1128–1142, 2004.

31. J. Vanhatalo, H. Volzer, and J. Koehler. The refined process structure tree. Data

Knowledge Engineering, 68(9):793–818, 2009.

32. B. Weber, M. Reichert, and S. Rinderle-Ma. Change patterns and change support

features - enhancing flexibility in process-aware information systems. Data and

Knowledge Engineering, 66(3):438–466, 2008.

33. B. Weber, S. Wasim Sadiq, and M. Reichert. Beyond rigidity - dynamic process

lifecycle support. Computer Science - R&D, 23(2):47–65, 2009.

34. A.J.M.M. Weijters and W.M.P. van der Aalst. Rediscovering workflow models from

event-based data using little thumb. Integr. Comput.-Aided Eng., 10(2):151–162,

2003.

35. A. Wombacher and M. Rozie. Evaluation of workflow similarity measures in service

discovery. Service Oriented Electronic Commerce, pages 51–71, 2006.

36. M. zur Muehlen and J. Recker. How much language is enough? theoretical and

practical use of the business process modeling notation. In CAiSE’08, pages 465–

479. LNCS 5074, Springer, 2008.