代谢网络结构与功能的Petri网分析

发展基因组尺度代谢网络模型的模拟和分析方法有助于学习这些网络的结构与功能关系,是当前计算系统生物学领域的一个重要研究主题。由于具备严格的数学描述,直观的图形表达,外加存在众多的算法和工具,Petri网可能成为代谢网络模拟和分析的有力工具。应用位置/变迁网来分析代谢网络的结构与功能特征,首先建立了巴斯德毕赤酵母代谢的Petri网模型,随后计算了该模型中的P、T不变量,并讨论了它们的生物学意义。     

Identification of Petri Nets from Knowledge of Their Language

In this paper we deal with the problem of identifying a Petri net system, given a finite language generated by it. First we consider the problem of identifying a free labeled Petri net system, i.e., all transition labels are distinct. The set of transitions and the number of places is assumed to be known, while the net structure and the initial marking are computed solving an integer programming problem. Then we extend this approach in several ways introducing additional information about the model (structural constraints, conservative components, stationary sequences) or about its initial marking. We also treat the problem of synthesizing a bounded net system starting from an automaton that generates its language. Finally, we show how the approach can also be generalized to the case of labeled Petri nets, where two or more transitions may share the same label. In particular, in this case we impose that the resulting net system is deterministic. In both cases the identification problem can still be solved via an integer programming problem.

An algorithmic approach for analysis of finite-source retrial systems with unreliable servers

This paper aims at presenting an approach for analyzing finite-source retrial systems with servers subject to breakdowns and repairs, using Generalized Stochastic Petri Nets (GSPNs). This high-level formalism allows a simple representation of such systems with different breakdown disciplines. From the GSPN model, a Continuous Time Markov Chain (CTMC) can be automatically derived. However, for multiserver retrial systems with unreliable servers, the models may have a huge state space. Using the GSPN model as a support, we propose an algorithm for directly computing the infinitesimal generator of the CTMC without generating the reachability graph. In addition, we develop the formulas of the main stationary performance and reliability indices, as a function of the number of servers, the size of the customer source and the stationary probabilities. Through numerical examples, we discuss the effect of the system parameters and the breakdown disciplines on performance.     

Tutorial and Survey Articles: An introduction to Petri Nets

This paper describes the fundamental concepts and characteristics of Petri nets (PNs) that make them a significant tool for modeling and analyzing asynchronous systems with concurrent and parallel activities and follows the extensions that improved the implementation capabilities of the original PNs.

Their first and most relevant extension was time modeling, a vital aspect of system performances not considered in the original version. There are several possibilities for introducing time in PNs. Among them, a technique that associates time with places is presented in some detail. As PNs tend to become cumbersome and time consuming when large and complex systems are involved, a method for decomposing timed PNs of open queuing networks is reviewed here.

Though initially developed as an information/computer-based technique, PNs were immediately adopted in a variety of application areas, such as manufacturing, design, planning and control. Viewed through a more recently developed programming perspective, the ordinary PNs became “high level” PNs suitable for defining different data types and for applying hierarchical approaches.

It is expected that the robust theoretical basis of this tool coupled with its visual and flexibility features will continue to appeal to researchers and practitioners alike in a variety of domains and as a result will continue to evolve and expand.     

A framework for 3D model reconstruction in reverse engineering

We present a framework for 3D model reconstruction, which has potential applications to a spectrum of engineering problems with impacts on rapid design and prototyping, shape analysis, and virtual reality. The framework, composed of four main components, provides a systematic solution to reconstruct geometric model from the surface mesh of an existing object. First, the input mesh is pre-processed to filter out noise. Second, the mesh is partitioned into segments to obtain individual geometric feature patches. Then, two integrated solutions, namely solid feature based strategy and surface feature based strategy, are exploited to reconstruct primitive features from the segmented feature patches. Finally, the modeling operations, such as solid boolean and surface trimming operations, are performed to “assemble” the primitive features into the final model. The concepts of “feature”, “constraint” and “modeling history” are introduced into the entire reconstruction process so that the design intents are retrieved and exhibited in the final model with geometrical accuracy, topological consistency and flexible editability. A variety of industrial parts have been tested to illustrate the effectiveness and robustness of our framework.     

基于随机对象Petri网的柔性制造系统性能分析

为了增强传统对象Petri网的定量分析能力,提出随机对象Petri网模型。该模型具备随机性和层次特性,获得与随机Petri网的等价关系,从宏观和微观2个层面对系统进行性能分析,并将该模型应用到柔性制造系统中。实验结果表明,该系统保留了面向对象的建模能力,具有较强的定量分析能力。     

一种基于CIPN的网络协议建模方法*

基于Petri网的网络协议建模技术需要更有效地与现有通用网络协议仿真技术协同工作,结合CPN和IPN,提出了一种新的Petri网派生类CIPN用于网络协议的建模和形式化分析,突出了协议的离散事件系统特性。给出了CIPN的定义,并讨论了CIPN的运行机制,证明了CIPN事件可观测性的充要条件。通过一个MACA协议作为示例,完成了从网络协议的一般CPN模型到CIPN模型的等价性转换,并利用CIPN的事件可观测性定理对MACA协议进行了事件观测性分析。     

A component framework for system modeling based on high-level replacement systems

The aim of this paper is to present a generic component framework for system modeling that satisfies main requirements for component-based development in software engineering. In this sense, we have defined a framework that can be used, by providing an adequate instantiation, in connection with a large class of semi-formal and formal modeling techniques. Moreover, the framework is also flexible with respect to the connection of components, providing a compositional semantics of components. This means more precisely that the semantics of a system can be inferred from the semantics of its components. In contrast to other component concepts for data type specification techniques, our component framework is based on a generic notion of transformations. In particular, refinements and transformations are used to express intradependencies, between the export interface and the body of a component, and interdependencies, between the import and the export interfaces of different components. The generic component framework generalizes module concepts for different kinds of Petri nets and graph transformation systems proposed in the literature, and seems to be also suitable for visual modeling techniques, including parts of the UML, if these techniques provide a suitable refinement or transformation concept. In this paper the generic approach is instantiated in two steps. First to high-level replacement systems generalizing the transformation concept of graph transformations. In a second step it is further instantiated to low-level and high-level Petri nets. To show applicability we present sample components from a case study in the domain of production automation as proposed in a priority program of the German Research Council (DFG).     

An agent-based distributed computational experiment framework for virtual supply chain network development

This paper focuses on research on virtual supply chain networks instead of real supply chain networks by making use of agent technology and computational experiment method. However, the recent research is inefficient in computational experiment modeling and lack of a related methodological framework. This paper proposes an agent-based distributed computational experiment framework with in-depth study of material flow, information flow and time flow modeling in supply chain networks. In this framework, a matrix-based formal representation method for material flow, a task-centered representation method for information flow and an agent-based time synchronization mechanism for time flow are proposed to aid building a high quality computational experiment model for a multi-layer supply chain network. In order to conduct the model, a computational experiment architecture for virtual supply chain networks is proposed. In this architecture, coordination mechanisms among agents based on material flow, information flow and time flow as well as consistency check methods for computational experiment models are discussed. Finally, an implementation architecture of the framework is given and a case of virtual supply chain network is developed to illustrate the application of the framework. The computational experiment results of the case show that the proposed framework, not only feasible but correct, has sound advantages in virtual supply chain network development, computational experiment modeling and implementation.     

A framework for the verification of infinite-state graph transformation systems

We propose a technique for the analysis of infinite-state graph transformation systems, based on the construction of finite structures approximating their behaviour. Following a classical approach, one can construct a chain of finite under-approximations (k-truncations) of the Winskel style unfolding of a graph grammar. More interestingly, also a chain of finite over-approximations (k-coverings) of the unfolding can be constructed. The fact that k-truncations and k-coverings approximate the unfolding with arbitrary accuracy is formalised by showing that both chains converge (in a categorical sense) to the full unfolding. We discuss how the finite over- and under-approximations can be used to check properties of systems modelled by graph transformation systems, illustrating this with some small examples. We also describe the Augur tool, which provides a partial implementation of the proposed constructions, and has been used for the verification of larger case studies.     

Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems

In this paper an approach to on-line diagnosis of discrete event systems based on labeled Petri nets is presented. The approach is based on the notion of basis markings and justifications and it can be applied both to bounded and unbounded Petri nets whose unobservable subnet is acyclic. Moreover it is shown that, in the case of bounded Petri nets, the most burdensome part of the procedure may be moved off-line, computing a particular graph called Basis Reachability Graph.Finally, the effectiveness of the proposed procedure is analyzed applying a MATLAB diagnosis toolbox we developed to a manufacturing example taken from the literature.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

生化网络的随机Petri网建模与分析

细胞的行为是随机性的,学习细胞中的随机性有助于理解细胞的组织,设计和进化。建立、确认和分析随机的生化网络模型是当前计算系统生物学领域的一个重要研究主题。当前,标准的Petri网模型已经成为生化网络模拟和定性分析的有力工具。尝试使用随机Petri网对生化网络进行建模与分析,简单描述了随机Petri网理论对标准Petri网的扩充,通过对二聚作用和肌动蛋白这两个典型例子的建模与演化模拟,介绍、论证了随机Petri网理论的新应用。     

On-line fault detection in discrete event systems by Petri nets and integer linear programming

The paper addresses the fault detection problem for discrete event systems in a Petri Net (PN) framework. Assuming that the structure of the PN model and the initial marking are known, faults are modelled by unobservable transitions. Moreover, we assume that there may be additional unobservable transitions associated with the system legal behaviour and that the marking reached after the firing of any transition is unknown. The proposed diagnoser works on-line: it waits for the firing of an observable transition and employs an algorithm based on the definition and solution of some integer linear programming problems to decide whether the system behaviour is normal or exhibits some possible faults. The results characterize the properties that the PN modelling the system fault behaviour has to fulfill in order to reduce the on-line computational effort.     

一种基于线性逻辑的Petri网分析方法

1 引言 Petri网是一种用网状图形表示系统模型的方法,能够从组织结构、控制和管理的角度,精确描述系统中事件(变迁)之间的依赖(顺序)和不依赖(并发)关系。Petri网理论提供了强大的分析方法,如不变量分析、系统性能分析(如活性)等以证明系统的正确性。近年来Petri网也被用来表示知识推理,例如用于诊断和监控,这就需要发展一种关于Petri网行为的推理主题。有些学者把经典逻辑和Petri网相结合,用Petri网表示产生式规则系统,网的框架代表基于产生式规则     

A framework for virtual enterprise operation management

This paper presents researches on operation management for virtual enterprises (VEs). A virtual enterprise is a temporary alliance of member enterprises (MEs) formed to exploit fast-changing opportunities. During the operation of a virtual enterprise, its constituent member enterprises, which are geographically distributed and organizationally independent, collaborate with each other to execute the whole business process (BP) of the virtual enterprise. With the aim of addressing business integration for virtual enterprises, this paper develops a framework for virtual enterprise operation management. From the viewpoint of business processes, carried out is integral research on business process modeling, analyzing, and managing for virtual enterprises. Both the distributed business process model and the model of the virtual enterprise itself are established. The former provides the functional basis of the virtual enterprise operation, while the latter provides its structural basis. Further, the two models are integrated through the loading from the distributed business process model to the virtual enterprise model. Through such model separation and integration, business process management for virtual enterprises is enacted and business integration for virtual enterprises is achieved.     

Petri net modules in the transformation-based component framework

Component-based software engineering needs to be backed by thorough formal concepts and modeling techniques. This paper combines two concepts introduced independently by the two authors in previous papers. On one hand, the concept of Petri net modules introduced at IDPT 2002 in Padberg [J. Padberg, Petri net modules, Journal on Integrated Design and Process Technology 6 (4) (2002) 105–120], and on the other hand a generic component framework for system modeling introduced at FASE 2002 in Ehrig et al. [H. Ehrig, F. Orejas, B. Braatz, M. Klein, M. Piirainen, A generic component concept for system modeling, in: Proceedings of FASE ’02, Lecture Notes in Computer Science, vol. 2306, Springer, 2002]. First we develop a categorical formalization of the transformation based approach to components that is based on pushouts. This is the frame in which we show that Petri net modules can be considered as an instantiation of the generic component framework. This allows applying the transformation based semantics and compositionality result of the generic framework to Petri net modules. In addition to general Petri net modules we introduce Petri net modules preserving safety properties which can be considered as another instantiation of pushout based formalization of the generic framework.     

基于平行Petri网的制造系统调度与控制一体化方法

为了消除制造系统调度层与控制层之间的隔阂, 实现对生产事件快速灵活响应, 本文提出了一种调度与控制一体化的方法. 首先, 定义了一种新型Petri网模型, 即平行Petri网, 从而集成地描述了传感器、执行器、任务和资源信息, 构建制造系统的信息物理系统模型; 其次, 提出了一种从平行Petri网到赋时Petri网的抽象简化方法, 大规模压缩优化调度所需搜索的状态空间; 再次, 定义了策略Petri网以描述最优调度策略. 最后, 给出了平行Petri网与策略Petri网同步执行算法, 使得平行Petri网与物理系统同步执行.     

An Efficient Method for Computing Exact State Space of Petri Nets With Stopwatches

In this paper, we address the issue of the formal verification of real-time systems in the context of a preemptive scheduling policy. We propose an algorithm which computes the state-space of the system, modeled as a time Petri net with stopwatches, exactly and efficiently, by the use of Difference Bounds Matrices (DBM) whenever possible and automatically switching to more time and memory consuming general (convex) polyhedra only when required. We propose a necessary and sufficient condition for the need of general polyhedra. We give experimental results comparing our implementation of the method to a full DBM over-approximation and to an exact computation with only general polyhedra.     

An Improvement of McMillan's Unfolding Algorithm

McMillan has recently proposed a new technique to avoid the state explosion problem in the verification of systems modelled with finite-state Petri nets. The technique requires to construct a finite initial part of the unfolding of the net. McMillan's algorithm for this task may yield initial parts that are larger than necessary (exponentially larger in the worst case). We present a refinement of the algorithm which overcomes this problem.