文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > Petri网模型参数化可达图研究(1)
侵权投诉

Petri网模型参数化可达图研究(1)

第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网模型相关知识

Petri网模型参数化可达图研究(1)

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网等。

第1页

你可能喜欢

  • petri网
  • 装备保障
  • 图像检测
  • 彩色图像
  • ASP.NET
  • 遗传算法

热门文档

相关文档

  • 第八章随机Petri网模型与分析1_966307026

    第八章随机Petri网模型与分析1_966307026_交通运输_工程科技_专业资料。计算机...? 从SPN可达图的弧上转换变迁容易获得MC转移速率 矩阵的参数。 19 §8.2 ...

  • petri网1

    Petri网模型参数化可达图研... 6页 2财富值喜欢此文档的还喜欢 petri网理论...随着计算机 1 引言空间数据管理一直是 GS研究的主题, I 它包括 空间数据模型和...

  • Petri网系统的可达性研究

    在第六章,以停等协议的 Petri 网模型为例利用综合分析方法对可达性问题做了分析。最后,本文结尾对 Petri 网模型的可达性研究的存在问题和将来需要做的工作做了...

  • 一种构造Petri网可达图的方法(1)

    与人们所熟知的有限状 态机一样, P et ri 网是一种进行系统分析和研究的... Petri网模型参数化可达图... 暂无评价 6页 2.00 正规语言闭包运算的...

  • 基于攻击图的扩充Petri网攻击模型

    Petri网模型参数化可达图研... 6页 2财富值 基于多值逻辑Petri网的攻击.....本文通过系统最大承受攻击 能力这一概念,将攻击模型的研究扩展到二维角度,即...

  • 铁路工程形象进度图参数化生成系统研究

    Petri网模型参数化可达图... 6页 1下载券喜欢此文档的还喜欢 桥梁施工形象...图参数 化生成 系统 研究* 杨 观赐 李少波 胡 耀 潘伟 杰( 州大 学教育...

  • Pr-T Petri网的模型检测研究与应用

    Pr-T Petri网的模型检测研究与应用_IT/计算机_专业资料。Pr/T Petri PROD ...我们使用参数”-C”来指定可达图 产生时使用 CFFD-preserving 检测时,在采用 ...

  • 基于Petri网的作业网络模型的正确性研究

    3 JNW的Petri网模型Petri网是用于过程建模的一种流行技术。JNW4 JNW路由结构的...过程模型研究.微 对于这样一个JNW,用可达图生成算法建立了 图3所示的可达图。...

  • 第七章Petri网基础1_15406532

    Petri网研究的系统模型行为特性包括: ? 状态的可达(reachability) ? 位置的限界...Petri网的横向扩展: ? 从没有参数的网, 发展到时间Petri 网和随机Petri 网;...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email