# Confusion Analysis and Detection for Workflow Nets

Authors: Xiao-liang Chen; Zhong-yuan Jiang; Jian-hong Ye
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

Option processes often occur in a business procedure with respect to resource competition. In a business procedure modeled with a workflow net (WF-net), all decision behavior and option operations for business tasks are modeled and performed by the conflicts in corresponding WF-net. Concurrency in WF-nets is applied to keep a high-performance operation of business procedures. However, the firing of concurrent transitions in a WF-net may lead to the disappearance of conflicts in the WF-net. The phenomenon is usually called confusions that produces difficulties for the resolution of conflicts. This paper investigates confusion detection problems in WF-nets. First, confusions are formalized as a class of marked subnets with special conflicting and concurrent features. Second, a detection approach based on the characteristics of confusion subnets and the integer linear programming (ILP) is developed, which is not required to compute the reachability graph of a WF-net. Examples of the confusion detection in WF-nets are presented. Finally, the impact of confusions on the properties of WF-nets is specified.


---

## Body

## 1. Introduction

The workflow net (WF-net) [1, 2] of a business procedure is constructed to depict the logical relations among business tasks and to detect the potential faults in the procedure. Multithreaded tasks and option processes in a business procedure are usually implemented by concurrent and conflicting operations that can promote exact and efficient execution of the procedure. In its WF-net model, concurrent structures and conflicts are constructed to model and analyze multithreaded tasks and option processes, respectively.However, WF-nets suffer from a class of faults that are called confusions such that the disappearance of conflicts occur, which implies that the conflicting transitions in a conflict become disabled before the resolution of the conflict in a WF-net. Confusions are caused by the interlacements between concurrent and conflicting processes, which generate nondeterministic occurrence of conflicts and produce difficulties for the resolution of conflicts.The subnet shown in Figure1(a) is a confusion that may occur in WF-nets, which includes two concurrent transitions t
1 and t
2 at the shown marking and a structural conflict between transitions t
2 and t
3. The confusion may lead to the disappearance of the conflict between t
2 and t
3, which is undesired. The defect is illustrated in the example. If the two concurrent transitions t
1 and t
2 fire, the marking shown in Figure 1(d) can be reached. In this process, different sequential transition firing sequences (σ
1
=
t
1
t
2 and σ
2
=
t
2
t
1) with respect to the concurrent firing of t
1 and t
2 implicate completely different conflict behavior. Suppose that there are two observers who observe the firing of the sequences σ
1
=
t
1
t
2 and σ
2
=
t
2
t
1, respectively. Their observation for system behavior can be described as follows.(1)
t
1 fires first, which results in a conflict between t
2 and t
3. Then, the conflict is resolved in favor of t
2 and t
2 fires (σ
1
=
t
1
t
2).
(2)
t
2 fires first, which does not conflict with other transitions. Then, t
1 fires (σ
2
=
t
2
t
1).Figure 1
(a) A subnet system, (b) the subnet system obtained by firing the transitiont
1 in Figure 1(a), (c) the subnet system obtained by firing the transition t
2 in Figure 1(a), and (d) the subnet system obtained by concurrently firing the transitions t
1 and t
2 in Figure 1(a).There occurs the conflict betweent
2 and t
3 and the conflict can be resolved by firing transition t
2 in observation 1. However, observation 2 shows that no conflict occurs except sequentially firing t
2 and t
1. Hence, the confusion leads to the fact that the occurrence of the conflict between t
2 and t
3 is nondeterministic owing to the concurrent firing between t
1 and t
2. The conflict behavior described in observation 1 will not occur; that is, the disappearance of the conflict occurs, when the system fires the sequence σ
2
=
t
2
t
1.In a real-world workflow system, the construction of conflicts and concurrency usually attempts to reach a kind of balance between the resource utilization and the fulfillment of the performance requirements. Such balance can be achieved through the timing constraints reported in [3] and the bottlenecks of performance a workflow mentioned in [4]. However, the meaningful balance can only be presented between independent conflicts and concurrency; that is, the conflicts and concurrency contain different transitions in a WF-net, since their behavior will not be mutually interfered. Conversely, if there are dependent conflicts and concurrency in a WF-net, that is, confusions, conflicts can only be considered rather than the balance between conflicts and concurrency. The reason can be presented by considering the different importance of conflicts and concurrency in a workflow procedure.The significance of conflicts lies in the fact that they perform all option processes that are usually considered as the procedure interfaces to its external environment, for example, switches and decisions of humans. The interfaces should be determined such that the external environment can intervene a target result. Hence, the occurrence of conflicts should be observable and unambiguous in the evolution of a workflow procedure.Concurrency in a workflow procedure only facilitates the implement of performance requirements to obtain a desired running period, which does not contribute to the logical judgments and the correctness of the procedure. Assuming that the tasks in a procedure are not performed concurrently, researchers can still get an execution result except a higher execution performance. However, if there are no conflicts, the behavior of the procedure may not be completed or the procedure performing a desired work cannot be constructed.As aforementioned, a policy is required to determine whether a WF-net will be such an ambiguous conflict owing to concurrency. Hence, this paper aims at dealing with the formal description of confusions and providing a policy to decide whether a WF-net is confusion-free and where may appear confusions in the WF-net.Petri nets (PNs) [5–7] as a formalism to describe the behavior of discrete event systems have drew much attention from different areas, for example, workflow management [2, 8, 9], web services [10, 11], and flexible manufacturing systems (FMSa) [12, 13]. Confusion problems and their defects were first investigated in PNs by Rozenberg et al. in [14, 15]. Their work considers the defects of PNs with confusions and mentions that it is not always possible to avoid confusion in a PN system although conflict behavior in the system with confusions is difficult to analyze. This is due to the fact that the intermediate states, for example, the markings shown in Figures 1(b) and 1(c), determined by different sequential transition sequences, for example, t
1
t
2 and t
2
t
1, of concurrent transitions, are different from each other.If one requires to determine whether a conflict occurs in a PN with confusions, all possible sequential transition sequences generated by concurrent transitions in the PN have to be analyzed. However, the number of these sequences grows quickly with the increase of concurrent transitions. On the other hand, a confusion cannot be analyzed by using a reachability graph since independent concurrency (no concurrent transitions belonging to conflicting transitions) and concurrency in confusions cannot be differentiated in the reachability graph of a PN.Some studies are devoted to the analysis of the confusions in PNs, where the phenomenon of confusions is extensively reported by many PN applications such as workflow nets (WF-nets) [2, 8, 9], occurrence nets [16, 17], safe nets [18–20], generalized (unsafe) nets [19], and generalized stochastic PNs (GSPNs) [21, 22].The study on occurrence nets focuses on the PNs whose behavior can be interpreted by branching unfolding semantics [23]. In PNs, the behavior such as sequences, concurrency, conflicts, trails, choices, and alternatives can be described and analyzed by decomposing an occurrence net into substructures given by the node relations associated with the behavior. However, confusions cannot be described by the existing branching semantics. Hence, Smith and Haar consider the independence of events in occurrence nets and the indirect influences among concurrent events in [16, 17]. Furthermore, interference structural conflict clusters are developed in [17] in order to describe confusions. The clusters belong to a kind of the substructures of occurrence nets. In the work of Smith and Haar, confusion detection problems are not considered.In [18, 19], a confusion detection approach based on trace theory is proposed. Furthermore, communicating sequential process (CSP) model checker is used to verify the detected confusions. However, the precondition of the confusion detection is that a PN is converted into an interleaving process algebra CSP. The transformation can produce additional costs and is infeasible for an arbitrary PN. A feasible offline confusion detection policy is reported in [20], which requires computing the reachability graph of a PN and cannot be used in complex systems owing to state space explosions.Confusions in GSPNs are discussed in [21, 22]. The marking graph of a GSPN is not a stochastic process if the GSPN contains confusions, which implies that continuous-time Markov chains (CTMCs) cannot be used to analyze the GSPNs with confusions. Generally, a classical analytical approach for GSPNs is to assume that the subnets of immediate transitions are confusion-free in order that the analysis can proceed. However, the assumption does not intrinsically solve the problem of confusions since they really exist in GSPNs.A PN which models the control-flow dimension of a workflow is a WF-net. Both dynamic behavior and control of a case in a workflow can be specified in its WF-net [1, 24]. van der Aalst and Hee deal with the existence of confusions in WF-nets and show the defects of WF-nets with confusions [2, 8, 9]. First, a WF-net is said to be correct with a singleton token in its source place if the WF-net holds for the properties “soundness” and “well-structured,” which is reported in [9]. If a WF-net is sound, an arbitrary reachable marking generated by the WF-net can terminate properly. A well-structured WF-net has a number of nice properties. For example, the soundness of a WF-net can be verified in polynomial time and a sound well-structured WF-net is safe. However, the existence of confusions in WF-nets leads to nondeterministic conflicting processes. Hence, it is not amenable to say that a sound or a well-structured WF-net is correct since the properties “soundness” and “well-structured” in WF-nets cannot avoid confusions. Furthermore, confusions can affect the property “well-structured” of a WF-net under the acyclic (no directed cycle in the structure of a WF-net) restrictions. To be more specific,(1)
a sound and well-structured WF-net with cycles may cause confusions; this fact will be illustrated by giving an example in this paper;
(2)
if an acyclic sound WF-net contains a confusion, it is certainly not well structured; the conclusion will be specified in this work.Second, in a workflow management system (WFMS), four important building blocks (AND-split, AND-join, OR-split, and OR-join) are introduced to specify the functions of the WFMS, where OR-splits are said to be case variables and modeled with conflicts in the corresponding WF-system, which lead to different routings of a case (transition sequences). According to the requirements of WFMSs and the work of van der Aalst in [9], the routings of a case should be independent of the order in which tasks are executed; that is, the choice between conflicting transitions cannot be influenced by the order in which a nonconflicting transition fires. It is shown that the behavior of confusions should not occur in a WF-system modeling a WFMS.Third, in WF-net, only free choice is usually allowed due to the existence of confusions since the structures of confusions are nonfree choice. However, as discussed in [2], there are nonfree choice WF-nets that correspond to sensible workflows. They can be applied if confusion detection problems are solved.Fault detection and control in PNs is an important and computationally difficult problem owing to resource sharing, state space explosions, and complex conflicting and concurrent behavior. For example, some excellent deadlock detection and prevention methods of FMSs are proposed in PNs [25–31]. WF-nets belong to a subclass of PNs and the occurrence of confusions in a WF-net is undesired. Hence, this paper is intended to investigate the confusion problems in a WF-net. The main contributions include the following three aspects.(1)
The formalization of confusions is presented by defining a special class of subnets.
(2)
The impact of confusions on the properties of WF-nets is discussed.
(3)
A confusion detection policy is proposed without considering the reachability graph of WF-nets, which can return whether and where may occur a confusion in WF-nets.If a sound or well-structured WF-net is reported to be confusion-free according to the proposed detection policy, the WF-net can be used in any real-world workflow procedure. Correspondingly, once the proposed policy finds a confusion in WF-nets, researchers or engineers will be able to give up the use of such WF-nets or design a method to ensure the occurrence of conflicts before using them.This paper is organized as follows. Section2 introduces basic concepts of PNs and WF-nets. Section 3 formulates two classes of confusions and specifies their behavior by some examples. Section 4 presents algorithms for confusion detection. The proposed algorithms are applied to some examples and a real-world case. Section 5 deals with the impact of confusions on the properties of WF-nets. Conclusions and future work are presented in Section 6.


## 2. Basics of Petri Nets and Workflow Nets

This section provides the basics of PNs and WF-nets, where the definitions and the properties of PNs presented in this paper come from [6] and the details of WF-nets can be found in [9].A PNN is a four-tuple (
P
,
T
,
F
,
W
), where P and T are finite, nonempty, and disjoint sets. P is the set of places and T is the set of transitions. F
⊆
(
P
×
T
)
∪
(
T
×
P
) is called a flow relation of the net, represented by arcs with arrows from places to transitions or from transitions to places. W
:
(
P
×
T
)
∪
(
T
×
P
)
→
ℕ is a mapping that assigns a weight to an arc: W
(
x
,
y
)
>
0 if (
x
,
y
)
∈
F, and W
(
x
,
y
)
=
0 otherwise, where x
,
y
∈
P
∪
T and ℕ
=
{
0,1
,
2
,
…
} is a set of nonnegative integers. A net is self-loop-free (pure) if ∄
x
,
y
∈
P
∪
T, (
x
,
y
)
∈
F
∧
(
y
,
x
)
∈
F. N
=
(
P
,
T
,
F
,
W
) is called an ordinary net, denoted as N
=
(
P
,
T
,
F
), if ∀
f
∈
F
,
W
(
f
)
=
1.Letx
∈
P
∪
T be a node in a net N
=
(
P, T, F, W
). The preset of x is defined as •
x
=
{
y
∈
P
∪
T
∣
(
y
,
x
)
∈
F
}, while the postset of x is defined as x
•
=
{
y
∈
P
∪
T
∣
(
x
,
y
)
∈
F
}. Let X be a set of nodes with X
⊆
P
∪
T. We have •
X
=
∪
x
∈
X
•
x, and X
•
=
∪
x
∈
X
x
•. The structure of a self-loop-free PN can be represented by its incidence matrix [
N
]; that is, a |
P
|
×
|
T
| integer matrix with [
N
]
(
p
,
t
)
=
W
(
t
,
p
)
-
W
(
p
,
t
).A markingM of N is a mapping from P to ℕ. M
(
p
) denotes the number of tokens contained in place p. p is marked at marking M if M
(
p
)
>
0. (
N
,
M
0
) is called a net system or a marked net and M
0 is called an initial marking of N. A marking M can be denoted by ∑
p
∈
P
‍
M
(
p
)
p that is presented as multiset or formal sum notations. For example, a marking M
=
(
2,0
,
2,4
)
T in a net with four places can be denoted by M
=
2
p
1
+
2
p
3
+
4
p
4.A transitiont
∈
T is enabled at marking M if ∀
p
∈
t
•, M
(
p
)
≥
W
(
p
,
t
), which is denoted as M
[
t
〉. If t is enabled, it can fire. Its firing yields another marking M
′ such that ∀
p
∈
P
,
M
′
(
p
)
=
M
(
p
)
-
W
(
p
,
t
)
+
W
(
t
,
p
), which is denoted by M
[
t
〉
M
′. Marking M
′ is said to be reachable from M if there exists a transition sequence σ
=
t
1
t
2
⋯
t
n and markings M
1
,
M
2
,
…, and M
n
-
1 such that M
[
t
1
〉
M
1
[
t
2
〉
M
2
⋯
M
n
-
1
[
t
n
〉
M
′. This is denoted by M
[
σ
〉
M
′. The set of markings reachable from M in N defines the reachability set of (
N
,
M
), denoted as R
(
N
,
M
).A transitiont
∈
T in a PN system (
N
,
M
0
) is live at M
0 if ∀
M
∈
R
(
N
,
M
0
)
,
∃
M
′
∈
R
(
N
,
M
0
), M
′
[
t
〉 holds. The system (
N
,
M
0
) is live if ∀
t
∈
T, t is live at M
0. A PN (
N
,
M
0
) is safe if ∀
M
∈
R
(
N
,
M
0
), ∀
p
∈
P
,
M
(
p
)
≤
1. Generally, safe PNs are used to depict and analyze business processes, logistic systems, and workflow management systems. In a safe PN, a transition t
∈
T is enabled at marking M if ∀
p
∈
•
t, M
(
p
)
=
1, and ∀
p
∈
t
•, M
(
p
)
=
0.AP-vector is a column vector I
:
P
→
ℤ indexed by P, where ℤ is the set of integers. I is a P-invariant if I
≠
0 and [
N
]
T
·
I
=
0, where the bold0 denotes a column vector whose every entry equals 0. Let I be a P-invariant of N. Then ∀
M
∈
(
R
,
M
0
); I
T
·
M
=
I
T
·
M
0 holds. ∥
I
∥
=
{
p
∣
I
(
p
)
≠
0
} is called the support of I. I is called a minimal P-invariant if ∥
I
∥ is not a superset of the support of any other one and its components are mutually prime.LetN
=
(
P
,
T
,
F
) be a PN and n
1
,
n
k
∈
P
∪
T be two nodes in N, where k
∈
{
1,2
,
…
,
|
P
∪
T
|
}. A string C
=
n
1
n
2
⋯
n
k is called a path of N if ∀
i
∈
{
1,2
,
…
,
k
-
1
}, (
n
i
,
n
i
+
1
)
∈
F. C
=
n
1
n
2
⋯
n
k is called a directed path if ∀
i
∈
{
1,2
,
…
,
k
-
1
}, n
i
+
1
∈
n
i
•. C
=
n
1
n
2
⋯
n
k is called elementary path if for any two nodes n
i and n
j in C   i
≠
j
⇒
n
i
≠
n
j.Definition 1 (see [9]).
A PNN
=
(
P
,
T
,
F
) is said to be a workflow net (WF-net) if and only if (1)
N has a source place p
i
n
∈
P and a sink place p
out
∈
P such that •
p
in
=
∅ and p
out
•
=
∅.
(2)
For any nodex
∈
P
∪
T, x belongs to a directed path from p
in to p
out.
(
N
,
M
in
) is said to be a workflow system (WF-system) if M
in is the initial marking that contains only a singleton token in place p
in in the system.In this paper, “WF-net” and “WF-system” are used to distinguish an arbitrary net structureN and the structure N at initial marking M
in, that is, (
N
,
M
in
), respectively. WF-nets are a subclass of PNs. Hence, any analytical methods involved in PNs can be applied to WF-nets. In this paper, safe WF-system is considered only.Definition 2 (see [9]).
A PNN
~
=
(
P
~
,
T
~
,
F
~
) is said to be the extended WF-net from a WF-net N
=
(
P
,
T
,
F
) if an extra transition t
* exists such that P
~
=
P, T
~
=
T
∪
{
t
*
}, and F
~
=
F
∪
{
(
p
out
,
t
*
)
,
(
t
*
,
p
in
)
}. (
N
~
,
M
in
) is called an extended WF-system if (N
,
M
in) is a WF-system and N
~ is extended from N.The description of a business procedure in a WF-system is shown in Table1.Table 1
Description of a business procedure in a WF-system.
Business process
WF-system
Task
Transition
Condition
Place
Start condition
Marked source placep
in
End condition
Marked sink placep
out
Live task
Live transition in extended WF-system
Dead task
Dead transition in extended WF-system
Case
Path fromp
in to p
outThe life cycle of a business procedure is depicted by the logical relations among transitions in a WF-net. Marked source placep
in and sink place p
out in a WF-system are used to identify the beginning and the termination of a business procedure. A task in a business procedure contains three status:idle,ready, andfinished, which implies that a transition in corresponding WF-system is disabled, enabled, and fires, respectively.A WF-system cannot allow the retention of tokens in other places ifp
out is marked, which is ensured by condition (2) in Definition 1. Figures 2(a) and 2(b) show a WF-system (
N
,
M
in
) at initial marking M
in
=
(
1,0
,
0,0
,
0,0
)
T and its extended WF-system (
N
~
,
M
in
), respectively.(a) A sound WF-system(
N
,
M
in
), (b) the extended WF-system (
N
~
,
M
in
) of (
N
,
M
in
), and (c) a sound and well-structured WF-system (
N
′
,
M
in
′
).
(a)
(b)
(c)Definition 3 (see [9]).
A WF-system(
N
,
M
in
) with P
=
{
p
in,p
1
,
p
2
,
…
,
p
n
,
p
out
} is said to be sound if (1)
∀
M
∈
R
(
N
,
M
in
), M
in
[
σ
1
〉
M
⇒
∃
σ
2, [
σ
2
〉
M
out, where M
in
=
(
1
,
0,0
,
…
,
0
︸
n
+
1
)
T and M
out
=
(
0,0
,
…
,
0
︸
n
+
1
,
1
)
T.
(2)
∀
M
∈
R
(
N
,
M
in
), M
in
[
σ
1
〉
M
∧
M
≥
M
out
⇒
M
=
M
out.
(3)
∀
t
∈
T
~, ∀
M
∈
R
(
N
~
,
M
in
)
,
∃
M
′
∈
R
(
N
~
,
M
in
), M
′
[
t
〉 holds.Condition (1) in Definition3 guarantees that the marking M
out in a sound WF-system can be reached by firing an existing transition sequence at an arbitrary reachable marking, which implies that any case in a business procedure can be terminated eventually. Condition (2) in Definition 3 ensures that marking M
out is the only terminal marking. The fact that no dead transitions exist in the extended WF-system (
N
~
,
M
in
) of (N
,
M
in) is ensured by condition (3) in Definition 3.A WF-system(
N
,
M
in
) is sound if and only if the extended WF-system (
N
~
,
M
in
) of (
N
,
M
in
) is live and bounded. For example, the WF-system shown in Figure 2(a) is sound since its extended WF-system shown in Figure 2(b) is live and bounded.Definition 4 (see [9]).
A PNN is said to be well handled if for any pair of nodes x
∈
P
∪
T and y
∈
P
∪
T such that one of the nodes is a place and the other is a transition and for any pair of elementary paths C
1 and C
2 from x to y; the formula α
(
C
1
)
∩
α
(
C
2
)
=
{
x
,
y
}
⇒
C
1
=
C
2 holds, where α
(
C
1
) and α
(
C
2
) denote the set of all nodes in path C
1 and C
2, respectively. A WF-net N is well structured if the extended N
~ from N is well handled.The WF-system(
N
,
M
in
) shown in Figure 2(a) is not well structured and the WF-system (
N
′
,
M
in
′
) shown in Figure 2(c) is well structured. A well-structured WF-net has a number of nice properties. For example, the soundness of a WF-system can be verified in polynomial time and a sound well-structured WF-system is safe. A reasonable WF-system usually holds for soundness and well structure.


## 3. Conflicts, Concurrency, and Confusions

This section formalizes confusions in a PN system to a class of marked subnets with respect to special conflicting and concurrent characteristics. The formalization allows us to obtain a confusion detection policy in WF-systems.Definition 5 (see [32]).
A structural conflict in a netN
=
(
P
,
T
,
F
) is a pair K
=
〈
p
,
T
(
K
)
〉, where p
∈
P is called the structural conflicting place and T
(
K
)
=
{
t
1
,
t
2
,
…
,
t
n
} is the set of output transitions of p with n
=
|
p
•
|
≥
2. The elements in T
(
K
) are called structural conflicting transitions.Definition 6 (see [32]).
An effective conflict in a marked net(
N
,
M
0
), denoted by K
M
=
〈
p
,
T
(
K
M
)
,
M
〉, is associated with a structural conflict K
=
〈
p
,
T
(
K
)
〉 and a marking M
∈
R
(
N
,
M
0
) such that ∀
t
∈
T
(
K
M
), M
[
t
〉 is true, and M
(
p
)
<
∑
t
∈
T
(
K
M
)
W
(
p
,
t
), where T
(
K
M
)
⊆
T
(
K
) is the set of enabled transitions in T
(
K
) at marking M.The cardinality ofT
(
K
M
), that is, |
T
(
K
M
)
|, is said to be the size of effective conflict K
M. An effective conflict is said to be complete (resp., incomplete) if |
T
(
K
M
)
|
=
|
T
(
K
)
| (resp., 1
≤
|
T
(
K
M
)
|
<
|
T
(
K
)
|). Figures 3(a) and 3(b) show a structural conflict K
=
〈
p
2
,
{
t
1
,
t
2
,
t
3
,
t
4
}
〉 and an effective conflict K
M
=
〈
p
2
,
{
t
2
,
t
3
,
t
4
}
,
p
2
+
p
3
〉 associated with K, respectively, where T
(
K
)
=
{
t
1
-
t
4
} and T
(
K
M
)
=
{
t
2
-
t
4
}. The effective conflict K
M is incomplete since |
T
(
K
M
)
|
=
3
<
|
T
(
K
)
|
=
4.(a) A structural conflictK
=
〈
p
2
,
{
t
1
-
t
4
}
〉, (b) an effective conflict K
M
=
〈
p
2
,
{
t
2
-
t
4
}
,
p
2
+
p
3
〉, and (c) illustration of concurrency.
(a)
(b)
(c)Definition 7.
(1) Transitionst
1 and t
2 are said to be concurrent at marking M in a marked net (N
,
M) if M
[
t
1
〉, M
[
t
2
〉, and (
•
t
1
∪
t
1
•
)
∩
(
•
t
2
∪
t
2
•
)
=
∅.
(2) LetD
M
=
{
t
1
,
t
2
,
…
,
t
n
} be a transition set. It is said to be a set of concurrent transitions at marking M if ∀
t
i
,
t
k
∈
D
M, i
≠
k; transitions t
i and t
k are concurrent at marking M.
(3) The concurrent degree of a setD
M of concurrent transitions, denoted by λ, is defined as λ
=
|
D
M
|.
(4) LetD
M be a set of concurrent transitions in a marked net (N
,
M) with λ
=
|
D
M
|. It is said to be λ-max-concurrent in (N
,
M) if there does not exist a set of concurrent transitions D
^
M
≠
D
M with λ
^
=
|
D
^
M
| in (N
,
M) such that λ
^
>
λ. A transition in D
M is said to be λ-max-concurrent if D
M is λ-max-concurrent in (N
,
M).
(5) Let𝔻
M
=
{
D
1
M
,
D
2
M
,
…
,
D
ρ
M
} be the set of concurrent transition sets in (N
,
M); that is, ∀
D
j
M
∈
𝔻
M; D
j
M is a set of concurrent transitions in (N
,
M). 𝔻
M is said to be λ-max-concurrent if ∀
D
j
M
∈
𝔻
M; D
j
M is λ-max-concurrent in (N
,
M).Figure3(c) shows a marked PN that contains totally seven sets D
1
M
=
{
t
1
,
t
4
}, D
2
M
=
{
t
1
,
t
5
}, D
3
M
=
{
t
1
,
t
6
}, D
4
M
=
{
t
4
,
t
5
}, D
5
M
=
{
t
4
,
t
6
}, D
6
M
=
{
t
1
,
t
4
,
t
5
}, and D
7
M
=
{
t
1
,
t
4
,
t
6
} of concurrent transitions at marking M
=
p
1
+
p
4
+
p
5. Two sets D
6
M and D
7
M with λ
6
=
λ
7
=
3 are 3-max-concurrent since there does not exists a set of concurrent transitions from D
1
M to D
7
M, whose cardinality is greater than three. Suppose that 𝔻
1
M
=
{
D
6
M
,
D
7
M
} and 𝔻
2
M
=
{
D
1
M
,
D
2
M
,
D
7
M
} are two sets of concurrent transition sets. Then, 𝔻
1
M is 3-max-concurrent and 𝔻
2
M is not 3-max-concurrent since the concurrent degrees of D
1
M and D
2
M in 𝔻
2
M are less than three.Definition 8.
A marked PN(
N
¯
=
(
P
¯
,
T
¯
,
F
¯
)
,
M
¯
) is said to be a marked subnet of a PN system (
N
=
(
P
,
T
,
F
)
,
M
) if P
¯
⊆
P, T
¯
⊆
T, F
¯
=
F
∩
[
(
P
¯
×
T
¯
)
∪
(
T
¯
×
P
¯
)
], and M
¯ is a natural projection of marking M on place set P
¯. M
¯ is said to be valid (resp., invalid), denoted by M
¯
≺
M (resp., M
¯
⊀
M), if ∃
p
∈
P
¯, M
¯
(
p
)
=
1 (resp., ∀
p
∈
P
¯, M
¯
(
p
)
=
0).Definition 9.
A confusion, denoted by(
N
¯,T
(
K
)
,
M
¯,𝔻
M
¯
) or abbreviated to (
N
¯
,
M
¯
), is a marked subnet in a net system (
N
,
M
0
) such that(1)
there exists a structural conflictK
=
〈
p
,
T
(
K
)
〉 with p
∈
P
¯ and T
(
K
)
⊂
T
¯;
(2)
there exists a nonempty set𝔻
M
¯ that is composed of all 2-max-concurrent transition sets at the submarking M
¯ in (
N
¯
,
M
¯
);
(3)
∀
D
j
M
¯
∈
𝔻
M
¯, ∃
t
i
∈
D
j
M
¯
∖
T
(
K
) such that M
¯
[
t
i
〉
M
¯
′ and |
T
(
K
M
¯
)
|
≠
|
T
(
K
M
¯
′
)
|;
(4)
there exist two reachable markingsM and M
′ in R
(
N
,
M
0
) such that M
¯
≺
M and M
¯
′
≺
M
′ are true.A confusion is said to be a conflict-increasing confusion (CIC) if |
T
(
K
M
¯
)
|
<
|
T
(
K
M
¯
′
)
|. It is said to be a conflict-decreasing confusion (CDC) if |
T
(
K
M
¯
)
|
>
|
T
(
K
M
¯
′
)
|.Confusions are tackled as the marked subnets in a PN system, which are distinguished into CICs and CDCs. Two requirements on confusions are imposed by Conditions (1) and (2) in Definition9, respectively. If a marked subnet (
N
¯
,
M
¯
) is a confusion, it necessarily contains a structural conflict and all the sets of concurrent transitions in (
N
¯
,
M
¯
) are 2-max-concurrent at marking M
¯.Condition (3) in Definition9 implies the behavior characteristics of confusions. For a structural conflict K in a confusion, there exists at least a transition t not belonging to T
(
K
) in the confusion. Firing t changes the size of effective conflicts associated with K. Condition (4) in Definition 9 ensures that the behavior described in Condition (3) can actually occur in the original net system. Finally, confusions are classified into CICs and CDCs according to the relations of the size change of effective conflicts in Definition 9.If a marked subnet of a PN system satisfies Definition9, the disappearance of complete effective conflicts will occur in the marked subnet. The limitation of the 2-max-concurrency can limit the size of a subnet at a marking such that the marked subnet is exactly a CIC or a CDC. In other words, the behavior of a confusion defined in Definition 9 with the limitation of 2-max-concurrency can only be one of the two results, that is, increasing or decreasing the size of effective conflicts. Examples 1 and 2 are given to show the structures and behavior of CICs and CDCs defined in Definition 9, respectively.Example 1.
The marked subnet shown in Figure4(a) is a CIC (
N
¯
1
,
T
(
K
1
)
,
M
¯
1
,
𝔻
M
¯
1
), where T
(
K
1
)
=
{
t
1
,
t
2
,
t
3
,
t
4
}, M
¯
1
=
p
1
+
p
4, 𝔻
M
¯
1
=
{
D
1
M
¯
1
,
D
2
M
¯
1
}, D
1
M
¯
1
=
{
t
1
,
t
5
}, and D
2
M
¯
1
=
{
t
2
,
t
5
}. The confusion holds for Conditions (1) and (2) in Definition 9. N
¯
1 contains a structural conflict K
1
=
〈
p
1
,
{
t
1
-
t
4
}
〉 and two 2-max-concurrent transition sets D
1
M
¯
1 and D
2
M
¯
1 exist in the confusion such that 𝔻
M
¯
≠
∅ is true.Figure 4
The partial reachability graph of a CIC(
N
¯
1
,
M
¯
1
) with |
T
(
K
1
)
|
=
4 by concurrently firing transitions in D
1
M
¯
1
=
{
t
1
,
t
5
} and D
2
M
¯
1
=
{
t
2
,
t
5
}.The partial reachability graph of the confusion is shown in Figures4(b) and 4(c), which are obtained by concurrently firing transitions in D
1
M
¯
1
=
{
t
1
,
t
5
} and D
2
M
¯
1
=
{
t
2
,
t
5
}, respectively, where two transition firing sequences σ
1
=
t
1
t
5 and σ
2
=
t
5
t
1 (resp., σ
3
=
t
2
t
5 and σ
4
=
t
5
t
2) can be observed from the initial marking M
¯
1
=
p
1
+
p
4 to the terminal marking M
¯
4
=
p
2
+
p
3
+
p
5 (resp., M
¯
6
=
p
2
+
p
3
+
p
6) in Figure 4(b) (resp., Figure 4(c)) and any marking M
¯
j in Figure 4 is represented with the size of the effective conflict K
1
M
¯
j; that is, |
T
(
K
1
M
¯
j
)
|.According to Condition (3) in Definition9, (N
¯
1
,
M
¯
1) is a CIC since firing the nonconflicting transition t
5
∉
K
1 in D
1
M
¯
1 (resp., D
2
M
¯
1) can expand the size of the effective conflicts associated with K
1 from |
T
(
K
1
M
¯
1
)
|
=
2 to |
T
(
K
1
M
¯
3
)
|
=
|
T
(
K
1
)
|
=
4, where K
1
M
¯
1
=
〈
p
1
,
{
t
1
,
t
2
}
,
p
1
+
p
4
〉 is incomplete and K
1
M
¯
3
=
〈
p
1
,
{
t
1
-
t
4
}
,
p
1
+
p
2
+
p
3
〉 is complete.The fact whether the complete effective conflictK
1
M
¯
3 occurs according to the concurrent firing of transitions in D
1
M
¯
1
=
{
t
1
,
t
5
} and D
2
M
¯
1
=
{
t
2
,
t
5
} is nondeterministic. If σ
2
=
t
5
t
1 and σ
4
=
t
5
t
2 fire, the complete effective conflict K
1
M
¯
3 with size |
T
(
K
1
M
¯
3
)
|
=
|
T
(
K
1
)
|
=
4 at marking M
¯
3
=
p
1
+
p
2
+
p
3 can occur. If σ
1
=
t
1
t
5 and σ
3
=
t
2
t
5 fire, the processes M
¯
1
[
t
1
〉
M
¯
2
[
t
5
〉
M
¯
4 and M
¯
1
[
t
2
〉
M
¯
5
[
t
5
〉
M
¯
6 do not expand the size of the effective conflicts associated with K
1 such that a complete effective conflict occurs, where M
¯
1
=
p
1
+
p
2, M
¯
2
=
p
4
+
p
5, M
¯
4
=
p
2
+
p
3
+
p
5, M
¯
5
=
p
4
+
p
6, and M
¯
6
=
p
2
+
p
3
+
p
6.The completeK
1
M
¯
3 is expected to occur since all the structural conflicting transitions in K
1 are enabled such that the options can be done among transitions t
1
-
t
4. In this case, we can say that the disappearance of the effective conflict K
1
M
¯
3 occurs if the CIC fires the transition sequences σ
1
=
t
1
t
5 and σ
3
=
t
2
t
5.Example 2.
The marked subnet shown in Figure5(a) is a CDC that consists of two structural conflicts K
2
=
〈
p
1
,
{
t
1
-
t
4
}
〉 and K
3
=
〈
p
2
,
{
t
3
-
t
6
}
〉 at the initial marking M
¯
1
=
p
1
+
p
2. Only K
2 in the confusion is considered due to the symmetry. In other words, the confusion (
N
¯
2
,
T
(
K
2
)
,
M
¯
1
,
𝔻
M
¯
1
) is analyzed, where T
(
K
2
)
=
{
t
1
-
t
4
}, 𝔻
M
¯
1
=
{
D
1
M
¯
1, D
2
M
¯
1, D
3
M
¯
1, D
4
M
¯
1
}, D
1
M
¯
1
=
{
t
1
,
t
5
}, D
2
M
¯
1
=
{
t
1
,
t
6
}, D
3
M
¯
1
=
{
t
2
,
t
5
}, and D
4
M
¯
1
=
{
t
2
,
t
6
}.
The confusion is a CDC since firing transitiont
5
∉
T
(
K
2
) in D
1
M
¯
1 and D
3
M
¯
1 or firing another transition t
6
∉
T
(
K
2
) in D
2
M
¯
1 and D
4
M
¯
1 reduces the size of the effective conflict K
2
M
¯
1
=
〈
p
1
,
{
t
1
,
t
2
,
t
3
,
t
4
}
,
M
¯
1
〉 such that the options cannot be done in the complete effective conflict K
2
M
¯
1.
The partial reachability graph obtained by concurrently firing transitionst
1 and t
5 in D
1
M
¯
1 is shown in Figure 5(b). Two transition firing sequences σ
1
=
t
1
t
5 and σ
2
=
t
5
t
1 can be obtained. The complete effective conflict K
2
M
¯
1
=
〈
p
1
,
{
t
1
-
t
4
}
,
M
¯
1
〉 with |
T
(
K
2
M
¯
1
)
|
=
|
T
(
K
2
)
|
=
4 can be found at the initial marking M
¯
1
=
p
1
+
p
2. Hence, the options on conflicting transitions from t
1 to t
4 should be done for the effective conflict K
2
M
¯
1. However, an unfortunate transition t
5
∉
T
(
K
2
) can concurrently fire such that the size is reduced from |
T
(
K
2
M
¯
1
)
|
=
4 to |
T
(
K
2
M
¯
3
)
|
=
2, which leads to disabled conflicting transitions t
3 and t
4 before the options among conflicting transitions t
1
-
t
4 are executed, where M
¯
3
=
p
1
+
p
7. In this case, we can say that the disappearance of the effective conflict K
2
M
¯
1 occurs if the confusion fires transition sequence σ
2
=
t
5
t
1.
The concurrent firing of the transitions in other setsD
2
M
¯
1, D
3
M
¯
1, and D
4
M
¯
1 can be analyzed by the similar procedures of the analysis for transitions t
1 and t
5 in D
1
M
¯
1. Specifically, the disappearance of the effective conflict K
2
M
¯
1 occurs if the confusion fires transition sequence σ
3
=
t
6
t
1, σ
4
=
t
5
t
2, or σ
5
=
t
6
t
2.Figure 5
The partial reachability graph of a CDC (N
¯
2
,
M
¯
1) with |
T
(
K
2
)
|
=
4 by concurrently firing transitions in D
1
M
¯
1
=
{
t
1
,
t
5
}, D
2
M
¯
1
=
{
t
1
,
t
6
}, D
3
M
¯
1
=
{
t
2
,
t
5
}, and D
4
M
¯
1
=
{
t
2
,
t
6
}.


## 4. Detection of Confusions in WF-Systems

Conflicts and concurrency are used to control the option processes and to keep a high-performance operation of a WF-system. However, confusions may lead to the incomplete and nondeterministic conflicting behavior.This section deals with the detection problem of confusions in WF-systems. A confusion is tied to a special structure and a marking. Hence, the detection method is divided into two steps. First, the structureN
¯ of a confusion (N
¯
,
M
¯) in a WF-system is detected. Then, whether there exists a marking M
¯ such that the confusion occurs is decided by a method of integer linear programming (ILP), which does not require computing the reachability graph of the WF-system.Property 1.
IfN
¯ is a CIC subnet in a WF-net N, then ∃
t
i
,
t
j
,
t
k
∈
T
¯, i
≠
j
≠
k such that (
•
t
i
∪
t
i
•
)
∩
(
•
t
j
∪
t
j
•
)
=
∅
∧
t
k
∈
(
t
j
•
)
•
∧
t
i
•
∩
t
k
•
≠
∅ is true. If N
¯ is a CDC subnet in a WF-net N, then ∃
t
i
,
t
j
∈
T, i
≠
j such that (
•
t
i
∪
t
i
•
)
∩
(
•
t
j
∪
t
j
•
)
=
∅
∧
(
•
t
i
)
•
∩
(
•
t
j
)
•
≠
∅ is true.Property1 depicts the structural characteristics of a CIC and a CDC described in Definition 9. Algorithm 1 is developed to capture all confusion subnets in a WF-net according to Property 1. Let T
(
K
,
t
)
:
=
{
t
′
∣
t
′
∈
T
∧
t
•
∩
t
′
•
} in Algorithm 1 denote the conflicting transition set containing t.Algorithm 1:Detection of confusion subnets in WF-net N.
(1)
Input: WF-net N
=
(
P
,
T
,
F
).
(2)
Output: The set Q
ci of CIC subnets and the set Q
cd of CDC subnets.
(3)
Q
ci
:
=
∅, Q
cd
:
=
∅, h
:
=
0.
(4)
for each t
i
,
t
j
,
t
k
∈
T, i
≠
j
≠
k  do
(5) if  (
•
t
i
∪
t
i
•
)
∩
(
•
t
j
∪
t
j
•
)
=
∅
∧
t
k
∈
(
t
j
•
)
•
∧
•
t
i
∩
•
t
k
≠
∅  then
(6)  Capture a CIC subnet N
-
h
=
(
P
-
h
,
T
-
h
,
F
-
h
), where
(1)P
-
h
:
=
•
T
(
K
,
t
k
)
∪
T
(
K
,
t
k
)
•
∪
•
t
j
∪
(
t
j
•
∩
•
T
(
K
,
t
k
)
),
(2)T
-
h
:
=
T
(
K
,
t
k
)
∪
{
t
j
}, and
(3)F
-
h
:
=
F
∩
(
(
P
-
h
×
T
-
h
)
∪
(
T
-
h
×
P
-
h
)
).
(7)  if  N
-
h
∉
Q
ci  then
(8)
h
:
=
h
+
1, Q
ci
:
=
Q
ci
∪
N
-
h.
(9)  else
(10)
Q
ci
:
=
Q
ci.
(11)  end if
(12) end if
(13)
end for
(14)
for each t
i
,
t
j
∈
T, i
≠
j  do
(15) If
(
•
t
i
∪
t
i
•
)
∩
(
•
t
j
∪
t
j
•
)
=
∅
∧
(
•
t
i
)
•
∩
(
•
t
j
)
•
≠
∅
then
(16)  Capture a CDC subnet N
-
h
=
(
P
-
h
,
T
-
h
,
F
-
h
), where
(1)  P
-
h
:
=
•
T
(
K
,
t
i
)
∪
T
(
K
,
t
i
)
•
∪
•
T
(
K
,
t
j
)
∪
T
(
K
,
t
j
)
•,
(2)  T
-
h
:
=
T
(
K
,
t
i
)
∪
T
(
K
,
t
j
), and
(3)  F
-
h
:
=
F
∩
(
(
P
-
h
×
T
-
h
)
∪
(
T
-
h
×
P
-
h
)
).
(17)  if  N
-
h
∉
Q
cd  then
(18)
h
:
=
h
+
1, Q
cd
:
=
Q
cd
∪
N
-
h.
(19)  else
(20)
Q
cd
:
=
Q
cd.
(21)  end if
(22) end if
(23)
end for
(24)
Output: Q
ci and Q
cd.In a WF-system, the captured confusion subnets cannot perfectly describe the phenomenon of confusions since they are not related to markings. It does not mean that a confusion(
N
¯
,
M
¯
) necessarily exists if there is a confusion subnet N
¯ in a WF-system. Hence, we need to decide whether there exists a marking M
¯ such that confusion (
N
¯
,
M
¯
) occurs.Theorem 10.
Let (N
,
M
i
n) be a sound WF-system. Let I
1
,
I
2
,
…, and I
n denote all the minimal P-invariants computed by I
T
[
N
]
=
0
T. Then (N
,
M
i
n) is covered by I
1
,
I
2
,
…, and I
n and ∀
j
∈
{
1,2
,
…
,
n
}; Σ
p
∈
∥
I
j
∥
M
(
p
)
=
M
i
n
(
p
i
n
)
=
1 is true.Proof.
According to Definition1, we have ∀
p
i
∈
P; p
i belongs to an elementary directed path from p
in to p
out in N. Any elementary directed path in a WF-system (N
,
M
in) can deduce a minimal P-invariant. Hence, (N
,
M
in) is covered by I
1
,
I
2
,
…, and I
n if there are total n minimal P-invariants. A P-invariant I
j holds for I
j
T
·
M
=
I
j
T
·
M
in
=
1. Hence, we have Σ
p
∈
∥
I
j
∥
M
(
p
)
=
M
i
n
(
p
in
)
=
1.Algorithm2 is proposed according to Theorem 10, which is referred to find the places that may lead to the disappearance of an effective conflict in a confusion if they are marked. Then, an ILP is developed to decide whether a marking exists such that all these places are marked. If the result of the ILP equals the number of the places, an existing confusion in a WF-system can be finally determined.Algorithm 2:Detection of confusions by the ILP in WF-system (
N
,
M
in
).
(1)
Input: WF-system (
N
,
M
in
), Q
ci, and Q
cd.
(2)
Output: The set Q
^
ci of CICs and the set Q
^
cd of CDCs.
(3)
Q
^
ci
:
=
∅, Q
^
cd
:
=
∅,
(4)
for each N
-
h
∈
Q
ci  do
(5) Compute [
N
]
T
·
I
=
0 to obtain all minimal P-invariants I
1
,
I
2
,
…, and I
n.
(6) Find K
=
〈
p
,
T
(
K
)
〉 in N
-
h.
(7) Ω
1
:
=
T
-
∖
T
(
K
), Ω
2
:
=
T
(
K
)
∖
(
T
(
K
)
∩
(
Ω
1
•
)
•
).
(8) Compute the value υ of following ILP:
(
max
⁡
Σ
p
∈
•
(
Ω
1
∪
Ω
2
)
M
(
p
)
s.t.
:
Σ
p
∈
|
|
I
1
|
|
M
(
p
)
=
M
in
(
p
in
)
=
1
Σ
p
∈
|
|
I
2
|
|
M
(
p
)
=
M
in
(
p
in
)
=
1
,
⋮
Σ
p
∈
|
|
I
n
|
|
M
(
p
)
=
M
in
(
p
in
)
=
1
.
)
(9) if  υ
=
|
•
(
Ω
1
∪
Ω
2
)
|  then
(10)  M
-
:
=
Σ
p
∈
•
(
Ω
1
∪
Ω
2
)
M
(
p
)
p.
(11)  Q
^
ci
:
=
Q
^
ci
∪
(
N
-
h
,
M
-
).
(12) else
(13) Q
^
ci
:
=
Q
^
ci.
(14) end if
(15)
end for
(16)
for each N
-
h
∈
Q
cd  do
(17) Compute [
N
]
T
·
I
=
0 to obtain all minimal P-invariants I
1
,
I
2
,
…, and I
n.
(18) Compute the value υ of following ILP:
(
max
⁡
Σ
p
∈
•
T
-
M
(
p
)
s.t.
:
Σ
p
∈
|
|
I
1
|
|
M
(
p
)
=
M
in
(
p
in
)
=
1
Σ
p
∈
|
|
I
2
|
|
M
(
p
)
=
M
in
(
p
in
)
=
1
,
⋮
Σ
p
∈
|
|
I
n
|
|
M
(
p
)
=
M
in
(
p
in
)
=
1
.
)
(19) if  υ
=
|
•
T
-
|  then
(20)  M
-
:
=
Σ
p
∈
•
T
-
M
(
p
)
p.
(21)  Q
^
cd
:
=
Q
^
cd
∪
(
N
-
h
,
M
-
).
(22) else
(23)  Q
^
cd
:
=
Q
^
cd.
(24) end if
(25)
end for
(26)
Output: Q
^
ci and Q
^
cd.Let(
N
,
M
in
) be a WF-system and Q
ci and Q
cd denote the sets of its CIC and CDC subnets obtained by Algorithm 1, respectively. Suppose that N
¯
=
(
P
¯
,
T
¯
,
F
¯
)
∈
Q
c
i is a CIC subnet in (
N
,
M
in
), where T
(
K
) is the transition set of a structural conflict K in N, Ω
1
=
T
¯
∖
T
(
K
) is a set containing all nonconflicting transitions in T
¯, and Ω
2
=
T
(
K
)
∖
(
T
(
K
)
∩
(
Ω
1
•
)
•
) is a transition set with respect to K in T
¯. If there exists a marking M
¯
≺
M
∈
R
(
N
,
M
i
n
) with Σ
p
∈
•
(
Ω
1
∪
Ω
2
)
M
(
p
)
=
|
•
(
Ω
1
∪
Ω
2
)
|, that is, ∀
p
∈
(
Ω
1
∪
Ω
2
)
•, p is marked at M, we can decide that (N
¯
,
M
¯) is a CIC that can occur in the WF-system (
N
,
M
in
). Similarly, for a CDC subnet N
¯ in a WF-system (N
,
M
in), if there exists a marking M
¯
≺
M
∈
R
(
N
,
M
in
) with Σ
p
∈
T
¯
•
M
(
p
)
=
|
•
T
¯
|, we can decide that (N
¯
,
M
¯) is a CDC in the WF-system (
N
,
M
in
). The decision processes are formulated in Algorithm 2.Two WF-systems (N
,
M
in) and (N
′
,
M
in
′) are used to illustrate the proposed detection policy of confusions, which are shown in Figures 6(a) and 6(b), respectively. The WF-system (N
,
M
in) is sound and another WF-system (N
′
,
M
in
′) is sound and well structured, where anyone of them contains a CIC.(a) A sound WF-system(
N
,
M
in
), (b) a sound and well-structured WF-system (N
′
,
M
in
′), (c) a CIC (N
¯
,
M
¯) in (
N
,
M
in
), and (d) a CIC (N
¯
′
,
M
¯
′) in (
N
′
,
M
in
′
).
(a)
(b)
(c)
(d)If Algorithm1 is applied in WF-net N, the CIC subnet N
¯ shown in Figure 6(c) can be obtained, where t
i
:
=
t
2, t
j
:
=
t
3, t
k
:
=
t
5, and (
•
t
2
∪
t
2
•
)
∩
(
•
t
3
∪
t
3
•
)
=
∅
∧
t
5
∈
(
t
3
•
)
•
∧
•
t
2
∩
•
t
5
≠
∅ is true. Hence, the sets P
¯, T
¯, and F
¯ in N
¯ can be computed; that is,(1)
P
¯
:
=
T
•
(
K
,
t
5
)
∪
T
(
K
,
t
5
)
•
∪
t
3
•
∪
(
t
3
•
∩
T
•
(
K
,
t
5
)
)
=
{
p
1
,
p
4
}
∪
{
p
3
,
p
out
}
∪
{
p
2
}
∪
{
p
4
}
=
{
p
1
-
p
4
,
p
out
};
(2)
T
¯
:
=
T
(
K
,
t
5
)
∪
{
t
3
}
=
{
t
2
,
t
5
}
∪
{
t
3
}
=
{
t
2
,
t
3
,
t
5
};
(3)
F
¯
:
=
F
∩
(
(
P
¯
×
T
¯
)
∪
(
T
¯
×
P
¯
)
).Algorithm2 is applied to decide whether there exists a reachable marking M
¯ in (
N
,
M
in
) such that (
N
¯
,
M
¯
) is a CIC. First, the supports of three minimal P-invariants I
1
-
I
3, that is, ∥
I
1
∥
=
{
p
in
,
p
1
,
p
3
,
p
out
}, ∥
I
2
∥
=
{
p
in
,
p
1
,
p
out
}, and ∥
I
3
∥
=
{
p
in
,
p
2
,
p
4
,
p
out
}, are obtained by computing [
N
]
T
·
I
=
0. Then, the ILP depicted in line 8 of Algorithm 2 can be implemented and returns a value v
=
2. It implies that there exists a marking in WF-system (
N
,
M
in
) such that places p
1 and p
2 in N
¯ are marked. In other words, a confusion (
N
¯
,
M
¯
) with M
¯
=
p
1
+
p
2 is detected, which will occur in the WF-system (N
,
M
in). Similarly, in WF-system (N
′
,
M
in
′), the confusion (N
¯
′
,
M
¯
′) shown in Figure 6(d) can be detected by the procedures of Algorithms 1 and 2. These examples show that the detection method developed in this paper can effectively detect confusions in WF-systems.The WF-system (N
′′
,
M
in
′′) shown in Figure 7(a) depicts a real-world case of complaint processes, which is reported in [9]. There are four structural conflicts K
1
=
〈
p
3
,
{
t
3
,
t
4
}
〉, K
2
=
〈
p
4
,
{
t
8
,
t
13
}
〉, K
3
=
〈
p
6
,
{
t
6
,
t
7
}
〉, and K
4
=
〈
p
11
,
{
t
11
,
t
12
}
〉, which implement the logical judgments of WF-system (N
′′
,
M
in
′′) such that a complaint case can be complete. According to the study in this paper, the prerequisite of implementing reasonable logical judgment is that the WF-system (N
′′
,
M
in
′′) is confusion-free. Hence, Algorithms 1 and 2 are considered in (N
′′
,
M
in
′′). First, the confusion subnet N
′′ shown in Figure 7(b) can be detected by Algorithm 1. However, a confusion with respect to N
′′ will not occur in the WF-system (N
′′
,
M
in
′′) since the ILP in Algorithm 2 returns the value v
=
2. It is shown that no reachable marking exists in the WF-system such that all the places p
4, p
6, and p
7 in N
′′ are marked. Finally, a conclusion that the complaint process will not cause a confusion and its WF-system is confusion-free is obtained. The WF-system can be correctly used to model and analyze complaint cases without considering the disappearance of any conflict.(a) A real-world WF-system (N
′′
,
M
in
′′) of complaint processes and (b) a CIC subnet N
′′ in (N
′′
,
M
in
′′).
(a)
(b)


## 5. Impact of Confusions on the Properties of WF-Systems

The algorithms developed in Section4 show a policy to detect confusions in a WF-system. In the following, the impact of confusions on the properties of WF-systems is specified.Property 2.
A sound and well-structured WF-net(
N
,
M
in
) with cycles may contain confusions.Proof.
The example shown in Figure6(b) that is a sound and well-structured with a cycle. According to Algorithms 1 and 2, a CIC shown in Figure 6(d) can be obtained. Hence, a sound and well-structured WF-net (
N
,
M
in
) with cycles may contain confusions.Property 3.
An acyclic sound WF-system(
N
,
M
in
) is not well structured if (
N
,
M
in
) contains a confusion (
N
¯
,
M
¯
) with M
¯
≺
M
∈
R
(
N
,
M
in
).Proof.
There are two cases only for confusion subnetN
¯.
Case  (1). If N
¯ is a CIC subnet, there must be three differentiable transitions t
i, t
j, and t
k holding for (
•
t
i
∪
t
i
•
)
∩
(
•
t
j
∪
t
j
•
)
=
∅, t
k
∈
(
t
j
•
)
•, and •
t
i
∩
t
k
•
≠
∅. According to Definitions 1 and 3, and •
t
i
∩
t
j
•
=
∅, there must be some places and a transition t
∈
T
¯ modeling an AND-split such that two different elementary paths C
1
=
p
in
,
…
,
t
,
…
,
p
a
,
…
,
p
out and C
2
=
p
in
,
…
,
t
,
…
,
p
b
,
…
,
p
out in N exist, where p
a
∈
t
i
•, p
b
∈
t
j
•, and p
a
≠
p
b. Otherwise, if t
∉
T
¯, ∄
M
¯
≺
M
∈
R
(
N
,
M
in
) holding for M
¯
[
t
i
〉 and M
¯
[
t
j
〉. In other words, there is a dead transition between t
i and t
j in the extended WF-system (N
~
,
M
in), which violates the sound property. Hence, transition t necessarily exists.
(
N
,
M
in
) is sound and transition t splits a token into multiple tokens. Hence, there must be some transitions and places with p
∈
P
¯ modeling an AND-join such that the tokens in different places can converge to p. We can deduce that there exist two different elementary paths C
1
=
p
in
,
…
,
t
,
…
,
p
a
,
…
,
p
,
…
,
p
out and C
2
=
p
in
,
…
,
t
,
…
,
p
b
,
…
,
p
,
…
,
p
out in N. Otherwise, if p
∉
P
¯, we can conclude that ∃
M
∈
R
(
N
,
M
in
)
∧
M
≥
M
out
⇏
M
=
M
out. In other words, there are tokens in the places belonging to P
¯
∖
{
p
in
∪
p
out
} at the terminal state in (
N
,
M
in
), which also violates the sound property. According to C
1 and C
2, we have two different elementary paths C
1
′
=
t
,
…
,
p
a
,
…
,
p and C
2
′
=
t
,
…
,
p
b
,
…
,
p owing to p
a
≠
p
b. However, α
(
C
1
′
)
∩
α
(
C
2
′
)
=
{
t
,
p
} cannot deduce C
1
′
=
C
2
′. According to Definition 4, (
N
,
M
in
) is not well structured.
Case  (2). If N
¯ is a CDC subnet, there must be three differentiable transitions t
i, t
j, and t
k holding for (
•
t
i
∪
t
i
•
)
∩
(
•
t
j
∪
t
j
•
)
=
∅, (
•
t
i
)
•
∩
(
•
t
j
)
•
≠
∅, and t
k
∈
(
•
t
i
)
•
∩
(
•
t
j
)
•. WF-system (
N
,
M
in
) is sound. Hence, there exists a marking M
¯ with respect to M
¯
≺
M
∈
R
(
N
,
M
in
) holding for M
¯
[
t
i
〉 and M
¯
[
t
j
〉. Otherwise, if M
¯ does not exist, transition t
k will be dead owing to t
k
∈
(
•
t
i
)
•
∩
(
•
t
j
)
•
≠
∅. According to Definition 1, •
t
i
∩
t
j
•
=
∅ and t
i
•
∩
t
j
•
=
∅, there must be some places and a transition t
∈
T
¯ modeling an AND-split and also exist some transitions and places with p
∈
P
¯ modeling an AND-join to product two different elementary paths C
1
=
p
in
,
…
,
t
,
…
,
p
a
,
…
,
p
,
…
,
p
out and C
2
=
p
in
,
…
,
t
,
…
,
p
b
,
…
,
p
,
…
,
p
out, where p
a
∈
t
i
•, p
b
∈
t
j
•, and p
a
≠
p
b. Similarly, C
1
′
=
t
,
…
,
p
a
,
…
,
p and C
2
′
=
t
,
…
,
p
b
,
…
,
p are also two different elementary paths. According to Definition 4, (
N
,
M
in
) is not well structured.According to Property3, confusions can affect the property “well-structured” of an acyclic sound WF-system. As an example, the acyclic sound WF-system shown in Figure 6(a) is not well structured owing to the existence of a CIC.


## 6. Conclusions and Future Work

Confusion detection problems in WF-systems are tackled in this paper. First, the work explores CICs and CDCs in a WF-system by formalizing them as a class of marked subnets with respect to the limitation of conflicts and concurrency. The disappearance of conflicts in a confusion can be described in such marked subnets, which motivates us to develop confusion detection methods proposed in this paper.Second, a policy is developed to capture confusions, in which a detection algorithm is proposed to find confusion subnets in a WF-system and a decision algorithm based on ILP is proposed to decide whether the found subnets will eventually cause confusions at a reachable marking. The policy avoids computing the reachability graph of a WF-system. Two examples and a real-world case of WF-systems reported by van der Aalst [9] are used to illustrate the detection of confusions. The results show that the detection method is feasible and efficient.Third, the impact of confusions on the properties of WF-systems is specified. A conclusion is obtained; that is, if an acyclic WF-system contains a confusion, it is certainly not well structured. Future work attempts to find the avoidance policy of confusions in WF-systems by using timing constraints in [3] or supervisory control in [6].



---

*Source: 825313-2014-05-07.xml*