非对称选择工作流网络健壮性难题的共NP硬度分析

160 浏览量更新于2024-08-26 收藏 570KB PDF 举报

"这篇研究论文探讨了非对称选择工作流网络（Asymmetric-Choice Workﬂow Nets，简称ACWF-nets）的健全性问题的共NP硬度。文章指出，虽然自由选择工作流网络（Free-Choice Workﬂow Nets，简称FCWF-nets）的健全性问题可以在多项式时间内解决，但因为FCWF-nets无法模拟大部分Web服务组合和跨组织业务流程，所以实际应用中更为广泛的ACWF-nets成为了研究焦点。作者Guanjun Liu和Changjun Jiang展示了即使是三界线性（three-bounded）的ACWF-nets，其弱健全性问题也是共NP困难的，并且后续的研究进一步证明了对于三界线性的无环ACWF-nets，弱健全性问题是共NP完全的。在本文中，作者深化了这些结果，首先证明无论是单界线性（one-bounded）还是k界线性（k>1）的ACWF-nets，其健全性问题都是共NP困难的。其次，他们还证明了对于任何无环ACWF-nets，健全性和弱健全性是等价的，即一个无环ACWF-net若在健全性上是正确的，那么它的弱健全性也必定正确。这些发现对于理解和评估ACWF-nets的健壮性具有重要意义，同时也揭示了在处理这类网络时的计算复杂性挑战。" 这篇论文的核心贡献在于： 1. 明确了ACWF-nets在建模Web服务和跨组织业务流程中的重要性，强调了它们相对于FCWF-nets的优势，尽管FCWF-nets的健全性问题可以通过多项式时间算法解决。 2. 提供了ACWF-nets健全性问题的共NP硬度证明，无论网络是否受到边界限制，都存在计算上的困难性。 3. 展示了对于无环ACWF-nets，健全性和弱健全性的等价性，这是对之前关于三界线性无环网络弱健全性问题共NP完全性的结果的补充和强化。这些研究成果不仅加深了对工作流网络理论的理解，也为实际业务流程的设计、验证和优化提供了理论基础，同时提示了在设计高效算法解决此类网络的健全性问题时可能需要面对的计算复杂性挑战。

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 Workﬂow 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 workﬂow 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 workﬂow 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 workﬂow nets, soundness, web service composition.

I. I

NTRODUCTION

Workﬂow nets (WF-nets), as stated by van der Aalst et al. [3],

have become one of the standard ways to model and analyze work-

ﬂows. 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 deﬁned [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 Identiﬁer 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 workﬂow 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 predeﬁned 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},andN

={1, 2,...,m}

for each m ∈ N \ N

Deﬁnition 1 (Net): A net is a three-tuple N = (P, T, F),whereP is

a ﬁnite set of places, T a ﬁnite 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

···x

of nodes

such that ∀j ∈ N

n−1

: (x

, x

n+1

) ∈ F.Apathx

···x

is elemen-

tary if for any two nodes x

and x

of the path, j = k ⇒ x

= x

An elementary path x

···x

is a circuit if (x

, x

) ∈ 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 deﬁned

2168-2216

 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.

下载后可阅读完整内容，剩余3页未读，立即下载

weixin_38644141

粉丝: 6
资源: 924

非对称选择工作流网络健壮性难题的共NP硬度分析

蚁群算法非对称TSP问题

CNN进阶技巧：如何优化卷积神经网络的性能

CNN超参数优化：提升卷积神经网络性能的策略

【人脸识别算法详解】：理解卷积神经网络（CNN）在人脸检测中的作用

CatBoost与主流机器学习框架比较：深度分析与选择指南

体育课评分系统 微信小程序+SSM毕业设计 源码+数据库+论文+启动教程.zip

【东证期货-2024研报】短期关注天气能否触发惜售.pdf

客运自助售票小程序 微信小程序+SSM毕业设计 源码+数据库+论文+启动教程.zip

一个完整yolov8整合包.zip

解决CAM350导入提示“找不到首标题%，载入停止”

最新资源

体育课评分系统微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip

客运自助售票小程序微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip