题  目

作 者

摘       要

第九届全国Petri网学术年会文集

p-网—一类新型的模块化高级Petri网

曹木亮 吴智铭 杨根科

p-网是一类新型的模块化的高级Petri网。p-网有机地结合了两类并发模型Petri 网和p-演算，p-网既可称为Petri网中的p-演算，又是p-演算的Petri网形式的体现，从而在语义上实现了从p-演算到Petri网的一种自动翻译，较完整地解决了p-演算的分布式语义问题，在p－网中，任一p-网都可由四类基本p-网：Tau网、输入网、自由输出网和匹配网通过p-网的复合规则复合而成，这一结果不仅使得一个p-进程能够在p-网中得到自动的演进，也使得p-网自身具有了极大的可操作性和可计算性。

基于线性时态逻辑的Petri网模型检测

蒋屹新 林  闯 刑栩嘉

Petri网是一种重要的数学工具，它能有效地对并发系统进行描述和建模。线性时态逻辑LTL则是描述和验证并发系统特性的一种重要的形式化工具，它能方便准确地描述并发系统的重要性质，如安全性和活性。文章深入描述了线性时态逻辑、Büchi自动机、Petri网和同步积之间的内在联系，并探讨了基于线性时态逻辑的Petri网模型检测策略。与其它方法比较，这种模型检测的策略结合了线性时态逻辑和Petri网模型的不同优点，增强了Petri网的模型分析和验证能力。最后，通过对一个并发系统形式化的模型检测分析，验证了相应的结论。

基于时间Petri网的密码协议分析

张广胜 吴哲辉 逄玉叶

形式化分析方法由于其精炼、简洁和无二义性逐步成为分析密码协议的一条可靠和准确的途径，但是密码协议的形式化分析研究目前还不够深入。在文中首先对四类常见的密码协议形式化分析方法作了一些比较，阐述了各自的特点，然后用时间Petri网来表示和分析密码协议。该方法不但能够反映协议的静态和动态的特性，而且能够对密码协议进行时间、空间上的性能评估。作为实例，对Aziz-Diffie 无线协议作了详细的形式分析和性能评估，验证了已知的、存在的漏洞，并且给出了该协议的改进方案。

Petri网系统合成操作的活性保持性研究

蒲  飞 陆维明

合成操作是Petri网系统建模中一种重要的自底向上建模方法，而在Petri网系统的合成过程中，保性性质是一个重要的研究问题。本文综述了我们对Petri网系统两种合成操作（共享合成、同步合成）活性保持性的研究工作。与以往研究不同，侧重从并发语言的角度讨论。定义了相应合成操作的路径并发合成运算，以此建立两种合成操作Petri网系统的并发语言关系式。这些语言关系式可用于判定相应合成操作Petri网系统的活性与无死锁性，同时给出合成的Petri网系统活性与无死锁性的充要条件。最后分别给出条件使得合成的Petri网系统有活性保持性质。

MPI通信函数的增广Petri网模型

崔焕庆 吴哲辉 韩丛英

MPI是目前最流行的并行编程消息传递标准之一，它提供了多种点到点通信函数和集群通信函广Petri网模型，有利于解决此问题，并更好地利用它们编写并行程序。

并行程序与状态序列¾¾交叉语义约定的研究

袁崇义 余  鹏 王生原

许多程序模型是以数学或逻辑为基础设计并分析的，但程序模型的实现首先是个物理系统，它依物理规律，而非数学或逻辑规则活动。但人们习惯于用状态序列对并列程序模型的语义作数学处理。一旦偏序的状态空间用交叉的方法全序化，并用于论证程序性质，误导就在所难免。所谓误导，指的是与实际运行的偏差，借助于Petri网，可以将它们暴露出来。其实偏差的出现与Petri网的基本现象冲突(conflict)、冲撞(contact)、并发(concurrency)和混惑(confusion)相关。本文用Petri网分析误导的情况。

基于随机Petri网的乘积形式解存在的一个充分条件

方贤文 吴哲辉 倪丽娜

目前，判定一类随机Petri网（SPN）是否具有乘积形式解还没有比较好的方法。在这篇文章里给出了一个基于随机Petri网的乘积形式解存在的判定定理，它对于判定一些SPN模型是非常有用的。利用这个定理，可以发现两部件自动组装生产线模型具有乘积形式解，然后画出该模型的状态空间图，根据局部平衡方程，就可以得到此模型任意状态的稳定概率。

无冲突可重复网极小活标识的配置

许安国 赵义军

首先给出无冲突可重复网的定义，并证明无冲突可重复网是结构活的。然后将无冲突可重复网的极小活标识的配置化为强连通 图极小活标识的配置。文[2]虽然给出 图极小活标识的判断方法，但是对于一个比较复杂的 图的极小活标识的配置是无法实现的。本文通过求解强连通 图的 个线性无关的极小 不变量的支集，找出 个线性无关的有向回路组，然后给出构造强连通 图以任一变迁为根的有向生成树，最后给出配置强连通 图极小活标识的有效算法。

计算一类递归方程的增广Petri网模型

崔焕庆 吴哲辉 张广胜

递归方程的计算一直是一个较为复杂的问题，为更好的解决这一问题，建立各种模型是十分必要的。斐波那契数列是一个著名的递归方程，在这个方程的基础上，针对同类的递归方程建立了增广Petri网模型，并对模型的运行进行了分析。

Petri   网的公平分解和守恒分解

王培良 赵义军

给出了Petri网的公平分解和守恒分解的定义，同时给出了Petri网达到公平分解和守恒分解的具体方法，并证明了这种分解方法保持了网的一些结构性质。

可达性等价于状态方程可满足性的两个Petri-Nets网子类

邱经华 吴哲辉

可达性是Petri网的一个基本性质，其判定问题是Petri网理论研究方面的一个重要课题。众所周知，一个Petri网的状态方程可满足性是其可达性的一个必要不充分条件。然而[2]证明了，对于活的T-系统，其状态方程可满足性是其可达性的一个充分必要条件。另外[3]指出，对于活的加权T-系统，这一点也成立。下面第1部分给出一种包含活T-系统的活Petri网子类，并证明其状态方程可满足性是其可达性的一个充分必要条件。特别地，第2部分提出另一种Petri网子类（可以是不活的），并证明其状态方程可满足性也是其可达性的一个充分必要条件。

Petri网可扩展性标记语言

周必水 胡伟军

PNML（Petri网标记语言）是一种基于XML的Petri网的交换格式。因为可以用PNTD（Petri类型定义符）来定义Petri网的类型，PNML支持任何一种类型的Petri网。PNML主要用来在解决由于不同的Petri网类型而导致的问题。

无界时延混合Petri网（UTHPN）的可覆盖性演变图及性质

赵义军 王培良

时延混合Petri网（THPN）是由David最早提出的一类混合Petri网模型，而构造时延混合Petri网的演变图是对其性质进行分析的有效方法. 赵义军等在文[1]中给出了有界时延混合Petri网的演变图构造方法及性质分析，但对无界的时延混合Petri网，其演变图却不能用同样的方法构造出来.在本文中，通过引入无界量符号 ，给出了UTHPN的可覆盖性演变图的构造方法，并在此基础上讨论了UTHPN的有关性质.

基于模糊有色Petri网的不确定学习和推理方法

陈亚华 吴时霖

模糊Petri网模型可以用于模糊推理，但在Petri网中不得不用独立子网表示所有类型的过程，即使这些过程具有相同的行为，这导致整个Petri网变得很大。文中提出基于模糊有色Petri网的不确定性推理方法和基于遗传算法的学习过程。在减少网络规模，计算时间和克服解释网络困难的同时，它能保持等量的信息，提供结构化的表示，使知识库中的规则之间的关系易于表示。

基于有限容量库所方法的死锁防止算法

茹  雨 吴维敏

针对变迁均可控、可观的推广Petri网，给出了一种防止死锁的算法。该算法基于将死锁防止问题转化为控制规范的迭代算法和将控制规范施加到被控对象上的有限容量库所方法。它相对于只能面向某一类网的死锁防止方法，在通用性上有了很大改进；而且设计的控制器是结构型的，在线计算少、执行快；不过由于是迭代算法，有时离线计算量较大。最后用一个示例说明了该算法，并进行了进一步的讨论。

扩展Petri网在实时数据库并发控制中的应用

韩耀军 罗雪梅 蒋昌俊

提出了初始化弧的概念，并将这一概念引入高级时间Petri网中，从而给出了扩展的高级时间Petri网（Extended High-Level Time Petri Nets-EHLTPN）。此外，在EHLTPN模型中，变迁所附加的常量时间区间扩展为变量时间区间。用EHLTPN对实时数据库系统的并发事务进行了建模，所建模型不仅可以描述并发事务在数据存取中所出现的各种现象，而且还可以实现2PL-LW协议所具有的可避免并发事务的无用重启、无用等待、无死锁的等功能。

一类模糊Petri网的动态特性及应用

李孝忠

提出一类新的模糊Petri网，讨论了其可达性问题，其特点是一方面保持适度的不确定性，以便于分析，另一方面又可作为许多实际问题的模型。最后给出求解知识表示与推理的问题的例子.

虚拟接口体系结构的Petri网模型及分析

沙  静 蒋昌俊

随着计算机硬件的发展，网络硬件支持Gb/s的带宽已成为现实。但是由于分层网络软件频繁的系统调用和内存-内存拷贝，物理层和应用层之间形成性能鸿沟。虚拟接口体系结构是一种崭新的机群系统内部通信思想，它为用户提供了一个直接与网络相联系的虚拟接口，使操作系统不参与进程双方的通信过程，大大提高了通信效率。首先介绍了虚拟接口体系结构，然后为Berkeley模型建立了Petri网模型，通过模型对其工作模式进行分析，并对其中存在的活锁问题给出了具有实际意义的解决方法。

非马尔可夫随机Petri网的分析方法及应用

林  闯 李雅娟 刘雪宁

Petri网是模型并行系统和分布式系统的一种强有效的形式化工具。它能够很好地刻画系统的动态行为、分析系统的性能。目前研究的大多数随机Petri网假定模型中所有变迁的实施时间呈指数分布，但是在许多实际系统中，变迁的实施时间呈确定性分布或一般性分布，这就需要研究非马尔可夫模型。文章主要讨论非马尔可夫随机Petri网的分析技术，即基于马尔可夫再生理论进行分析求解，并举例进行说明，在文章的最后进行了总结和展望。

两个智力问题的增广Petri网模型

许安国 赵义军

给出人携带狼，羊，白菜安全过河问题的增广Petri网模型及著名的用餐哲学家问题的一个无饥饿解的增广Petri网模型。

从协议Petri网到Estelle的转换

罗军舟 杨晓燕

Petri网和Estelle是国际上流行的两种描述通信协议的形式技术。基本Petri网及其衍生变种具有图形的直观表示和数学的分析方法，在协议工程领域有着广泛的应用。而Estelle类似于程序语言，可对协议进行无二义的描述。本文针对现有Petri网系统的不足，从协议形式描述的角度出发，定义了一种抽象通信特性的协议Petri网，给出了由协议Petri网转换为Estelle形式的方法。基于此方法文章还构造了自动实现转换的算法，并给出了一个实例。

描述VHDL语句的Petri Nets模型

朱国魂 王聪敏

提出了一个可以描述VHDL中对象和控制流的Petri Nets模型，对比了只支持控制流CFPN模型的描述能力，给出了VHDL中对象：信号、变量和数据类型对模型的影响，并以具体实例分析了两种模型的不同抽象结果。

程序属性的UniNet描述

周国富 余  鹏 袁崇义 屈婉玲

在传统建模方法中，程序操作和程序自我控制相脱离，使得程序的计算与并行特性不能形成完整的一致性的描述，因此形成的规范都只是从某一个角度来刻画了程序。为克服这些不足，本文在揭示程序状态与操作，操作与控制共存的事实的基础上，采用UniNet独特的描述方法来完整而全面地刻画程序。

Petri网的分层递归模型

张继军 吴哲辉

Petri网的分层模型是应用Petri网对复杂系统建模时的一种常用手段。在传统的Petri网分层模型中，是不考虑递归的。这样的分层模型虽然为系统的建模和分析带来方便，但并增强模拟能力。在分层模型中引入递归的概念，可以使系统的模拟能力增强。可以证明，任意一个上下文无关语言都可以被一个分层递归Petri网识别。

广域Web集群的随机高级Petri网模型及性能分析

单志广 林  闯 魏丫丫

广域Web服务器集群是由多个局域Web服务器集群在Internet上广域分布而形成的一种服务器体系结构，是目前解决Web系统超载和提供高性能服务器的一种有效手段。基于随机高级Petri网的性能建模与分析技术，提出了一种广域Web服务器集群的随机高级Petri网模型；对模型进行了精化设计以简化模型求解的复杂性；研究了广域Web服务器集群的多级负载均衡综合方案，包括广域集群级的集群站点选择算法、局域集群级的请求分配算法和服务器级的请求调度算法，这些算法可以一致地综合在随机高级Petri网模型中；并且利用随机高级Petri网的性能分析技术对负载均衡综合策略进行了性能分析与评价。

基于VHDL的时延Petri网仿真

赵不贿 杜天艳 严仰光

在实时控制系统中，常常需要使用时延Petri网对系统进行建模、分析. 作者提出了用硬件描述语言对时延Petri网进行描述，用VHDL语言中的wait语句和after语句来模拟Petri网中的时延特性，通过EDA软件工具对时延Petri网进行仿真，获得系统的动态性能，这为时延Petri网的分析提供了新的路径，并为控制系统的设计和电路实现奠定了基础. 文章最后给出了一个实例，仿真波形表明了这种方法的正确性.

有色Petri网在系统分析中的应用

周必水 李旭东

Coloured Petri 网(简称 CP-nets 或CPN )是一种用于设计、详细说明、仿真和检验的面向图形的语言。它特别适合于那些通讯、同步、资源共享非常重要的系统。例如应用程序间的通讯协议、分布式系统、嵌入式系统、自动化生产系统、工作流分析和超大规模集成电路芯片。

多Agent系统的Petri网建模研究

郭  峰 姚淑珍

Agent作为一种新的软件开发范型，应用领域逐步扩大，但其潜在优势并没有在应用中完全展现，主要原因是缺少成熟实用的软件开发方法和工具。在软件工程领域Agent通常被认为是对象尤其是并发对象的进一步扩展，为了充分利用已有的面向对象方法和工具，首先提出了一种基于对象的混合Agent结构，然后从系统和个体两个层次上设计了体现多Agent系统行为特征的 Petri网模型，最后分析了多Agent系统仿真需要实现的关键算法。

投入产出系统Petri网模型

赵明清 张秀娟 蒋昌俊

Petri网是分析系统的一种有用工具。介绍了Petri网和投入产出系统的基本概念；给出了构造投入产出系统Petri网模型的方法；讨论了投入产出系统Petri网模型的性质；基于投入产出系统Petri网模型，得到了投入产出系统可分解的充分条件和不可分解的必要条件。为使问题阐述清楚，引入了一个具体的投入产出系统例子。将Petri网理论用于投入产出系统的研究，能够直观地反映出投入产出系统结构及其动态行为，是一件十分有意义的事情。

有色Petri网在通信协议中的应用

周必水 郦  泓

有色Petri网（CPNs）提供了一个框架用来对系统进行设计。有色Petri网有着很广泛的应用领域，很多CPNs项目在工业中得以应用。通讯协议、操作系统、硬件系统、嵌入式系统和软件设计也是有色Petri网的应用领域。

用层次颜色Petri网模拟主体行为

马炳先 徐颖蕾 吴哲辉

智能主体动态动作的形式化描述是开发应用多主体系统的关键之一，目前对于主体动作的形式化描述多是基于逻辑学的描述，不易直接应用到系统开发中。该文通过利用层次颜色Petri网对市场多主体系统的模拟，提出并讨论了利用层次颜色Petri网为多主体系统建模、模拟主体行为的方法，该方法对多主体系统中主体间的各种动态关系有较好的刻画，并且通过层次化的方法减少了利用一般Petri网系统（如: P/T系统）模拟复杂系统时所遇到的难度。

基于Petri网的工作流模式¾¾工作流模式分析研究

余  鹏 周国富 屈婉玲 袁崇义

随着企业建模、工作流概念的出现以及相关技术的发展，Petri网因其既有严格的形式定义，又有直观的图形表示，既有丰富的系统描述手段和系统行为分析技术，又为计算机科学提供坚实的概念基础等诸多优点也被应用于这一新兴领域，对工作流理论基础进行研究。本文将利用Petri网来描述和分析工作流的各种模式，比较模式之间的异同，并对模式进行合并和重划分。

  CORBA系统事务处理的模拟和分析

郑  红 李师贤

事务处理对于建立可靠的CORBA应用系统是很关键的，事务处理已经成为分布式应用系统设计的原则。CORBA的一个重要的服务是OMG的提出了对象事务处理服务OTS(Object Transaction Service)，负责将事务处理与对象在ORB层上结合。事务成为分布式对象系统中恢复、一致性、并发的基本单位。用着色时序Petri网模拟和分析CORBA环境下的事务处理。