（计算机软件与理论专业论文）petri网结构理论研究.pdf

西华大学硕- 上学位论文 申明 本人申明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此申明。 作者 导师 讶础年幻3 日 d 年月 日 l2 钟6 尸 西华大学硕士学位论文 p e t r i 网结构理论研究 计算机软件与理论专业 研究生杨博指导教师宋文 摘要 p e t r i 网是建模和分析的工具，它的主要特性包括：并行，不确定性，异步 和分步描述能力和分析能力。它既有直观的图形表示，又有深刻的数学内涵和 基础。 p e t r i 网的结构理论的思想是以某种特定结构比如s i p h o n ( s i p h o n 是这样一 些库所的集合：关联的流入变迁，一定也是关联的流出变迁，所以一旦s i p h o n 不被标识，将永远不被标识，这一特征对于网的活性，弱活性的描述极其深刻) 、 不变量和子网覆盖，通过这些结构上t o k e n 的分布特征研究网的动态行为。 本人的工作是结构理论下的研究。利用结构性分析理论、化简技术、不变 技术，对p e t r i 网的主要行为特征进行了较为深入细致的研究，得到一些新的结 果： p e t r i 网中，混惑会给系统分析和系统控制带来麻烦，有混惑的系统不是好 系统，有混惑的模型不是好模型。文中针对混惑的特质进行了研究，在已知的 3 种结构混惑( 增混惑、减混惑、不增不减混惑) 的基础上，证明了不增不减混惑 是增混惑和减混惑的复合，这使得在解决混惑的检测与消除的时候，进一步减 小问题的规模，并在随后的研究分析中得到了混惑的充要条件，同时借助带抑 制弧的p e t r i 子网构造了混惑的消除器，并利用可达图对构建的混惑消除器进行 分析，证明了它是可行的。 现在流行的分析技术( s i p h o n 与陷阱，s i p h o n 与不变量，覆盖技术等) 都面临 随着p e t r i 网规模的扩大而随指数阶增长。p e t r i 在1 9 8 6 年的“f o r g o t t e nt o p i c s 两华大学硕士学位论文 o f n e tt h e o r y ”中提出了信息流的概念。用信息流替代原来的结构，用信息流 的构造规则的p e t r i 网表示来构造p e t r i 网，达到避开状态空间爆炸问题的目的。 以此目的，本文在基本网系统和c e 系统这一级别上，构造出了信息流运算的 一个最小完备集 只，q 的p e t r i 网表示。构造的p e t r i 网简洁而准确的刻画了信 息流运算与流动的特点，并能根据所构造的p e t r i 网来体现信息流的复合运算。 关键字：p e t r i 网、结构分析技术、动态行为、混惑、信息流 2 s t r u c t u r a lt h e o r yr e s e a r c h e sb a s e do np e t r in e t c o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rd e g r e ec a n d i d a t ey a n gb o s u p e r v i s o rs o n gw e n a b s t r a c t p e t r in e t sw e r et h em o d e l i n ga n da n a l y z i n gt o o lo fn e t s i t sm a i nc h a r a c t e r i s t i c i n c l u d e dt h ef a l l o w i n gi t e m s ：p a r a l l e l i s m , i n d e f i n a b i l i t y , a s y n c h r o n i s m , s t e p b y - s t e p d e s c r i b e da b i l i t ya n da n a l y z i n ga b i l i t y i tc o u l db ee x p r e s s e db yf i g u r e sd i r e c t l y ；i t a l s oh a dt h ep r o f o u n dc o n n o t a t i o no fm a t h e m a t i c sa n dt h ef o u n d a t i o n t h es t r u c t u r a lt h e o r yr e s e a r c h e so fp e t r in e t sw e r em a i nt h a ti n v e s t i g a t i n g t h ed i s t r i b u t i o na n dd y n a m i cb e h a v i o ro ft o k e n0 1 1s o m ee s p e c i a ls t r u c t u r es u c ha s m v a r l a n t ，s u b n e to v e r c a s t ，s i p h o n ( s i p h o nw a st h ec o m p o u n do fs p a c e s ：c o r r e l a t i v e i n f l o wt r a n s i t i o nm u s tb ec o r r e l a t i v eo u t f l o wt r a n s i t i o nt o o ，s oo n c es i p h o nw a sn o t b em a r k e d ，i tw o u l dn e v e rb em a r k e da g a i n t h el i v e n e s sa n df e e b l el i v e n e s so f n e t s w e r ed e s c r i b e dq u i t ep r o f o u n d l ya b o u tt h i sk i n do f c h a r a c t e r ) t h ep u r p o s eo ft h i st h e s i sw a sar e s e a r c hi ns t r u c t u r a lt h e o r i e so f p e t r in e t s t h e m a i nc o n t e n to ft h i sr e s e a r c hw a st od oa d e e p e rr e s e a r c ha b o u tt h em a i nb e h a v i o r c h a r a c t e r i s t i c so fp e t r in e t s b yu s i n gc o n s t i t u t i v ea n a l y s i s t h e o r y , s i m p l i f i e d t e c h n o l o g ya n di n v a r i a b l et e c h n o l o g ya n dt og e ts o m en e wr e s u l t s t h e s er e s u i t sa s f o l l o w s i np e t r in e t s ，c o n f u s i o nc o u l d b r i n gs o m et r o u b l ef o rs y s t e ma n a l y s i sa n d s y s t e mc o n t r 0 1 t h es y s t e mo rm o d e lw i t hc o n f u s i o nw a sn o t q u i t eg o o d t h i st h e s i s i n c l u d e dr e s e a r c h e sa b o u t c o n f u s i o n b a s i co nt h r e e a l r e a d yk n o w nc o n m s i o n 【i n c r e a s i n g ，d e c r e a s i n ga n dn o n - i n c r e a s i n ga n dn o n d e c r e a s i n g c o n f u s i o n ) t h i s t h e s i sh a dp r o v e dt h a tn o n - i n c r e a s i n gn o n d e c r e a s i n gc o n f u s i o nw a st h e c o m p o u n d o fn o n i n c r e a s i n ga n d n o r l d e c r e a s i n g c o n f u s i o n b e c a u s eo ft h i s w h e nt h e 西华大学硕士学位论文 e l i m i n a t i o na n dd e t e c t i o no fc o n f u s i o nw e r gb e i n gs o l v e d ，t h es c a l eo fp r o b l e m s w o u l dd e c r e a s e a tt h es a m et i m e ，t h e n e c e s s a r ya n ds u f f i c i e n tc o n d i t i o n o f c o n f u s i o nw e r eg o t t e nf i o mr e s e a r c ha n a l y s i sa f t e r , a n dc o n f u s i o ne l i m i n a t o rc r e a t e d b yu s i n gt h ep e t r is u b n e t sw i t hi n h i b i t o ra r c ，a n di ta l s op r o v e dt h a ta n a l y z i n gt h e c o n s t r u c t e dc o n f u s i o ne l i m i n a t o rw a sf e a s i b l eb yu s i n gr e a c h a b i l i t yg r a p h s c u r r e n ta n a l y z i n gt e c h n o l o g y ( s i p h o na n dt r a p s ，s i p h o na n di n v a r i a n t ，o v e r c a s t t e c h n o l o g ya n ds oo n ) h a dt o f a c et h ep r o b l e mt h a te x p o n e n t i a lo r d e ri n c r e a s e d a l o n gw i t he x t e n d i n gt h es c a l eo fp e t r i n e t s p e t r ih a dp r o p o s e dt h ec o n c e p to f i n f o r m a t i o nf l o w si n “f o r g o t t e nt o p i c s o fn e tt h e o r y ”i n19 8 6 i n s t e a do ft h e o r i g i n a ls t r u c t u r e ，t h ee x p r e s s i o no fp e t r in e tw h i c hw a sc o n s t r u c t e db yu s i n gt h e s t r u c t u r a lp r i n c i p l e so f i n f o r m a t i o nf l o w sc o n s t r u c t e dp e t r in e tf o rt h ep u r p o s eo f e s c a p i n gt h ep r o b l e mo fs p a c e se x p l o s i o n f o rt h i sp u r p o s e ，b a s i c o nb a s i cn e t s y s t e ma n dc es y s t e m , t h i st h e s i sh a dc o n s t r u c t e dt h ee x p r e s s i o no f p e t r in e to fa m i n i m u mc o m p l e t es e t 日，q ) o fs t e a mo p e r a t i o n t h ec o n s t r u c t i n gp e t r in e t d e s c r i b e dt h ef e a t u r e so fi n f o r m a t i o ns t r e a mo p e r a t i o na n df l o w ss i m p l ya n d a c c u r a t e l y a n dt h ec o m p o u n do p e r a t i o no fi n f o r m a t i o nf l o w sw a sr e f l e c t e db yt h e c o n s t r u c t i n gp e t r in e t k e y w o r d s ：p e t r in e t s ，s t r u c t u r a la n a l y z i n gt e c h n o l o g y , d y n a m i cb e h a v i o l c o n f u s i o n ，i n f o r m a t i o nf l o w s 4 两华大学硕上学位论文 第一章综述 1 1p e t r i 网的理论的发展与应用 1 9 6 2 年由德国的c a r la d a mp e t r i 在他的博士论文“k o m m u n i k a t i o nm i t a u t o m a t e n ( 用自动机通讯) 中提出了p e t r i 网的概念。p e t r i 阐述了一台计算机 中的两个异步分支间的通讯理论基础。并特别注意到事件之间因果关系的描述。 他的论文是p e t r i 网理论研究发展的奠基石。2 0 世纪7 0 年代初，p e t r i 网的概念 和思想方法受到欧美学者的广泛关注。对p e t r i 网的各种性质的研究，以及把 p e t r i 网运用于各种实际的系统的建模和性质分析的论文和研究报告开始大量涌 现。经过4 0 多年的发展不仅p e t r i 网理论本身已经成为一门系统的、独立的学 科分支，而且p e t r i 网在计算机科学技术( 如操作系统、并行编译、网络协议、 软件工程、形式语义、人工智能等) ，机械设计与制造( 如柔性制造系统) ，以 及其他许多科学技术领域，都得到了广泛的应用。时至今日，p e t r i 网的应用和 研究大大地扩展了，并形成了一个专致于p e t r i 网的学术团体。其理论研究工作 已经沿着两个方向发展：其纵向发展为：条件事件( c e ) 网t 2 1 ，位置变迁( p t ) 网【3 j ，高级网( h l n ，包括谓词变迁网【4 】，有色网【5 ，6 】等) 。横向发展为：无参数 网到时间p e t r i 网 7 】，随机p e t r i 网【8 】，自然数标记个数到概率标记个数掣9 , 1 0 。 p e t r i 网是一种可用图形表示的组合模型，具有直观、易懂的优点，对描述 和分析并发现象有独到之处。它是一种适用于多种系统的图形化、数学化建模 工具，为描述和研究具有并行、异步、分布式和随机性等特征的信息加工系统 提供了强有力的手段。作为一种图形化工具，可以把p e t r i 网看作与数据流图相 似的通讯辅助方法；作为一种数学化工具，它可以建立状态方程、代数方程和 其他描述系统行为的数学模型。经过4 0 多年的发展，它己成为描述物理世界的 异步并发现象并揭示其可计算规律的重要理论和成熟模型。它既为理论工作者 也为工程师们所广泛使用。它可作为不同学科领域工作者之间的通信媒介，便 于人们进行交流和理解。 利用p e t r i 网模型可以研究两类特性：依赖于初始状态和独立于初始状态的 西华大学硕士学位论文 特性【l 卜1 4 】。前者是指状态行为特性，后者是指状态结构特性。p e t r i 网可以分析 的状态行为特征有可达性、有界性、活性、活性单调性、家态( 可逆性) 、包容 性和持续性等【l 孓1 7 j 。一般情况下，p e t r i 网中变迁发生条件满足局部化公理，不 用表示系统中数据值或属性的具体变化或运算。在大型和复杂的系统模型应用 中，p e t r i 网的模型状态空间的规模将随着实际系统规模的扩大而呈指数增长。 因此，在实际应用中，常常不仅需要根据特定的应用环境对网模型加以限制、 修改或扩充，而且需要对p e t r i 网模型进行化简处理或结构分析等【l8 。3 0 j 。 1 2 p e t r i 网分析技术概述 相对于覆盖技术( 基于状态空间的验证方法) 所面临的状态空间爆炸问题， 结构理论同样面临类似的问题，但是对于一些子类的动态行为的分析，结构理 论的分析能力是较强的( 比如对于自由选择网，清华大学林闯教授以基于随机 p e t r i 网研究网络协议问题，他对具有自由选择网结构的随机p e t r i 网做了较深 入的研究，得到了一些较好的结果) 。 结构理论的思想是以某种特定结构比如s i p h o n 、不变量和子网覆盖，通过 这些结构上t o k e n 的分布特征研究网的动态行为。s i p h o n 是这样一些库所的集 合：关联的流入变迁，一定也是关联的流出变迁，所以一旦s i p h o n 不被标识， 将永远不被标识，这一特征对于网的活性，弱活性的描述极其深刻。当某个 s i p h o n 不被标识后，它的输出变迁将永远不会发生，因此不能满足网的活性； 当所有极小s i p h o n 不被标识，那么整个网完全死锁；当s i p h o n 中至少有一个极 小陷阱能够被标识，比如一个极小死锁中至少包含着一个m 0 标识的陷阱，由 于陷阱具有特征：一个陷阱一旦被标识将永远被标识，于是它的输出变迁是活 的，网就不会死锁，具有弱活性。前面的描述称为s h o 条件( h u l t 、b e s t 、陆维 明、焦莉就是利用这一特征研究了f c ，a c 网的活性、有界性，得到了一些较 好的结果【3 卜硎) 。如果这个极小死锁与某一个正s 不变的交集不为空集，且此 交集在m 0 被标识，系统也不会死锁。西安电子科大李志武教授关于柔性制造 无死锁性控制就是基于这样的思想。但是网人已经证明随着网的规模的增长， 西华大学硕士学位论文 极小s i p h o n 的个数成指数增长，因此，在一般网上，无论前者还是后者，都无 法回避n p 问题，欲在一般网上利用结构分析技术讨论网的动态行为，只能是 理论性的，不具有太多的实际意义，因为无法回避“s i p h o n 个数成指数增长”， 似乎一条不可逾越的鸿沟出现在人们的面前。当然结构分析技术对于特殊的子 类还是比较有用的，i ：t 女if c 。另外，关于“s i p h o n 个数成指数增长”是n p 的， 但是是否为n p c 的目前不得而知，或许人们能够从数学上证明它不是n p c 的， 存在着p 算法将是结构分析技术追求的目标。下面将给出与结构分析技术相关 的分析方法的综述： ( 1 ) 覆盖技术 对于有界p e t r i 网，由于其可达标识集r ( 螈) 是一个有限集，因此可以以 月( ) 作为顶点集，以标识之间的直接可达关系为弧集构成一个有向图。这种 有向图称为p e t r i 网的可达标识图。通过一个p e t r i 网的可达标识图可以分析这 个网系统的状态变化和变迁发生序列的情况，从而得知网系统的有关性质。 然而，当不是有界p e t r i 网时，由于n ( m o ) 是一个无限集，不可能画出 乙的可达标识图。为了用有限形式表达一个有无限个状态的系统的运行情况， 需要引入一个表示无界量的符号国。当库所s ；中的标识数在p e t r i 网的运行过程 中趋向于无限增长时，就把标识向量中的第j 个分量改为c o ，以此覆盖所有这 类标识。这样，就可以通过一个有限的图( 树) 来反映这个p e t r i 网的运行情况。 称这种有限图( 树) 为p e t r i 网乙的覆盖图( 树) 。但是，在覆盖图进行搜索的时候， 通常搜索的路径长度是关于节点数的指数阶的。 ( 2 ) 偏序分析 迹语言是有波兰人a m a z u r k i e w i c z 3 4 】于1 9 7 7 年提出的，是试图通过并发 系统的序列观察来刻划系统的非序列行为的一种工具。 迹语言的研究主要集中在两个方面：一方面设计到迹的图表示理论和图文 法理论【3 5 1 。参考文献 3 6 试图通过无向结点标号图产生语言，给出图文法处理 的一个精巧数学框架n l c 文法，参考文献 3 7 】以类似于正规串文法的途径形式 化处理n l c 文法，从而导出所谓的b n l c 文法。参考文献 3 8 通过有向图产生 9 西华大学硕士学位论文 语言，n l c 文法的一个变种，即r d n l c 文法。参考文献 3 9 讨论了由r d n l c 文法的一个子类产生的正规迹语言特征。这方面的研究，依赖图是一个基本的 工具，就像串是串文法理论的基础，它是图文法理论的基础。另一方面，研究 与迹语言理论有关的代数作为并发系统规范说明和描述技术的基础，考察迹语 言与其他模型( 如e n 系统、时态逻辑) 之间的关系及其转换问题，这方面的 工作可见参考文献 4 1 】。 偏序语言是由j g r b o w s k i 4 0 于1 9 7 9 年首先提出的，它能够对并发行为予以 清晰地刻划，被认为是研究并发系统在串语言和进程语义下行为的一个统一的 框架。 偏序语言建立于一个严格的偏序结构( a ， ，是满 足下列两个条件的最小集： ( 1 ) 眠 m o ； ( 2 ) v m m o ， 如果3 t et ，s t m t m ， 贝0 m 7 m o 定义2 1 7 令是网，x = put ，若比x ：。工nx 。= 矽，则为单纯网 ( p u r en e t ) 。若v x ，y ex ：。x = 7ax = y jx = y ，则为简单l 网( s i m p l en e t ) 。 定义2 1 8 冲突( c o n f l i c t ) f 。1 9 2 1a nn e tw i t hc o n f l i c tmp 图2 1p 处存在冲突关系 若m p 。 a m t 2 ，但1 m ，t 2 ) ，则z 。和f 2 在p 处冲突。冲突有的时候 又称为选择( c h o i c e ) 和不确定( n o n d e t e r m i n i s m ) ，因为它可以作为允许外部环境加 以选择决策( d e c i s i o n ) 之处。 定义2 1 9 冲撞( c o n t a c t ) 库所s 。s 在标识m 下( 可能) 有冲撞( c o n t a c t ) 的条件是：存在，t ，使得 v s s ：w ( s ，t ) m ( s ) 。但m ( s o ) k ( s o ) 一w ( t ，s o ) 。 若在的任何可达标识下都不可能有冲撞，那么就说是无冲撞 ( c o n t a c t f r e e ) 系统。 若对于变迁t l , t 2 t 和标识m ，w ( s ，t 1 ) + w ( s ，t 2 ) m ( s ) k ( s ) - w ( t 。，s ) 一w ( t 2 ，s ) 对所有s s 成立，那么就说t 1 和t 2 在m 有并发 ( c o n c u r r e n t ) 权。 沪曳崩 擎名昌p f i 9 2 2a nn e tw i t hc o n t a c ti np 图2 2p 处存在冲撞关系 定义2 1 1 0 1 4 ( 1 ) 以库所集尸为序标集的列向量y ：p 弓z 叫作网n 的p 一向量，其中z 是整数集； ( 2 ) 以变迁集丁为序标集的列向量u ：tjz 叫作网n 的丁一向量； ( 3 ) 以p xt 为序标集的mxn 阶矩阵c ：p x t z 叫作网的关联矩阵 ( i n c i d e n c em a t r i x ) ，其矩阵元素，0 ) = 鸭，易) 一，0 ) 2 2 网系统分类 定义2 2 1 设= ( b ，e ；f ，c o ) 为一个基本网系统。满足下列条件的最小集合 c f l ( b ) ( ( 曰) 是曰的幂集) 称为的完全情态集( c o m p l e t es e to f c a s e s l ： ( 1 ) c o c ； ( 2 ) v c c ，若存在q ，乞e 和c l ，乞b ，使得c 1 e l c 和d 吃 c 2 ，则 c i ，c 2 c 定义2 2 2 设= ( 曰，e ；f ，c o ) 为一个基本网系统，c 是的完全情态集。 若( b ，；f ) 是个简单网，而且： ( 1 ) v 6 b ，3 c , ，c 2 c ，使得b ec 】，但6 仨c 2 ， ( 2 ) v e ee ，3 q ，c 2 c ，使得q e c 2 ，则称= ( b ，e ；f ，c ) 为一个条件事件 系统( c o n d i t i o n e v e n ts y s t e m ) ，简记为c e 系统。 定义2 2 3 六元组= ( s ，t ；f ，k ，w ，m ) 称为一个库所变迁系统 ( p l a c e t r a n s i t i o ns y s t e m ) ，简称p 厂r 系统，其中： ( 1 ) ( s ，t ；f ) 是一个网， w ：f 寸 1 , 2 ，3 ，) 称为权函数( w e i g h t e df u n c t i o n ) k ：s 一 1 ，2 ，3 ，) 称为容量函数( c a p a c i t yf u n c t i o n ) m ：sj 1 , 2 ，3 ， 是的一个标识，满足条件： v s s ：m ( s ) k ( s ) ( 2 ) 满足变迁发生规则： ( a ) 对于f t ，m t 的条件为： 两华大学硕士学位论文 v 距f ：m ( s ) w ( s ，t ) v s t o 一t ：m ( s ) + w ( t ，s ) k ( s ) v s t n 。t ：m ( s ) + w ( t ，s ) 一w ( s ，f ) k ( s ) ( b ) 若m t m ，则对协s ， m o ) = m ( s ) 一w ( s ，f ) ，若s e t t m ( s ) + w ( t ，s ) ，若s f 一t m ( s ) + w ( t ，s ) 一w ( s ，吐若s e 。t f 3 t 。 m ( s ) ，其它 p 厂r 系统是c e 系统在库容量函数以及权值函数上的扩展。 定义2 2 4 标识网( m a r k e dn e t s ) 令n = ( s ，r ；，) 是一个p e t r i 网，称为标识网。映射： 胍s _ 0 ，1 ，2 ) 称为网的一个标识( m a r k i n g ) 。二元组( n ，m ) ( 也即四元组( s ，t ；f ，m ) ) 称为一 个标识网( m a r k e dn e t ) 。 2 3p e t r i 网的结构和行为特征 定义2 3 1 出现序? l j ( o c c u r r e n c es e q u e n c e ) 设= ( s ，t ；f ，k ，w ，眠) 为有限无冲撞p t 一系统。 ( 1 ) 仃= m 。t 1 m f 2 鸩t n m n 为的一个有限出现序列的充分必要条件是： 对所有的f ，待1 , 2 ，玎，m i 一。 f ， m i ，其中眠为之初始标识，n 称为盯的长 度。 ( 2 ) 仃= m o t ，m f ：鸠为的一个无限出现序列的充分必要条件是：对所 有的i ，江1 , 2 ，n ，m 一1 i t ， m 定义2 3 2 变迁序列( t r a n s i t i o ns e q u e n c e ) 设= ( s ，t ；f ，k ，w ，) 为有限无冲撞p l 系统。 ( 1 ) 若仃= m o t l m l t 2 m 2 t m 。为的出现序列，则毛= f l t 2 t 。称为的变 迁序列，瓦的长度与仃长度同为刀 1 6 西华大学硕士学位论文 ( 2 ) 若仃= m o t ，m ，t 2 鸠为的无限出现序列，则互= f l t 2 称为的无限 变迁序列，简称变迁序列。 定义2 3 3 活。i 生( l i v e n e s s ) ，有界性( b o u n d e d n e s s ) n = ( p ，t ；f ) 是一个p e t r i 网，= ( n ，眠) 是一个网系统： ( 1 ) 变迁t et 在下是活的当且仅当对m m o ，3 m m ，使得 m 7 i t ： ( 2 ) 是活的当且仅当丁中所有的t 在中都是活的： ( 3 ) 中库所p 是有界的，当且仅当存在一个正整数k ，对蝴 ，有 m ( p 1 尼； ( 4 ) 是有界的，当且仅当中所有库所都是有界的； ( 5 ) 是弱活的( d e a d l o c k - f r e e ) 当且仅当m 【m o ，3 t t ，使得m t ； ( 6 ) 是死的( d e a d l o c k ) 当且仅当埘 m 0 ，t , s t 1 t 定义2 3 4 s 不变( s i n v a r i a n t ) 、t - 不变( t - i n v a r i a n t ) 吲 是一个p e t r i 网，c 是网 r 的关联矩阵，是一个户向量，j 是的一 个s 一不变当且仅当：c7 1 = 0 ；j 是一个t 向量，是的一个t - 不变当且 仅当：c j = 0 ； 若i 0 ， 1 是正的s 不变；被s 不变覆盖当且仅当任意的p 存在着， 使得i ( p ) 0 ； p e t r i 网的s 不变的线性组合仍然是s 不变。t 不变的线性组合仍然是t - 不变。 定义2 3 5 死锁( s i p h o n ) 和陷阱( t r a p ) 令n = ( 尸，t ；f ) 是一个p e t r i 网， ( 1 ) s p 是的一个s i p h o n ( 死锁) 当且仅当s s ； ( 1 ) s p 是的一个t r a p ( 陷阱) 当且仅当s 。s ； ( 2 ) d p 是的一个极小s i p h o n ( 陷阱) 当且仅当d 的任何非空子集都不是 的s i p h o n ( 陷阱) 。 定义2 3 6 家态( h o m es t a t e ) 令n = ( p ，t ；f ) 是一个p e t r i 网，= ( n ，眠) 是一个网系统。如果 v m a 【m o 孤 m ，那么称眠是该网系统的一个家态。家态也叫系统的可 1 7 西华大学硕士学位论文 逆性。 第三章p e t r i 网的动态行为研究方法分析 p e t r i 网是适应于形式化软件开发的很好的描述工具。p e t r i 网理论研究分为 建模与验证两个方面，结构技术是p e t r i 网的验证技术的基本方法之一，其主要核 心是基于死锁，基于这一方法的研究已取得一些很好的结果，但死锁的个数是网 规模的指数阶的。这就意味着目前有关网的理论研究结果与实用的验证方法有 着一条难于逾越的鸿沟。本章对p e t r i 网的动态行为研究方法给出了一个较为详 尽的概述。 3 1 建模与验证 p e t r i 网的理论与应用研究是相辅相成，互相渗透的。可以说，p e t r i 网的理 论研究主要分为两大部分：建模与验证。建模是便于对系统进行性能分析。为 了用p e t r i 网分析实际系统的性质，首先要建立实际系统的p e t r i 网模型。一般 地说，p e t r i 网可以描述的系统是那些由离散事件组成的系统，事件之间有一定 的相互依赖关系，这种依赖关系通过系统的状态来反映。事件的接连发生和状 态的不断变化的过程就是系统的运行。目前已经有诸多将p e t r i 网用于建立模型 的研究，如，基于p e t r i 网的工作流建模，基于p e t r i 网的通讯协议的建模，基 于p e t r i 网的有限状态机建模等等。 对一个已建立的p e t r i 网模型，需要对其进行分析、检测、验证。现有的 p e t r i 网分析技术包括：基于状态方程和代数分析技术 6 4 ，6 5 ，6 6 ，基于可覆盖树 ( 图) 的分析技术 6 7 ，6 8 ，基于化简分解的归纳分析技术 6 9 8 1o 代数分析技术 主要以关联矩阵的形式对一个网系统的结构给予刻画，然后建立状态可达的线 性系统关系，这种分析途径首先是由p e t e r s o n 6 4 提出，之后m u r a t a 6 5 的工作 最为出色。它的优点是基于线性代数的方法刻画网的静态结构，用不变量 西华大学硕士学位论文 ( i n v a r i a n t s ) 研究的网的一些性质，尤其是结构性质。当然，其作用是有限的， 难于很好地刻画动态特征。一般来说，它对可达性的刻画只是一个必要条件， 而非充分，只有针对无冲突的子类才是充要的。最近，文献 6 6 3 试图做出努力， 取得了一些进展，但仍未很好的解决。图分析技术是以一个有限的有向( 树) ， 直接展现一个网系统的运行机制，类似于一个状态机。k a r p 和m i l l e r 6 7 首先 提出这一思想，它的优点是能反映一个网系统的动态行为和一些特征。特别地， 对一个有界p e t r i 网，它能准确刻画，而且对应一个有限状态机。然而，对无界 p e t r i 网，它只能部分反映。虽说可达树是p e t r i 网分析的一个较好工具，但无 法回避状态空间爆炸。为此，人们提出极小可达树、可达树化简 6 8 3 等办法来 克服这一困难，只能说在一定程度上起到了作用；结构技术的核心是s i p h o n ， 已经有人证明当网的规模扩大时，s i p h o n 的规模成指数增长，因此国内外大部 分基于结构分析技术得到的结论都是有着较强的理论意义，较小的应用价值， 因此要解决这一问题，那就必须绕开s i h p o n ，否则基于s i p h o n 的结构分析很难 普适。国内西安电子科技大学李志武教授将s i p h o n 与s 不变( t 不变) 结合， 提出了基本性标理论，较好的解决了结构技术中的障碍，以柔性制造作为背景 得到了一些实用性强的结果，但是李教授的结论要么是充分，要么是必要的， 少有充要命题，因此只是较好的解决的系统无死锁性的预防，而没有彻底解决 系统死锁的判定，但是他的基本性标理论以其独具匠心为结构分析技术开辟了 新的思路和方法，让人耳目一新。 3 2 化简 化简是将一个较复杂的p e t r i 网简化成一个比较简单的网的等价变换过程， 这个过程减少了可达状态空间的规模，对简单网的分析能为理解原网提供充分 的信息。m u r a t a 6 9 ，7 0 针对t 图提出若干化简规则，并讨论了这些规则对活性、 安全性的保持关系；蒋昌俊 7 1 推广了m u r a t a 的工作，进一步提出了对加权t - 图 的化简规则，并给出了化简运算对结构性质的保持条件；a a l s t 7 2 在工作流过程 验证中使用了这些技术；m u g a r z a 7 3 和f e r s c h a 7 4 给出了并行程序的化简规则， 1 9 西华大学硕上学位论文 并给出了相应的p e t r i 化简规则；林闯 7 5 ，7 6 运用自底向上逐步综合替代的分层 分析方法，给出了基本随机p e t r i 网性能等价公式，并利用变迁可实施谓词和随机 开关对模型进行了精化设计及化简这些化简方法都是在权为1 的p e t r i 网上考 虑或者是在加权的特殊p e t r i 网子类上考虑的；文 7 7 将化简方法推广到加权的 p t 网，并给出了其对结构性质及公平性、s ( t ) 一不变量的保持条件较新的研究 成果有基于实时系统的化简规则 7 8 及其在工作流方面的应用 7 9 ，8 0 ，8 1 。但是， 就总体而言大多数工作都局限在保性研究上，而且条件过强，很难普适。 保持行为的化简和分解研究，减弱条件，提高适应性将是进一步努力的目 标。 3 3 子类的行为研究 p e t r i 网理论研究的另一主流方向是建立在通用网论基础之上的并发行为的 特性研究。通用网论是从更为基础、更为抽象的网模型( 如c e 系统，p 厂r 系统) 上探讨系统的特性。北京大学袁崇义教授在他的著作“p e t r i 网原理与应用”中 指出：文献中有不少把系统基网的性质与系统性质联系起来的文章，例如基网 为t - 网，s 网，自由选择网等等，由于网结构上的特性，给系统性质的分析带 来方便。这类文章类似数学，加上一些条件就能够得到新的结论，而不完全是 从应用领域考虑，找出特定领域至特征在相应p e t r i 网上的反应，再根据这类网 结构上的性质分析网系统的性质。这种观点反映了袁崇义教授p e t r i 网研究的方 法论。细细品味，不能说完全没有道理。 3 4p e t r i 网语言研究 另一方面，p e t r i 网语言也是p e t r i 网中一个重要研究方向，h a c k 8 3 和 p e t e r s o n 6 4 最早从事这方面的研究，将一个p e t r i 网所有可能的引发序列的集合 视为该网产生的语言文 6 4 研究了语言的封闭性，以及与经典形式语言的关系。 h a c k 在文 8 2 中讨论了网模型的计算能力，指出带抑止弧的增广p e t r i 网与图灵 2 0 西华大学硕：l 学位论文 机在计算能力上是等价的，从而充分显示出p e t r i 网模型的表达能力。然而，同 经典形式语言相比，p e t r i 网语言显得不那么成熟。首先没有建立p e t r i 网语言 的表达层次及相应的文法关系，只将p e t r i 网看成是语言的产生器，而没有考察 作为识别器的可能。 就p e t r i 网讨论的一些重要性质( 如活性等) 极少以语言的形式加以刻画和分 析。这反映出了p e t r i 网语言研究的不成熟性。从p e t r i 网语言和进程演化而来 的迹语言和偏序语言是系统行为的新的表示工具。迹语言是由波兰人 m a z u r k i e w i c z 于1 9 7 7 年提出的，试图通过并发系统的序列观察来刻画系统的非 序列行为的一种工具。偏序语言是由g r a b o w s k i 于1 9 7 9 年首先提出的，它对并 发行为能清晰地刻画，被认为是研究并发系统在串语义和进程语义下行为的一 个统一的框架。最新的基于迹语言的研究集中在对迹语言理论有关的代数作为 并发系统规范说明和描述技术的基础，考察迹语言与其它模型( 如e n 系统，时 态逻辑) 之间的关系及其转换问题。研究了偏序语言的一些性质，以及从p e t r i 网中如何导出各种语义之间的关系，将偏序语言推广到无限字的情况，并做了 性质研究，将偏序语言应用于结构的重组，使之成为新的逻辑程序控制器。迹 语言或并发控制语言对并发系统的行为，尤其是并发行为都能给出很好的刻画， 而且起到了各种语义之间关系的桥梁。然而，这些语言在系统性质( 如活性，公 平性等) 方面的刻画与分析手段仍不令人满意。它们对系统规范的形式说明及其 系统模型的构造仍需进一步努力，增强其可操作性，使之适于系统控制也将是 进一步研究的方向。 第四章基于p e t