活的单支Petri网的可达性判定方法及改进的可覆盖性树的构造算法

摘要

Petri网是一种系统描述和分析的工具。在Petri网的诸多性质研究中，可达性研究大概是最基本的一个动态性质研究。可达性在一定意义上可说是研究Petri网其他动态性质的基石，许多其他问题都可以通过可达性问题来叙述。因此，可达性判定问题是Petri网理论研究的一个重要课题。 目前有两种较为成熟的方法—矩阵方程、可达性树或可覆盖树可对Petri网的可达性进行分析，但是这两种方法却各有其局限性。对于第一种方法，一般来说由于ω符号的存在而受到局限，不能解决可达性和活性问题，也不能确定一个引发序列是否可能；而第二种方法也存在局限性，首先，矩阵A不并不能完全恰当的反映出Petri网的结构，其次，在引发向量中也缺少序列的信息。 本文首先从局部入手，对活的Petri网的一种子网——活的单支Petri网的可达性判定方法进行了研究，提出了三个结论并加以证明，从而给出了对活的单支Petri网的可达性进行判定的方法。然后从全局入手，对加权无界Petri网进行研究，找出了不能仅靠可覆盖性树对无界Petri网的可达性进行判定的原因，即：可覆盖性树为了用有限形式表达一个具有无限个状态的系统的运行情况，引入了一个标识无界量的ω，这样当库所中的标识数在Petri网的运行过程中趋于无限增长时，就用ω来标识向量中的第j个分量，由此覆盖所有这类标识。但ω这个无界量的引入却导致了无界Petri网运行过程中的某些重要的信息的丢失，从而使得我们不能使用可覆盖性树来分析无界Petri网的各种动态性质。 基于通过使用某个关于正整数的表达式去代替代表任意正整数的ω来减少这种“跨度”的思想，本论文对可覆盖性图的节点作了一些适当的改良，通过将可覆盖性树中的节点细化为：序列节点、复制节点、准复制节点的方法，从而令无界Petri网运行过程中的信息丢失减小，为一个任意的Petri网(包括无界Petri网)的可达性判定方法提供了依据。但是本研究所提出结论的的不足之处在于：只是绝大部分在准复制节点处可达的标识在其准复制源节点处也是可达的，并不是所有部分，因此这种特性就使得我们为保证可达性判定的严谨而必须要进一步对准复制源节点及其子孙节点作特殊处理，从而保证剩下这绝小部分的标识(即在准复制节点处可达而在其准复制源节点处不可达)不被遗漏。而采用什么样的特殊方法来进行处理就是我下一步要继续深入研究的。

目录

文摘

英文文摘

论文说明：符号说明

声明

第一章引言

1.1 Petri网概述

1.2本文的工作与创新

1.2.1本文的研究工作

1.2.2本文的创新之处

1.3本文的组织

第二章Petri网基本知识

2.1 Petri网的特点

2.2 Petri网的应用领域

2.3基本概念

2.3.1网的定义

2.3.2标识网与网系统的定义

2.3.3库所/变迁系统(简称P/T系统)的定义

2.4 Petri网的动态性质

2.4.1可达性(Reachability)的定义

2.4.2可覆盖性((bverability)的定义

2.4.3有界性和安全性(Bounded and Safety)的定义

2.4.4活性(Liveness)的定义

2.5 Petri网的基本分析方法

2.5.1可达标识图(Reachable marking graph)与可覆盖性(Coverabilitytree)

2.5.2关联矩阵和状态方程

2.5.3变迁发生序列与Petri网语言

2.5.4 Petri网进程

第三章利用状态方程或可覆盖性树进行可达性判定的局限性

3.1利用状态方程进行可达性判定的局限性

3.2利用可覆盖性树进行可达性判定的局限性

第四章活的单支petri网的可达性判定

4.1活的单支Petri网的定义

4.2活的单支Petri网的一个可达性判定方法

第五章改进的可覆盖性树的构造方法及描述

5.1改进的可覆盖性树中的节点类型

5.2改进的可覆盖性树中的节点的生成示例

5.2.1序列节点

5.2.2复制节点

5.2.3准复制节点

5.2.4死节点

5.2.5一般节点

第六章改进的可覆盖性树(ICT)的构造算法

6.1基本概念

6.1.1序列因子

6.1.2导出序列

6.1.3前置节点、前置变迁

6.2改进的可覆盖性树(ICT)的构造算法

6.2.1构造ICT所采用的数据结构

6.2.2改进的可覆盖性树(ICT)的构造算法

6.2.3算法6.1的可终止性证明

第七章结束语

7.1已取得的研究成果

7.2下一步的研究工作

附录

参考文献

致谢

攻读学位期间发表的学术论文目录