Page 163 - 《软件学报》2021年第5期

朱锐 等:基于完全有限前缀展开的行为等价过程树生成算法 1387

→
P 0: t 1
c 1 c 3 → →
c 0 t 0 t 4 c 5 t 5 c 6
||
t 2 t 0 t 4 t 5
c 2 c 4
×
t 3 t 1
t 2 t 3
(→,(→,t 0,(||,×(t 3,t 2)，t 1)),→(t 4,t 5))

Fig.1 Petri net to process tree mapping
图 1 Petri 网到过程树的映射

本文提出了一种基于完全有限前缀展开的行为等价过程树生成算法.该算法从过程模型活动的发生权的
角度,讨论了如何将用 Petri 网描述的模型转化为行为等价过程树,并分析了不能转化的情况.本文第 1 节重点对
行为等价过程树生成问题进行阐述.第 2 节对本文涉及到的基本概念进行表述.第 3 节详细论述基于完全有限
前缀展开的等价过程树生成算法及思路.第 4 节对本文所提算法进行相关实验.第 5 节将算法与其他相关工作
进行对比分析.第 6 节对本文的主要工作进行总结并展望未来工作.
1 问题描述

尽管将 Petri 网表示的过程模型转化为过程树模型可简化模型的复杂性,有利于直观地对模型进行分析.但
并不是所有的 Petri 网表示的过程模型都可以转化为过程树.当前,对于过程树转化的研究是针对基于块结构的
过程模型(block-structured process model,简称 BSPM) [16−18] ,例如图 1 中的模型 P 0 就是一个 BSPM 模型.现有的
转化算法 [19] 通过识别活动间的基本块结构,能够将一个 BSPM 转化为一棵过程树,文献[18]提出可以通过补充
基本块的方式增加过程树的表达能力,但是仍然只能将 BSPM 转化相应的过程树.例如图 2 中所示过程模型 P 1 ,
相较于图 1 中的过程模型 P 0 ,P 1 是一个的非 BSPM,在结构上多了库所 c 7 和 c 8 ,无法通过上述方法产生行为等价
的过程树.但通过识别 P 1 的活动间基本关系(发生权关系),能够发现 P 1 可以用与 P 0 相同的过程树进行表
达:(→,(→,t 0 ,(||,×(t 3 ,t 2 ),t 1 )),→(t 4 ,t 5 ).
根据过程模型是否能够等价转化为行为等价过程树,将过程模型进行了分类(如图 3 所示),其中与过程树的
行为等价的过程模型(process tree in behavior equivalent’s process model,简称 TEPM)是可以转化为行为等价过
程树的模型.

Fig.2 A non-BSPM example Fig.3 Classification of process models
图 2 非 BSPM 示例 图 3 过程模型分类

针对如何将 TEPM 转化为行为等价过程树的问题,本文的研究内容及贡献如下.
(1) 提出过程模型活动关系的抽取方法.该方法不仅可以支持基于基本块的过程模型 BSPM 中简单的活动
关系抽取,还可以发现现有方法无法解决的具有复杂结构的过程模型活动关系抽取问题(例如图 2 中 t 2 和 t 3 之
间的关系).
(2) 提出了模型重构方法.该方法首先定义了活动关系间是否存在且只存在一种基本关系的冲突判断条
件,该条件可以用于判断过程模型是否为 TEPM.接着,定义了活动关系的优先级,该优先级能够解决由于活动重