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

1388 Journal of Software 软件学报 Vol.32, No.5, May 2021

构所导致的其他活动关系无法判断问题.最后,建立了过程重构算法,该算法在不影响过程模型其他结构的基础
上,能够将多个活动重构为一个新活动.
(3) 提出了基于完全有限前缀展开的行为等价过程树生成算法.该算法通过活动关系判断和模型重构的不
断循环操作,最终构建出行为等价过程树,能够有效地将具有复杂结构的 TEPM(如图 3 中阴影部分所示)转化为
过程树.

2 预备知识

为了更好地理解本文提出的方法,下面将给出与本文研究方法相关的一些预备知识.
2.1 过程模型和过程树
定义 1(过程模型). 一个四元组 p=(C,A;F,M 0 )作为一个 Petri 网,其中,C 是条件集,∀c∈C 称作一个条件;A 是
活动集,∀a∈A 称作一个活动,a 的发生称为 a 被执行或者 a 点火;F 是 Petri 网上的流关系,F⊆C×A∪A×
C;M 0 (M 0 ⊆C)为 p 的初始情态,一个 d∈M 0 被称为托肯.
本文使用 Petri 网系统(EN 系统)来表示过程模型,Petri 网的其他相关概念,请参阅文献[20−22].
定义 2(过程树). 对于一个过程模型 p=(C,A;F,M 0 ),A 为其活动集,则活动 a∈A∪{τ}为一个过程树;设
M 1 ,M 2 ,…M n (n>0)为 n 个过程树,过程树间关系符号记为◎,则◎(M 1 ,M 2 )为过程树.
本文中使用顺序(→),选择(×),并发(||),迭代(∝)共 4 种关系符号,使用符号◎表示其中的一种.关于过程树的
更多相关概念请参见文献[23,24].

Fig.4 Four basic block-structures
图 4 4 种基本块结构

定义 3(基本块). 顺序块、选择块、并发块、迭代块被称为基本块,具体如图 4 所示,其中,黑色变迁表示内
部活动,它不会产生其他任何外部行为.一个五元组 s=(C,A;F,a e ,a x )作为一个基本块,其中,C 是条件集,∀c∈C 称
作一个条件;A 是活动集,∀a∈A 称作一个活动,a 的发生称为 a 被执行或者 a 点火;F 代表流关系,F⊆C×A∪A×C;a e ,
a x ∈A 为 p 的入口活动和出口活动.
定义 4(基于块结构的过程模型(BSPM)) [16−18] . BSPM 根据严格的活动结构来定义基于块结构,设过程片段
s=(C,A;F,a e ,a x )是一个由基本块构成的过程片段,则基于块结构的过程模型 p 的获得方式为:
(1) 构造条件集 C′,定义条件 c e 和 c x ,使 C′=C∪{c e ,c x }.
(2) 构造流关系集 F′,定义条件 c e 和 c x ,使 F′=F∪{(c e ,a e ),(a x ,c x )}.
(3) 为条件 c e 添加托肯,并设当前情态为初始情态 M 0 .
(4) p=(C′,A;F′,M 0 ).
定义 5(复杂结构). 设 s 为一个过程片段,无法使用基本块和有限次地活动重构(具体请参阅文献[16−18])
操作得到 s,则将该过程片段 s 称为复杂结构.
定义 6(过程模型的行为空间). 设 p=(C,A;F,M 0 )是一个过程模型,设σ⊆A*为过程模型 p 上的一个变迁序列,
则 p 上所有可能发生的变迁序列的集合称为 p 行为空间,记为࣪(p),则σ∈࣪(p).
定义 7(与过程树行为等价的过程模型(TEPM)). 一个四元组 p=(C,A;F,M 0 )被称作一个 TEPM,当且仅当存
在一个过程树模型 t,使得 p 与 t 之间满足:
(1) 不存在σ使得σ∈࣪(p)∧σ∉࣪(t).