Symbolic execution of concurrent systems using Petri nets

Techniques for analyzing sequential programs in order to improve their reliability have been widely studied in the past. Among the most interesting analysis techniques, we consider symbolic execution. However, analysis techniques for concurrent programs, and in particular symbolic execution, are still an open research area. In this paper, we define a method for symbolic execution of concurrent systems, based on an extension of the Petri net formalism, called EF nets. EF nets are a powerful, highly expressive and general formalism. Depending on the level of abstraction of actions and predicates that one associates to the transitions of the net, EF nets can be used as a high-level specification formalism for concurrent systems, or as a lower level internal representation of concurrent programs. Thus, the model is not dependent on a particular concurrent programming language, but it is flexible enough to be the kernel model for the representation of a wide set of systems and programming languages. In the paper, in order to support the analysis of a concurrent system or program, at first a general algorithm for symbolically executing an EF net is defined. Then, a more efficient algorithm is given for the particular, though important, subclass of EF nets, defined as safe EF nets. Such algorithm is proved to significantly help in reducing the amount of information needed to characterize a symbolic execution. Both the modelling power of the EF nets and the usefulness of the concurrent symbolic execution algorithms defined are illustrated by means of a case study.     

Reachability analysis of real-time systems using time Petri nets

Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.     

Uncertainty management in expert systems using fuzzy Petri nets

The paper aims at developing new techniques for uncertainty management in expert systems for two generic class of problems using fuzzy Petri nets that represent logical connectivity among a set of imprecise propositions. One class of problems deals with the computation of fuzzy belief of any proposition from the fuzzy beliefs of a set of independent initiating propositions in a given network. The other class of problems is concerned with the computation of steady-state fuzzy beliefs of the propositions embedded in the network, from their initial fuzzy beliefs through a process called belief revision. During belief revision, a fuzzy Petri net with cycles may exhibit “limit cycle behavior” of fuzzy beliefs for some propositions in the network. No decisions can be arrived at from a fuzzy Petri net with such behavior. To circumvent this problem, techniques have been developed for the detection and elimination of limit cycles. Further, an algorithm for selecting one evidence from each set of mutually inconsistent evidences, referred to as nonmonotonic reasoning, has also been presented in connection with the problems of belief revision. Finally, the concepts proposed for solving the problems of belief revision have been applied successfully for tackling imprecision, uncertainty, and nonmonotonicity of evidences in an illustrative expert system for criminal investigation     

Fuzzy rule base systems verification using high-level Petri nets

In this paper, we propose a Petri nets formalism for the verification of rule-based systems. Typical structural errors in a rule-based system are redundancy, inconsistency, incompleteness, and circularity. Since our verification is based on Petri nets and their incidence matrix, we need to transform rules into a Petri nets first, then derive an incidence matrix from the net. In order to let fuzzy rule-based systems detect above the structural errors, we are presenting a Petri-nets-based mechanism. This mechanism consists of three phases: rule normalization, rules transformation, and rule verification. Rules will be first normalized into Horn clauses, then transform the normalized rules into a high-level Petri net, and finally we verify these normalized rules. In addition, we are presenting our approach to simulate the truth conditions which still hold after a transition firing and negation in Petri nets for rule base modeling. In this paper, we refer to fuzzy rules as the rules with certainty factors, the degree of truth is computed in an algebraic form based on state equation which can be implemented in matrix computation in Petri nets. Therefore, the fuzzy reasoning problems can be transformed as the liner equation problems that can be solved in parallel. We have implemented a Petri nets tool to realize the mechanism presented fuzzy rules in this paper.     

Distributed control systems simulation using high level Petri nets

To deal with the complexity of the implementation of control systems for flexible manufacturing systems, formal methods of design are needed. In this work the modeling and validation tool selected is high level Petri nets. Based on this approach we have studied the problems that a distributed implementation can introduce. For the evaluation of different strategies of the model implementation and the scheduling of production tasks a simulator has been constructed. This simulator has been written in Ada language.     

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网 (即所有前向路径子网是状态机 )的状态反馈控制器设计. 在非并发的假设条件下, 所综合的控制器是最大允许.     

Compositional schedulability analysis of real-time systems using time Petri nets

This paper presents an approach to the schedulability analysis of real-time systems modeled in time Petri nets by separating timing properties from other behavioral properties. The analysis of behavioral properties is conducted based on the reachability graph of the underlying Petri net, whereas timing constraints are checked in terms of absolute and relative firing domains. If a specific task execution is schedulable, we calculate the time span of the task execution, and pinpoint nonschedulable transitions to help adjust timing constraints. A technique for compositional timing analysis is also proposed to deal with complex task sequences, which not only improves efficiency but also facilitates the discussion of the reachability issue with regard to schedulability. We identified a class of well-structured time Petri nets such that their reachability can be easily analyzed.     

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.     

Decision support in flexible manufacturing systems using timed Petri nets

Contingency response in a dynamic system such as a flexible manufacturing system requires that the system be able to identify and evaluate a number of alternatives. This paper shows how dummy transitions can be incorporated in a timed Petri net to model contingencies in the system such as machine or tool breakdown, quality deterioration, or production volume surge, etc. An algorithm is presented to evaluate system response in the steady state. A decision support system complete with a problem processor (incorporating the Petri net model), a database, and a query system is outlined.     

A deadlock prevention approach for a class of timed Petri nets using elementary siphons

To solve the problem of deadlock prevention for timed Petri nets, an effective deadlock prevention policy based on elementary siphons is proposed in this paper. Without enumerating reachable markings, deadlock prevention is achieved by adding monitors for elementary siphons, increasing control depth variables when necessary, and removing implicit, liveness‐restricted and redundant control places. The final supervisor is live. First, a timed Petri net is stretched into a stretched Petri net (SPN). Unchanging the system performance, each transition in the SPN has a unit delay time. Then the siphon‐control‐based approach is applied. Monitors computed according to the marking constraints are added to the SPN model to ensure all strict minimal siphons in the net invariant‐controlled. A liveness‐enforcing supervisor with simple structure can be obtained by reverting the SPN into a TdPN. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.     

Performance evaluation of parallel systems by using unboundedgeneralized stochastic Petri nets

Methods of calculating efficiently the performance measures of parallel systems by using unbounded generalized stochastic Petri nets are presented. An explosion in the number of states to be analyzed occurs when unbounded places appear in the model. The state space of such nets is infinite, but it is possible to take advantage of the natural symmetries of the system to aggregate the states of the net and construct a finite graph of lumped states which can easily be analyzed. With the methods developed, the unbounded places introduce a complexity similar to that of safe places of the net. These methods can be used to evaluate models of open parallel systems in which unbounded places appear; systems which are k-bounded but are complex and have large values of k can also be evaluated in an appropriate way. From the steady-state solution of the model, it is possible to obtain automatically the performance measures of parallel systems represented by this type of net     

Real-time scheduling of batch systems using Petri nets and linear logic

This paper presents an approach to model, design and verify scenarios of real-time systems used in the scheduling and global coordination of batch systems. The initial requirements of a system specified with sequence diagrams are translated into a single p-time Petri net model representing the global behavior of the system. For the Petri net fragments involved in conflicts, symbolic production and consumption dates assigned to tokens are calculated based on the sequent calculus of linear logic. These dates are then used for off-line conflict resolution within a token player algorithm used for scenario verification of real-time specifications and which can be seen as a simulation tool for UML interaction diagrams.     

Modelling of batch production systems using Petri nets with dynamic tokens

This article deals with the qualitative modelling of batch production plants. The approach held is Petri net based. First a definition of a three-level net formalism is presented; the formalism extends the Valk's approach of nets in nets in which the tokens are other nets; in this extension the lower level net handles symbolic tokens. Then a methodology for the modelling of batch processes is proposed; in this methodology the upper level describes the plant layout, the next level models an entity that goes with the batch through the plant and specifies the material and the process routes that the batch must follow, and the third level represents detailed treatments to perform into the process cells using specific equipment. The use of the modelling formalism is illustrated through an example dealing with the coordination of a batch manufacturing system.