Implementing Coloured Petri Nets Using a Functional Programming Language

Coloured Petri Nets (CPNs) are a graphically oriented modelling language for concurrent systems based on Petri Nets and the functional programming language Standard ML. Petri Nets provide the primitives for modelling concurrency and synchronisation. Standard ML provides the primitives for modelling data manipulation and for creating compact and parameterisable CPN models.Functional programming and Standard ML have played a major role in the development of CPNs and the CPN computer tools supporting modelling, simulation, verification, and performance analysis of concurrent systems. At the modelling language level, Standard ML has extended Petri Nets with the practical expressiveness required for modelling systems of the size and complexity found in typical industrial projects. At the implementation level, Standard ML has been used to implement the formal semantics of CPNs that provide the theoretical foundation of the CPN computer tools.This paper provides an overview of how functional programming and Standard ML are applied in the CPN modelling language and the supporting computer tools. We give a detailed presentation of the key algorithms and techniques used for implementing the formal semantics of CPNs, and we survey a number of case studies where CPNs have been used for the design and analysis of systems. We also demonstrate how the use of a Standard ML programming environment has allowed Petri Nets to be used for the implementation of systems.     

用着色Petri网建模工作流模式

工作流模式指在工作流过程模型中反复出现的过程基本构造,是衡量工作流建模语言在控制流方面的表达能力和适用性的重要标准,目前市场上的工作流引擎对其支持得并不好。本文重点阐述了基于着色Petri网的工作流建模语言对当前流行的20种工作流模式的支持情况。结果表明,该语言不仅能很好地支持全部模式,而且具有建模简洁、准确的特点。同其它建模语言相比,用着色Petri网建模工作流模式具有较好的灵活性和扩展性。它也为如何使基于着色Petri网的工作流引擎能够正确、有效地支持全部20种工作流模式提供了有意义的指导。     

基于状态空间等价类的有色Petri网特性验证

在有色Petri网的状态空间中,有时一些状态具有相似的行为,这些状态可以用定义在状态空间上的一致的等价关系来表达,对每个等价状态类只研究它的一个代表状态的行为,这极大地减小了有色Petri网的状态空间。但是,通常对一个给定的等价关系是否为一致的验证都是通过用户的经验人工进行的,这不但容易产生错误,而且效率低下。该文依据普通状态图和等价类状态图的标记迁移系统关系,对状态空间一致性等价定义的计算机辅助验证做了深入的讨论,给出了相应的结果。     

Coloured Petri Nets and CPN Tools for modelling and validation of concurrent systems

Coloured Petri Nets (CPNs) is a language for the modelling and validation of systems in which concurrency, communication, and synchronisation play a major role. Coloured Petri Nets is a discrete-event modelling language combining Petri nets with the functional programming language Standard ML. Petri nets provide the foundation of the graphical notation and the basic primitives for modelling concurrency, communication, and synchronisation. Standard ML provides the primitives for the definition of data types, describing data manipulation, and for creating compact and parameterisable models. A CPN model of a system is an executable model representing the states of the system and the events (transitions) that can cause the system to change state. The CPN language makes it possible to organise a model as a set of modules, and it includes a time concept for representing the time taken to execute events in the modelled system. CPN Tools is an industrial-strength computer tool for constructing and analysing CPN models. Using CPN Tools, it is possible to investigate the behaviour of the modelled system using simulation, to verify properties by means of state space methods and model checking, and to conduct simulation-based performance analysis. User interaction with CPN Tools is based on direct manipulation of the graphical representation of the CPN model using interaction techniques, such as tool palettes and marking menus. A license for CPN Tools can be obtained free of charge, also for commercial use.     

有色Petri网的一种密码协议建模分析

密码协议是任何安全系统的基础,对它的设计越来越受到广大用户的关注.本文详细论述了文献[1]提到的一种密码协议,并使用有色Petri网对该协议建模分析,说明该设计的正确性.     

基于Petri网的WSCI形式化模型分析

WSCI是一种Web服务组合标记语言,对于一些关键的业务流程,任何设计错误都会造成重大损失,因此有必要为WSCI语言建立形式化模型并给予分析,从而保证正确的业务流程部署。本文主要给出了WSCI的分析方法,基于文献[1]给出了形式化模型,提出了该形式化模型下的一种网融合方法。该方法将表示进程的网模型与其表示例外处理和子流程的网模型进行合并,形成统一的网模型。本文最后还给出了在该网模型下的可达图分析方法,从而达到分析带有例外处理的WSCI形式化模型的目的。     

A Congruence for Petri Nets

We introduce a way of viewing Petri nets as open systems. This is done by considering a bicategory of cospans over a category of p/t nets and embeddings. We derive a labelled transition system (LTS) semantics for such nets using GIPOs and characterise the resulting congruence. Technically, our results are similar to the recent work by Milner on applying the theory of bigraphs to Petri Nets. The two main differences are that we treat p/t nets instead of c/e nets and we deal directly with a category of nets instead of encoding them into bigraphs.     

有色Petri网的一种面向对象扩展形式

Ｐｅｔｒｉ网与面向对象的结合一直是一个令人感兴趣的研究课题。本文把有色Ｐｅｔｒｉ网引入到面向对象方法中,提出了一种面向对象的扩展有色Ｐｅｔｒｉ网,简称为ＯＥＣＰＮ,     

基于Petri网和B语言集成的形式化方法

本文中提出了一种能够描述分布式系统和实时系统的形式化方法-Petri-B 网，Petri-B 网是集成了 Petri 网理论 和 B 语言的形式化方法，它不仅具有了 Petri 网的特点，还具备了 B 语言的长处。本文定义了 Petri-B 网并用它来描述一个座位预 订系统。     

基于有色网的多Agent计划建模

有色网能够描述资源和操作的具体语义。首先,由于计划中的操作和状态的个数的有限性,与有色网的元素个数有限性约束完全一致。另外,计划中的动作与有色网中的变迁语义类似,以及计划中的操作和状态和有色网中的库所语义非常类似。因此,有色网应用到计划的形式化中,有其独特的优势。本文根据约定的前提条件,计划建模从操作、状态和交互3个方面来具体实现,并给出了建模方法。计划的规范描述、有效性验证以及计划的模拟都可以直接应用经典Petri网或有色网的理论技术。     

时间Petri网分析工具的实现

时间Petri网是非常适合描述实时系统的模型工具,由于时间的复杂性因素使得它的可达性分析变得非常困难。该文在分析了基于全局时间变量的时间Petri网的可达性算法的基础上,采用OOP技术,实现了一个时间petri网的分析工具。     

一种利用UML的Petri网软件实现方法

Petri网既是一种图形化建模工具,又是一种形式化数学工具。Petri网具有对并发、并行、分布、异步系统进行验证仿真的能力。但是,Petri网是用来描述和分析要开发的系统模型的工具。不是计算机的实现工具,必须要通过一定的方法才能将Petri网用软件来实现。由于UML(统一建模语言)具有友善的用户界面,易于编程实现,故提出一种利用UML作为过渡的Petri网软件实现方法。     

延迟时间Petri网的验证分析

延迟时间Petri网（Delay Time Petri Nets，DTPN）是一类重要的时间扩展Petri网系统，解决了其他时间扩展Petri网（如时间Petri网）在保存时间约束时所面临的困难。可调度验证的目的是验证工作流模型时间约束的合理性，对流程实例的时间可达性进行仿真。提出一种基于DTPN的时间约束工作流验证分析方法。给出了DTPN的相关定义，并结合工作流控制结构描述了变迁可触发的时间条件；提出了DTPN触发点的概念以及基于此的验证分析算法；简要分析了DTPN的特性。DTPN的研究丰富完善了现有时间Petri网体系，具有积极的意义。     

Condensed state spaces for symmetrical Coloured Petri Nets

This paper deals with state spaces. A state space is a directed graph with a node for each reachable state and an arc for each possible state change. We describe how symmetries of the modelled system can be exploited to obtain much more succinct state space analysis. The symmetries induce equivalence classes of states and equivalence classes of state changes. It is then possible to construct a condensed state space where each node represents an equivalence class of states while each arc represents an equivalence class of state changes. Such a condensed state space is often much smaller than the full state space and it is also much faster to construct. Nevertheless, it is possible to use the condensed state space to verify the same kind of behavioural properties as the full state space. hence, we do not lose analytic power.We define state spaces and condensed state spaces for a language called Coloured Petri Nets (CP-nets). This language is in widespread use for the modelling and analysis of concurrent systems. However, our techniques are general and they can be used for many other kinds of labelled transition systems. The paper does not assume that the reader is familiar with CP-nets (or Petri nets in general)—although such knowledge will, of course, be a help. The first four sections of the paper introduce the basic concepts of CP-nets. The next three sections deal with state spaces, condensed state spaces and computer tools for state space analysis. Finally, there is a short conclusion.     

安全协议扩展Petri网模型及检测

协议安全性分析是网络安全的一个难题,运用形式方法对协议进行安全分析和检测,找出安全漏洞仍是该领域的研究热点。本文提出了一种新的基于扩展Petri网的安全协议建模方法,并且使用该方法对经典协议做了建摸、分析和检测,构造了攻击模型,证明了这种方法的有效性。     

A measure of mental workload during multitasking: Using performance-based Timed Petri Nets

Multitasking is common in emergency, which will result in man-made error due to many factors such as inappropriate Mental Workload (MW). To improve the performance under multitasking, the automatic equipment or assistive systems carry out task/interface optimizations according to the MW evaluation results, and the effectiveness of these technologies depends on how to choose an appropriate MW evaluation model. This paper has developed a performance-based Timed Petri Nets (TPN) model to evaluate MW during multitasking. The concrete functioned places and transitions, were proposed to structure a human resource allocation and recovery processes in TPN. The characteristics of operator are interpreted as initial markings of places and delay of transitions. Task performance is calculated as the difference between the triggering time of two transitions and a behavior process structure, respectively. The real-time MW is quantified and expressed as the remaining percentage of tokens in the attention resource place. A case study of triple-task execution was examined for verification of the model. Furthermore, the distinguishability and stability of the model, its comparison with ACT-R, and the application in task optimization were discussed.Relevance to industryThe Timed Petri Nets-based model can analyse the influence between mental workload and system states while proposed quantitative and individualized results of mental workload, which can direct a mental workload-based task optimization in safety-critical systems under multitasking in the design phase.     

用Petri网结构化的方法求解实时并行运算调度问题

本文讨论多资源有顺序关系的运算调度问题.算法中每步所需时间已知,用Petri网建模可使问题高度结构化,搜索空间只限于符合顺序的可行解部分[1],求得有资源约束及无资源约束两种条件下并行处理的最小时间跨度和相应的调度方案,所得结果为精确解.     

Petri网和优先矩阵在项目管理中的应用

本文针对项目管理,建立了Petri网模型Project_net,并在其中用优先矩阵的方法表现网中托肯的移动.优先矩阵明确地表达了网中变迁的优先关系,为项目管理者分析项目管理中项目活动的优先关联关系提供了简便的方法.     

基于着色Petri网的系统可生存性仿真平台

对可生存系统组件在攻击、抵抗、恢复3种因素作用下的状态转换过程进行分析,设计基于着色Petri网的系统可生存性仿真平台,从攻击强度、攻击密度、恢复强度、攻击策略、恢复策略5个方面模拟可生存系统的行为特性。以一个IPTV网络服务系统为例,利用平台仿真其在遭受不同攻击时的服务提供能力。仿真结果表明,该平台能较好地实现系统可生存性分析。     

连续Petri网的死锁和陷阱结构性态分析

连续Petri网是用来分析和描述具有连续变量的系统,被证明是有效的建模工具。本文主要讨论连续Petri网死锁和陷阱结构的性质,并结合算例对此进行了说明。