Fluid approximation of Petri net models with relatively small populations

Fluidization is an appealing relaxation technique based on the removal of integrality constraints in order to ease the analysis of discrete Petri nets. The result of fluidifying discrete Petri nets are the so called Fluid or Continuous Petri nets. As with any relaxation technique, discrepancies among the behaviours of the discrete and the relaxed model may appear. Moreover, such discrepancies may have a comparatively bigger effect when the population of the system, the marking in Petri net terms, is “relatively” small. This paper proposes two complementary approaches to obtain a better fluid approximation of discrete Petri nets. The first one focuses on untimed systems and is based on the addition of places that are implicit in the untimed discrete system but not in the continuous. The idea is to cut undesired spurious solutions whose existence worsens the fluidization. The second one focuses on a particular situation that can severely affect the quality of fluidization in timed systems. Namely, such a situation arises when the enabling degree of a transition is equal to 1. This last approach aims to alleviate such a state of affairs, which is termed the bound reaching problem, on systems under infinite servers semantics.     

Toward the use of Petri nets for the formalization of OWL-S choreographies

In this paper, we present a Petri net-based approach for modeling the choreography of semantic Web services which are described following the OWL-S specification. In our approach, each control construct of the OWL-S choreography is represented through a Petri net pattern that captures formally its operational semantics. The main difference between our work and the main proposals that model the semantics of OWL-S services choreography is that, although both approaches represent the service choreography with Petri nets, our proposal is also concerned with the practical execution of the Petri nets by the client. Therefore we also represent the flow of data, the outputs transformations, the effects in the environment, in addition to the structures that control the choreography of the services in our Petri net models. The implementation of the OWL-S choreography is performed in a Petri net ontology-based engine. This is another difference with traditional approaches that only use Petri nets for the analysis of the service properties. Furthermore, the use of an underlying ontology engine for supporting both the domain models of OWL-S services and the Petri net models provides several advantages in terms of reasoning, extension, and reuse.     

Half a century after Carl Adam Petri’s Ph.D. thesis: A perspective on the field

It is certainly worth remarking on half a century of a work defining a landmark in Discrete Event Dynamic Systems (DEDS) theory. This invited contribution aims to combine some historical facts with elements of a conceptual view on concurrent DEDS, giving pointers about the development of the field. Simplifying the historical trajectory, it can be said that the seed sown by Carl Adam Petri in 1962 first grew in America (essentially until the mid 1970s), where an appropriate intellectual ambiance existed in computer science, business process management and switching systems design. Later, many other new lines of activity, including logic control and performance evaluation, flourished in Europe. Today Petri nets are widespread all over the world. The conceptual paradigm of Petri nets deals inter alia with modeling, logical analysis, performance evaluation, parametric optimization, dynamic control, diagnosis and implementation issues. In summary, multidisciplinary in themselves, formalisms belonging to the Petri nets paradigm may cover several phases of the life-cycle of complex DEDS.Given the hundreds of research and text monographs on Petri nets, together with the many thousands of theoretical and applied contributions on the subject, not to mention the ISO (International Organization for Standardization) or IEC (International Electrotechnical Commission) standards for the use of Petri nets in engineering, this work cannot hope to be a complete survey or a tutorial in the more classical sense. It is more of an impressionistic overview of the field.     

Well-structured languages

This paper introduces the notion of well-structured language. A well-structured language can be defined by a labelled well-structured transition system, equipped with an upward-closed set of accepting states. That peculiar class of transition systems has been extensively studied in the field of computer-aided verification, where it has direct an important applications. Petri nets, and their monotonic extensions (like Petri nets with non-blocking arcs or Petri nets with transfer arcs), for instance, are special subclasses of well-structured transition systems. We show that the class of well-structured languages enjoy several important closure properties. We propose several pumping lemmata that are applicable respectively to the whole class of well-structured languages and to the classes of languages recognized by Petri nets or Petri nets with non-blocking arcs. These pumping lemmata allow us to characterize the limits in the expressiveness of these classes of language. Furthermore, we exploit the pumping lemmata to strictly separate the expressive power of Petri nets, Petri nets with non-blocking arcs and Petri nets with transfer arcs.     

基于Petri网的Web服务BPEL4WS建模与分析

描述了Web服务业务流程执行语言(BPEL4WS或BPEL)的Petri网建模方法，利用网结构描述基于Web服务业务流程的行为特性。在对BPEL4WS的结构性活动和故障补偿处理机制进行逐层分析的基础上，提出了一个利用Petri网的逐步求精技术对流程进行建模的算法。然后结合具体实例阐述了利用该算法建模的详细过程，并对所生成的Petri网模型进行了完整性（soundness)验证     

On the Regularity of Petri Net Languages

Petri nets are known to be useful for modeling concurrent systems. Once modeled by a Petri net, the behavior of a concurrent system can be characterized by the set of all executable transition sequences, which in turn can be viewed as a language over an alphabet of symbols corresponding to the transitions of the underlying Petri net. In this paper, we study the language issue of Petri nets from a computational complexity viewpoint. We analyze the complexity of theregularity problem(i.e., the problem of determining whether a given Petri net defines an irregular language or not) for a variety of classes of Petri nets, includingconflict-free,trap-circuit,normal,sinkless,extended trap-circuit,BPP, andgeneralPetri nets. (Extended trap-circuit Petri nets are trap-circuit Petri nets augmented with a specific type ofcircuits.) As it turns out, the complexities for these Petri net classes range from NL (nondeterministic logspace), PTIME (polynomial time), and NP (nondeterministic polynomial time), to EXPSPACE (exponential space). In the process of deriving the complexity results, we develop adecomposition approachwhich, we feel, is interesting in its own right, and might have other applications to the analysis of Petri nets as well. As a by-product, an NP upper bound of the reachability problem for the class of extended trap-circuit Petri nets (which properly contains that of trap-circuit (and hence, conflict-free) and BPP-nets, and is incomparable with that of normal and sinkless Petri nets) is derived.     

有色Petri网协作模型的BPEL代码实现

Web服务业务流程执行语言（BPEL）提供了有力的技术来聚合封装的功能以及定义高质量的Web服务,然而,尽管功能强大,但是BPEL却难于使用。另一方面,有色Petri（CPNs）可以用于模拟、分析以及校验Web服务。为了在CPNs协作模型和业务流程的执行之间建立一座桥梁,给出了基于CPNs从过程模型驱动演绎出一致的BPEL代码的方法。首先,把CPNs协作模型转换为结构工作流网模型;然后,把工作流网模转换为BPEL代码,最后,通过电话机故障修理的案例研究,说明了算法的有效性。     

Petri net based formal analysis for multimedia conferencing services orchestration

Development of services that span over the Internet and Telecom networks is driving significant efforts towards the integrated of services offered by Telecom operators. Service-oriented communication (SOC) is a new trend in the industry to enable communication through a service-oriented architecture (SOA) and thereby package communications as services. In this paper, we firstly introduce the design and implementation for business process execution language (BPEL) based multimedia conferencing communication services orchestration, and mainly focus on the issue of guaranteeing the correctness of such applications, we presents a Petri net-based approach to analyzing the BPEL based multimedian conferencing communication services orchestration correctness and also a set of translation rules is proposed to transform BPEL processes into Petri nets. Especially, we define the correctness of multimedia conferencing services orchestration and address the verification method based on Petri nets. The algorithms and corresponding reliable issues have been proposed, such as the coverability tree for detecting flow safeness, the incidence matrix & state equation for finding reachable issues, and a transitive matrix for detecting a deadlock problem. With the Petri Net Markup Language (PNML) are introduced to transform a orchestrated services into a Petri net model, and providing an automated support for the formal analysis of their behavior. Finally, we give the conclusions.     

Petri net-based process monitoring: a workflow management system for process modelling and monitoring

Nowadays business process management is becoming a fundamental piece of many industrial processes. To manage the evolution and interactions between the business actions it is important to accurately model the steps to follow and the resources needed by a process. Workflows provide a way of describing the order of execution and the dependencies between the constituting activities of business processes. Workflow monitoring can help to improve and avoid delays in industrial environments where concurrent processes are carried out. In this article a new Petri net extension for modelling workflow activities together with their required resources is presented: resource-aware Petri nets (RAPN). An intelligent workflow management system for process monitoring and delay prediction is also introduced. Resource aware-Petri nets include time and resources within the classical Petri net workflow representation, facilitating the task of modelling and monitoring workflows. The workflow management system monitors the execution of workflows and detects possible delays using RAPN. In order to test this new approach, different services from a medical maintenance environment have been modelled and simulated.     

Can I find a partner? Undecidability of partner existence for open nets

We study open nets as Petri net models of web services, with a link to the practically relevant language WS-BPEL. For those nets, we investigate the problem of operability which we consider as fundamental as the successful notion of soundness for workflow nets, i.e., Petri net models of business processes and workflows. While we could give algorithmic solutions to the operability problem for subclasses of open nets in earlier work, this article shows that the problem is in general undecidable.     

Verifying soundness of business processes: A decision process Petri nets approach

This paper presents a trajectory-tracking approach for verifying soundness of workflow/Petri nets represented by a decision-process Petri net. Well-formed business processes correspond to sound workflow nets. The advantage of this approach is its ability to represent the dynamic behavior of the business process. We show that the problem of finding an optimum trajectory for validation of well-formed business processes is solvable. To prove our statement we use the Lyapunov stability theory to tackle the soundness verification problem for decision-process Petri nets. As a result, applying Lyapunov theory, the well-formed verification (soundness) property is solved showing that the workflow net representation using decision process Petri nets is uniformly practically stable. It is important to note that in a complexity-theoretic sense checking the soundness property is computationally tractable, we calculate the computational complexity for solving the problem. We show the connection between workflow nets and partially ordered decision-process Petri net used for business process representation and analysis. Our computational experiment of supply chains demonstrate the viability of the modeling and solution approaches for solving computer science problems.     

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.     

用UML与Petri网为智能代理建模

统一建模型语言（UML）已经成为软件系统的分析与设计的标准工具，但由它扩充而成的代理统一建模型语言（AUML）还没变成一个标准，目前的AUML规格说明还有很多的局限性，还不能胜任多代理系统的开发．Petri网是仿真、验证软件系统执行的正确性与有效性的形式化工具．本文主要分析当前AUML规格说明和Petri网概念．找出它们之间的结合点，提出用Petri网扩充AUML的方法．将其应用于多代理系统的开发，就能实施之前运用Petri网进行系统的正确性与有效性验证．     

基于Petri网的工作流过程建模

业务过程建模是整个工作流管理系统的基础,选择一种高效的建模技术对复杂多变的实际业务流程进行形式化表示对构建一个灵活的工作流管理系统起着至关重要的作用。本文利用了Petri网技术给业务过程建模,构造了一个灵活可分析的过程模型：首先介绍了相关的基于Petri网的工作流建模技术,接着描述了Petri网到工作流过程模型执行的映 射,然后给出了一个具体的基于Petri网建模方式的实例,最后利用随机Petri网和概率论的一些知识对该模型进行了时间性能分析。     

Prediction of business process durations using non-Markovian stochastic Petri nets

Companies need to efficiently manage their business processes to deliver products and services in time. Therefore, they monitor the progress of individual cases to be able to timely detect undesired deviations and to react accordingly. For example, companies can decide to speed up process execution by raising alerts or by using additional resources, which increases the chance that a certain deadline or service level agreement can be met. Central to such process control is accurate prediction of the remaining time of a case and the estimation of the risk of missing a deadline.To achieve this goal, we use a specific kind of stochastic Petri nets that can capture arbitrary duration distributions. Thereby, we are able to achieve higher prediction accuracy than related approaches. Further, we evaluate the approach in comparison to state of the art approaches and show the potential of exploiting a so far untapped source of information: the elapsed time since the last observed event. Real-world case studies in the financial and logistics domain serve to illustrate and evaluate the approach presented.     

Abstract processes of place/transition systems

A well-known problem in Petri net theory is to formalise an appropriate causality-based concept of process or run for place/transition systems. The so-called individual token interpretation, where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig, is often considered too detailed. The problem of defining a fully satisfying more abstract concept of process for general place/transition systems has so-far not been solved. In this paper, we recall the proposal of defining an abstract notion of process, here called BD-process, in terms of equivalence classes of Goltz-Reisig processes, using an equivalence proposed by Best and Devillers. It yields a fully satisfying solution for at least all one-safe nets. However, for certain nets which intuitively have different conflicting behaviours, it yields only one maximal abstract process. Here we identify a class of place/transition systems, called structural conflict nets, where conflict and concurrency due to token multiplicity are clearly separated. We show that, in the case of structural conflict nets, the equivalence proposed by Best and Devillers yields a unique maximal abstract process only for conflict-free nets. Thereby BD-processes constitute a simple and fully satisfying solution in the class of structural conflict nets.     

Scheduling and control of real-time systems based on a token player approach

Petri nets are a powerful formalism for the specification and verification of concurrent systems, such as sequential systems and manufacturing systems. To deal with real-time systems whose time issues become essential, different extensions of Petri nets with time have been proposed in the literature. In this paper, a new scheduling and control technique for real-time systems modeled by ordinary P-time Petri nets is proposed. Its goal is to provide a scheduling for a particular firing sequence, without any violation of timing constraints ensuring that no deadline is missed. It is based on the firing instant notion and it consists in determining an inequality system generated for a possible evolution (in terms of a feasible firing sequence for the untimed underlying Petri net) of the model. This system can be used to check reachability problems as well as evaluating the performances of the model considered and determining the associated control for a definite functioning mode and it introduces partial order on the execution of particular events.     

Automatic construction of systems of distributed components from nested Petri nets models

Multi-level multi-agent systems (MASs) with dynamic structure are widely used in solving important applied problems in telecommunication, transportation, social, and other systems. Therefore, ensuring correct behavior of such systems is an actual and important task. One of the most error-prone stages of system development in the framework of model-oriented approach is the implementation stage, in the course of which a program code is constructed based on the model developed. This paper presents an algorithm for automated translation of MAS models represented as nested Petri nets into systems of distributed components. Nested Petri nets are the extension of Petri nets in the framework of the nets-within-nets approach, which assumes that tokens in a Petri net may themselves be Petri nets, possess autonomous behavior, and interact with other tokens of the net. This makes it possible to model MASs with dynamic structure in a natural way. The translation presented in this paper preserves distribution level and important behavioral properties (safety, liveness, and conditional liveness) of the original model and ensures fairness of the target system execution. The use of such translation makes it possible to automate construction of distributed MASs by models of nested Petri nets. As a test example, translation of nested Petri nets into systems of distributed components was implemented on the basis of the EJB component technology.     

Model checking Petri nets with names using data-centric dynamic systems

Petri nets with name creation and management (\({\nu}\)-PNs) have been recently introduced as an expressive model for dynamic (distributed) systems, whose dynamics are determined not only by how tokens flow in the system, but also by the pure names they carry. On the one hand, this extension makes the resulting nets strictly more expressive than P/T nets: they can be exploited to capture a plethora of interesting systems, such as distributed systems enriched with channels and name passing, service interaction with correlation mechanisms, and resource-constrained workflow nets that explicitly account for process instances. On the other hand, fundamental properties like coverability, termination and boundedness are decidable for \({\nu}\)-PNs. In this work, we go one step beyond the verification of such general properties, and provide decidability and undecidability results of model checking \({\nu}\)-PNs against variants of first-order \({\mu}\)-calculus, recently proposed in the area of data-aware process analysis. While this model checking problem is undecidable in the general case, decidability can be obtained by considering different forms of boundedness, which still give raise to an infinite-state transition system. We then ground our framework to tackle the problem of soundness checking over workflow nets enriched with explicit process instances and resources. Notably, our decidability results are obtained via a translation to data-centric dynamic systems, a recently devised framework for the formal specification and verification of data-aware business processes working over full-fledged relational databases with constraints. In this light, our results contribute to the cross-fertilization between the area of formal methods for concurrent systems and that of foundations of data-aware processes, which has not been extensively investigated so far.     

Semantics for consistent activation in context-oriented systems

ContextContext-oriented programming languages provide dedicated programming abstractions to define behavioral adaptations and means to combine those adaptations dynamically according to sensed context changes. Some of these languages feature programming abstractions to explicitly define interaction dependencies among contexts. However, the semantics of context activation and the meaning of dependency relations have been described only informally, which in some cases has led to incorrect specifications, faulty implementations and inconsistent system behavior.ObjectiveWith the aim of avoiding faulty implementations and inconsistencies during system execution, this paper proposes both a formal and run-time model of contexts, context activation and context interaction.MethodAs a formal and computational basis, we introduce context Petri nets, a model based on Petri nets, which we found to match closely the structure of contexts in context-oriented systems. The operational semantics of Petri nets permits the modeling of run-time context activations. Existing Petri net analyses allow us to reason about system properties. As validation, we carried out small and medium-sized case studies.ResultsIn the cases explored, context Petri nets served effectively as underlying run-time model to ensure that declared context interaction constraints remain consistent during context manipulation. Moreover, context Petri nets enabled us to analyze certain properties regarding the activation state of particular contexts.ConclusionContext Petri nets thus proved to be appropriate to encode and manage the semantics of context activation, both formally and computationally, so as to preserve the consistency of context-oriented systems.