IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS: SYSTEMS, VOL. 45, NO. 8, AUGUST 2015 1201
Co-NP-Hardness of the Soundness Problem for
Asymmetric-Choice Workflow Nets
Guanjun Liu and Changjun Jiang
Abstract—van der Aalst et al. proved that the soundness problem is
solvable in polynomial time for free-choice workflow nets (FCWF-nets).
However, FCWF-nets cannot model most web services composition and
interorganizational business processes because the interaction among pro-
cesses does not usually satisfy the free-choice requirement. Asymmetric-
choice workflow nets (ACWF-nets) as a larger class than FCWF-nets
can model lots of such cases. Our previous work showed that the (weak)
soundness problem is co-NP-hard for three-bounded ACWF-nets. Later,
Tiplea et al. proved that for three-bounded acyclic ACWF-nets, the weak
soundness problem is co-NP-complete. We sharp these results in this
paper. First, we prove that for ACWF-nets, whether they are one-bounded
or k-bounded (k > 1), the soundness problem is co-NP-hard. Second, it
is proven that the soundness is equivalent to the weak soundness for any
acyclic ACWF-nets, i.e., an acyclic ACWF-net is sound if and only if it
is weakly sound.
Index Terms—Business process models, complexity, interorga-
nizational workflow nets, soundness, web service composition.
I. I
NTRODUCTION
Workflow nets (WF-nets), as stated by van der Aalst et al. [3],
have become one of the standard ways to model and analyze work-
flows. In fact, WF-nets can also model many other concurrent systems
such as web services composition in which multiple processes inter-
act via sending/receiving messages [5], [7], [10], [19], [21]. Notice
that the models of these interactive systems are usually called
interorganizational WF-nets that may be thought of as a class of
WF-nets [12], [13].
Soundness [1], [3] is a crucial property of WF-nets. It implies that
the target state can always be reachable and each task has a (potential)
right to be executed. Sometimes, web service compositions do not
require that each task must take part in the runs of these systems.
Therefore, soundness is too strict for them and thus weak soundness
is defined [3]. Weak soundness guarantees that the target state is
always reachable but not each task has a chance to be executed.
van der Aalst et al. [3] proved that the (weak) soundness problem is
decidable for general WF-nets. We also proved that the (weak) sound-
ness problem is PSPACE-complete for bounded WF-nets [11], [14].
Fortunately, van der Aalst et al. [2], [3] gave a polynomial-time
algorithm to solve the soundness problem for free-choice WF-nets
(FCWF-nets), which is based on the rank theory [6]. FCWF-nets can
well model the structures of business processes such as AND-split,
AND-join, OR-split, and OR-join [2], [3]. However, some concurrent
Manuscript received July 2, 2014; revised October 15, 2014; accepted
December 2, 2014. Date of publication January 12, 2015; date of current
version July 15, 2015. This paper was supported in part by the Alexander
von Humboldt Foundation and in part by the National Natural Science
Foundation of China under Grant 61202016 and Grant 91218301. This paper
was recommended by Associate Editor M. K. Tiwari.
G. Liu is with the Key Laboratory of the Ministry of Education
for Embedded System and Service Computing and the Department of
Computer Science, Tongji University, Shanghai 201804, China (e-mail:
liuguanjun@tongji.edu.cn).
C. Jiang is with the Key Laboratory of the Ministry of Education for
Embedded System and Service Computing and the Department of Computer
Science, Tongji University, Shanghai 201804, China.
Digital Object Identifier 10.1109/TSMC.2014.2386802
systems such as web services composition must consider the inter-
action among different components/processes [9], [15], [17], [18].
This makes the related models more and more complex so that
FCWF-nets cannot model them. Additionally, van der Aalst et al. [4]
pointed out that “in the workflow management domain, test arcs
(i.e., self-loops in Petri nets) are often used to model that the exe-
cution of one task in one sub-procedure has to wait until another
sub-procedure has advanced until a predefined point.” Generally, a
WF-net with test arcs is not a free-choice one. Motivated by this
reason, they explored asymmetric-choice WF-nets (ACWF-nets) that
are a larger class than FCWF-nets and can model many complex
cases. We proved that the (weak) soundness problem is co-NP-hard
for three-bounded ACWF-nets [11]. At that time, we did not know
what the complexity of the (weak) soundness is for one-bounded (i.e.,
safe) or two-bounded ACWF-nets. Recently, Tiplea et al. [20] proved
that for three-bounded acyclic ACWF-nets, the weak soundness prob-
lem is co-NP-complete. However, they did not discuss the complexity
of the soundness problem for three-bounded acyclic ACWF-nets.
This paper sharps the previous results and draws two conclusions.
One is that for one-bounded ACWF-nets, the soundness problem
is also co-NP-hard. This means that for general ACWF-nets, the
soundness problem is co-NP-hard. The other one is that for acyclic
ACWF-nets, whether they are one-bounded or k-bounded (k > 1),
the soundness is equivalent to the weak soundness (i.e., an acyclic
ACWF-net is sound if and only if it is weakly sound). This means
that for three-bounded acyclic ACWF-nets, the soundness problem
is also co-NP-complete because Tiplea et al. [20] proved that their
weak soundness problem is co-NP-complete.
The remainder of this paper is organized as follows. Section II
introduces some basic terminologies. Section III proves that the
soundness problem is co-NP-hard for ACWF-nets. Section IV proves
that soundness and weak soundness are equivalent for acyclic
ACWF-nets. Section V concludes this paper.
II. B
ASIC NOTIONS
For self-completeness, we recall Petri nets and WF-nets. For more
details, one may refer to [3], [16], [19]and[22].
Denote N ={0, 1, 2, 3,...}, N
0
={0},andN
m
={1, 2,...,m}
for each m ∈ N \ N
0
.
Definition 1 (Net): A net is a three-tuple N = (P, T, F),whereP is
a finite set of places, T a finite set of transitions, F ⊆ (P×T)∪(T×P)
a set of arcs, and P ∩ T =∅.
A net may be seen as a directed bipartite graph. Generally, a tran-
sition is represented by a rectangle and a place by a circle in a net
graph. A path of a net is a nonempty sequence x
1
x
2
···x
n
of nodes
such that ∀j ∈ N
n−1
: (x
n
, x
n+1
) ∈ F.Apathx
1
x
2
···x
n
is elemen-
tary if for any two nodes x
j
and x
k
of the path, j = k ⇒ x
j
= x
k
.
An elementary path x
1
x
2
···x
n
is a circuit if (x
n
, x
1
) ∈ F.Anetis
acyclic if it has no circuit. A net is strongly connected if for any two
nodes x and y there is a path from x to y.
Transition t is an input transition of place p and p is an output place
of t if (t, p) ∈ F. Input place and output transition can be defined
2168-2216
c
2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.