Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (4): 226-228.DOI: 10.3778/j.issn.1002-8331.2011.04.063

• 工程与应用 • Previous Articles     Next Articles

Improved algorithm combining graph-reduction and graph-search for workflow verification

DANG Zhengjun,DU Zhongjun   

  1. College of Computer Science and Technology,Sichuan University,Chengdu 610065,China
  • Received:2009-05-13 Revised:2009-07-22 Online:2011-02-01 Published:2011-02-01
  • Contact: DANG Zhengjun



  1. 四川大学 计算机学院,成都 610065
  • 通讯作者: 党正军

Abstract: Since the structural conflicts in workflow processes can lead to malfunction of workflow management systems,the problem should be detected before workflow processes are put into execution.Up to now,workflow verification without cycles is well solved in Mahanti-Sinnakkrishnan algorithm.L.Kai and L.Qing proposed an algorithm called CWRS to verify workflow graphs which may have cycles,but it has some deficencies which can lead to misjudgment.This paper mainly analyzes the CWRS algorithm,and points the deficencies,then proposes an improved method to completely solve the structural conflicts even if unpaired AND nodes exist in the loop.

Key words: workflow, directed graph, workflow verification

摘要: 工作流程中的结构冲突将导致工作流管理系统无法正常运行,因此需要在工作流图付诸实施之前要验证工作流的正确性,检测出其中的冲突。目前,无环工作流图的冲突检测在Mahanti-Sinnakkrishnan算法中已经得到了较好的解决,L.Kai和L.Qiang提出了CWRS算法用来检测有环工作流图的结构冲突,但该算法存在缺陷,会产生误判。对CWRS算法进行分析,指出了该算法的缺陷,并提出了改进方法,解决了有环工作流图AND型节点不配对时的冲突检测问题。

关键词: 工作流, 有向图, 工作流验证

CLC Number: