PDF《第30 卷第 6 期》

F ? (P*T)∪ (T*P)是有向连接弧的集合;

W : F →N+ (N+ ={1, 2,是连接弧的权重. 当且仅当?f ∈F, W(f) = 1时, 称N = (P, T, F, W)为普通网(ordinary net), 可 以记作N = (P, T, F). 若?f ∈ F, W(f) 1, 称N = (P, T, F, W)为一般网(generalized net). 给定一个变 迁t ∈ T, ・ t = {p ∈ P|(p, t) ∈ F}, t・ = {p ∈ P|(t, p) ∈ F};

给定一个库所p ∈ P, ・ p = {t ∈ T|(t, p) ∈ F}, p・ = {t ∈ T|(p, t) ∈ F}. 若?x∈P ∪T, ・ x∩x・ = ?, 则称网N为一个纯网(pure net). 若?t ∈ T, |・ t| = |t・ | = 1, 则称网N是状态机(state machine). 网N的标识是映射 M : P → N (N = {0, 1, 2, M(p)表示库所p中的托肯数, 托肯用实心 圆点或数字表示. 称(N, M0)为标识网, 其中M0为网N的初始标识. 本文采用一种简洁的方式表示向 量以节省空间, 即用表达式 p∈P M(p)p表示向量M, 如图1所示网(N?, M?0)中, 记M?0 = 10p7 + 10p11 + 2p12 + 2p13 + 3p14 + p15. 下文中其他向量, 也以同样方式表示. 标识网(N, M0)中, 称变迁t ∈ T在标识M0下是状态使能的, 当 且仅当?p ∈・ t, M0(p) W(p, t), 记为M0[t . 一个 状态使能的标识是能够激发的, 激发后的标识为M, ?p ∈ P, M(p) = M0(p) ? W(p, t) + W(t, p), 记为M0[t M. σ = t1t2 ・ ・ ・ tk表示变迁的激发序列, 若 满足M0[t1 M1[t2 ・ ・ ・ [tk Mk, 即M0[σ Mk, 则称 Mk是M0的可达标识. 网N中, M0的所有可达标识 集记为R(N, M0). 定定定义 义义1[11] 给定一个Petri网N = (P, T, F, W), γ = (x1, x2,xk), 其中: 结点xi ∈ P ∪ T, i ∈ {1, 2,k}, k ∈ N+ 且k 1. 若?i ∈ {1, 2, k ? 1}, xi+1 ∈ x・ i, 则称γ为路径. 若路径γ中的结点 各不相同(头尾结点除外), 则称该路径为从x1到xk 的一条基本路径, 用符号EP(x1, xk)表示. 定定定义 义义2[2] 给定一个标识网(N, M0), 如果?M ∈ R(N, M0), 都?M ∈ R(N, M), 使得M [t , 则称 变迁t ∈ T是活的. 若?t ∈ T都是活的, 则称标识网 (N, M0)是活的. 定定定义 义义3[8] 给定一个Petri网N = (P, T, F, W), |P| = u, |T| = v, A是网N的关联矩阵, A[t, p] = W(t, p) ? W(p, t). 若存在 u 维向量 I, I =

0 满足 A ・ I = 0, 则称I是网N的一个PC不变式. 记I={pj ∈ P|I(j) = 0}为PC不变式I的支撑集, I + = {pj ∈ P|I(j) >

0}为I的正支撑集, I ? = {pj ∈ P|I(j) <

0}为I的负支撑集. 称一个PC不变式是极 小的当且仅当它的支撑集中不包含任何其他PC不 变式的支撑集. 如果一个PC不变式I 满足条件 I = ?且I?=?, 则称其为PC半流. 定定定义 义义4[8] 给定一个Petri网N = (P, T, F, W), 集合S = ?且S ? P. 如果・ S ? S・ (S・ ?・ S), 则称 S是一个信标(陷阱). 一个信标是极小的当且仅当不 存在其他信标是其真子集. 若一个极小信标不包含 任何已标记的陷阱, 则称其为SMS;

否则, 称为非严 格的极小信标. 第6期徐姗姗等: 一类活性Petri网控制器的冗余检测及结构简化

675 定定定义 义义5[5] 给定一个标识网(N, M0), S是网N 的一个信标. 如果标识M ∈R(N, M0)下, ?p∈S, 使得M(p) maxp・, 其中maxp・=maxt∈p・{W(p, t)}, 则称S在标识M下是最大标记的(max-marked). 如 果对于?M ∈ R(N, M0), S在可达标识M下都是 最大标记的, 则称S是最大受控的(max-controlled)信标. 引引引理 理理1[18] 给定一个标识网(N, M0), S是网N 的一个信标. 如果网中存在PC不变式I同时满足以 下3个条件, 那么信标S是最大受控的. 条件如下: 1) I + ? S;

2) ?p ∈ ( I ? ∩ S), maxp・ = 1;

3) p∈P I(p)M0(p) >