第19卷增刊1 系
统 仿 真 学 报© Vol. 19 Suppl. 1
2007年8月 Journal of System Simulation Aug., 2007
Petri网模型参数化可达图研究
宋佳兴,林 闯
(清华大学计算机科学与技术系,北京 100084)
摘 要:Petri网是一种对并发系统进行描述和建模的重要数学工具,可达图是Petri网模型的主要分析方法。为了解决由于系统参数化造成的Petri模型可达图难以构造并且无法进行模型性质检验的问题,在分析现有参数化可达图方法的基础上,利用参数化标识提出一种新的Petri网模型完全参数化可达图构造方法。同时给出了这种可达图的有关特性及其证明,并举例说明了如何利用这种参数化可达图对系统进行模型性质检测。
关键词:Petri网;参数化;可达图;模型性质检测
中图分类号:TP391 文献标识码:A 文章编号:1004-731X (2007) S1-0038-06
Research on Parameterized Reachability Graph of Petri Net Models
SONG Jia-xing, LIN Chuang
(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)
Abstract: Petri net is an important mathematical tool for concurrent systems description and modeling, and reachability graph analysis is one of the most effective methods for Petri net models. In order to solve the problem of constructing reachability graphs and verifying properties of parameterized system Petri net models, a novel completely parameterized reachability graph (PRG) based on parameterized markings is presented. Constructing algorithm for the PRG is introduced, and some primary properties of this kind of PRG are given and proved. An example is presented to illustrate how to use the PRG for modeling property verification.
Key words: petri net; parameterized; reachability graph; modeling property verification
引 言
Petri网是一种重要的数学工具,它能有效地对并发系统进行描述和建模,并对系统的并发性、异步性和不确定性具有很强的动态分析能力[1-3]。Petri网可以通过建立系统的可达图或者状态方程来描述系统的行为,其中,可达图是Petri网模型的主要分析方法之一。
模型性质检测[3-4]是一种应用范围广泛的并发系统模型验证技术,其优点是可编程性强,易于生成自动检测工具,缺点是必须基于被检测模型的状态可达图,有效性受到模型状态空间爆炸问题的影响。一方面在大型、复杂系统的模型中,模型的状态空间随着实际系统的规模增大而呈指数性增长,在很多情况下因计算的复杂性导致这种可达图分析方法是不可行的。另一方面可达图是根据系统模型初始标识计算出来的,这就意味着如果系统模型是参数化的,那么针对参数的每一个赋值都可能要计算一个完全不同的可达图,这就导致对带参数的系统的模型分析变得十分困难[2]。
很多学者进行了大量的工作来解决上述两方面的问题,状态空间爆炸的问题可以通过对称的方法对模型进行压缩表示来简化系统的状态空间,如高级Petri网、随机高级Petri
网等就是非常有效的模型[1-2],基于Petri网状态可达图的偏序简化和偏序语义技术也被广泛采用[5-8]。同时一些参数化的方法被用来解决参数化模型性质检验问题,这些方法中一另一类方法是行为的符号表示法[11-12],类是典型程序法[9-10],
而这两种方法都有各自的局限性。
本文在给出参数化标识和完全参数化可达图形式化定义的基础上,提出一种新的构造完全参数化可达图的算法。在一定的约束条件下,完全参数化可达图的每一状态标识中所有位置的标记数都用变量参数来表示,这种参数化可达图表示方法对状态标识进行了分类,表示方法简单灵活,具有较强的描述能力和分析能力。此外,本文还给出了这种参数化可达图的有关特性及其证明,并且分析了如何利用这种参数化可达图对系统进行模型性质检测,给出了对系统模型性质进行检测的判定算法。
1 Petri网模型相关知识

1.1 Petri网基本概念
[定义1] 一个三元组(S,T;F)是一个Petri网,当且仅当:
(1) S∪T≠ (网非空);S∩T= (二元性); (2) F (S×T)∪(T×S)(流关系仅在于S与T的元素之间);
(3) dom(F)∪cod(F) = S∪T(没有孤立元素)。 其中,S是位置集,T是变迁集,F是弧集;dom(F)= {x | 38
收稿日期:2007-05-10 修回日期:2007-06-28 基金项目:国家自然科学基金(60673187; 90412012)
作者简介:宋佳兴(1974-), 男, 吉林农安人, 博士生, 助理研究员, 研究方向为计算机网络, 随机Petri网等; 林闯(1948-), 男, 辽宁沈阳人, 博士, 教授, 研究方向为系统性能评价, 计算机网络, 随机Petri网等。
第八章随机Petri网模型与分析1_966307026_交通运输_工程科技_专业资料。计算机...? 从SPN可达图的弧上转换变迁容易获得MC转移速率 矩阵的参数。 19 §8.2 ...
Petri网模型参数化可达图研... 6页 2财富值喜欢此文档的还喜欢 petri网理论...随着计算机 1 引言空间数据管理一直是 GS研究的主题, I 它包括 空间数据模型和...
在第六章,以停等协议的 Petri 网模型为例利用综合分析方法对可达性问题做了分析。最后,本文结尾对 Petri 网模型的可达性研究的存在问题和将来需要做的工作做了...
与人们所熟知的有限状 态机一样, P et ri 网是一种进行系统分析和研究的... Petri网模型参数化可达图... 暂无评价 6页 2.00 正规语言闭包运算的...
Petri网模型参数化可达图研... 6页 2财富值 基于多值逻辑Petri网的攻击.....本文通过系统最大承受攻击 能力这一概念,将攻击模型的研究扩展到二维角度,即...
Petri网模型参数化可达图... 6页 1下载券喜欢此文档的还喜欢 桥梁施工形象...图参数 化生成 系统 研究* 杨 观赐 李少波 胡 耀 潘伟 杰( 州大 学教育...
Pr-T Petri网的模型检测研究与应用_IT/计算机_专业资料。Pr/T Petri PROD ...我们使用参数”-C”来指定可达图 产生时使用 CFFD-preserving 检测时,在采用 ...
3 JNW的Petri网模型Petri网是用于过程建模的一种流行技术。JNW4 JNW路由结构的...过程模型研究.微 对于这样一个JNW,用可达图生成算法建立了 图3所示的可达图。...
Petri网研究的系统模型行为特性包括: ? 状态的可达(reachability) ? 位置的限界...Petri网的横向扩展: ? 从没有参数的网, 发展到时间Petri 网和随机Petri 网;...
热门文档