第5章 一些 Petri 网子类的动态性质分析和判定

Petri 网的动态性质中，比较重要的有可达性、有界性（包括安全性）、活性和公平性等。其中对可达性和有界性，已经有算法可以判定；而对活性和公平性，虽然可以通过定义 Petri 网的语义所用是图灵机，从而判定其不可判定性，但对某些特定类型的 Petri 网，还是可以判定的。第 4.2 节列举了一些重要的 Petri 网子类，并分析了它们的某些性质。本章将进一步分析这些 Petri 网子类的动态性质，并给出判定算法。

首先讨论的是有界性。对于任意一个标识 $M_0$，若 Petri 网 $N$ 是 $k$-有界的，则对任意标识 $M$，$M$ 从 $M_0$ 可达时，$M$ 中每个库所的托肯数不超过 $k$。若 $k=1$，则称 $N$ 是安全的。显然，若 Petri 网 $N$ 是有界的，则其所有库所的托肯数必定有上界。因此，有界性是可达性分析的一个重要方面。

其次讨论活性。对于任意一个变迁 $t$，若存在一个标识 $M$ 从 $M_0$ 可达，使得 $t$ 在 $M$ 中是激发的，则称变迁 $t$ 是活的。若 $t$ 对任意 $M_0$ 都是活的，则称 $t$ 是绝对活的。活性分析的目的是为了判定系统是否存在死锁。

最后讨论公平性。对于任意一个变迁 $t$，若 $t$ 在每一个循环中都能激发，则称 $t$ 是公平的。公平性分析的目的是为了判定系统是否存在饥饿现象。

本章的目的是通过分析一些 Petri 网子类的活性和可达性的判定方法，使得 Petri 网的动态性质分析更加简便。

5.1 标识 $S$-图

定义 5.1

网 $N=(S,T;F)$ 称为一个 $S$-图当且仅当
$$\forall t\in T:{|}^{\bullet }t|=|t^{\bullet }|=1\text{\hspace{1em}(5.1)}$$
如果 $N$ 是一个 $S$-图，$M$ 为 $N$ 的一个标识，则称 $(N,M)$ 为标识 $S$-图。□

对于每个变迁他的前后集只有一个库所所以称它为S-图

一个 $S$-图 $N=(S,T;F)$ 可以简化表示成一个有向图
$$SG=(S,E)\text{\hspace{1em}(5.2)}$$
其中 $SG$ 的结点集 $S$ 就是网 $N$ 的库所集，图 $SG$ 的有向边集 $E$ 包含 e k = ( s i , s j ) e_k = (s_i, s_j) ek​=(s