对一个Petri网进程表达式的探讨

摘 要：Petri网进程是Petri网分析和验证的有效手段，而Petri网的进程表达式可以给出系统全部进程的描述。针对文献《一种基于同步合成构造Petri网进程表达式的方法》提出的基于同步合成的Petri网表达式构成方法中的一个引理进行深入研究，并通过一个反例，说明这种方法的错误之处。

关键词：Petri网；同步合成；基本进程段；进程表达式

中图分类号：TN301 文献标志码：A 文章编号：1672-1098（2014）03-0057-03

Petri网是一种描述与分析异步并发系统的数学模型[1-3]，特别便于描述并发与冲突，是研究并发系统的一个合适而有效的工具[4-5]。Petri网进程则是对系统行为描述和分析的最有力的工具[6]390，因为进程将状态和变迁并重， 把系统中发生的变化和引起的状态改变如实记录下来， 它可以很清楚地反映出网系统运行中的变迁之间的顺序、并发、同步等现象[7]。Petri网的进程表达式可以给出系统全部进程的描述， 因此对其进行深入研究具有极其重要的意义。目前，国内外学者对于Petri网的进程表达式的研究比较广泛[8]340。其中，文献[6]387 考察结构简单的Petri网的进程行为， 给出各种类型的Petri网的进程表达式的描述方法， 然后拓展了Petri 网同步合成的概念， 分析了同步合成过程中基本进程段集之间的关系， 并利用同步混排给出了进程表达式之间的关系。本文主要针对文献[6]385中的一个引理进行进一步的探讨，以期为基于同步合成的Petri 网进程表达式的更为完善的构成方法奠定基础。

1 引理证明中的错误

关于基本进程段的定义及相关概念参考文献[6]385，下面是文献[6]385中的两个值得商讨的结论。 假设有两个活的S-网Σ1和Σ2，它们的基本进程段集分别为P1={P11，P12，…，P1m}（m>0）和P2={P21，P22，…，P2n}（n>0），其中P1i（1≤i≤m），P2j（1≤j≤n）都是可重复的进程段且满足：若P1i 与P2j有共同的变迁，则这些共同的变迁在P1i中的顺序与在P2j中的顺序是相同的。这样由引理4所求得的同步合成网Σ的所有基本进程段也都是可重复的进程段，这表明合成网Σ是活的Petri网，它的所有变迁都是活的。

但是两个活的S-网同步合成之后，所得到的同步合成网并不一定就是活的，即由引理4所得到的合成网的基本进程段集合是错误。同理，定理4也是错误的。

下面给出了一个反例并进行了讨论，这个反例来自于文献[6]385。

2 反例与讨论

图1a给出了一个Petri网模型Σ，由文献[6]390中给出的方法求取Σ对应的Petri网模型的进程表达式，先将Σ分解成Σ1和Σ2，分别如图1的b和c所示，得到的Σ1和Σ2是S-网并且Σ=Σ1ΞΣ2。其中Σ1的基本进程段为P1、P2，Σ2的基本进程段为P3、P4，分别如图2的a和b所示。然后根据引理4，对Σ1的基本进程段P1、P2与Σ2的基本进程段P3、P4进行同步合成则得到Σ的两个基本进程段P5和P6，如图3所示。显然，根据引理4求出的Σ的基本进程段集并不能完全表示原网Σ的所有进程。在子网模型Σ1和Σ2中，所有的变迁都是活的。Σ1的每个进程都是集合Pref{Exp（P1+P2）*}的一个元素，Σ2的每个进程都是集合Pref{Exp（P3+P4）*}的一个元素，所以Σ1和Σ2的基本进程段集合都是正确的。但是在原网模型中，Σ并不是一个活的Petri网。当变迁t11与t21都发生后，就没有变迁再能发生，基本进程段P5和P6无法表示这种情况，变迁t11与t21发生所对应的进程段并不是集合Pref{Exp（P5+P6）*}中的元素。所以根据引理4将两个S-网（同步合成可以得到原网）的基本进程段集进行同步合成求得原网的进程段集并不能完全描述原网的所有进程，即求得的并不是基本进程段集，所以引理4和定理4都是不正确的。

在文献[8]342中有一个类似于引理4的结论，而文献[6]382中叙述的是基本进程，并不是文献[6]385-390中定义的基本进程段，这是两个不同的概念，引理4直接引用文献[6]385中的结论，这是文献[6]385-390中出现这个错误的根源。从而，文献[6]385-390中基于定理4的其他结论也是靠不住的。

3 结论

本文分析和研究了Petri网的进程表达式的作用，深入研究了基于同步合成的Petri网进程表达式构成方法中的一个引理的证明方法，并通过反例说明该构成方法的错误之处。 本文工作本着尊重科学，坚持实事求是的原则，指出该方法的错误之处，为进一步提出基于同步合成的Petri 网进程表达式的构成方法奠定基础。

参考文献：

[1] MURATA T.Petri nets： properties， analysis， and applications[J]. Proceedings of the IEEE， 1989， 77（4）：541-580.

[2] 吴哲辉. Petri网导论[M]. 北京： 机械工业出版社，2006：10-150.

[3] 闫春钢， 汪明新，刘关俊.有界Petri 网进程表达式与活性的关系[J].应用科学学报，2012，30（4）：387-390.

[4] 吴哲辉. 有界Petri网的进程表达式[J]. 中国科学（A辑），1995，25（12）：1 332-1 340.

[5] 蒋昌俊.同步合成网的进程特性研究[J].电子学报，1997，25（2）： 57-60.

[6] 曾庆田.一种基于同步合成构造Petri网进程表达式的方法[J].计算机学报，2008，31（3）： 381-390.

[7] 袁崇义. Petri 网原理与应用[M]. 北京： 电子工业出版社， 2005：8-250.

[8] 吴哲辉. 无界公平Petri网的进程表达式[J].计算机学报， 2000，23（4）： 337-344.