下载文档原格式
第七章 Petri 网顺序序列的测试与判定7.1 引言Petri 网合法发射序列的判定问题是网论中一重要研究课题，它是许多网论问题的直接基础，如：时延Petri 网的经典的调度问题 [1-3] 和循环调度问题 [12, 14, 16]都能被归结为这类判定问题；Petri 网极小初始标识的配置问题 [8-10,13,15] 也能被转化为这类判定问题；还有众所周知的Petri 网可达性问题 [4-6] 更是以这类判定问题为基础。
在 [8, 9, 11] 中，Petri 网合法发射序列的判定问题被深入研究，多项式判定算法被给出，时间复杂性被分析。
研究获知，这类判定问题对于一般Petri 网，甚至对于某些自由选择网都是NP-完全问题 [11]。
而仅仅对于几个简单网类，如：坚持网、无冲突网和状态机网，这类判定问题才是多项式可解的。
文 [16] 考虑了Petri 网合法发射序列的判定问题的一个近似问题，从而给出近似问题的一个多项时间算法。
由此足见，Petri 网合法发射序列的判定问题一般而言是一类困难问题。
另一方面，这类问题又是网论中的十分重要而基础的问题。
因此，这项工作的每一点推进都是非常重要的。
文[21]研究了坚持网、无冲突网和状态机网的同步合成网类，获得了这一网类合法发射序列判定问题的多项式判定算法，从而对以往的工作有了重要推进。
在这一章中，我们将着重介绍Petri 网的合法发射序列的判定问题和合成过程中序列测试等问题的有关算法。
7.2 发射序列测试为了验证系统的功能，测试系统功能的保持性，就是要测试系统的发射序列是否被保持到目标系统。
复杂系统的发射序列的测试是一个困难问题，分解复杂系统和分布测试集成求解的方法是解决此问题的一种有效途径。
下面具体来讨论这种方法。
定理 7.1 设,2,1),,;,(0==i M F T P PN i i i i i 是两个Petri 网, 21PN PN PN T O =, 且21T T ⋂=∆。
Petri 网的基本理论1. 基本定义定义1.1 一个Petri 网（结构）N 是一个四元组),,,(W F T P ，P 和T 分别成为库所和变迁的集合，P 和T 非空、有限且不相交。
即φφφ≠≠T ,≠T P P ,。
φ≠⨯⨯⊆)()(P T T P F 称为流关系或有向弧的集合。
N →⨯⨯)()(:P T T P W 是一个映射，该映射为每一条弧分配一个权值，即若,F f ∈0)(>f W 若F f ∉，0)(=f W 。
称W 为Petri 网N 的权函数。
从图论上讲，Petri 网是一种双枝有向图，库所和变迁成为Petri 网的节点。
用图形表示Petri 网时，库所用圆圈表示，变迁用矩形或杠表示。
库所和变迁之间用有向弧连接，同一类型的节点间不能用有向弧连接。
定义1.2 若1)(,=∈∀f W F f ，Petri 网),,,(W F T P N =成为普通网。
否则N 称为一般网。
一个普通网可记作),,(F T P N =。
定义1.3 若1),(,),(=∈∀t p W F t p ，Petri 网称为PT-普通网。
定义1.4 Petri 网),,,(W F T P N =的标识M 是一个从P 到N 的映射。
),(0M N 称为网系统或标识网，0M 称为N 的初始标识。
在不引起混淆的情况下，简单称),(0M N 为Petri 网，),(0M N 有时也写成),,,,(0M W F T P 。
库所中的标识用称之为托肯的小黑点表示。
当托肯数较多时直接用数字表示。
定义1.5 令P p ∈是Petri 网),,,(W F T P N =的库所。
当且仅当0)(>p M 时称p 在M 下是被标记的。
当且仅当D 中至少有一个库所被标记时，称库所集P D ⊆在M 下是被标记的。
称∑∈=D p p M D M )()(为库所子集D 在M 下的托肯总和。
定义 1.6 令T P x ∈是Petri 网),,,(W F T P N =的节点。
1.一个经典的Petri网由四元组（库所，变迁，输入函数，输出函数）组成。
2.如果一个变迁的每个输入库所（input place）都拥有托肯，该变迁即为被允许(enable)。
一个变迁被允许时，变迁将发生(fire)，输入库所(input place)的托肯被消耗，同时为输出库所(output place)产生托肯。
3.高级模型：为了解决经典Petri网中的问题，研究出了高级Petri网，在以下方面进行了扩展：o 令牌着色一个令牌通常代表具有各种属性的对象，因此令牌拥有值（颜色）代表由令牌建模的对象的具体特征，如一个令牌代表一个工人（张三，28岁，经验3级）。
o 时间为了进行分析，我们需要建模期间，延迟等，因此每一个令牌拥有一个时间戳，变迁决定生产出的令牌的延迟。
（这类Petri网模型规定每个变迁都具有有限的引发时延，其触发规则被修改为:每一个触发变迁都有一个时延过程;一个变迁一旦使能必须立即触发。
）o 层次化构造一个复杂性与数据流图相当的Petri网的机制。
子网是由库所，变迁和子网构成的网络。
o 时序增加时序逻辑的定义，更好的描述行为过程4.两个库所或变迁之间不允许有弧5.有两个变迁都被允许的可能，但是一次只能发生一个变迁6.Petri网络是静态的7.Petri网的状态由托肯在库所的分布决定8.两个变迁争夺一个托肯的情形被称之为冲突9.多个弧连接两个节点的情况。
在输入库所和变迁之间的弧的个数决定了该变迁变为被允许需要的令牌的个数。
弧的个数决定了消耗/产生的令牌的个数10.petri网基本概念：Petri网是一种用有向图及称为初始标识的初始状态表示的特殊的系统模型其中有向图由库所变迁以及从库所到变迁或者从变迁到库所的有向弧组成，称为Petri网结结构。
标识是一个m维数组(m为库所个数)，它的一元素对应一库所，取值为非负整数。
标识代表系统的状态。
11.不同类型的资源相应地，变迁的发生就可能不只是简单地复制和传递令牌，而是要对从输入库所取来的令牌经过加工，变成新颜色的令牌后再传递给输出库所这就是有色Petri网的两个特别之处:令牌是有颜色的，变迁的发生可以改变令牌的颜色。
