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

Workflow Verification and Polynomial Algorithm of Model Decomposition

作　　者：庞善臣[1,2] 蒋昌俊[1] 

机构地区：[1]同济大学计算机科学与工程系,上海200092 [2]山东科技大学信息科学与工程学院,山东青岛266510

出　　处：《同济大学学报（自然科学版）》2009年第3期390-394,共5页Journal of Tongji University:Natural Science

基　　金：国家“973”重点基础研究发展规划资助项目(2004CB318001-13);国家自然科学基金资助项目(90412013,90718012,60503002,60534060);上海市基础研究重点资助项目(05JC14063)

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

关 键 词：工作流 PETRI网 模型分解及验证 多项式算法 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]