petri网顺序序列的测试与判定

《petri网顺序序列的测试与判定》由会员分享，可在线阅读，更多相关《petri网顺序序列的测试与判定（29页珍藏版）》请在金锄头文库上搜索。

1、第七章第七章 Petri 网顺序序列的测试与判定网顺序序列的测试与判定7.1 引言引言Petri 网合法发射序列的判定问题是网论中一重要研究课题，它是许多网论问题的直接基础，如：时延 Petri 网的经典的调度问题 1-3 和循环调度问题 12, 14, 16都能被归结为这类判定问题；Petri 网极小初始标识的配置问题 8-10,13,15 也能被转化为这类判定问题；还有众所周知的 Petri 网可达性问题 4-6 更是以这类判定问题为基础。在 8, 9, 11 中，Petri 网合法发射序列的判定问题被深入研究，多项式判定算法被给出，时间复杂性被分析。研究获知，这类判定问题对于一般 Pet

2、ri 网，甚至对于某些自由选择网都是 NP-完全问题完全问题 11。而仅仅对于几个简单网类，如：坚持网、无冲突网和状态机网，这类判定问题才是多项式可解的。文 16 考虑了 Petri 网合法发射序列的判定问题的一个近似问题，从而给出近似问题的一个多项时间算法。由此足见，Petri 网合法发射序列的判定问题一般而言是一类困难问题。另一方面，这类问题又是网论中的十分重要而基础的问题。因此，这项工作的每一点推进都是非常重要的。文21研究了坚持网、无冲突网和状态机网的同步合成网类，获得了这一网类合法发射序列判定问题的多项式判定算法，从而对以往的工作有了重要推进。在这一章中，我们将着重介绍 Petri

3、网的合法发射序列的判定问题和合成过程中序列测试等问题的有关算法。7.2 发射序列测试发射序列测试为了验证系统的功能，测试系统功能的保持性，就是要测试系统的发射序列是否被保持到目标系统。复杂系统的发射序列的测试是一个困难问题，分解复杂系统和分布测试集成求解的方法是解决此问题的一种有效途径。下面具体来讨论这种方法。定理定理 7.1 设是两个 Petri 网, , 且 , 2, 1),;,(0iMFTPPNiiiii21PNPNPNT。若 ，则 当且仅当 21TT 2, 1),(iPNLiiTT1212()()21。)(PNL证明证明 因为 ，则2, 1),(iPNLii当且仅当 : ；TT1212

4、()()212, 1),()(iPNLiTTi当且仅当 ； 2, 1),)(1 21 iPNLiTTi当且仅当 。) )() )(21 11 2121PNLPNLTTTT 从定理 3.4，我们有。)(21PNL定理定理 7.2 设是两个 Petri 网, , 且, 2, 1),;,(0iMFTPPNiiiii21PNPNPNT。则 当且仅当 。21TT 2, 1),()(iPNLiTTii)(PNL证明证明 根据引理 6.1、定理 7.1，易证本结论是正确的。基于定理 7.1 和定理 7.2 , 我们可以得到下面的测试算法。 算法算法 7.1 Shufting_Test输入输入 qjiPNLi

5、ij., 2, 1; 2, 1),(输出输出 / 若 则，否则 b jjq( ), ,., 1 2)(2121PNPNLTjjb j( ) 1。/b j( ) 0(1) begin(2) for to doj 1q(3) if thenTjTj1212()()(4) b j( ) 1(5) else b j( ) 0(6)endif(7) endfor(8) endbegin.算法算法 7.2 Beloning_Test输入输入 2, 1,;., 2, 1,iPNqjij输出输出 / 若 则 ，否则 。/b jjq( ), ,., 1 2)(21PNPNLTjb j( ) 1b j( ) 0(

6、1)begin(2) 基于可达图生成算法，产生的可达图; 2, 1,iPNi)(iPNRMG(3) for to doj 1q(4) if then2, 1),()(iPNLiTTi(5) b j( ) 1(6) else b j( ) 0(7) endif(8) endfor(9) endbegin.显然，算法 Shufting_Test 只需要一些投影操作和比较操作，而算法 Beloning_Test 只需要一些投影操作和测试子系统的发射序列。因此，测试过程的复杂性被化简。例例 7.1 在图 6.1 的 Petri 网中，有一组 序列 。现在要测iPNijjq, ,., ; 1 2i 1

7、2,试是否为真，这里。)(21PNLjj21PNPNPNT利用先前描述的算法 Shufting_Test，测试结果如下面的两个表 (当 )。q 10表表 7.1：对于 10 个序列的算法 Shufting_Test 的测试结果=? ?1j2 j)(11jT)(22jT)(11jT)(22jT)(21PNLjjacdeba gabfa aba aba = bebeac bfab bba bab no acdebe bfaga ab baa no beacde bfag ba ba = beacde bfaga ba baa no acdeb gabf ab ab = acdeb gabfag a

8、b aba no beacde bfag baa ba no beac bfag ba ba = bebea bfabf bba bab no 例例 7.2 图 6.1 中的 Petri 网有一组序列，现在要测试PNqjj., 2, 1,。 利用前面描述的算法 Beloning_Test，其测试结果如下面的表qjPNLj., 2, 1?)(7.2 中显示 ( 这里 ) 。q 10表表 7.2: 对于 10 个序列的算法 Beloning_Test 的测试结果? ? ?jTTj1()TTj2()()(11PNLjTT)()(22PNLjTT)(PNLjabefabef abeabe abfabf

9、 befacdea beacdea bfaa gacgdeacde acdeacde gaga gacbed acbed gab bfdecabc bdecabc bfab bfeacdea beacdea bfaa fgcdeac cdeac fga befagcdeac beacdeac bfaga gacgde acde gag gacdega acdea gaga 7.3 合法发射序列的判定合法发射序列的判定Petri 网合法发射序列的判定问题可以被形式化地描述如下：给定一个 Petri 网和一个非负整数的维向量，现在要判定是,;,(FTPPN M0)TX否存在的一个合法发射序列（即：），使得是