工作流模型验证及分解的多项式算法分析

Workflow Verification and Polynomial Algorithm of Model Decomposition

摘要:

基于工作流的Petri网结构化建模方法，证明了工作流网的T不变量和P不变量的存在性、可覆盖性，给出了一个工作流模型完整性的充要条件，进一步得到了基于T不变量的多项式分解算法，与以往非多项式分解算法相比，克服了遍历的不足，降低了算法复杂度，给出的实例验证了算法的有效性.

关键词:工作流; Petri网; 模型分解及验证; 多项式算法

Abstract:

This paper presents a new necessary and sufficient condition for the soundness of workflow model based on the Petri nets modeling techniques.Some properties of workflow net were analyzed and verified,such as the existence of Tinvariant and Pinvariant of the workflow net(WFnet),the sets of transitions and places be covered by Tinvariants and Pinvariants respectively. A polynomial algorithm of workflow model decomposition based on Tinvariant is presented.Compared with other exponential algorithms, the algorithm is simple, easy to understand and operate,and can also effectively simplify decomposition and analysis of the workflow systems. The effect of the paper’s research results is verfied with an example.

Key words:workflow; Petri net; model decomposition and verification; polynomial algorithm