Verification of bounded Petri nets using integer programming

Model checking based on the causal partial order semantics of Petri nets is an approach widely applied to cope with the state space explosion problem. One of the ways to exploit such a semantics is to consider (finite prefixes of) net unfoldings—themselves a class of acyclic Petri nets—which contain enough information, albeit implicit, to reason about the reachable markings of the original Petri nets. In [19], a verification technique for net unfoldings was proposed, in which deadlock detection was reduced to a mixed integer linear programming problem. In this paper, we present a further development of this approach. The essence of the proposed modifications is to transfer the information about causality and conflicts between the events involved in an unfolding, into a relationship between the corresponding integer variables in the system of linear constraints. Moreover, we present some problem-specific optimisation rules, reducing the search space. To solve other verification problems, such as mutual exclusion or marking reachability and coverability, we adopt Contejean and Devie's algorithm for solving systems of linear constraints over the natural numbers domain and refine it, by taking advantage of the specific properties of systems of linear constraints to be solved. Another contribution of this paper is a method of re-formulating some problems specified in terms of Petri nets as problems defined for their unfoldings. Using this method, we obtain a memory efficient translation of a deadlock detection problem for a safe Petri net into an LP problem. We also propose an on-the-fly deadlock detection method. Experimental results demonstrate that the resulting algorithms can achieve significant speedups.

ReSpecT Nets: Towards an Analysis Methodology for ReSpecT Specifications

A key feature for infrastructures providing coordination services is the ability to define the behaviour of coordination abstractions according to the requirements identified at design-time. We take as a representative for this scenario the logic-based language ReSpecT (Reaction Specification Tuples), used to program the reactive behaviour of tuple centres. ReSpecT specifications are at the core of the engineering methodology underlying the TuCSoN infrastructure, and are therefore the “conceptual place” where formal methods can be fruitfully applied to guarantee relevant system properties.In this paper we introduce ReSpecT nets, a formalism that can be used to describe reactive behaviours that can succeed and fail, and that allows for an encoding to Petri nets with inhibitor arcs. ReSpecT nets are introduced to give a core model to a fragment of the ReSpecT language, and to pave the way for devising an analysis methodology including formal verification of safety and liveness properties. In particular, we provide a semantics to ReSpecT specifications through a mapping to ReSpecT nets. The potential of this approach for the analysis of ReSpecT specifications is discussed, presenting initial results for the analysis of safety properties.     

基于Petri网的虚拟企业建立过程模型

首次将Petri网理论引入虚拟企业领域,提出了用Petri网对动态,并发的虚拟企业产生建立过程进行描述,使虚拟企业的建立过程在Petri网上得到清晰、全面的描述,为企业管理层进行决策提供了一种简洁、直观的决策分析工具。     

OMR抽象模型

在计算机领域反映现实世界中的事物,离不开有效模型的支持。这个模型一方面是现实世界中具体事物的抽象,另一方面又便于计算机实现。提出的OMR模型反映了现实世界的运行规律,用对象、消息和关系三要素对现实事物进行抽象和描述,是辅助计算机实现的有效工具。为了从形式化和数学化的角度描述OMR模型,又探讨了对象内Petri网和对象间Petri网,从而使OMR模型进一步丰满。     

基于工作流的虚拟企业信息管理模型

现代企业生产环境随着生产的全球化已经跨越 了国界,进行全球范围内的资源优化配置是有效利用全球资源的理想方案, 虚拟企业正是在 此需求下产生的．由于虚拟企业的分布式特点,其信息管理不同于传统的本地的管理方式． 本文给出一个基于工作流的虚拟企业信息管理模型,此模型支持的异构环境是地理上分散的 ,涉及到不同的应用包,多平台、多协议和多种用户界面,为虚拟企业生产信息管理提出了 一种方案．     

嵌入式网络体系结构研究及网络接口实现*

回顾了以往嵌入式网络采用的体系结构,介绍了它们的发展以及存在的问题。提出一种基于因特网的嵌入式网络体系结构,在对其网络接口的实现中,介绍了以单片机为硬件核心和以thin TCP/IP为软件核心的实现方案。这种体系结构的实现将推动嵌入式网络技术的发展。     

Iterative analysis of Markov regenerative models

Conventional algorithms for the steady-state analysis of Markov regenerative models suffer from high computational costs which are caused by densely populated matrices. In this paper, a new algorithm is suggested which avoids computing these matrices explicitly. Instead, a two-stage iteration scheme is used. An extended version of uniformization is applied as a subalgorithm to compute the required transient quantities “on-the fly”. The algorithm is formulated in terms of stochastic Petri nets. A detailed example illustrates the proposed concepts.     

Modeling And Performance Evaluation Of Branch And Value Prediction In Ilp Processors

Speculative execution is one of the key issues to boost the performance of future generation microprocessors. In this paper, we introduce a novel approach to evaluate the effects of branch and value prediction, which allow the processor to execute instructions beyond the limits of control and true data dependences. Until now, almost all the estimations of their performance potential under different scenarios have been obtained using trace-driven or execution-driven simulation. Occasionally, some simple deterministic models have been used. We employ an analytical model based on recently introduced Fluid Stochastic Petri Nets (FSPNs) in order to capture the dynamic behavior of an ILP processor with aggressive use of prediction techniques and speculative execution. Here we define the FSPN model, derive the state equations for the underlying stochastic process and present performance evaluation results to illustrate its usage in deriving measures of interest. Our implementation-independent stochastic modeling framework reveals considerable potential for further research in this area using numerical solution of systems of partial differential equations and/or discrete-event simulation of FSPN models.     

基于Petri Net的BPEL流程建模与分析验证

设计了一个基于Petri Net的Web服务组合流程建模引擎.把BPEL流程的语法元素按其语义转换为Petri Net模板,通过模板组合来得到整个流程的Petri Net模型,并以Petri Net标记语言(Petri Net Mark-up Language,PNML)文件格式来描述Petri Net模型,从而能够利用现有的支持PNML文件的Petri Net分析工具对流程进行分析,通过对Petri Net的性质验证来达到对服务流程的验证目的,以在流程定义阶段发现其存在的问题.实际结果表明,采用该工具可以确保服务组合流程设计的正确性,增加服务组合的可靠性.     

A hybrid model for real time simulation of urban traffic

In this paper a hybrid model is presented to predict the behavior of traffic in urban area. Intersections and on/off-ramps are modeled by Colored Timed Petri Nets while road links are modeled by a stochastic discrete time model. It is assumed that vehicle routings at each intersection are stochastic. A Particle Filter algorithm based on the hybrid model is developed to estimate the system state. The validation of the model by using real data is discussed. The limited computational effort required makes the model suitable to be used in simulation-based control schemes for urban traffic.