无标注L型Petri网语言属性判定的一种方法

摘要：

Petri网和自动机是离散事件动态系统建模的两种重要方法,研究这两种模型之间的关系,对于更好地理解和控制离散事件动态系统的行为具有重要作用.本文从形式语言的角度对该问题进行了研究,提出了判定无标注L型Petri网语言属性的方法,引入有效递增子和线性子等概念来刻画Petri网语言的性质.对于一个Petri网PN,当PN没有有效递增子时,PN对应的Petri网语言是正则语言.当PN的某个有效递增子有两个及其以上线性子时,PN对应的Petri网语言是上下文有关的.当PN的所有有效递增子只有一个线性子时,如果只有一个有效递增子,则PN对应的Petri网语言是上下文无关的;如果PN有两个及其以上有效递增子,则顺序引发、嵌套引发和选择引发时PN对应的Petri网语言是上下文无关的,并发引发和交叉引发时PN对应的Petri网语言是上下文相关的.本文还对可达树进行了改进,给出了利用改进后的可达树来判定有效递增子的方法,从而使得本文给出的判定无标注L型Petri网语言属性的方法具有可操作性.

关键词：Petri网语言、形式语言、自动机理论、可达树、正则语言、上下文无关语言、上下文相关语言

所属期刊栏目：47

分类号：TP311.5;TP212;TP13

资助基金：国家自然科学基金;中央高校基本科研业务费专项;中央高校基本科研业务费专项;河北省高等学校科学技术研究项目;青海省重点研发项目

在线出版日期：2017-07-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共19页

页码：696-714