第八章Petri网合法发射序列的判定讲述.ppt

第八章 Petri网顺序序列  的测试与判定 提纲 一、合法发射序列的判定 二、合法发射向量的判定 问题 设PNi=(Pi,Ti;Fi, M0i) (i=1,2) 是两个Petri网，PN= PN1 OT PN2 ， 且?= T1 ?T2 。 问题一： 给定??T* ，??L(PN)？ 问题二：若?i? L(PNi) =(P,T;F, M0) ， ?1??2?L(PN)？其中?1??2={?| ??T1?T2 ??Ti(?)= ?i, i=1,2} 一、合法发射序列的判定 直接测试算法 依序判断每个变迁是否可以发生？ 一、合法发射序列的判定 定义8.1. 设Ti (i=1,2) 是两个字母表，且T1 ?T2??。LTi分别是Ti上的一个语言，对于?i? LTi ，令 ?1??2={?| ??T1?T2 ??Ti(?)= ?i, i=1,2} 则称?1??2是?1、?2的同步序列集。 若Xi是对应于?i的发射向量，令X= X1?X2，使得??t ? T1 ? T2： （1）若(t ? T1 ?T2) ?(X1(t)=X2(t))，则X(t)= X1(t); （2）若(t ? Ti –(T1 ?T2)) ?(X3-i(t)=0)，则X(t)= Xi(t); 则称X是X1、X2的同步发射向量。 c a d b e 4 3 1 2 PN2 a b g 6 7 5 PN1 c a d b e 4 3 1 2 g 6 7 5 f f ?1 =acdeb ?2 =gabf ?1??2 ={gacdebf} a b c d e f g X1 =(1, 1, 1, 1, 1) X2 =(1, 1, 1, 1) X1?X2 =(1, 1, 1, 1, 1, 1, 1) 一、合法发射序列的判定 引理8.1. 设T 是一个字母表，且? T1 ,T2 ??T: T1 ? T2 =T，T1 ?T2??。对于??T*，令 ??T?Ti(?)= ?i, i=1,2。则??T1??(?1)= ??T2??(?2)，这里?= T1 ?T2 。 一、合法发射序列的判定 定理8.1. 设PNi=(Pi,Ti;Fi, M0i) (i=1,2) 是两个Petri网，PN= PN1 OT PN2 ， 且?= T1 ?T2 。若?i? L(PNi) ，则?1??2?L(PN)当且仅当??T1??(?1)= ?T2??(?2)。 一、合法发射序列的判定 定理8.2. 设PNi=(Pi,Ti;Fi, M0i) (i=1,2) 是两个Petri网，PN= PN1 OT PN2 ， 且?= T1 ?T2 。则?? L(PN) 当且仅当 ?T? Ti(?)= ?i? L(PNi) 。 一、合法发射序列的判定 一、合法发射序列的判定 一、合法发射序列的判定 c a d b e 4 3 1 2 PN2 a b g 6 7 5 PN1 f c a d b e 4 3 1 2 g 6 7 5 f PN 一、合法发射序列的判定 对于10个序列的算法Shufting_Test的测试结果 一、合法发射序列的判定 对于10个序列的算法Beloning_Test 的测试结果 二、合法发射向量的判定 设PN=(P,T;F, M0) 是一个Petri网， X 是|T|维非负整数向量， 问题三：X是PN的发射向量? 对于一般网类是NP-完全问题，仅对于可持续网、无冲突网和标识S-图（状态机网）是多项式可解的。 问题四：M是PN的可达标识？ 二、合法发射向量的判定 定义8.2. 设PNi=(Pi,Ti;Fi, M0i) (i=1,2,?,k) 是k个Petri网， ?i 是PNi的发射序列，Xi 是?i对应的发射向量， i=1,2,?,k。则记 PN1?i= PN1 OT PN2 OT ? OT PNi T1?i=T1?T2???Ti ?1?i= ?1??2 ????i X1?i = X1?X2 ? ? ?Xi 二、合法发射向量的判定 引理8.2.设PNi=(Pi,Ti;Fi, M0i) (i=1,2) 是两个Petri网， PN1?2= PN1 OT PN2 =(P,T;F, M0)，X是PN的|T|维非负整数向量，?T? Ti(X)=Xi，则X是PN的发射向量当且仅当 （1）Xi是PNi的发射向量； （2） ??T1? T