Petri网语言表达式及其求解算法

Petri网语言是描述网系统动作序列的集合。为了给出一个网系统语言的形式描述,基于Petri网的状态转换图,分析了Petri网的行为特征,定义了α闭包表达式和Petri网语言表达式,给出了求解Petri网语言表达式的算法,为Petri网语言的形式化描述和分析提供了一种新方法。

Petri网的进程表达式与语言表达式

Petri网的语言和进程都是网系统行为的一种有效的描述手段 .对应的进程表达式和语言表达式给出了系统全体行为的约束描述 .本文首先对 Petri网的进程表达式进行了类型的划分并给出了相应的代数判定依据 ,随后证明了 Petri网的进程表达式与语言表达式的类型一致性 ,由此给出了由进程表达式求取语言表达式的算法 ,为基于 Petri网语言 (尤其是无界 Petri网 )

有界Petri网进程表达式与活性的关系

Petri网进程是对Petri网并发语义的一个刻画,是Petri网分析和验证的有效手段.该文针对有界Petri网研究进程表达式和活性性质之间的关系,给出了基于进程表达式的有界Petri网及其同步合成网的活性判定定理.同时研究了进程表达式与虹吸、陷阱间的关系,是Petri网活性研究的一个新的尝试.

无界公平Petri网的进程表达式

Ｐｅｔｒｉ网的进程表达式是以该网系统的基本子进程集为字母表的一个正规表达式．它用有限形式给出了网系统的所有（无限多个）进程的集合．作者于１９９５年给出了对任意给定的有界Ｐｅｔｒｉ网求其进程表达式的一个算法．这个算法对无界Ｐｅｔｒｉ网是不适用的，其原因在于子进程同构的概念在无界网系统中没有意义．对此，作者通过定义进程段行为等价的概念，导出了无界Ｐｅｔｒｉ网的进程表达式的一般形式，并借助无界公平网的特征可达树得出求给定无界公平网进程表达式的一个算法。

无界Petri网的进程表达式

借助进程网系统的概念 ,首先证明了无界Petri网Σ的进程与其进程网系统ΣP的语言之间存在一一映射关系 ,将求取Σ的进程表达式的问题转化成求取ΣP的语言问题 .由于ΣP的结构一般比较复杂 ,直接求取其语言仍然比较困难 .通过定义库所的指标函数 ,将结构复杂的ΣP分解成结构简单的子网系统 ,引入了语言的同步交运算 ,给出了利用这些子网系统求取结构复杂的ΣP语言的方法 ,从而得到了求取无界Petri网Σ的进程表达式的算法 .

稳定有界Petri网的进程表达式

文献[1]证明一个有界Petri网的进程表达式是以该网的基本子进程集为字母表的正规表达式,然而没有给出基本子进程的求解方法。定义了一类有界Petri网———稳定有界Petri网,并给出其基本子进程的求解算法,进而利用有限自动机的语言表达式的求解方法来求解稳定有界Petri网的进程表达式。另外,还给出了由符合一定条件的S-网的进程表达式来构造其同步合成网的进程表达式的算法。

正规表达式与恰当终结的标准Petri网

给出了一种较特殊的Petri网子类——恰当终结的标准Petri网,可以证明恰当终结的标准Petri网产生的语言是正规语言,反之任一正规语言都可由恰当终结的标准Petri网产生。研究了恰当终结的标准Petri网语言关于连接运算"o"、选择(并)运算"∪"、kleene闭包运算"*"、并行运算"∥"的性质,给出了用恰当终结的标准Petri网(带空标注)模拟和带并发算子的正规表达式的方法。

基于行为表达式的任意随机Petri网的品质分析

提出一种基于行为表达式的品质分析方法，可以做任意分布的有界或无界随机Ｐｅｔｒｉ网的品质分析．该方法不仅拓广了分析范围，解决了文献［４］中没有解决的问题，而且不必画出Ｐｅｔｒｉ网的可达标识图，使分析过程更为简洁．

操作表达式的Petri网表示(英文)

程序以操作表达式的形式呈现,而其语义则以公理的形式给出。为帮助理解这些公理并作为实现操作表达式的基础,给出了操作表达式的Petri网表示。传统Petri网的库所(place)概念与程序中变量概念有本质的不同,增加了变量概念的Petri网称为C_net。从回顾C_net的基本定义入手,研究操作表达式的网表示。

一种基于同步合成构造Petri网进程表达式的方法

Petri网的进程是用于系统行为和状态描述的有效工具,Petri网的进程表达式可以给出系统全部进程的描述,但是对于任意无界Petri网而言求取其进程表达式十分困难.文中首先考察结构简单的S-网的进程行为,给出各种类型的S-网的进程表达式的描述方法.然后拓展了Petri网同步合成的概念,分析了同步合成过程中基本进程段集之间的关系,并利用同步混排给出了进程表达式之间的关系.随后证明了一个Petri网可以通过一组S-网同步合成得到,利用S-网的进程表达式给出了构造Petri网的进程表达式的方法.

并发表达式与安全标号Petri网

本文定义了并发表达式，指出其表达能力与安全标号Petri网是等价的，并且我们给出并发表达式到安全标号Petri网转换的一个线性时间复杂性的算法．

对一个Petri网进程表达式的探讨

Petri网进程是Petri网分析和验证的有效手段,而Petri网的进程表达式可以给出系统全部进程的描述。针对文献《一种基于同步合成构造Petri网进程表达式的方法》提出的基于同步合成的Petri网表达式构成方法中的一个引理进行深入研究,并通过一个反例,说明这种方法的错误之处。

正规表达式与恰当终结的标准Petri网(英文)

已知一个语言表达式或语言的集合,如何构造产生该语言的Petri网模型是Petri网语言理论中的一个重要问题。为解决这个问题,引入一种称为恰当终结的标准Petri网模型。研究了恰当终结的标准Petri网语言(无ε-空标注)关于连接算""、选择(并)运算"+"、kleene闭包运算"+"、并行运算"//"的性质,证明了恰当终结的标准Petri网语言与正规语言的等价性,并给出了正规表达式到恰当终结的标准Petri网(带ε-空标注)的转换算法。作为对传统形式语言的有益补充,还给出了带并发算子的正规表达式到恰当终结的标准Petri网(带ε-空标注)的转换算法。

正规表达式到无空标注Petri网的构造方法

已知一个语言表达式或语言的集合,如何直接构造产生该语言的Petri网模型是Petri网语言理论中的一个重要问题。语言表达式到Petri网(无ε-空标注)的转换算法更有难度。研究了恰当终结的标准Petri网语言(无ε-空标注)关于连接算、选择(并)运算、闭包运算、并行运算的性质,在此基础上给出正规表达式到无ε-空标注的恰当终结的标准Petri网的转换算法。作为对传统形式语言的有益补充,还给出了带并发算子"//"的正规表达式到恰当终结的标准Petri网(无ε-空标注)的转换算法。

S-网的进程表达式及求取方法研究

Petri网的进程是用于系统行为和状态描述的有效工具,但是通常很难给出结构复杂Petri网进程的全部描述。本文考察结构简单的S-网的进程行为,给出各种类型的S-网的进程表达式的描述方法,为结构复杂Petri网系统的进程描述提供借鉴和帮助。

广义有界上下文无关语言与Petri网语言

提出了广义有界上下文无关语言的概念,该类语言是上下文无关语言的真子集;证明了广义有界上下文无关语言与上下文无关Petri网语言的等价性;进一步给出了上下文无关Petri网语言的一种形式描述--上下文无关Petri网语言表达式,对上下文无关Petri网语言给出了较完整的结构特征.

共享合成Petri网系统的语言递归性与系统活性

在Petri网系统合成操作的研究中,大系统的一些好性质,如活性、无死锁性的判定,是一个重要的研究内容.研究了Petri网系统的一种重要的合成操作棗共享合成,着重研究了Petri网系统共享合成的行为关系(语言关系),指出并证明了Petri网系统共享合成过程中语言的递归性质,得到一个并发语言形式的共享合成语言关系式.这个语言关系式为应用Petri网系统对具有并发行为特征的系统进行建模分析提供了一种有效的形式化工具.进而利用这个语言关系式来判定共享合成网系统的活性与无死锁性,得到共享合成网系统活及无死锁的充要条件.最后给出了一些条件,在这些条件下,可用小系统的语言子集来判定共享合成网系统的活性,从而达到用小系统来研究大系统活性的目的.

Petri网语言的同步交运算

Petri网语言是用于系统行为分析的有力工具 ,利用传统的语言运算并不能很好地刻画 Petri网的语言行为 .为此 ,本文给出一种新的 Petri网语言运算操作—同步交运算 ,并就网系统的分解和合成过程中的行为关系 ,分析了Petri网语言的同步交运算的作用和意义 .

Petri网语言的Pumping引理

Petri网语言是Petri网理论的重要组成部分,也是系统行为分析的一种重要的工具.Petri网语言的Pumping引理反映了Petri网语言的共性,可用来证明某些语言不是Petri网语言.已经证明,当一个Petri网语言可被某个有界Petri网产生时,此语言是正规语言,因此,正规语言的Pumping引理对此语言是有效的,但正规语言的Pumping引理并不适用于所有的Petri网语言.文中给出了一种Petri网语言的Pumping引理,证明其对任意无空标注的Petri网语言都有效,并且正规语言的Pumping引理是此引理的一种特殊形式.利用此Pumping引理可以证明某些语言是不能由Petri网产生的.

基于分解的结构复杂Petri网的语言行为描述

Petri网语言是用于系统行为分析的强有力手段,然而给定一个Petri网尤其是结构复杂的网系统,很难直接求解其语言表达式.针对这个问题,通过定义Petri网的库所指标函数,把一个结构复杂的网系统分解成结构简单的子网,即子网中每个变迁的输入库所和输出库所的数目均小于等于1,并分析了这些子网系统的语言特性.利用Petri网语言同步交运算,给出了一种求取结构复杂Petri网的语言表达式的方法,从而为利用网语言分析系统的行为提供了理论依据和方法.