Information Technology Reference
In-Depth Information
Definition 2 (Weak Order Relation).
Let
P
=(
A, s, e, C, F, T
)
be a process
model and
T
P
its set of traces. The
weak order relation
P
⊆
A
×
A
contains all
pairs
(
x, y
)
, such that there is a trace
σ
=
n
1
,...,n
m
in
T
P
with
j
∈{
1
,...,m
−
m
for which holds
n
j
=
x
and
n
k
=
y
.
Two activity nodes of a process model might be related by weak order in three
different ways, which define the characteristic relations of the behavioural profile.
1
}
and
j<k
≤
Definition 3 (Behavioural Profile).
Let
P
=(
A, s, e, C, F, T
)
be a process
model. A pair
(
x, y
)
∈
A
×
A
is in one of the following relations:
◦
The
strict order relation
P
,if
x
P
y
and
y
P
x
.
◦
The
exclusiveness relation +
P
,if
x
P
y
and
y
P
x
.
◦
The
interleaving order relation
||
P
,if
x
P
y
and
y
P
x
.
The set
B
P
=
{
P
,
+
P
,
||
P
}
of all three relations is the
behavioural profile
of
P
.
We illustrate the relations of the behavioural profile for the lower model in Fig. 1.
For instance, it holds (1)
(5) as both activities are ordered whenever they oc-
cur together in a trace. It holds (8) + (9) as both activities will never occur in
a single trace, and (5)
(6) due to the potential concurrent execution. The rela-
tions of the behavioural profile are mutually exclusive. Along with the reverse
strict order
||
−
1
=
, the relations partition the
Cartesian product of activities. An activity is either said to be
exclusive to itself
(e.g., (1) + (1) in Fig. 1) or in
interleaving order to itself
(e.g., (6)
{
(
x, y
)
∈
(
A
×
A
)
|
(
y, x
)
∈
}
(6)). The
former holds, when an activity cannot be repeated, whereas the latter implies
that the activity may be executed multiple times. The behavioural profile is a
behavioural abstraction. Hence, there may be process models that show differ-
ent trace semantics but have equal behavioural profiles. Moreover, behavioural
profiles may be lifted from activities to labels of activities. Still, this may re-
sult in serious information loss as two occurrences of activities with equal la-
bels would not be distinguished. The behavioural profile
||
B
P
of a process model
P
=(
A, s, e, C, F, T
) may be restricted to a subset of activity nodes
A
⊂
A
by
to
A
×
A
.We
restricting the definition of the three relations
P
,+
P
,and
||
P
refer to this restricted profile as the behavioural profile over
A
.
Computation of the behavioural profile of a process model is done eciently
under the assumption of soundness. Soundness is a correctness criteria that guar-
antees the absence of behavioural anomalies, such as deadlocks [25]. It has been
defined for WF-nets, so that it can be directly applied to our notion of a pro-
cess model. We are able to reuse techniques for the computation of behavioural
profiles introduced for sound free-choice WF-nets [16]. Using these results, be-
havioural profiles are computed in
O
(
n
3
) time with
n
as the number of nodes of
the respective WF-net.
3 A Set Algebra for Behavioural Profiles
To introduce a set algebra for behavioural profiles, we first discuss a notion of
strictness for profile relations in Section 3.1. Then, Section 3.2 introduces set-
theoretic relations, while Section 3.3 turnsthefocusonset-theoretic operations.
