Petri网的符号ZBDD可达树分析技术.doc

《计算机学报》2009年12期，2009，32（12）
Petri网的符号ZBDD可达树分析技术*基金项目：国家自然科学基金资助项目（60563005，60243002）
作者简介：李凤英，女，辽宁人，博士研究生，主要从事符号模型检验、Petri网、符号调度技术的研究。E-mail: lfy@
古天龙，男，山西人，博士，教授，博导，主要从事形式化方法、符号计算、知识工程等的研究。
徐周波，女，浙江人，博士研究生，主要从事符号调度技术、符号模型检验、软件测试的研究。

李凤英1,2，古天龙2，徐周波1,2
（1.西安电子科技大学电子工程学院 西安 710071）
（2.桂林电子科技大学计算机学院 桂林 541004）
摘 要: Petri网是一种适合于并发系统建模、分析和控制的图形工具。可达树是Petri网分析的典型技术之一 ，它通过标识向量集合表征系统的状态空间，组合复杂性严重制约了该分析技术可处理系统问题的规模。零压缩决策图（ZBDD,zero-suppressed binary decision diagrams）是一种新型的数据结构，是表示和处理稀疏向量集合的一种有效技术。本文基于Petri网可达标识向量的稀疏特征，给出了Petri网分析的符号ZBDD技术，该技术通过对标识向量（状态）的布尔向量表示、可达标识向量（状态）的符号ZBDD生成，实现Petri网可达状态空间的高效符号操作和紧凑符号表示。实验表明，基于ZBDD的符号可达性分析算法能够有效处理较大规模Petri网问题。
关键词:Petri网；零压缩二叉决策图；可达树；状态空间

1 引言
Petri网是一种适于对具有异步、并发特征的离散事件系统进行模拟、分析、设计和控制的图形数学工具，已在制造系统、通信网络、数字电路综合与验证等领域得到了广泛应用[1,2,3]。Petri网分析是其应用中的一个关键环节，现有的Petri网分析方法主要有：可达树，状态方程以及结构化简等。可达树方法通过枚举方式穷尽生成Petri网的所有可达标识向量，并以树结构形式表示Petri网的可达状态空间，进而判定相应的活性、安全性、有界性、可达性等性质。对于有界Petri网，可达树方法是一种有效和实用的技术；对于无界Petri网，则需要采用可达树方法的扩展技术—可达图方法。该类方法的局限性在于：状态组合复杂性制约了可处理Petri网模型的规模；状态方程方法通过Petri网的关联矩阵建立标识向量和迁移引发向量之间的矩阵代数方程，基于矩阵代数方程求解Petri网的位置（迁移）不变量，根据不变量的特征来判定Petri网的一些性质。该方法适合于特殊结构Petri网，且随着Petri网模型规模的增大关联矩阵的维数也随之增大，对于大规模Petri网的处理也会带来不便；结构化简方法通过合并特殊的位置、迁移或结构，在保持一定性质不变的前提下来降低Petri网的规模。该方法要求所处理Petri网具有特定的结构，一般作为前两种方法的辅助技术使用。在Petri网模型中，由系统自身的并发特性和状态迁移的语义交织引起的状态组合复杂性，是Petri网分析技术中的一个瓶颈问题，严重制约了Petri网的应用[4]。
状态组合复杂性一直是计算机科学和应用人员关注的一个重要问题。减缓或者部分程度上避免状态组合复杂性问题的一种可行策略是：状态的符号或者隐式描述。有序二叉决策图（OBDD， Ordered Binary Decision Diagram）则是迄今为止最为有效的符号技术之一[5,6]。OBDD为布尔函数提供了一种有效和规范的描述方法，同时，布尔函数的所有复杂运算都可以基于OBDD数据结构得到极大地简化实现。尽管，OBDD技术并不能克服所有应用中的状态组合爆炸，但确实解决了许多无法解决的大规模状态应用问题（如，OBDD可处理具有1020状态的应用系统，而显式枚举所能处理的系统状态为103~106）。Pastor等建立了基于有序OBDD的Petri网符号分析方法，其实质是用OBDD表示Petri网标识集的特征函数，对Petri网的各种性能进行分析。该方法适用于有界Petri网，为大规模Petri网模型的分析探索了一条新的有效途径[7,8]。零压缩二叉决策图（ZBDD，Zero-Suppressed Binary Decision Diagrams）是OBDD的一种扩展形式，是描述和操作稀疏二进制向量的高效技术[9,10,11]。在ZBDD技术中，ZBDD的结点数取决于二进制向量集合中1的个数。在Petri网中，位置中的托肯（token）对应于标识向量中非零元素，并且Petri网的标识向量具有稀疏特征。鉴于此，我们建立了基于ZBDD的Petri网符号可达树分析技术，给出了Petri网的符号ZBDD表示、可达标识向量生成算法。算例仿真结果表明了符号ZBDD分析技术的有效性。

2 预备知识
2.1 Petri网
定义1 一个Petri网定义为六元组： PN = < P, T, F, W, K, M0> ，其中，
P = { p1, p2, …, pn }为位置集合；
T = { t1, t2, …, tm }为迁移集合（P∩T = Æ，P∪T≠Æ）；
F Í ( P ´ T )∪( T ´ P ) 为流关系（关系弧）；
W : F →Z+为流关系的权函数（Z+={1，2，3，…}），即关系弧的权重；
K: P →Z+∪{ω}，是位置上的容量函数（ω为无穷大数）；
M0: 为初始标识向量。一个标识向量是一个函数M：P →Z+∪{0}，表示位置中托肯的分布情况。
定义2 对于tT，pP，令•t={ p | (p , t )F}，t•={ p | (t , p )F}，•p= { t | (t , p )F}，p•={ t | (p , t )F}，则称•t(•p)为迁移t（位置p）的前集或输入集，t•(p•)为迁移t（位置p）的后集或输出集。
Petri网中位置是静态的，迁移是动态的。迁移的引发将使位置中托肯的分布发生变化，即产生新的标识。迁移t1, t2, …, tr的依次引发，将使标识依次发生变化M0, M1, …, Mr，相应地产生一引发序列σ = M0 t1 M1 t2 …tr Mr，或简记为σ = t1 t2 … tr ，并称标识M r是从M0引发σ可达的，记为M0[σ>Mr或MrÎ[M0>。
定义3 在一个具有初始标识M0的Petri网中，位置p ÎP为k-有界的（kÎZ+），当且仅当"MÎ[M0>：M（p）£k。一个Petri网为k-有界的，当且仅当Petri网中每一位置都是k-有界。Petri网是安全的，当且仅当它是1-有界的。显然，对于安全Petri网，对于"MÎ[M0>有：M(p) £1，且每条弧上的权重为1，所以安全Petri网可以简写为四元组：PN = < P, T, F, M0>。
定义4（迁移的使能条件） 如果"pΕt有M(p)³W(p, t),且"pÎt•有M(p)£K(p)-W(t, p)，则称迁移t是使能的或者具有引发权。
定义5（迁移的引发规则） 在标识M下，使能迁移t的引发将产生新的标识M'，记为M [t>M'：
M'(p)=M(p)- W(p, t)+W(t, p)。
2.2 零压缩二叉决策图
对于从{0，1}n到{0，1}的布尔函数f (x1, x2, …,xn)，若第i个分量xi 取值为0或1，则得到{0, 1}n-1到{0，1}的布尔函数f (x1, …, xi-1, 1, xi+1, …,xn) 或 f (x1, …, xi-1, 0, xi+1, …,xn)，简记为或。布尔函数和分别称为布尔函数f (x1, x2, …, xn)关于变量xi的1-分量（xi分量）和0-分量（xi¢分量）。
定义6 对于从{0，1}n到{0，1}的布尔函数f (x1, x2, …, xn) 和给定变量序p(即x1, x2, …, xn是有顺序的)，有序二叉决策图（OBDD）是一个无环有向图，它满足：①OBDD中结点分为根结点、终结点和内部结点三类；② 终结点仅有2个，分别标记为0和1，并表示布尔常量0和1；③根结点和内部结点具有四元组属性(pointer(u), var(u), low(u), high(u))，其中：pointer(u)表示结点u所对应的布尔函数（对于根结点u, pointer(u) = f (x1, x2, …, xn)）；var(u)表示结点u的标记变元（根结点u的标记变元为变量序p中的第一个变量）；low(u) 表示结点u的0分枝子结点，对应于该结点布尔函数pointer(u)中变元var(u) 取0值后的布尔函数；high(u) 表示结点u的1分枝子结点，对应于该结点布尔函数pointer(u)中变元var(u) 取1值后的布尔函数；④根结点和内部结点均具有两个输出分枝弧，将它们和各自的两个分枝子结点联系在一起。结点u和low(u) 的连接弧称为0-边，结点u和high(u) 的连接弧称为1-边，且满足：对于结点u, low(u) ¹ high(u)；对于var(u) = var(v)的不同结点u 和v，则low(u) ¹ low(v) 或者high(u) ¹ high(v)；⑤任一有向路径上，布尔函数f(x1, x2, …, xn)中的每个变元均以变量序π所规定的次序依次至多出现一次。
在图形表示中，用方框表示终结点，用圆圈表示其它结点，结点之间通过虚线或者实线连接。通常，假设连接弧的方向向下，0-边用虚线表示，1-边用实线表示。
零压缩二叉决策图（ZBDD）是一种特殊的OBDD，是日本学者Minato为了克服OBDD表示组合集合（有限集合A的组合集合是该集合的幂集2A的一个子集合）的不足提出的，进一步降低了组合集合表示的空间需求，从而更为有效地处理组合集合相关的问题[9,12]。
对于具有n个元素的集合A= {a1, ,…, an}，从A中不考虑次序地取出任意r个元素，其中0≤r ≤n，所得到的集合称为集合A中元素的一个组合。若集合A中的每个元素ai均对应一个布尔变量xi，则组合集合中的元素可以用一个n维布尔向量（x1, x2,…, xn）表示，当元素ai不包含在组合中时，对应布尔变量xi=0，否则xi=1。由此可见组合集合可以用一个n元布尔函数f(x1, x2,…, xn)表示。OBDD为布尔函数提供了紧凑规范的表示，在很多情况下OBDD表示可大大降低组合集合表示的空间需求，使表示组合集合所用的结点数远小于集合包含的元素个数，并且使集合上的操作时间与表示集合所用的结点数目成正比。但是，用OBDD表示组合集合仍然存在一些问题，即组合集合的OBDD表示依赖于布尔变量的个数，当布尔变量个数不同时，相同的组合集合会得到全然不同的OBDD。比如对于两个不同的布尔变量域{a,b,c}和{a,b,c,d}，要表示相同的组合集合{a, b}，就会有两种截然不同的OBDD表示，如图1(a)和(b)所示。这表明OBDD表示与布尔变量域的选取有关。
(b)
0
1
a
b
b
c
d
S{a,b,c,d}

1-边
0-边
0
1
a
b
b
c
(a)
S{a,b,c}

图1 组合集合的OBDD表示
在ZBDD中，通过采用不同的冗余结点删除规则，有效改善了表示组合集合的效率。这也正是ZBDD不同于OBDD之处。在OBDD中，采用的是S-删除规则：删除那些0分枝结点和1分枝结点相同的冗余结点，如图2（a）所示。在ZBDD中，采用的是pD-删除规则：删除1分枝结点为0终结点的结点，如图2（b）所示。使用了新的删除规则的ZBDD中，未出现变量的缺省就表示该变量取值为0。
1-边
0-边
0
1
a
b
b
S{a,b,c}
S{a,b,c,d}
x
f
f
0
(b) pD-删除规则
0
1
1
w
v
xi
w
(a) S-删除规则
0

图2 不同的删除规则 图3 组合集合的ZBDD表示
图3给出了不同的布尔变量域{a,b,c}和{a,b,c,d}下组合集合{a, b}的ZBDD表示。对于同一个组合集合，只有一种ZBDD表示，这是因为ZBDD表示与布尔变量域无关。由图3可见，ZBDD表示组合集合比OBDD更为紧凑，这得益于ZBDD所采用的pD-删除规则。从ZBDD的根结点到1-终结点的路径数正好跟组合集合的元素个数相等，每条路径对应一个组合，路径中结点的个数与组合中变量的个数相等。
ZBDD的基本操作有9个 An Intruduction to Zero-Suppressed Binary Decision Diagrams. http://www.ee.pdx.edu/~alan-mi/research.htm
，这里主要介绍其中3个，分别由一个基本函数实现，其中P和Q表示以ZBDD表示的集合，v表示输入变量（布尔变量域）：
Subset0(P，v)：返回P中不包含元素v的所有组合的集合；
Subset1(P，v)：返回P中包含元素v的所有组合的集合；
Change(P，v)：对P中的每个组合，若包含v，在该组合中删除v；若不包含v，在该组合中增加v。
对于变量集合V={v1,v2,……,vn}，Subset操作和Change操作可进行如下扩展：
Subset1(P,V)= Subset1 (Subset1 (……(Subset1 (P,v1),……),vn-1), vn)
Subset0(P,V)= Subset0 (Subset0 (……(Subset0 (P,v1),……),vn-1), vn)
Change (P, V)= Change (Change (……(Change (P,v1),……),vn-1), vn)
3 安全Petri网的符号分析
对于安全Petri网PN=(P, T, F, M 0)，设P={p0, p1,…, pm}，任一可达标识的特征函数都可以用位置集合的一个子集来表示，在子集中出现的位置，说明该位置包含了托肯。标识集（标识向量构成的集合）可以用一个关于P的组合集合表示。例如，图4给出了一个包含五个位置P={p0, p1, p2, p3, p4}的安全Petri网，用{p0p2}表示初始标识位置p0和p2含有托肯，位置p1、p3和p4不含有托肯的标识。空标识集用逻辑“0”表示，对应ZBDD的0-终结点，本文也用“logicZero”表示，标识全集(不一定与可达标识集相等)的特征函数用逻辑“1” 表示，对应ZBDD的1-终结点，本文也用“logicOne”表示。标识集之间的操作可以通过ZBDD提供的运算来完成。
p0
p1
z
p2
p3
p4
t0
t1
t2

图4 安全Petri网的例
Petri网的结构蕴含着一个局部状态改变集，可称之为迁移函数，迁移函数决定了Petri网的动态特性。对于安全Petri网PN=（P, T, F, M0），若用Et表示迁移t的使能标识集的特征函数，则
Et=
迁移ti和tj并发的使能标识集为：

在标识M下使能迁移t的迁移函数δt将每个属于Et的标识M变为新的标识M'，定义为：

考虑在一个标识集而不是一个标识的情形下引发迁移t的情况。这种情况下，标识集M1由于迁移t引发而变换成标识集M2。通常把迁移函数导出的这种求一个标识集下由于迁移t引发而得到的可达标识集的运算称作image运算，image运算可表达为：
M2=img(M1, t)={M2|$ M1ÎM1ÙEt, δt(M1)=M2}
ti和tj并发时，可表达为：

更多个迁移并发的情况可进行类似推广计算。
标识集M下一步能到达的标识集的计算可表达为：

标识集M的可达标识集可通过一个运用image运算的符号遍历算法求出。该算法在宽度优先搜索算法的基础上，引用贪婪链技术实现了求可达标识的集合计算，即每次计算都是求一个标识集的可达标识集，而不是只求某个标识的可达标识，因而极大地减少了生成Petri网的所有可达标识集的运算次数。图5给出了Petri网的符号遍历算法。
Traverse_Petri-net (PN=(P, T, F, W, M0))
{ Reached = From = {M0};
do{
for each t∈T do From = From + img(From, t);
New = From - Reached;
From = New;
Reached = Reached + New;
} while (New!= Æ)
return Reached; /* M0的可达标识集*/
}

图5 Petri网的符号遍历算法
以图4所示的安全Petri网为例，利用图5所示的Petri网符号遍历算法，用一次外部迭代和三次内部迭代就可得到所有可达标识（如图6（a）所示）。图6（b）为可达标识集的ZBDD表示，只用了9个结点。图6（c）为该可达标识集的OBDD表示，需要14个结点。

(b) ZBDD表示
0
1
P0
P1
P1
P2
P4
P3
P4
P2
1-边
0-边
(c) OBDD表示
1
0
P0
P1
P1
P2
P4
P3
P4
P2
P2
P2
P3
P4
P3
P4
P4

{p0p1}
t2
t1
t1
t0
{p1p2}
{p0p3}
{p2p3}
{p4 }
t0
(a) 可达树

图6 安全Petri网的符号ZBDD可达树分析

4 加权和有界Petri网的符号分析
这一节主要将Petri网的符号ZBDD表示和分析技术扩展到加权和有界Petri网。
4.1位置编码
一个最多包含k个托肯的位置可以由一个布尔变量集来表示，用它来为p中的k个托肯编码。使用二进制编码时，一个k-有界的位置需要个布尔变量，即。例如，在3-有界的Petri网中，需要两个布尔变量。对形如的自然数N，则：

以图7所示Petri网为例，位置p0、p1、p2和p3的界分别为3，2，2和6。因此位置p0、p1和p2需要两个变量编码，分别为，和，p3需要三个变量编码，即。该Petri网的初始标识的布尔特征函数为{}。
p0
p1
p2
p3
t0
t1
t2
2
2
2

图7 加权和有界Petri网

4.2迁移引发
这里主要讨论加权和有界Petri网的迁移函数和迁移关系的二进制编码问题。迁移t使能的标识集的特征函数（Et）写成如下形式：

在标识M下使能迁移t的迁移函数可写成如下形式：

使用二进制编码表示时，用一组布尔变量表示位置p中托肯的数量，用同样数量的布尔常量表示权重W(p, t)，关系M(p)³ W(p, t)可以用下面式子来描述：

其中，g是逻辑与操作；+是逻辑或操作；>是大于操作，a>b即表示。
由特征函数Et定义的使能迁移t的标识为：

在图7所示Petri网中，每个迁移的使能标识集为

对于任何使能迁移t的标识，迁移的引发必须从其输入位置中移走相应的托肯，并在输出位置中增加相应的托肯。
位置p中托肯的数量用布尔变量的向量来表示，必须要减去的托肯的数量用布尔常量的向量来表示时，迁移函数δt(M)与二进制向量表示的两个自然数的减法是等价的，可以由下面的表示：

其中，Å为异或操作；Bj（j=0,…,KP）为借位函数，定义为：

其中，º表示逻辑相等，aºb即表示。
另一方面，必须添加的托肯的数量可以由另一个布尔常量的向量表示，这时，迁移函数δt(M)与二进制向量表示的两个自然数的加法是等价的，可以由下面的等式表示：

其中，Cj为进位函数，定义为：

以上两种情况都必须选择合适的变量wj，其中wj表示自然数常量W的第j位：

综上所述，位置pi的第j个变量的迁移函数为：

所以，迁移函数的计算式为：

映像函数img扩展到有界和加权Petri网为：

在图5的Petri网符号遍历算法基础上，我们采用上式给出的映像函数img，就可以实施加权和有界Petri网的可达状态空间的生成。
5 实验结果及分析
为了检验Petri网符号ZBDD分析算法的性能，选两组例子进行实验。第一组为可以升级的例子，主要检验安全Petri网的符号ZBDD分析算法的性能。一个是典型的哲学家就餐问题，其中n是哲学家的人数，图8（a）给出了一个哲学家就餐问题的Petri网表示[8]，图中虚线箭头表示可以扩展为n个哲学家就餐问题。另一个是局域网的槽环协议，图8（b）所示的是一个结点的槽环协议的Petri网模型[8]，虚线表示可以扩展为n个结点的槽环协议。

（a）一个哲学家就餐问题 (b) 一个结点的槽环协议
Fi
F(i+1) mod n
eating
take left fork
Leave forks and table
idle
start eat
go to table
acki+1
…
…
…
…
…
…
freei-1
usedi
int ack
give free slot
put message in slot
acki
freei
usedi-1
other
go on
write
owner
take right fork

图8 Petri网模型的例
第二组实验选用柔性制造系统（FMS）中作业调度的Petri网模型，主要检验有界和加权Petri网的ZBDD分析算法的性能。假设一个FMS有3台机器，4种作业J1、J2、J3、J4，每个作业有4个过程，它们对机器的需求如表1所示。第1行第J1列的M1/M2表示作业J1的第一个过程可以由M1或M2进行加工。其中Petri网的建模借鉴了文献[13]所介绍的方法。
表1 作业对机器的需求

作业
过程ss
J1
J2
J3
J4
1
M1/M2
M1/M2
M1/M2/M3
M2/M3
2
M2
M3
M2/M3
M1/M3
3
M1/M3
M1/M2
M1/M3
M2/M3
4
M1/M2
M1/M3
M1/M2
M1/M2/M3
利用Colorado大学的CUDDCUDD: CU decision diagram package release2.3.1.http://vlsi.Colorado.edu/fabio/CUDD/cuddIntro.htm
软件包，用C语言进行编程，在运行平台Windows 2000、P4 1500MHz CPU、128MB RAM上，对上面例子进行了实验，实验结果如表2和表3。表2和表3中位置列表示Petri网模型中位置的个数，迁移列表示迁移的个数，变量是OBDD或ZBDD所用变量的个数，可达标识是可达标识的个数，可达结点是可达标识集的OBDD或ZBDD表示的结点数，最大结点是算法运行中所需OBDD或ZBDD结点数的最大值，迭代次数是遍历算法中需要迭代的次数，时间是算法运行的CPU时间，单位为秒。
表2 安全Petri网的实验结果

OBDD
ZBDD
名称
位置
迁移
可达标识
变量
最大结点
可达结点
迭代次数
时间
变量
最大结点
可达结点
迭代次数
时间
Phil_5
35
25
2.2×103
35
15712
189
2
0.06
35
5255
92
2
0.03
Phil_8
56
40
2.2×105
56
22288
279
2
0.44
56
17054
158
2
0.06
Phil_10
70
50
4.7×106
70
39748
403
2
0.89
70
28760
202
2
0.13
Phil_15
105
75
1.0×1010
105
68613
584
2
4.61
105
71465
312
2
0.28
Phil_20
140
100
2.2×1013
140
71663
744
2
17.02
140
133370
422
2
0.53
Slot_5
50
50
1.7×106
50
94325
540
8
1.81
50
120717
411
8
0.33
Slot_7
70
70
8.0×108
70
484231
1014
10
13.88
70
630168
791
10
1.48
Slot_9
90
90
3.8×1011
90
2242495
1632
12
247.21
90
2207140
1291
12
5.20

12

从表2所示实验结果的可达结点列可以看出，对于同样的可达标识集，ZBDD的大小是OBDD的一半或三分之一。比如phil_15中，1.0×1010个可达标识用OBDD表示需要584个结点，而用ZBDD表示只用312个结点。从时间列可以看出，用ZBDD比用OBDD要快，尤其对于大规模Petri网，效果更加明显。这就说明，基于ZBDD的符号分析算法可用于较大规模Petri网的可达树生成和分析。
表3 有界Petri网的实验结果

OBDD
ZBDD
名称
位置
迁移
可达标识
变量
最大结点
可达结点
迭代次数
时间
变量
最大结点
可达结点
迭代次数
时间
Job2_3_1
27
28
11
27
946
71
2
0.01
27
596
18
2
0.02
Job2_3_2
27
28
3.0×103
37
31527
462
4
1.11
37
16700
206
4
0.05
Job2_3_4
27
28
1.6×105
47
66546
813
6
58.23
47
120012
552
6
0.23
Job2_3_8
27
28
1.6×107
57
932859
1727
10
307.75
57
773129
1932
10
1.53
Job3_3_1
41
46
1.4×103
41
18409
322
3
0.88
41
8713
125
3
0.06
Job3_3_2
41
46
1.2×105
56
183012
936
4
40.42
56
77982
375
4
0.25
Job3_3_4
41
46
3.5×107
71
溢出

71
561454
949
6
1.16
Job3_3_8
41
46
4.5×1010
86
溢出

86
9946986
3050
11
20.69
Job4_3_1
55
64
1.3×104
55
59616
408
3
2.42
55
27325
199
3
0.11
Job4_3_2
55
64
3.9×106
75
溢出

75
196362
552
4
0.47
Job4_3_4
55
64
5.6×109
95
溢出

95
1477324
1361
6
3.16
表3中名称列的Jobi_j_k表示该FMS中有i个作业、j台机器、生产批量为k。从该表的可达结点列可以看出，有界Petri网的标识向量不象安全Petri网那样稀疏，所以可达标识的结点数相差不是很悬殊，但ZBDD的结点数还是要比OBDD的结点数少。从最大结点列可以看出，由于对迁移的使能函数做了改进，ZBDD算法在执行过程中所需的最大结点数大大减少。这样，对于较大规模的有界Petri网，ZBDD算法能在合理时间内求得其相应的可达标识集。

6 结束语
零压缩二叉决策图（ZBDD）能有效地表示组合集合，是求解组合集合相关问题的有效工具。根据Petri网状态向量稀疏的特点，本文给出了基于ZBDD的Petri网的标识向量表示、使能迁移计算、可达标识向量生成的符号方法，使得Petri网的动态行为的计算能够在基于ZBDD数据结构的紧凑表示和高效操作下得到实施。在Petri网分析的时间和空间效率上，符号ZBDD技术都体现出了较之于符号OBDD技术具有明显的优势。
Petri网的可达状态空间是Petri网应用于系统模拟、分析、控制及其调度等的核心和基础。我们可以在生成Petri网可达状态空间的过程中，通过符号ZBDD的操作函数方便的实施Petri网的安全性、活性、有界性、可达性等性质判定。同时，我们也可以基于Petri网可达状态空间的紧凑符号ZBDD描述，开展Petri网模型下系统的控制策略、调度方案等的设计，这是我们正在开展的研究课题。此外，基于ZBDD描述的Petri网性质证明、ZBDD的变量序问题等也将是进一步开展的研究工作。

参考文献
[1] Murata T. Petri nets: properties, analysis and applications// Proceedings of IEEE, 1989, 77 (4): 541-574
[2] Gu Tianlong, Parisa A Bahri. A survey of Petri-net applications in batch processes. Computers in Industry, 2002, 47 (1): 99-111
[3] LUO Jun-zhou, SHEN Jun, GU Guan-qun. From Petri Nets to Formal Description Techniques and Protocol Engineering. Journal of Software, 2000, 11 (5): 606-615 (in Chinese)
(罗军舟, 沈俊, 顾冠群. 从Petri网到形式描述技术和协议工程. 软件学报, 2000, 11 (5): 606-615)
[4] JIANG Yi-xin, LIN Chuang, QU Yang, YIN Hao. Research on Model-Checking Based on Petri Nets.
Journal of Software, 2004, 15 (9): 1265-1276 (in Chinese)
(蒋屹新, 林闯, 曲扬, 尹浩. 基于Petri网的模型检测研究. 软件学报, 2004, 15 (9): 1265-1276)
[5] Bryant R E. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, 1986, 35 (8):677-691
[6] Bryant R E. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams. ACM Coputing Surveys, 1992, 24 (3): 293-318
[7] Pastor E, Cortadella J. Efficient Encoding Schemes for Symbolic Analysis of Petri Nets// Proceedings of the Conference on Design, Automation and Test in Europe, Paris, March 1998, 790-795
[8] Pastor E, Cortadella J. Symbolic Analysis of Bounded Petri Nets, IEEE Transactions on Computers, 2001, 50 (5): 432-448
[9] S Minato. Zero-suppressed BDDs for Set Manipulation in Combinatorial Problems// Proceedings of DAC, 1993. 272-277.
[10] Minato S. Zero-suppressed BDDs and Their Applications. International Journal on Software Tools for Technology Transfer, 2001, 3 (2): 156-170
[11] Yoneda T, Hatori H, Takahara A and Minato S. BDDs vs. Zero-Suppressed BDDs: For CTL Symbolic Model Checking of Petri Nets// Proceedings of International Conference, LNCS 1166, 1996, 435-449
[12] Tomisaka M, Yoneda T. Partial Order Reduction in Symbolic State Space Traversal Using ZBDDs. IEICE Trans. on Information and Systems, 1999, E00-D (1): 704-711
[13] Jiao Li, Lu Wei-ming. Synthesis and Property-Preservation of Petri Net System Based on Shared Places. Chinese Journal of Computer, 2007, 30 (3): 352-360 (in Chinese)
(焦莉, 陆维明. 基于共享位置的Petri网综合与保性. 计算机学报, 2007, 30 (3): 352-360)

Symbolic Reachability Analysis of Petri Nets Using ZBDDs
LI Feng-Ying1,2,GU Tian-Long2,XU Zhou-Bo1,2
(1.Electronic Engineering School, Xidian University, Xi′an, 710071)
(2.School of Computer Science, Guilin University