当前位置:首页 >> 英语学习 >>

Preservation of Liveness and Deadlock-Freeness in Synchronous Synthesis of Petri Net System


1000-9825/2003/14(12)1977

?2003 Journal of Software 软 件 学 报

Vol.14, No.12

同步合成 Petri 网系统活性与无死锁性的保持性
蒲 飞 1,2+, 陆维明 1
1 2

?

(中国科学院 数学与系统科学研究院 数学研究所,北京 (湖南怀化学院 数学系,湖南 怀化 418008)

100080)

Preservation of Liveness and Deadlock-Freeness in Synchronous Synthesis of Petri Net Systems
PU Fei1,2+,
1

LU Wei-Ming1

(Institute of Mathematics, Academy of Mathematics and System Sciences, The Chinese Academy of Sciences, Beijing 100080, China) (Department of Mathematics, Hu’nan Huaihua College, Huaihua 418008, China)

2

+ Corresponding author: Phn: 86-10-62541849, Fax: 86-10-62541829, E-mail: pufei@amss.ac.cn http://www.amss.ac.cn

Received 2003-05-07; Accepted 2003-06-18 Pu F, Lu WM. Preservation of liveness and deadlock-freeness in synchronous synthesis of Petri net systems. Journal of Software, 2003,14(12):1977~1988. http://www.jos.org.cn/1000-9825/14/1977.htm Abstract: Synthesis process is an important bottom-up approach on modeling Petri net systems, and the

preservation of certain good properties such as liveness, deadlock-freeness, reversibility and so forth is also a significant problem in the study of synthesis processes. In this paper, the preservation of liveness and deadlock-freeness is discussed for a synchronous synthesis process. The difference from other work is that the presented approaches are based on the concurrent composition of paths using a concurrent language. The concurrent language relation formula is presented and proved in the synchronous synthesis of Petri net systems, and it can be applied to judge the liveness and deadlock-freeness of a synthesized system. Meanwhile, criteria which are necessary and sufficient for the liveness and deadlock-freeness of the resultant system are developed. Finally, conditions under which the preservation of liveness and deadlock-freeness holds for the synchronous synthesis of Petri net systems are proposed. Key words: synchronous synthesis process; preservation of liveness and deadlock-freeness; concurrent language; synchronous path; concurrent composition of paths 摘 要: 合成操作是 Petri 网系统建模中一种重要的自底向上建模方法,而在 Petri 网系统的合成研究中,一些好

性质,如活性、无死锁性、可回复性等的保持性,是一个重要的研究问题.研究了 Petri 网系统同步合成操作活性

? Supported by the National Natural Science Foundation of China under Grant No.60073013 (国家自然科学基金 ); the National

Grand Fundamental Research 973 Program of China under Grant No.G1998030416 (国家重点基础研究发展规划 (973)) 第一作者简介 : 蒲飞 (1970- ),男 ,湖南洪江人 ,博士生 ,讲师 ,主要研究领域为 Petri 网理论及应用 ,并发理论 ,进程代数 .

1978

Journal of Software

软件学报

2003,14(12)

与无死锁性的保持性 . 与以往研究工作不同 , 基于路径的并发合成用并发语言的方法 , 提出并证明了同步合成 Petri 网系统的一个并发语言关系式.该语言关系式可用于判定同步合成 Petri 网系统的活性与无死锁性,同时给 出了同步合成 Petri 网系统活性与无死锁性的充要条件.最后提出一些条件,在这些条件下,同步合成 Petri 网系统 有活与无死锁的保持性质. 关键词: 同步合成操作;活性与无死锁性的保持性;并发语言;同步路径;路径并发合成 文献标识码: A 中图法分类号: TP301

Petri 网是一种系统的数学和图形的建模和分析工具,特别适用于对具有同步、并发、冲突的离散事件系统 进行建模和分析 ,因而广泛应用于复杂系统的设计与分析中 .如计算机系统、分布式并行处理系统、计算机集 成制造系统等.用 Petri 网来表示并发、互斥、同步显得直接、自然而精确,同时,由于 Petri 网研究有坚实的数 学基础 , 因此它为系统模型的分析和验证提供了一种有力的方法 . 但是 , 当建模的系统较大而且复杂时 , 就会由 于状态空间爆炸而带来系统分析上的高复杂性问题 . 有一种重要的方法可以用来降低大系统建模分析的复杂 度,即系统的合成操作.合成操作就是把相对较小的 Petri 网系统合成一个大的 Petri 网系统,通过大系统保持小 系统的某些性质 ,如活性、无死锁性等 ,而得到大系统相应的性质 , 或能用小系统较容易地判定大系统的某些性 质,从而达到利用小系统来研究大系统的目的. 在 Petri 网系统的合成操作方面已有较多的研究工作.Y. Souissii[1]研究了共享合成 Petri 网系统的活性保持 性问题.基于对活性满足单调性条件的推广,他提出了 F-强网的概念,得出两个活的 F-强网系统共享合成后仍是 活的这一结论 . 但其不足是 , 两个活的 F- 强网系统共享合成后不一定是 F- 强网 , 这使得它的应用受到局限 .Y. Souissi[2] 还研究了在一些合成方式下 Petri 网系统的活性保持性问题 , 方法仍是基于活性单调性条件的推 广.M.D. Jeng[3~5]研究了用 Petri 网系统来建模柔性制造系统的合成方法,提出了资源控制网的概念.每一个子系 统都是资源控制网 , 且按两个约束条件合成起来 , 这样得到大系统有结构活性 .A. Aybar[6] 用分解方法研究大系 统的性质,采用一种称为包含原则(including principle)方法分解大系统,以此保证合成后的大系统具有小系统相 应的性质 ,并提出了这种方法在分散控制中的应用 .G. Berthlet[7,8] 提出用变形的方法来研究系统的一些性质 ,如 活性、 无死锁性及有界性等保持性问题.J. Esparza[9,10]提出了合成活且有界的自由选择网的法则,可使合成后的 网系统保持活性 .总之 ,上述这些研究工作都是基于代数的方法或结构的方法 ,而用语言的方法来研究保持性问 题尚不多见 .语言关系反映了系统之间的动态行为关系 ,因此 ,从语言的角度研究保性问题更能反映系统合成中 相互动态行为关系,是一个富有吸引力的研究方向. C.J. Jiang[11]用语言的方法研究 Petri 网系统同步合成的一些性质,给出了同步合成 Petri 网系统活性及无死 锁性与非阻塞性的关系 , 同时提出了系统行为之间行为相关性概念 , 刻画了子系统语言与同步合成系统语言之 间的关系.文献[12]中提出了同步合成 Petri 网系统动态不变性概念(状态不变性、 行为不变性),讨论了它们之间 的关系.H.Q. Wang[13]用文献[11]中的一个同步合成 Petri 网系统的语言关系式来研究其他合成操作(如自环连 接、抑制弧连接)的一些性质,但是需将自环连接、抑制弧连接的 Petri 网系统转化为一个中间的网系统,相应地 称为自环扩张网及多元自环网 ,然后变为同步合成操作的形式 ,从而能应用同步合成方面的结果来研究 .由于中 间的这些转化过程,给直接分析与应用带来不便.同时,需要指出的是,文献[11~13]的结果都是基于 Petri 网系统 顺序语言的形式得到的,因此尚不能完整地刻画具有并发行为特征的系统动态行为关系,同时,同步合成 Petri 网 系统的活性保持性问题在文献[11~13]中尚未研究. 本文研究了同步合成 Petri 网系统活性与无死锁性的保持性问题,重点放在由同步合成过程中语言的递归 性得到的并发语言关系式上.该语言关系式可用来判定同步合成 Petri 网系统的活性及无死锁性,得到同步合成 Petri 网系统活及无死锁的充要条件.进一步提出一些条件,使得同步合成 Petri 网系统有活性及无死锁性的保持 性质. 本文第 1 节介绍相关的基本概念和术语.第 2 节给出同步合成 Petri 网系统的一个并发语言关系式.第 3 节 讨论同步合成 Petri 网系统的动态不变性.第 4 节讨论同步合成 Petri 网系统活及无死锁的充要条件.第 5 节给出 条件,使得同步合成 Petri 网系统有活性及无死锁性的保持性.第 6 节给出结论及下一步研究工作设想.

蒲飞 等:同步合成 Petri 网系统活性与无死锁性的保持性

1979

1

基本概念和相关术语
关于 Petri 网的基本概念及术语可参见文献[14~16].这里只给出本文所需要的一些概念. 定义 1.1[14~16]. 设 Σ =(P,T ;F, M 0 )是一个 Petri 网系统,称 LS ( Σ ) ={α |α ∈ T * 且 M 0 [α >]为网系统 Σ 的顺序语

言或网系统 Σ 的顺序行为,其中 T * 是 T 的闭包. 定义 1.2[14~16]. 设 Σ =(P,T ;F, M 0 )是一个 Petri 网系统,称 LC ( Σ ) ={α |α ∈ ( P(T ? ))? 且 M 0 [α >}为网系统 Σ 的 并发语言或并发行为,其中 P(T)表示 T 的幂集. 通常,当 Rt ∈P(T)时,| Rt |=0 称为空步,记为 Rt =ε .| Rt |=1 称为单步,| Rt |≥2 称为并发步. 下面给出 Petri 网系统同步合成操作的定义. 定义 1.3[14~17]. 设 Σ i = ( Pi , Ti ; Fi , M 0 i ) (i=1,2)是两个 Petri 网系统 ,满足 P1 ∩ P2 =?, T1 ∩ T2 ≠?.若 Petri 网系统

Σ =(P,T ;F, M 0 )满足:
(1) P= P1 ∪ P2 ; (2) T= T1 ∪ T2 ; (3) F= F1 ∪ F2 ; (4) M0 (p)= M 0 i ( p ) ,如果 p∈ Pi (i=1,2), 则称 Σ 是 Σ 1 与 Σ 2 的同步合成网系统,记为 Σ = Σ 1OT Σ 2 ,并记 T0 = T1 ∩ T2 . T0 中的变迁称为同步变迁. 定义 1.4. 设 Σ =(P,T ;F, M 0 )是一个 Petri 网系统. (1) ?P ′ ?P,定义 M |P ′ ( p ) =M(p), ? p∈ P′ ,称 M |P ′ 为标识 M 在 P′ 上的投影; (2) ?T ′ ?T,α∈ ( P(T ? ))? ,定义 α |T ′ 为α 中属于 T ′ 的字符组成的步序列,称 α |T ′ 为步序列α在 T ′ 上的投影. 定义 1.5. 设 L 是 Σ 上的一个并发语言,语句α, β ∈L.称 “?”为 L 的乘法运算,意为α ?β ≡α β ,即一种并发串的 连接;称“+”为 L 的加法运算,意为 α + β ≡ {α } + {β } ≡ {α , β } . 定义 1.6[14~16]. 设 Petri 网系统 Σ =( ( P, T ; F , M 0 ) ,称 Petri 网系统 Σ 是活的,当且仅当对 ? M∈[ M 0 >, ? t∈T,

? M ′ ∈[M >使得 M ′ [t>;称 Petri 网系统 Σ 是无死锁的,当且仅当对 ? M∈[ M 0 >, ? t∈T 使得 M[t>.
为了下文方便讨论,我们还需要引入一些定义. 定 义 1.7. 设 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2) 是 Petri 网 系 统 , Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) . Σ i ( 或 Σ ) 的 步 序 列

α∈ ( P(Ti ? )) ? (或 P(T * )* )称为 Σ i (或 Σ )上的一条路径,如果 ? M, M ′ ∈[ M 0 >,使得 M[ α > M ′ . 定义 1.8. 设 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2)是 Petri 网系统, Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) , T0 = T1 ∩ T2 .
(1) 对 Σ i 的任一路径 α1 ∈ ( P(Ti )) ? , 有 α1 ∩ P (T0 ) =?, 记作 M 1 [ α1 > M 2 ( M 1 ∈[ M 0 > ) , 如果有 Σ 3? i 中的一
条路径 α 2 ∈ ( P(T3*? i ))? 且 α 2 ∩ P (T0 ) =?,满足 M 2 [ α 2 > M 3 且还存在 α 3 ∈ P (T0 ) ,使得 M 3 [ α 3 >,则 α = α1 ? α 3 称为
?

Σ i 上的一条基本同步路径 ,同时把 β = α 2 ? α3 称为 Σ 3? i 上的一条与 α 互同步路径 .亦称 α 和 β 为一对互同步路
径.记 (α , β ) = α 3 ,则α ,β 分别可写成α = α1 ? (α , β ) , β = α 2 ? (α , β ) ( α1 和 α 2 可以为ε ).

(2) 设 α 是 Σ i 上的一条路径,满足α∩ P (T0 ) =?,则称α为 Σ i 上的一条基本非同步路径.
定义 1.9. 设 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2)是 Petri 网系统, Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .设 α 和 β 是 Σ 上的路径, 则 Σ 上关于路径间的有效乘法“⊕”定义如下:

1980

Journal of Software
如果 α和β是一对互同步路径 , ? α1 ? ? ?α ? ? o (α , β ), α1 o α 2 o (α , β ), o α , β) o α , β) , β = α2 ( . 记α = α1 ( ? 2? ?α ? ? ?β ? ?, α o β , ? ? 如果 α和β不是一对互同步路径 , (1) α和β是Σ i 或Σ 3? i 上基本非同步路径满足 :

软件学报

2003,14(12)

(1.1) M [α > M 1 ? M 1 [ β > 且M [ β > M 2 ? M 2 [α >; (1.2) M [α > M 1 ? ?M 1 [ β >; ( 2) α是Σ i 或Σ 3 ? i 上基本非同步路径 , β是Σ i 或Σ 3 ? i 上基本同步路径 , 设γ是β的互同步路径 , ( 2.1) 若M [α > M 1 ? M 1 [ β ⊕ γ > 且M [ β ⊕ γ > M 2 ? M 2 [α >; ( 2.2) M [α > M 1 ? M 1[ β ⊕ γ > 且M [ β ⊕ γ > M 2 ? ?M 2 [α >; ( 2.3) 其他; (3) α是Σ i 或Σ 3 ? i 上基本同步路径 , β是Σ i 或Σ 3? i 上基本非同步路径 , 设γ是α的互同步路径 , 若 : (3.1) M [α ⊕ γ > M 1 ? M 1 [ β > 且M [ β > M 2 ? M 2 [α ⊕ γ >; (3.2) M [α ⊕ γ > M 1 ? M 1 [ β > 且M [ β > M 2 ? ?M 2 [α ⊕ γ >; (3.3) 其他; ( 4) α是Σ i 或Σ 3 ? i 上基本同步路径 , β是Σ i 或Σ 3 ? i 上基本同步路径 , 设α的互同步路径为 γ , β的互同步路径为 σ , 若 : ( 4.1) M [α ⊕ γ > M 1 ? M 1 [ β ⊕ σ > 且M [ β ⊕ σ > M 2 ? M 2 [α ⊕ γ >; ( 4.2) M [α ⊕ γ > M 1 ? M 1[ β ⊕ σ > 且M [ β ⊕ σ > M 2 ? ?M 2 [α ⊕ γ >; ( 4.3) 其他; (5) α ? ( P (Ti* ))* U ( P (T3*? i ))* 或β ? ( P (Ti* ))* U ( P (T3*? i ))* , (5.1) 若M [α > M 1 ? M 1[ β > 且M [ β > M 2 ? M 2 [α >; (5.2) 若M [α > M 1 ? M 1 [ β > 且M [ β > M 2 ? ?M 2 [α >; (5.3) 其他.

ε,
? α ? ? o β ⊕ γ) , ?, α ( ?β ⊕γ ? ? ? o β ⊕ γ) α( ,

ε,
?α ⊕ γ ? ? ? β ? ?, (α ⊕ γ ) o β , ? ? (α ⊕ γ ) o β ,

α⊕β =

ε,
?α ⊕ γ ? ? ? β ⊕σ ? ?, (α ⊕ γ ) o ( β ⊕ σ ), ? ? o β ⊕ σ) , ( α ⊕ γ) (

ε,
?α ? ? ?β ? ?, α o β , ? ?

α o β, ε,
注:(1) 这里均有 M∈[ M 0 >.

(2) 运算“⊕”表示 Σ 上路径间的并发合成. (3) 规定 Σ 上路径演算的规则为 (3.1) “⊕”的运算级高于“?”; (3.2) “?”的运算级高于“+”. 定义 1.10. 设 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2)是 Petri 网系统, Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .
? i ′ (1) 记 BM , M ′ ={ α ∈ ( P (Ti )) |α 是 Σ i 上一条基本同步路径 ,满足 M[α > M ,其中 M∈[ M 0 >](i=1,2); ?

? i (2) 记 BM , M ′ ={α ∈ ( P (Ti )) |α 是 Σ i 上一条基本非同步路径 ,满足 M[α > M ′ ,其中 M∈[ M 0 >](i=1,2);

?

蒲飞 等:同步合成 Petri 网系统活性与无死锁性的保持性

1981

i ′ (3) 定义 li (Σ i ) ={ BM , M ′ | ? M∈[ M 0 >, ? M ∈[M> } (i=1,2),则 li ( Σ i ) 表示 Σ i 上所有基本同步路径的集合 ; i (4) 定义 li ( Σ i ) ={ BM , M ′ | ? M∈[ M 0 >, ? M ′ ∈[M>](i=1,2),则 li ( Σ i ) 表示 Σ i 上所有基本非同步路径的集合 .

定义 1.11. 设 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2)是 Petri 网系统, Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .

(1) 如果 Σ i 的任意一条基本非同步路径α 均可延长为 Σ i 的一条基本同步路径 β ,则称 Σ i 为良结构 Petri 网
系统; (2) 如果 Σ i 不是良结构 Petri 网系统,则称 Σ i 为非良结构 Petri 网系统. 定义 1.12. 设 Petri 网系统 Σ =(P,T;F, M 0 ),U,V 为 Σ 一些步序列的集合 ,若 Σ 产生的语言 L( Σ ) 满足如下 方程:

L( n ) ( Σ ) = L( n ?1) ( Σ ) ⊕U+V, 简记为 L( Σ ) = L( Σ ) ⊕U+V,
则称此方程为 Σ 的语言递归方程 ,亦称 Σ 定义的语言可由该递归方程迭代产生 ,初始迭代值为 L( 0 ) ( Σ ) = {ε } ,其 中 ε 为空步. 下面我们给出这些定义的例子. 例 1:如图 1 所示, Σ 是 Petri 系统 Σ 1 与 Σ 2 的同步合成网系统.
P3 c P1
? ?

a

a P5
? ?

d

P6 P7

P3

c

P1

a P5
? ?

?

d

P6 P7

P4

P2

b

Σ1

b

e

?

P4

P2

e b

Σ2

Σ =Σ 1 OTΣ 2

Fig.1 图1 ? ? a ? ? a ?? ? ? , Σ 1 的基本非同步路径集为 l1 (Σ 1 ) = 由图 1 易知 , Σ 1 的基本同步路径集为 l1 (Σ 1 ) = ?a , b, ca , cb, c? ?b ? ?, ? ?b? ?? ? ? ? ? ?? ? ?

? ?a? ? a ? ? a ? ? d ? ? d ? ? d ?? a ? ? ? ? ? {ε , c}. Σ 2 的 基 本 同 步 路 径 集 为 l2 ( Σ 2 ) = ?a, b, ? , da , d 2 a, eb, e 2b, dea , deb, de? ? ? ?? ? ? ?? , Σ 2 ? ? ?b ? ?, ed ? ? ? ?, ? ? ? ?a, ? ? ? ?b,? ? ?b? ? ? ? b ? ? e ? ? e ? ? e ?? b ? ? ? ? ? ? d ?? ? ? ? 的基本非同步路径集为 l2 ( Σ 2 ) = ?ε , d 2 , e 2 , de, ed , ? ?. ? ? e ? ? ?? ? ? ? d ?? a ? ? a ? ? d ?? a ? ?a? 2 2 易知 α =c ? ?e ? ?? ?b? ?b? ?b? ? cda d 是 Σ 产生的一个语句 , 且 α 可以写成 α= c? ? ⊕? ?∈ ?e ? ?? ?b ? ? ⊕ca⊕da⊕ d , 其中 c? ? ?? ? ? ? ? ?? ? ? ? ? d ?? a ? 2 l1 ( Σ 1 ) , ? ?e ? ?? ?b? ? ∈ l2 (Σ 2 ) ,ca ∈ l1 ( Σ 1 ) ,da∈ l2 (Σ 2 ) , d ∈ l2 (Σ 2 ) .因为 ? ?? ?
2 2 2 α = c? ?e ? ?e ? ?? ?? ?b? ? ? ? ? ? ⊕? ? ⊕ca⊕da⊕ d =c ? ? ?ca⊕da⊕ d ? ? ?? ? ? ? ⊕ca⊕da⊕ d =c ? ? ?? b ? ? ?? b ? ? ? ? e ?? b ?

?a?

? d ?? a ?

? d ?? a ?

? d ?? a ?

?a? ? ? ? 注意到 c ? ?b?

? d ?? a ? ? d ?? a ? ? d ?? a ? 2 2 2 =c ? ?e ? ?e ? ?e ? ?? ?? ?? ?b? ?b? ?b? ? ?cda⊕ d =c ? ? ?cda? d =c ? ? cda d . ? ?? ? ? ?? ? ? ?? ? ? d ?? a ? ? ? ?? ? ? ? ,ca 与 da 互为同步路径.同时,有 Σ 1 及 Σ 2 均为良结构 Petri 网系统. 与? ? e ?? b ? LC ( Σ ) = LC ( Σ ) ⊕( l1 ( Σ 1 ) ⊕ l2 (Σ 2 ) + l2 (Σ 2 ) ⊕ l1 ( Σ 1 ) + l1 ( Σ 1 ) + l2 (Σ 2 ) ).

0) (Σ ) = {ε } : 可以验证 Σ 的语言集 LC ( Σ ) 可由如下递归方程迭代生成,其中初始迭代值 L(C

2

同步合成 Petri 网系统的并发语言关系式
在这一节中,我们给出一个同步合成 Petri 网系统的并发语言关系式,该语言关系式表示 Petri 系统之间的动

1982

Journal of Software

软件学报

2003,14(12)

态和并发行为.首先有如下定理: 定理 2.1. 设 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2) 是 Petri 网系统 , Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) , 则 Σ 产生的并发语言
LC ( Σ ) 可由如下递归语言关系式合成(为方便起见,下文把 LC ( Σ ) 记为 L( Σ ) ):

L( Σ ) = L( Σ ) ⊕( l1 ( Σ 1 ) ⊕ l2 (Σ 2 ) + l2 (Σ 2 ) ⊕ l1 ( Σ 1 ) + l1 ( Σ 1 ) + l2 (Σ 2 ) ).
这里, li (Σ i ) , li (Σ i ) 及⊕的定义见第 1 节定义 1.9 及定义 1.10,记该递归语言关系式为语言关系式 (?) .

(?)

证明 :下面证明对任意语句 α∈ L( Σ ) ,α均可由递归语言方程 (?) 迭代生成 .由于 Σ 是 Σ 1 与 Σ 2 的同步合成 ,我 们分如下几种情况加以讨论: (1) α∩ P (T0 ) =?.

(1.1) α是 Σ i (i=1 或 2)的基本非同步路径,则α可由递归方程 L( Σ ) = L( Σ ) ⊕ li (Σ i ) 生成,故α能由递归语言方
程 (?) 迭代生成.

(1.2) α 由 Σ i 及 Σ 3? i 中的基本非同步路径组成 , 类似地 ,α 可由递归方程 L( Σ ) = L( Σ ) ⊕( li (Σ i ) + l 3? i (Σ 3? i ) ) 迭
代生成. (2) α∩ P(T0 ) ≠?.

(2.1) α 由一些互同步路径组成 , 显然 α 可由递归方程 L( Σ ) = L( Σ ) ⊕( li (Σ i ) ⊕ l3? i ( Σ 3? i ) + l3? i ( Σ 3? i ) ⊕ li (Σ i ) )
迭代生成,因此α可由递归语言方程 (?) 迭代生成. (2.2) α 由 一 些 互 同 步 路 径 及 Σ i 上 的 基 本 非 同 步 路 径 组 成 , 则 α 可 由 递 归 方 程
L( Σ ) = L( Σ ) ⊕( li (Σ i ) ⊕ l3? i ( Σ 3? i ) + l3? i ( Σ 3? i ) ⊕ li (Σ i ) + li (Σ i ) )迭代生成,所以α可由迭代语言方程 (?) 迭代生成.

(2.3) 如果 α 由一些互同步路径及 Σ i , Σ 3? i 上的基本非同步路径组成 , 则 α 可由递归方程 L( Σ ) = L( Σ ) ⊕ ( li (Σ i ) ⊕ l3? i (Σ 3? i ) + l3? i ( Σ 3? i ) ⊕ li (Σ i ) + li (Σ i ) + l 3? i (Σ 3? i ) )迭代生成,因而α可由递归方程 (?) 迭代生成.


3

同步合成 Petri 网系统的动态不变性
文献[11]提出并证明了 Petri 网系统同步合成的动态不变性,即状态不变性和行为不变性,它们的定义如下: 定义 3.1[11,12]. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OΣ 2 =( P, T ; F , M 0 ) ,其中 O 为一种合成操作.

若 ? M∈[ M 0 >都有 M | Pi ∈[ M 0i >(i=1,2),则称 Σ 满足状态不变性. 定义 3.2[11,12]. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OΣ 2 =( P, T ; F , M 0 ) ,其中 O 为一种合成操作. 若 ? α∈ L( Σ ) ,都有 α |Ti ∈ L( Σ i ) (i=1,2),则称 Σ 满足行为不变性. 定理 3.1[11,12]. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) ,则 Σ 满足状态不变性. 在文献[11,12]中给出的证明是基于顺序语言的方法,这里我们给出一个基于并发语言的证明. 证明:对 ? M∈[ M 0 >,记 M 0 [ α >M,类似于定理 2.1,我们分如下情形讨论:

(1) α 是 Σ i (i=1,2) 的基本非同步路径 , 则显然有 M 0 |Pi [α > M |Pi 且 M |P3?i = M 0 3?i . 又 M 0 |Pi = M 0 i , M 0 |P3?i =

M 0 3?i , 因此有 M |Pi ∈[ M 0 i >且 M |P3?i ∈[ M 0 3?i >.
(2) α 是由 Σ i 及 Σ 3? i 中的基本非同步路径组成 , 为简便起见 , 不妨记为 α = α1 ⊕ α 2 (≠ε ), 其中 α1 是 Σ i 上的基
本 非 同 步 路 径 , α 2 是 Σ 3? i 上 的 基 本 非 同 步 路 径 . 同 样 可 以 得 到 M 0 |Pi [ α1 > M |Pi 且 M 0 |P3?i [ α 2 > M |P3?i . 又

M 0 |Pi = M 0 i , M 0 |P3?i = M 0 3?i , 所以 M |Pi ∈[ M 0i >, M |P3?i ∈[ M 0 3?i >.
(3) α 是由一些互同步路径组成 , 为简便起见 , 不妨记 α = α1 ⊕ α 2 (≠ ε ), 其中 α1 是 Σ i 的基本同步路径 , α 2 是

Σ 3? i 上 α1 的互同步路径 , 则有 M 0 |Pi [ α1 \ (α1 , α 2 ) > M 1 |Pi , M 1 |P3?i [ α 2 \ (α1 , α 2 ) > M 2 |P3?i , M 1 |Pi = M 2 |Pi , M 0 |P3?i =
M 1 |P3?i 且 M 2 [ (α1 , α 2 ) >M. 由于 Σ 是 Σ 1 与 Σ 2 的同步合成网系统 , 因此有 M 2 |Pi [ (α1 , α 2 ) > M |Pi 在单个 Σ i 中成
立,同样, M 2 |P3?i [ (α1 ,α 2 ) > M |P3?i 在单个 Σ 3? i 中成立. 综上有: M 0 |Pi [ α1 \ (α1 , α 2 ) > M 2 |Pi [ (α1 , α 2 ) > M |Pi 在单个 Σ i 中成立,

M 0 |P3?i [ α 2 \ (α1 , α 2 ) > M 2 |P3?i [ (α1 , α 2 ) > M |P3?i 在单个 Σ 3? i 中成立.

蒲飞 等:同步合成 Petri 网系统活性与无死锁性的保持性 而 M 0 |Pi = M 0 i , M 0 |P3?i = M 0 3?i , 因此有 M |Pi ∈[ M 0i >, M |P3?i ∈[ M 0 3?i >.

1983

(4) α由一些互同步路径及 Σ i 的基本非同步路径组成 ,记 α = α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k ⊕ α 2 k +1 ,其中 α 2 j ?1 与

α 2 j (1≤j≤k) 是一对互同步路径 , α 2 k +1 是 Σ i 的基本非同步路径 . 设 M 0 [ α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k > M ′ [ α 2 k +1 >M, 由
上面的 (3) 可知 M ′ |Pi ∈[ M 0i >, M ′ |P3?i ∈[ M 0 3?i >. 因为 α 2 k +1 是 Σ i 的基本非同步路径 , 则有 M ′ |Pi [ α 2 k +1 > M |Pi , 且

M |P3?i = M ′ |P3?i . 故有 M | Pi ∈[ M 0i >, M | P3?i ∈[ M 0 3?i >.
(5) α由一些互同步路径及 Σ i , Σ 3? i 的基本非同步路径组成,类似于(4)可知, M |Pi ∈[ M 0i >, M | P3?i ∈[ M 0 3?i >.
综上可知,定理 3.1 结论成立. 定理 3.2
[11,12]



. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 = ( P, T ; F , M 0 ) ,则 Σ 满足行为不变性.


同样,在文献[11,12]中给出该定理的证明方法是基于顺序语言的.我们可以给出基于并发语言的证明. 证明:实际上,定理 3.1 的证明过程,也证明了定理 3.2,这里不再重复.

4

同步合成 Petri 网系统活性与无死锁性的判定
本节我们将利用第 2 节中得到的同步合成 Petri 网系统并发语言关系式来判定同步合成 Petri 网系统的活

性与无死锁性. 引理 4.1. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) . 如果 Σ 1 或 Σ 2 是非良结构

Petri 网系统,则 Σ 就是不活的. 证明:不失一般性,设 Σ 1 是非良结构 Petri 网系统,α 是 Σ 1 上的一条基本非同步路径,且α 不能延长为 Σ 1 的基
本同步路径.设 M[α > M ′ ,其中 M∈[ M 0 >,则对 ? Rt ∈ P(T0 ) 及 ? M ′′ ∈[ M ′ >: ?M ′′ [ Rt >.因此 Σ 是不活的. 定理给出. 定义 4.1. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) ,则称如下递归语言方程: □ 注: Σ 1 及 Σ 2 均为良结构 Petri 网系统只是同步合成网系统 Σ 活的必要条件, Σ 是活的充要条件将由下面的

L( Σ ) = L( Σ ) ⊕( l1 ( Σ 1 ) ⊕ l2 (Σ 2 ) + l2 (Σ 2 ) ⊕ l1 ( Σ 1 ) )
产生的语言子集为同步合成网系统 Σ 语言 L( Σ ) 的核,其中初始值为 L( 0 ) ( Σ ) = {ε } .记为 Ker ( L( Σ )) . 下面讨论核 Ker( L( Σ )) 与同步合成网系统 Σ 活性的关系. 定义 4.2. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 = ( P, T ; F , M 0 ) ,且 L 是 Σ 上的一个语言子 集 .令

L ={α ∈L| ? α ′ ∈L, α ⊕ α ′ (≠ε)∈L}, L ={α ∈L| ? α ′ ∈L, α ⊕ α ′ (≠ε)∈L 且| α ′ |≠0}, L ={α ∈L| ? α ′ ∈L, α ⊕ α ′ (≠ε)∈L 且|| α ′ ||=||L||},
其中 |α |表示 α 中所出现字符的个数,||α ||表示α 中出现的字符全体,则称 L , L , L 分别是语言 L 的递归闭语言、 严 格递归闭语言、强递归闭语言. 定理 4.2. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) ,则 Σ 是活的充要条件是:(1)

Σ i (i=1,2)都是良结构 Petri 网系统;(2) Ker( L( Σ )) = Ker ( L( Σ )) .
证明 :(?) 如果 Σ 是活的 , 由引理 (3.1) 可知 , Σ i (i=1,2) 都是良结构 Petri 网系统 . 以下证明条件 (2) 成立 . 对
? α ∈ Ker( L( Σ )) (α ≠ ε), ? t∈T, 记 M[α > M ′, 其中 M∈[ M 0 >. 我们将证明存在 α ′ ∈ Ker( L( Σ )) , 使得 α ⊕ α ′ (≠ε)∈

Ker( L( Σ )) 且 t∈ α ′. 由 Ker( L( Σ )) 的定义,设 α = α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k (k ≥ 1),其中 α 2i ?1 , α 2i (i=1,2,…,k)是一对
′ ⊕ α0 ′′ 且 互同步路径.由于 Σ 1 及 Σ 2 均为良结构 Petri 网系统 ,t 一定在某一对互同步路径上.记 t∈ α ′, 其中 α ′ = α 0 ′ 和 α0 ′′ 是一对互同步路径 . 设 α ⊕ α1 ′ ⊕ α2 ′ ⊕… ⊕ α 2 ′ n ?1 ⊕ α 2 ′ n (≠ε )是任意一条从 α 开始的互同步路径链 , 如果 α ′ α0

不在此链上 , 则有 ? M ′′ ∈[ M ′ >: ? M ′′ [t>. 但这与 Σ 是活的相矛盾 . 因此存在 α ′ ∈ Ker( L( Σ )) 使得 α ⊕ α ′ (≠ε)∈

Ker( L( Σ )) 且 || α ′ ||=T, 故 有 Ker( L( Σ )) ? Ker ( L( Σ )) . 另 一 方 面 , Ker ( L( Σ )) ? Ker ( L( Σ )), 所 以 Ker( L( Σ )) = Ker ( L( Σ )) .

1984

Journal of Software

软件学报

2003,14(12)

(?)如果(1)及(2)成立,则对 ? M∈[ M 0 >, ? t∈T,设 M 0 [ α >M,我们证明 ? M ′ ∈[M>,使得 M ′ [t>. (1) 如果 α 是 Σ i 的一条基本非同步路径 , 由于 Σ i 是良结构 Petri 网系统 , 因此存在 α1 ∈ ( P(Ti )) ? 及 α 2 ∈ ( P(T3*? i ))? 使得 α ⊕ α1 (≠ε)与 α 2 是互同步路径 ,则有 α ⊕ α1 ⊕ α 2 (≠ε)∈ Ker( L( Σ )) .又 Ker( L( Σ )) = Ker ( L( Σ )) ,存在
′ o t o α3 ′′ , 因 而 ? M 2 ∈[M > 满 足 α 3 ∈ Ker( L( Σ )) 满 足 || α3 ||=T, 且 α ⊕ α1 ⊕ α 2 ⊕ α3 (≠ε)∈ Ker( L( Σ )) . 记 α3 = α 3 ′ M 0 [α ⊕ α1 ⊕ α 2 > M 1 [ α 3 > M 2 [t>. (2) 如果α 是由 Σ i 和 Σ 3? i 上一些基本非同步路径组成,则类似于(1)可证.
?

(3) 如果α 是由一些互同步路径组成,则易知结论成立. (4) 如果α 是由一些互同步路径和 Σ i , Σ 3? i 中的基本非同步路径组成,同样类似于(1)可证.
综上可知, Σ 是活的. 下面讨论同步合成 Petri 网系统 Σ 无死锁的判定问题. 定义 4.3. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .设 L ? L( Σ ) ,令: □

exp(L)={α ∈L| ? α ′ ∈ ( P(T ? )) ? :α ⊕ α ′ (≠ε)∈ L( Σ ) }; stexp(L)={α ∈L| ? α ′ ∈ ( P(T ? )) ? :α ⊕ α ′ (≠ε)∈ L( Σ ) 且| α ′ |≠0}. 其中,| α |表示 α 中出现的字符个数,则称 exp(L),stexp(L)分别是 L 在 Σ 上的扩展语言、严格扩展语言. 定理 4.3. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) ,则 Σ 是无死锁的当且仅当 L( Σ ) \ Ker ( L( Σ )) =stexp( L( Σ ) \ Ker ( L( Σ )) ),其中“\”是集合的差运算.
证 明 :(?) 若 Σ 是 无 死 锁 的 , 则 对 ? α ∈ L( Σ ) \ Ker ( L( Σ )) , 记 M 0 [α >M, 存 在 t ∈ T 使 得 M[t>, 因 此

α ⊕ t(≠ε)∈ L( Σ ) , 所以 α ∈stexp( L( Σ ) \ Ker ( L( Σ )) ). 即有 L( Σ ) \ Ker ( L( Σ )) ? stexp( L( Σ ) \ Ker ( L( Σ )) ). 另一方面 ,
显然有 stexp( L( Σ ) \ Ker ( L( Σ )) ) ? L( Σ ) \ Ker ( L( Σ )) .因此 L( Σ ) \ Ker ( L(Σ )) =stexp( L( Σ ) \ Ker ( L( Σ )) ).

(?)若 L( Σ ) \ Ker ( L( Σ )) =stexp( L( Σ ) \ Ker ( L( Σ )) ),则对 ? M∈[ M 0 >,记 M 0 [ α >M,因此 α 为如下情形之一: (1) α ∈ Ker ( L( Σ )) , 由 Ker ( L( Σ )) 的定义有 , α ′ ∈ Ker( L( Σ )) 且 | α ′ |≠0, 使得 α ⊕ α ′ ∈ Ker( L( Σ )) , 故存在 t ∈ α ′ 使得 M[t>. (2) α ∈ L( Σ ) \ Ker ( L( Σ )) , 由于 L( Σ ) \ Ker ( L( Σ )) =stexp( L( Σ ) \ Ker ( L( Σ )) ), 则存在 α ′ ∈ ( P(T ? )) ? 使得 α ⊕ α ′ (≠ε)∈ L( Σ ) ,因此有 t∈ α ′ 使得 M[t>.
综合(1)、 (2)可知, Σ 是无死锁的. □

5

同步合成 Petri 网系统活性与无死锁性的保持性
本节我们给出一些条件,在这些条件下,如果子网系统活(无死锁),则同步合成网系统活(无死锁). 定理 5.1. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .如果 Σ i (i=1,2)满足如下条

件,则 Σ 是活的. (1) Σ i (i=1,2)均为良结构 Petri 网系统;

(2) Σ i (i=1,2)都是活的.
证明:我们用定理 4.2 来证明.由(1)只需证 Ker( L( Σ )) = Ker( L( Σ )) .因为 Ker( L( Σ )) ? Ker( L( Σ )) ,故只要证明

Ker( L( Σ )) ? Ker( L( Σ )) 即可 . 对 ? α∈ Ker( L( Σ )) ,设 α= α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k (k ≥ 1), 其中 α 2i ?1 , α 2i (i=1,2,…,k)
是 一 对 互 同 步 路 径 . 不 失 一 般 性 , 设 α 2 k ?1 是 Σ 1 的 基 本 同 步 路 径 , α 2 k 是 Σ 2 上 与 α 2 k ?1 的 互 同 步 路 径 , 记 为
M 1 [ α 2 k ?1 ⊕ α 2 k > M 2 其中 M 1 ∈[ M 0 >. 由定理 3.1 可知 , M 2 |P2 ∈[ M 0 2 >, 又 Σ 2 是活的且为良结构网系统 , 则对 ′ ? α2 ′ ?…? α n ′ 且 α i′ (1 ≤ i ≤ n?1)是基本同步路径 , α n ′ 是 Σ 2 的基本同步路径或 ? t∈ T2 ,有 α ′ ∈ ( P(T2* ))? ,其中 α ′ = α1 ′ 是 Σ 2 的基本非同步路径 ),使得在 Σ 2 上 (仅看单个 Σ 2 ) M 2 |P2 [ α1 ′ ? α2 ′ ? …? α n ′ ?t>.同时 基本非同步路径 (不妨设 α n

存 在 Σ 1 上 与 α i′ (1≤i≤n?1) 互 同 步 路 径 α i′′ 满 足 α i′ ⊕ α i′′ ≠ε, 则 在 同 步 合 成 网 系 统 Σ 上 , 有 M 3 ∈[ M 2 > 满 足

′′ ⊕…⊕ α n ′′?1 > M 3 . ′ ⊕ α1 ′ ?1 ⊕ α n M 2 [ α1

蒲飞 等:同步合成 Petri 网系统活性与无死锁性的保持性

1985

′′ ⊕…⊕ α n ′′?1 ⊕( α n ′ ?t 是 Σ 2 的基本同步路径 ,设 α n ′′ 是 α n ′ ?t 的互同步路径 ,则有 α = α1 ′ ⊕ α1 ′ ?1 ⊕ α n ′ ? t)⊕ 如果 α n ′′ ∈ Ker( L( Σ )) 满足 α ⊕ α (≠ε)∈ Ker( L( Σ )) 且 t∈ α .如果 α n ′ ?t 不是 Σ 2 的基本同步路径,由 Σ 2 是良结构 Petri 网 αn ′′+1 ∈ ( P(T1 )) ? 使得 α n ′′+1 是 α n ′ +1 ∈ ( P(T2* ))? 及 α n ′ ?t? α n ′ +1 是 Σ 2 的基本同步路径且 α n ′ ?t? α n ′ +1 的互同步 系统 , 存在 α n ′′ ⊕…⊕ α n ′′?1 ⊕( α n ′′+1 (≠ε)∈ Ker( L( Σ )) 满足 α ⊕ α (≠ε)∈ Ker( L( Σ )) 且 ′ ⊕ α1 ′ ?1 ⊕ α n ′ ?t? α n ′ + 1 )⊕ α n 路径 . 因此有 α = α1
t∈ α .总之,必有 α ∈ Ker( L( Σ )) 使得α ⊕ α ( ≠ ε )∈ Ker( L( Σ )) 且|| α ||= T2 .
类似地,存在 α ′ ∈ Ker( L( Σ )) ,使得α ⊕ α ⊕ α ′ ∈ Ker( L( Σ )) 且 || α ′ || = T1 ,因此有 α 0 = α ⊕ α ′ ∈ Ker( L( Σ )) 满足
|| α 0 || =T,使得 α ⊕ α 0 (≠ ε) ∈ Ker( L( Σ )) ,故而 α ∈ Ker( L( Σ )) ,从而 Ker( L( Σ )) ? Ker( L( Σ )) .由定理 4.2 可知 , Σ 是
?

活的. □ 由于定理 5.1 中的条件(1)不易判定,进一步我们给出如下条件,使得同步合成 Petri 网系统同样有活性保持 性质. 定理 5.2. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .如果下列条件成立,则 Σ 是 活的.

(1) 在单个子网系统 Σ i (i=1 或 2)中,对 ? M i ∈[ M 0 i >,若对 ? Rt ∈ P(T0 ) ,有 M i′ ∈[ M i >及α ∈ ( P(Ti )) ? 使得
M i [α > M i′ [ Rt >, 则在单个子网系统 Σ i 中另外存在 α ′ ∈ ( P(Ti )) ? 及 M i′′ ∈[ M i >,满足 M i [ α ′ > M i′′ [ Rt >且 α ′ ∩ P(T0 ) =?(如果α ∩ P(T0 ) =?,则 α ′ 就可取为α).
?

?

(2) Σ i (i=1,2)是活的.
注 : 条件 (1) 意为对单个子网系统 Σ i 中以任意一条同步变迁步 Rt 为终点的路径 ,在 Σ i 中存在另一条中间不 经过同步变迁的仍以 Rt 为终点的路径. 证明:由定理 5.1,若能证明 Σ i (i=1,2)均为良结构网系统即可.先证 Σ 3? i 是良结构 Petri 网系统,对 Σ 3? i 中任一 基本非同步路径α ,记为 M 1 |P3?i [α > M 2 |P3?i , 其中 M 1 ∈[ M 0 >,则由定理 3.1 可知, M 2 |P3?i ∈[ M 0 3?i >.又 Σ 3? i 是活的 , 故在单个 Σ 3? i 上有 t∈ T0 , α1 ∈ ( P(T3*? i ))? 且 α1 ∩ P(T0 ) =?,使得 M 2 |P3?i [ α1 > M 3 |P3?i [t>,且对此 t∈ T0 由条件(1)和 条件 (2), 在单个网系统 Σ i 上也有 α 2 ∈ ( P(Ti )) ? 使得 α 2 ∩ P(T0 ) =? 且 M 2 |Pi [ α 2 > M 3 | Pi [t>, 从而在同步合成网 系统 Σ 上 , 有 M 3 [ t >, 因此 α ? α1 ? t 是 Σ 3? i 的基本同步路径 , α 2 ? t 是相应的互同步路径 . 所以 , Σ 3? i 是良结构网 系统. ′∈ ′ |Pi [ β > M 2 ′ |Pi , 其中 M 1 下面再证 Σ i 也是良结构网系统 . 对 Σ i 中任意一条基本非同步路径 β , 记为 M 1
′ ∈ ( P(T3*? i ))? 使得 M 2 ′ |P3?i [ α1 ′ ? t > 且 α1 ′ ∩ P(T0 ) =?. 因 [ M 0 >.由于 Σ 3? i 是活的 ,则在单个网系统 Σ 3? i 中有 t∈ T0 , α1 ′ ∈ ( P(Ti )) ? 且 α 2 ′ ∩ P(T0 ) =?,使得 M 2 ′ |Pi [ α 2 ′ ?t>,从 此 t∈ T0 ,同样,由 Σ i 是活的及条件(1),在单个网系统 Σ i 上有 α 2 ′ ∈[ M 2 ′ >使得 M 3 ′ [t>.因此 β ? α 2 ′ ?t 是 Σ i 的基本同步路径, α1 ′ ?t 是相应的互同步路径,故 Σ i 也是良结构网 而有 M 3
? ?

系统. □ 我们还给出如下条件,使得同步合成 Petri 网系统有活性保持性. 定理 5.3. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .如果下列条件成立,则 Σ 是 活的.

(1) 若在单个子网系统 Σ i 中(i=1 或 2),若对 ? t∈ T0 ,存在 t ′ ∈ Ti 且 t ′ ? T0 使得 ? (t ′) ? ? t 且 (t ′)? ? t ? . (2) Σ i (i=1,2)是活的.
证明:由定理 5.2,只需证明子网系统 Σ i 满足定理 5.2 中条件 (1)即可.在单个网系统 Σ i 中,对 ? M i ∈[ M 0i >, 对 ? Rt ∈ P(T0 ) ,若有 M i′ ∈[ M i >,α ∈ ( P(Ti )) ? ,使得 M i [α > M i′ [ Rt >且 α ∩ P(T0 ) =?,则得证 .若 α ∩ P(T0 ) ≠?,不 妨设α = α1 ? Rt1 ? α 2 ,记为 M i [ α1 > M i1 [ Rt1 > M i2 [ α 2 > M i′ [ Rt >,其中 α i ∩ P(T0 ) =?(i=1,2)及 α i ≠ε,且 Rt1 ∈ P(T0 ) , 则由条件 (1), 在网系统 Σ i 上存在 Rt′1 ∈ P (Ti ) 且 Rt′1 ∩ P(T0 ) =?, 使得 ? ( Rt′1 ) ? ? Rt1 且 ( Rt′1 )? ? Rt1 ? , 故而在 Σ i 上有 路径 α1 ? Rt′1 ? α 2 ? Rt ,使得 M i [ α1 > M i1 [ Rt′1 > M i′2 [ α 2 > M i′′ [ Rt >,其中( α1 ? Rt′1 ? α 2 )∩ P(T0 ) =?. 一般地 ,设 α = α1 ? Rt1 ? α 2 ?...? α k ?1 ? Rt ? α k ,其中 α i ∩ P(T0 ) =?, Rt i ∈ P(T0 ) (i=1,2,…,k).类似地 ,有 α ′ = α1 ?
k

?

Rt′1 ? α 2 ?...? α k ?1 ? Rt′k ? α k ,满足 Rt′1 ∈ P(Ti ) 且 Rt′1 ∩ P(T0 ) =?(1 ≤ i ≤ k),使得 M i [ α ′ > M i′′ [ Rt >.故由定理 5.2,同步

1986
合成网系统 Σ 是活的. 例 2:如图 2 所示, Σ 是 Σ 1 与 Σ 2 的同步合成网系统.
P1 a P2 c
?

Journal of Software

软件学报

2003,14(12)


P1 b P3 P5
?

a d P6 f e g P7 e h P8 i P5
?

b P3
?

P2 d f

c

P6 P4 P7 g

e P8 h

i

d

P4

Σ1

Σ2

Σ =Σ 1 OTΣ 2

Fig.2 图2
易知, Σ 1 , Σ 2 是活的,且 Σ 2 满足定理 5.3 的条件,则由定理 5.3 可知, Σ 是活的. 下面我们给出定理 5.2 及定理 5.3 的一个应用. 定义 5.1. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .在子网系统 Σ i 中 , 对 ? t ∈
T0 ,若 ? t ′ ∈ Ti 且 t ′ ? T0 满足 ? (t ′) = ? t 且 (t ′)? = t ? ,则称 t ′ 为 Σ i 中同步变迁 t 的替换变迁.相应地,定义同步变迁步 Rt 的替换变迁步 Rt′ .

一般情况下,两个活的 Petri 网系统 Σ 1 , Σ 2 作同步合成,所得到的网系统 Σ 不一定是活的.若 Σ 不活,则可通 过适当添加同步变迁(步 )的替换变迁(步 ),使所得到的网系统变活.我们把定理 5.2 与定理 5.3 中的条件结合起 来,则有如下定理: 定理 5.4. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .若 (1) Σ i (i=1,2)是活的但 Σ 不 活 ;(2) 任 取 子 网 系 统 Σ i (i=1 或 2)( 仅 看 单 个 的 网 系 统 Σ i ), 对 ? M i ∈[ M 0 i >, 若 对 某 个 Rt ∈ P(T0 ) , 有
M i′ ∈[ M i > 及 α ∈ ( P(Ti )) ? 满足 M i [α > M i′ [ Rt > 但 α ∩ P(T0 ) ≠?. 又不存在另一个 α ′ ∈ ( P(Ti )) ? , 使得 M i [ α ′ > M i′′ [ Rt > 且 α ′ ∩ P(T0 ) =?. 那 么 , 在 Σ i 中 添 加 Rt′ ∈α ∩ P(T0 ) 的 替 换 变 迁 步 Rt′′ 得 到 子 网 统 Σ i′ , 记
? ?

Σ ′ = Σ i′ OT Σ 3? i ,则有 Σ ′ 是活的.
证明:由定理 5.2 及定理 5.3 易证. 网系统变活. 例 3:如图 3 所示, Σ 是 Σ 1 与 Σ 2 的同步合成网系统.
a P1
?



注 :该定理说明任取一个子网系统 , 只要在其上添加相应的替换变迁 ( 步 ) 以后 , 就可以使所得到的同步合成

P7 b b
?

P2 P3

g P8 P9

a

P1

?

P7 b
?

P2 P3

g

P8 d P9 P10 f
f′

c

P4 P5 P6

d

d P10 f

h

c e

P4 P5 P6

h i

e

f

P11 P12

i

P11 P12

Σ1

Σ2

′ Σ ′ = Σ 1OT Σ 2

Fig.3 图3
易知 Σ 1 , Σ 2 均是活的 , 但同步合成网系统 Σ 不活 . 在 Σ 2 中添加变迁 f 的替换变迁 f ′ 以后 ( 图中以粗线表 示),由定理 5.4 可知, Σ ′ 是活的(注:也可以在 Σ 1 上添加相应的替换变迁(步)). 下面我们讨论同步合成网系统无死锁的保持性问题,首先有如下定理: 定理 5.5. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .如果满足如下条件,则 Σ 是 无死锁的.

蒲飞 等:同步合成 Petri 网系统活性与无死锁性的保持性
?

1987

(1) 在单个子网系统 Σ i (i=1 或 2)中,对 ? M i ∈[ M 0i >,若对 ? Rt ∈ P(T0 ) ,有 M i′ ∈[ M i >及 α ∈ ( P(Ti )) ? 使得
M i [α > M i′ [ Rt >, 则 在 单 个 子 网 系 统 Σ i 中 另 外 存 在 一 个 α ′ ∈ ( P(Ti )) ? , Rt′ ∈ P(Ti \ T0 ) 及 M i′′ ∈[ M i > 满 足 M i [ α ′ > M i′′ [ Rt′ >且 α ′ ∩ P(T0 ) =?.
?

(2) Σ i (i=1 或 2)是无死锁的.
注:(2)中的 Σ i 与(1)中的 Σ i 相同. 证明:我们用定理 4.3 来证明.因 stexp( L( Σ ) \ Ker ( L( Σ )) )? L( Σ ) \ Ker ( L( Σ )) ,因此只需证 L( Σ ) \ Ker ( L( Σ )) ?

stexp( L( Σ ) \ Ker ( L( Σ )) ). 对 ? α ∈ L( Σ ) \ Ker ( L( Σ )) , 有 α ? Ker ( L( Σ )) , 因 此 由 Ker ( L( Σ )) 的 定 义 可 得 :(1) α ? Ker( L( Σ )) ;(2) α ∈ Ker( L( Σ )) ,但不存在 α ′ ∈ Ker( L( Σ )) 满足 | α ′ | ≠0 且 α ⊕ α ′ (≠ε ) ∈ Ker( L( Σ )) . 情 形 1. 记 α = α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k ⊕ α 2 k +1 ⊕ α 2 k + 2 , 其 中 α 2i ?1 , α 2i (i=1,2,…,k) 是 一 对 互 同 步 路 径 . α 2 k +1 , α 2 k + 2 分 别 是 Σ i 及 Σ 3? i 的 基 本 非 同 步 路 径 , α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k 可 以 为 ε , α 2 k +1 也 可 以 为 ε , 但 α 2 k + 2 ≠ε.不妨设 α 2 k +1 ≠ε,记 M 0 [ α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k ⊕ α 2 k +1 > M 1 [ α 2 k + 2 >.由定理 3.1 可知, M 1 |Pi ∈[ M 0i >.再
由条件 (2), 存在 t∈ Ti , 使在单个网系统 Σ i 上有 M 1 |Pi [t>. 若 t? T0 , 则显然在同步合成网系统 Σ 上有 M 1 [t>. 若
? t∈ T0 , 则 由 条 件 (1), 对 单 个 网 系 统 Σ i 上 路 径 α 2 k +1 ?t, 存 在 α ′ ∈ ( P(Ti )) ? 且 α ′ ∩ P (T0 ) =?, t ′ ∈ Ti \ T0 , 使 得

M 1 |Pi [ α ′ ? t ′ >.而 M1 |Pi = M 2 |Pi (因 α 2 k + 2 是 Σ 3? i 的基本同步路径 ),因此 ,在同步合成网系统 Σ 上 ,有 M 1 [ α ′ ? t ′ >,
亦有 M 2 [ α ′ ? t ′ >.故 Σ 无死锁. 情形 2. α = α1 ⊕ α 2 ⊕…⊕ α 2 k ?1 ⊕ α 2 k (≠ε ),其中 α 2i ?1 , α 2i (i=1,2,…,k)是一对互同步路径 .记 M 0 [α > M ′ ,则由 定理 3.1 可知 M ′ |Pi ∈[ M 0 i >.由条件 (2), 存在 t∈ Ti ,使在单个网系统 Σ i 上 , M ′ |Pi [t>.若 t? T0 , 则显然在 Σ 上有
M ′ [t>. 若 t∈ T0 , 由 条 件 (1), 存 在 α ′ ∈ ( P(Ti )) ? , α ′ ∩ P (T0 ) =?, t ′ ∈ Ti \ T0 , 使 得 在 单 个 网 系 统 Σ i , 有
M ′ |Pi [ α ′ ? t ′ >.易知,在 Σ 上, M ′ [ α ′ ? t ′ >成立.故 Σ 无死锁.
?



定理 5.6. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .如果 Σ i (i=1,2)满足如下条件, 则 Σ 是无死锁的.

(1) 若在单个子网系统 Σ i 中(i=1 或 2),若对 ? t∈ T0 ,存在 t ′ ∈ Ti 且 t ′ ? T0 使得 ? (t ′) ? ? t 且 (t ′)? ? t ? ; (2) Σ i (i=1 或 2)是无死锁的.
注:(2)中的 Σ i 与(1)中的 Σ i 相同. 证明:由定理 5.5,只要证明满足定理 5.5 的条件(1)即可,这可类似于定理 5.3 的证明,略. □ 一般情况下 ,两个无死锁的 Petri 网系统 Σ 1 , Σ 2 作同步合成 ,所得到的网系统 Σ 不一定是无死锁的.若 Σ 有 死锁,同样可以通过添加同步变迁(步)的替换变迁(步)使所得到的合成网系统无死锁,因此也有如下定理: 定理 5.7. 设 Petri 网系统 Σ i = ( Pi , Ti ; Fi , M 0i ) (i=1,2), Σ = Σ 1OT Σ 2 =( P, T ; F , M 0 ) .若 (1) Σ i (i=1,2)是无死锁的 但 Σ 有死锁 ;(2) 任取单个子网系统 Σ i (i=1 或 2) 中 , 对 ? M i ∈[ M 0i >, 若对某个 Rt ∈ P(T0 ) , 有 M i′ ∈[ M i > 及

α ∈ ( P(Ti ? )) ? 满足 M i [α > M i′ [ Rt > 但 α ∩ P(T0 ) ≠?. 又不存在另一个 α ′ ∈ ( P(Ti ? ))? , Rt′ ∈ P(Ti \ T0 ), 使得 M i [ α ′ >
M i′′ [ Rt′ > 且 α ′ ∩ P(T0 ) =?. 那么在 Σ i 中添加 Rt′ ∈ α ∩ P(T0 ) 的替换变迁步 Rt′′ 及 Rt 的替换变迁步 Rt 得到子网 系统 Σ i′ ,记 Σ ′ = Σ i′ OT Σ 3? i ,则 Σ ′ 是无死锁的.
注 :该定理说明 ,任取一个子网系统 ,只要在其上添加相应的替换变迁 (步 )以后 ,就可以使所得到的同步合成 网系统变为无死锁.

6

结论及下一步的研究工作
在对复杂大系统进行建模分析时 , 一个重要问题是设法降低系统状态的高复杂度 .合成操作是一种有效的

方法来处理系统的复杂状态.因此,系统合成操作的保持性研究是一个重要的研究课题.文献[11~13]研究了 Petri 网系统同步合成操作的语言性质 ,建立了相应的语言关系式 .给出了同步合成网系统活性、无死锁性与非阻塞 性的关系,同时讨论了 Petri 网系统同步合成的动态不变性.但由于是基于顺序语言的讨论,因此给这些结果的应 用带来一定的局限 ,而且同步合成网系统的活性保持性尚没有讨论 .为了给出一个更为广泛使用的方法 ,本文定

1988

Journal of Software

软件学报

2003,14(12)

义了路径并发合成的运算 “ ⊕ ”,以此来建立同步合成网系统的并发语言关系式 .该语言关系式可用来判定同步 合成网系统的活性与无死锁性 ,给出了相应的充要条件 .同时提出一些条件 ,使同步合成网系统有活性及无死锁 性的保持性质,并用例子说明了所给出的方法的有效性.本文的方法及结果容易推广到加权 Petri 网系统的同步 合成操作中 .下一步的研究工作是进一步推广同步合成网系统满足活性及无死锁性的保持性条件 ,并研究同步 合成网系统其他性质的保持性问题. References:
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] Souissi Y. On liveness preservation by composition of nets via a set of places. In: Rozenberg G, ed. Lecture Notes in Computer Science, Vol 524. New York: Springer-Verlag, 1991. 277~295. Souissi Y, Memmi G. Composition of nets via a communication medium. In: Rozenberg G, ed. Lecture Notes in Computer Science, Vol 483. New York: Springer-Verlag, 1990. 457~470. Jeng MD. A Petri net synthesis theory for modeling flexible manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 1997,27(2):169~183. Jeng MD, Diceare F. A review of synthesis techniques for Petri nets with application to automated manufacturing systems. IEEE Transactions on Systems, Man, and Cybernetics, 1993,23(1):301~312. Jeng MD, Diceare F. Synthesis using resource control nets for modeling share resource systems. IEEE Transactions on Robotics and Automation, 1995,11(3):317~327. Aybar A, Ifar A. Overlapping decompositions and expansions of Petri nets. IEEE Transactions on Automatic Control, 2002,47(3): 511~515. Berthelot G. Checking properties of nets using transformations. In: Rozenberg G, ed. Lecture Notes in Computer Science, Vol 254. New York: Springer-Verlag, 1985. 19~40. Berthelot G. Transformations and decompositions of nets. In: Rozenberg G, ed. Lecture Notes in Computer Science, Vol 256. New York: Springer-Verlag, 1986. 359~376. Esparza J, Silva M. On the analysis and synthesis of free choice systems. In: Rozenberg G, ed. Lecture Notes in Computer Science, Vol 483. New York: Springer-Verlag, 1990. 243~286. Esparza J, Silva M. Top-Down synthesis of live and bounded free choice nets. In: Rozenberg G, ed. Lecture Notes in Computer Science, Vol 524. New York: Springer-Verlag, 1991. 118~139. Jiang CJ. A PN Machine Theory of Discrete Event Dynamic System. Beijing: Science Press, 2000 (in Chinese). Jiang CJ. Petri net dynamic invariance. Science in China (Series E), 1997,27(6):605~611 (in Chinese with English abstract). Wang HQ, Jiang CJ, Liao SY. Behavior relations in synthesis process of Petri net models. IEEE Transactions on Robotics and Automation, 2000,16(4):400~406. Murata T. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 1989,77(4):541~580. Peterson JL. Petri Net Theory and the Modeling of Systems. Englewood Cliffs: Prentice-Hall, Inc., 1981. Resig W. Petri nets. In: EATCE Monographs on Theoretical Computer Science, Vol.4. New York: Springer-Verlag, 1985. Ferrarini L, Trioni M. Modeling shared resources with generalized synchronization within a Petri net bottom-up approach. IEEE Transactions on Systems, Man, and Cybernetics-Part B: Cybernetics, 1996,26(45):653~659.

附中文参考文献:
[11] [12] 蒋昌俊 .离散事件动态系统的 PN 机理论 .北京 :科学出版社 ,2000. 蒋昌俊 .Petri 网的动态不变性 .中国科学 (E 辑 ),1997,27(6):605~611.


相关文章:
biological uselessness of pain and fear.doc
biological uselessness of pain and fear_
On the Equivalence between Liveness and deadlock Freeness in ....unkown
//www.researchgate.net/publication/278769160 On the Equivalence between Liveness and deadlock Freeness in Petri Nets ARTICLE JANUARY 2003 READS 4 2 ...
Siphons, Traps, Liveness, Deadlock-Freeness in Petri Nets.unkown
CIS 525 Software Development of Parallel and Distributed Systems 1 Siphons, Traps, Liveness, Deadlock-Freeness in Petri Nets Let us assume that N=(P,...
On reachability and deadlock-freeness of Hybrid Adaptive ....unkown
Preprints of the 18th IFAC World Congress Milano (Italy) August 28 - September 2, 2011 On reachability and deadlock-freeness of Hybrid Adaptive Petri ...
Deadlock-Freeness Analysis of Continuous Mono-T-Semiflow ....unkown
51, NO. 9, SEPTEMBER 2006 Deadlock-Freeness Analysis of Continuous Mono-...Unfortunately, some impor- tant properties, as liveness, may not be ...
Timing and deadlock-freeness in Continuous Petri nets.unkown
July 6-11, 2008 Timing and deadlock-freeness in Continuous Petri nets ...Therefore, liveness of the discrete autonomous model is nor necessary, ...
Timing and Deadlock-Freeness in Continuous Petri Nets.unkown
and Deadlock-Freeness in Continuous Petri Nets Conference Paper July ...Therefore, liveness of the discrete autonomous model is nor necessary, ...
An extension of the liveness theory for concurrent sequential....pdf
of liveness (the deadlock freeness is a ...2. PR 6= ; and (P fp0 g) \ PR = ;. ...Mart nez. Synthesis of live models for a class...
Deadlock-Freeness of Hexagonal Systolic Arrays.unkown
(52 pages) online, http://ssfm.cs.up.ac.za/TR-ThS-2010.pdf Deadlock-Freeness of Hexagonal Systolic Arrays Stefan Gruner & Theuns Steyn Department ...
On deadlock-freeness analysis of autonomous and timed ....unkown
For this subclass, the equivalence between liveness and deadlock-freeness ...t1 32 p 1 2 t2 2p2 23 3 t1 p 1 2 t2 p 2 (a) (b) Figure 1...
Proving Liveness Properties of Concurrent Programs_....pdf
Absence of deadlock: the program never enters a state in which no further...Flon and Suzuki [3] also present a formal proof system for liveness ...
Linear Analysis of Deadlock-Freeness of Petri Net Models.unkown
See discussions, stats, and author profiles for this publication at: http://www.researchgate.net/publication/282861100 Linear Analysis of Deadlock-Freeness...
Deadlock-freeness of hexagonal systolic arrays.unkown
See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/220112840 Deadlock-freeness of hexagonal ...
Deciding Liveness in Component-Based Systems is NP-hard.pdf
Deciding Liveness in Component-Based Systems is NP-hard_专业资料。Abstract....Proposition 1 Sys (F ) is deadlock-free and F is not satis?able if ...
A Polynomial Algorithm to Prove Deadlock-Freeness of Wormhole....unkown
2010 18th Euromicro Conference on Parallel, Distributed and Network-based Processing A Polynomial Algorithm to Prove Deadlock-Freeness of Wormhole Networks ...
Exclusion-Freeness in Multi-party Exchange Protocols.pdf
In the next section we introduce the concept of exclusion-freeness and ...After a chosen deadline, the TTP will verify if the set of identities ...
Design and Implementation of a Java-based Distributed ....pdf
must take into account temporal conditions: liveness, deadlock-freeness, process synchronization and communication, this is often called correctness debugging....
A Study of Mobile Agents Liveness Properties on.pdf
free the machine for the local user: migration and cloning with liveness....Also, a dead machine has the same probability p of being turned on again...
Linear algebraic techniques for the analysis of Petri nets_....pdf
deadlock-freeness, structural liveness or ...2. A producer-consumer Petri net and its p-...Silva. On the analysis and synthesis of free ...
Freeness with amalgamation, limit theorems and S-transform in....pdf
arXiv:0709.0011v2 [math.OA] 14 Oct 2007 FREENESS WITH AMALGAMATION, LIMIT THEOREMS AND S-TRANSFORM IN NON-COMMUTATIVE PROBABILITY SPACES OF TYPE B ...
更多相关标签: