Abstract: Since the structural conflicts in workflow processes can lead to malfunctioning of workflow management systems, so the conflicts should be detected before workflow processes are put into execution. Up to now, there is no perfect algorithm which can be able to detect the structural conflicts in the workflow both with loop and without loop. The authors proposed a new algorithm based on graph-search by making use of a skillful method, which transformed the loop in the workflow to an acyclic sub graph. It was able to efficiently detect the structural conflicts in the workflow even with loop.

Key words: workflow, directed graph, workflow verification, graph-search, deadlock, asynchronous

摘要： 工作流程中的结构冲突会导致工作流管理系统无法正常运行，因此需要在工作流程付诸实施之前验证工作流的正确性，检测出其中的冲突。目前，尚无一个完美的算法既能检测出无环工作流图的冲突,也能检测出带环工作流图中的结构冲突,为此提出了一种新的基于图搜索的工作流图验证算法,利用巧妙方法将流程图中的环转化为无环流程子图,高效地检测出了有环工作流图和无环工作流图的结构冲突。

关键词: 工作流, 有向图, 工作流验证, 图搜索, 死锁, 异步