学位论文 > 优秀研究生学位论文题录展示

有界Petri网的语言识别算法研究

作　者: 崔婷婷
导　师: 曾庆田
学　校: 山东科技大学
专　业: 计算机软件与理论
关键词: 变迁序列 S-网关联矩阵库所指标语言识别
分类号: TN912.34
类　型: 硕士论文
年　份: 2011年
下　载: 23次
引　用: 0次
阅　读: 论文下载

内容摘要

作为分布式系统建模和分析工具,Petri网的应用领域越来越广泛。Petri网的变迁引发序列反映了Petri网的运行特征,一个Petri网产生的语言可以理解为由Petri网接受的所有变迁发生序列表示的字符串所构成的集合。目前,有关Petri网语言的研究已非常完善,但大多数只是将Petri网作为一种语言产生器来应用,而极少考察它作为语言识别器的可能。按照这个思路,本文针对三种不同类型的语言识别方法做了一些探讨和尝试。第一,将结构简单且行为易于分析的Petri网子类——S-网按照含有源变迁和汇变迁的情况分为四类；利用有限自动机与Petri网可达图的等价性,将Petri网的运行情况转化为一个自动机的运行；而后对这四类S-网进行或多或少的处理,从而成为能生成自动机S-网并提出了它们的识别算法；最后对算法的时间复杂度做了简单分析。第二,针对有界Petri网提出两个串行识别算法,分别为基于向量的语言识别算法和基于库所指标分解的语言识别算法。首先,利用S-网语言识别的思路给出了有界Petri网的语言识别算法并对时间复杂度做了分析；其次,Petri网的运行过程可以转换为向量的计算,通过向量计算的方法给出了有界Petri网语言识别的另一种算法。第三,为降低时间复杂度以及解决有界Petri网生成可达性树时存在的状态爆炸问题,提出了一种基于库所指标分解的有界Petri网语言的并行识别算法。在给出基于库所指标的分解方法的基础上提出了基于库所指标分解的Petri网语言的并行识别算法并分析了算法的时间复杂度。

全文目录

摘要  5-6
Abstract  6-12
1 引言  12-17
  1.1 选题背景和意义  12-13
  1.2 国内外相关研究现状  13-15
  1.3 论文的主要研究内容  15-16
  1.4 论文章节安排  16-17
2 Petri网的基本概念  17-25
  2.1 网与网系统  17-20
  2.2 Petri网的动态性质  20-22
  2.3 Petri网的分析方法  22-23
  2.4 变迁发生序列和Petri网语言  23-24
  2.5 本章小结  24-25
3 S-网的语言识别算法  25-38
  3.1 有界Petri网的有限自动机生成算法及复杂度分析  26-28
  3.2 标识S-图的语言识别算法及复杂度分析  28-30
  3.3 仅含汇变迁的标识S-网语言识别算法及时间复杂度分析  30-32
  3.4 仅含源变迁的S-网语言识别算法及时间复杂度分析  32-34
  3.5 仅含源变迁的标识S-网语言识别算法及时间复杂度分析  34-36
  3.6 实例分析  36-37
  3.7 本章小结  37-38
4 有界Petri网的串行语言识别算法  38-48
  4.1 预备知识  39-40
  4.2 基于有限自动机的Petri网识别算法及时间复杂度计算  40-42
  4.3 基于向量描述的有界Petri网语言识别算法及时间复杂度分析  42-43
  4.4 实例分析  43-47
  4.5 本章小结  47-48
5 基于库所指标分解的有界Petri网语言的并行识别算法  48-67
  5.1 基于库所指标的有界Petri网的分解方法  48-58
  5.2 基于库所指标分解的有界Petri网语言并行识别算法  58-62
  5.3 实例说明  62-65
  5.4 本章小结  65-67
6 总结与展望  67-68
致谢  68-69
攻读硕士期间主要成果  69-70
参考文献  70-73

有界Petri网的语言识别算法研究

内容摘要

全文目录

相似论文