有界Petri网的合法引发序列判定算法

摘要

合法引发序列是Petri网可达性问题的一部分,它是Petri网研究领域的一个重要研究课题,该文针对Petri网的一个子类——有界Petri网给出了一个判定合法引发序列算法.该文给出的算法是在变迁序列分解的基础上实现的.我们讨论了变迁序列分解的依据、分解方法在合法引发序列判定中的应用以及分解的逆过程——变迁子序列合成合法引发序列的运算等.这些,是该文提出的判定算法的Petri网方面的理论依据.在变迁序列分解的指导思想下,我们的算法主要通过以下两步工作完成:(1)首先对给出的已知条件中满足状态方程的n维非负整数向量进行处理,得到一组X的基础向量X<,b>,使得在Petri网的可达标识图中,若存在一条由M<,0>到M<,d>的有向无环路,则X<,b>为这样的路上变迁引发序列的发生数向量.同时,我们记录下所有X<,b>的非零分量和的最大值作为控制第二步工作的终止.这一部分是以网的极小T-不变量为工具完成的.(2)经过第一步的工作,我们得到与判定X的合法引发序列问题等价而问题规模缩减了简化问题--判定X的基础向量X<,b>的合法引发序列.故我们解决后一问题.而由X<,b>的定义可知,它只能对应一条有向无环路上的变迁引发序列,所以,算法中在构建Σ<,1>=(S,T;F,M<,0>)的部分可达树RT(Σ<,1>)和Σ<,2>=(S,T;F,M<,d>)的部分逆向可达树RT<'-1>(Σ<,2>)的同时寻找这样的有向无环路.若能够找到,则说明有某个X<,b>对应一条使M<,d>由M<,0>可达的有向无环路上的变迁引发序列,算法判定成功,反之,则认为不存在合法引发序列,算法判定为失败.

目录

文摘

英文文摘

声明

第一章绪论

§1.1引 言

§1.2课题研究现状及解决方法

§1.3本文工作内容综述

§1.4本文思路及安排

第二章Petri网的基本知识

§2.1 Petri网概述

§2.2 Petri网和基本概念和性质

§2.3 Petri网的基本分析方法

第三章合法引发序列判定算法

§3.1算法基础

§3.2算法思想描述

§3.3数据结构的选择

§3.4算法流程图

§3.5算法的伪代码描述

第四章算法分析

§4.1算法的正确性证明

§4.2算法的时间复杂性分析

§4.3算法验证示例

第五章结束语

§5.1本文所做工作总结

§5.2后续研究课题展望

致谢

参考文献