Search

1.1 Relationship between Petri net and linear logic Petri nets were first introduced by Petri in his seminal Ph.D. thesis, and both the theory and the applications of his model have flourished in concurrency theory (Reisig & Rozenberg, 1998a; Reisig & Rozenberg, 1998b). The relationships between Petri nets and linear logics have been studied by many researchers (Engberg & Winskel, 1997; Farwer, 1999; Hirai, 2000; Hirai 1999; Ishihara & Hiraish, 2001; Kamide, 2004, Kamide, 2006; Kanovich, 1995; Kanovich 1994; LarcheyWendling & Galmiche, 1998; Larchey-Wendling & Galmiche, 2000; Lilius, 1992; Mart -Oliet & Meseguer, 1991; Okada, 1998; Tanabe, 1997). A category theoretical investigation of such a relationship was given by Mart -Oliet and Meseguer (Mart -Oliet & Meseguer, 1991), purely syntactical approach using Horn linear logic was established by Kanovich (Kanovich, 1995; Kanovich 1994), a naive phase linear logic for a certain class of Petri nets was given by Okada (Okada, 1998), a linear logical view of object Petri nets were studied by Farwer (Farwer, 1999), and various Petri net interpretations of linear logic using quantale models were obtained by Ishihara and Hiraishi (Ishihara & Hiraish, 2001), Engberg and Winskel (Engberg & Winskel, 1997), Larchey-Wendling and Galmiche (Larchey-Wendling & Galmiche, 1998; Larchey-Wendling & Galmiche, 2000), and Lilius (Lilius, 1992). Petri net interpretations using Kripke semantics for various fragments and extensions of intuitionistic linear logic were studied by Kamide (Kamide, 2004; Kamide, 2006c). In (Kamide, 2004), Petri net interpretations of various fragments of a spatio-temporal soft linear logic were discussed. In (Kamide, 2006c), Petri nets with inhibitor arcs, which were first introduced by Kosaraju (Kosaraju, 1973) to show the limitation of the usual Petri nets, were described using Kripke semantics for intuitionistic linear logic with strong negation. The approarches using Kripke semantics can obtain a very simple correspondence between Petri net and linear logic.

Predictive performance models are used increasingly throughout the phases of the software engineering lifecycle of distributed systems. However, as systems grow in size and complexity, building models that accurately capture the different aspects of their behavior becomes a more and more challenging task. The challenge stems from the limited model expressiveness on the one hand and the limited scalability of model analysis techniques on the other. This chapter presents a novel methodology for modeling and performance analysis of distributed systems [Kounev, 2006]. The methodology is based on queueing Petri nets (QPNs) which provide greater modeling power and expressiveness than conventional modeling paradigms such as queueing networks and generalized stochastic Petri nets. Using QPNs, one can integrate both hardware and software aspects of system behavior into the same model. In addition to hardware contention and scheduling strategies, QPNs make it easy to model software contention, simultaneous resource possession, synchronization, blocking and asynchronous processing. These aspects have significant impact on the performance of modern distributed systems. To avoid the problem of state space explosion, our methodology uses discrete event simulation for model analysis. We propose an efficient and reliable method for simulation of QPNs [Kounev & Buchmann, 2006]. As a validation of our approach, we present a case study of a real-world distributed system, showing how our methodology is applied in a step-by-step fashion to evaluate the system performance and scalability. The system studied is a deployment of the industry-standard SPECjAppServer2004 benchmark. A detailed model of the system and its workload is built and used to predict the system performance for several deployment configurations and workload scenarios of interest. Taking advantage of the expressive power of QPNs, our approach makes it possible to model systems at a higher degree of accuracy providing a number of important benefits. The rest of this chapter is organized as follows. In Section 2, we give a brief introduction to QPNs. Following this, in Section 3, we present a method for quantitative analysis of QPNs based on discrete event simulation. The latter enables us to analyze QPN models of realistic size and complexity. In Section 4, we present our performance modeling methodology for distributed systems. The methodology is introduced in a step-by-step

This chapter presents a systematic methodology for modeling and control of supply chain networks, especially focusing on formal representation and control synthesis aspects. A supply chain is represented as a discrete event dynamic system. The use of high-level Petri nets is proposed to formulate event related rules commonly seen in supply chains and analyze cause-effect relationships between events. Petri nets have been successfully introduced as an effective tool for describing control specifications and realizing the control in automated supply chain processes. The extended net representation of the productive task flows can provide more synthetic specifications for consistent management and control of supply chain systems by a top-down refinement methodology. Software implementation is described to simulate and control real supply chain processes.

Control of a large-scale automated manufacturing system is an important and challenging issue. Its discrete event system model represented by Petri nets tends to become highly complicated in structure, especially when there exist uncontrollable or unobservable events. The existing approaches are nontrivial to design both efficient and maximally permissive supervisors to impose constraints on an overall system. In this paper, instead of considering the control problem from an overall system perspective, we intend to transform an overall control problem into the one designing multiple controllers in parallel, each of which is much simpler in structure. A Petri net structure is decomposed via integer linear programming or a polynomial decomposition method to obtain multiple state-machine subnets that constitute a decentralized system. A necessary and sufficient condition for preserving the equivalence in terms of states and behaviors between the overall system and its decentralized version is reported. Constraints representing control requirements are further converted and enforced in the respective subnets. Then, supervisors are generated via a generalized mutual exclusion constraint method. By considering the deviations between the subnet control and overall control, this paper formulates a communication mechanism to guarantee that the decentralized system runs in an appropriate manner. Finally, two examples are presented to demonstrate the proposed approach.

The main contribution of this correspondence paper consists in a linear algebraic characterization of the admissible marking set relative to a Petri net with uncontrollable transitions, subject to a linear constraint. In more detail, given a linear constraint that limits the number of tokens in one place, an algorithm is proposed to compute an approximation of the admissible marking set in terms of a disjunction of transformed linear constraints. The optimality of the solution is guaranteed provided that certain conditions are satisfied during the intermediate steps of the iterative approach. In all the other cases, the set of markings described by the transformed constraints could be surely contained in the admissible marking set.

This paper presents an ordinary Petri net (PN)-based approach to the modeling and race-detection problems of programs for programmable logic controllers (PLCs). First, a PLC program is formalized by a graph where nodes represent contacts and coils. Second, an algorithm is proposed to translate this graph into an ordinary PN. Third, a method is presented to detect whether there exists a race in a program by using a reachability graph technique, to locate a race by introducing the race path, and to correct a race by analyzing the subnet that contains it. An example is utilized to illustrate the theoretic results.

Elaborate efforts have been made to eliminate fake markings and refine ${\omega }$ -markings in the existing modified or improved Karp–Miller trees for various classes of unbounded Petri nets since the late 1980s. The main issues fundamentally are incurred due to the generation manners of the trees that prematurely introduce some potentially unbounded markings with ${\omega }$ symbols and keep their growth into new ones. Aiming at addressing them, this work presents a non-Karp–Miller tree called a lean reachability tree (LRT). First, a sufficient and necessary condition of the unbounded places and some reachability properties are established to reveal the features of unbounded nets. Then, we present an LRT generation algorithm with a sufficiently enabling condition (SEC). When generating a tree, SEC requires that the components of a covering node are not replaced by ${\omega }$ symbols, but continue to grow until any transition on an output path of an unbounded place has been branch-enabled at least once. In return, no fake marking is produced and no legal marking is lost during the tree generation. We prove that LRT can faithfully express by folding, instead of equivalently representing, the reachability set of an unbounded net. Also, some properties of LRT are examined and a sufficient condition of deadlock existence based on it is given. The case studies show that LRT outperforms the latest modified Karp–Miller trees in terms of size, expressiveness, and applicability. It can be applied to the analysis of the emerging discrete event systems with infinite states.

The main purpose of this correspondence is to point out the fallacy of Theorem 1 in the paper that is mentioned in the title, a result that attempts to provide a structural characterization for the liveness of the Petri net class considered in the manuscript. The closing part of the correspondence also takes this opportunity to make some further remarks on the results that are claimed in the paper.

A novel scheme for simulating networked agent systems is presented. In this approach, the system is composed of identical communicating agents, which have multi-role capabilities in such a manner that they can perform diverse tasks, according to a given execution context. The agent’s behavior is modeled using a timed hybrid Petri net ( THPN) whose evolution, valid for all the agents, is computed off-line using Matlab. The agents are interconnected and simulated in a Java platform using the JADE middle-ware.

In this paper, we investigate the decidability and complexity of the fault diagnosis problem in unbounded labeled Petri nets. First, we show that checking diagnosability for unbounded Petri nets is decidable. We present a new necessary and sufficient condition for diagnosability, which can be reduced to a model checking problem for unbounded Petri nets. Then, we show that checking diagnosability for unbounded Petri nets is EXPSPACE-complete. This complexity result is further extended to various subclasses of Petri nets. To the best of our knowledge, this is the first paper that establishes decidability and complexity results for diagnosability of unbounded Petri nets.

This paper deals with the identification of time Petri net systems. An identification algorithm for timed net systems must take into account that the firing of a transition requires not only that the enabling condition is met, as in untimed net systems, but it is also required that the firing interval of a transition is congruent with the observed firing instant times. The key idea behind the approach is to express these conditions by a set of logical propositions that can be directly transformed into linear mixed-integer inequalities. The identification algorithm consists of building the logical propositions from the observed behavior and solving a mixed-integer linear programming problem.

State Class Graph is a very useful tool to analyse Time Petri nets properties. It generates however a states explosion problem in large Petri nets. This can be overcome by using unfolding technique, which still imposes restrictions on time analysis. This paper proposes a relaxation in the unfolding process, which generates a new occurrence net, in which all temporal sequences are preserved.

The above paper [1] proposes a method to reduce simultaneously a Petri net model and the linear constraints. The reduced result preserves the control specification and the liveness. This note shows via some simple counterexamples that some results claimed in the above paper are incorrect, and then presents the corresponding corrections for two of the results.

For bounded Petri nets, Cabasino et al. propose a diagnosability test method that is based on the analysis of a modified basis reachability graph and a basis reachability diagnoser. However, its complexity is exponential in the number of nodes of the basis reachability diagnoser. In order to reduce the complexity of their method, this paper presents a new diagnosability test approach for bounded Petri nets. We present the concept of an extended basis reachability graph and prove that our approach is of polynomial complexity in the number of nodes of extended basis reachability graphs. An example is given to illustrate the application of the presented approach.

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.

Logical Petri nets (LPNs) can well describe and analyze batch processing functions and pass the value indeterminacy in cooperative systems. Their structure is simpler than their equivalent inhibition PNs. To analyze them, a vector matching method was given previously. We present interactive LPNs (ILPNs) in this paper. Their liveness and boundedness are analyzed for the first time. Compatibility is analyzed for a composed system and reflects the possibility of correct/proper interactions among its subsystems. To characterize different cooperative abilities in practice, compatibility is defined for ILPNs. Some relationships among compatibility, liveness, boundedness, and conservativeness are revealed. An example is presented to discuss the effectiveness of the proposed method.

This paper presents a new method of computing a minimal supervisory structure that optimally enforces liveness on the Petri net models for flexible manufacturing systems (FMSs). The proposed method utilizes the structural properties of a Petri net model to avoid the computation of its reachability graph, which in general leads to the state explosion problem. This paper aims to design a single control place for each concurrent process of a Petri net model or a sub-net model, which thus provides a constant number of control places in a supervisor regardless of the number of resource places in a Petri net or sub-net model. It is shown that the structural size of a supervisor is minimal as the number of control places depends on the number of concurrent processes in the Petri net model. Precisely, two algorithms are developed in this paper. The first aims to compute active uncontrolled transitions and the second is concerned with a method to compute the generalized mutual exclusion constraints (GMECs) for each process of the Petri net model of an FMS. Furthermore, it provides an approach to design control places for each computed GMEC without solving integer linear programming problems, which greatly reduces the computational costs. When the computed control places are coupled with the uncontrolled Petri net model for an FMS, it optimally enforces liveness behavior of the Petri net model, and hence ensures the high utilization of resources in a considered system.

Deciding how to prevent discrete event systems (DESs) from reaching forbidden states is an important problem in the field of DES supervisory control. For DESs with uncontrollable events, linear constraint transformation becomes a popular technique for solving the forbidden state problem when Petri nets are used as a modeling tool and control specifications are given in the form of linear constraints. This paper proposes a novel linear constraint transformation approach that is applicable to PT-ordinary Petri nets with uncontrollable subnets being forward-concurrent-free. For such nets, a linear constraint can be transformed into an optimal transformed one (i.e., a linear constraint that exactly characterizes the admissible marking set) by using the proposed approach, which is computationally shown to be of polynomial complexity with respect to the net size. An example is presented to illustrate the developed technique.

In this paper we tackle the problem of verifying whether a scenario is executable in a Petri net. In contrast to sequentially ordered runs, a scenario includes both information about dependencies and independencies of events. Consequently, a scenario allows a precise and intuitive specification of a run of a concurrent or distributed system. In this paper we consider Petri nets with arc weights, namely marked place/transition-nets p/t-nets and p/t-nets with inhibitor arcs pti-nets. A scenario of a p/t-net is a labelled partial order lpo. A scenario of a pti-net is a labelled stratified order structure lso. Accordingly, the question is either whether a given lpo is in the language of a given p/t-net or whether an lso is in the language of a given pti-net. Different approaches exist to define the partial language of a Petri net. Each definition yields a different verification algorithm, but existing algorithms perform quite poorly in terms of runtime for most examples. We introduce a new compact characterization of the partial language of a Petri net. This characterization is optimized with respect to the verification problem. The paper is a revised and extended version of the conference paper [10].

Petri nets are a widely used tool to model, analyze and control discrete event systems that arise from automated production, intelligent transportation, and workflow management. For a class of Petri nets with uncontrollable transitions, this paper proposes a bottom-up algorithm to transform a given generalized mutual exclusion constraint into an optimal admissible one. Based on the transformation, a design method is proposed to synthesize an optimal supervisor. Compared with the existing methods that require the computation of exponential complexity, the proposed one can obtain an optimal supervisor with polynomial complexity.

Observation structures considered for Petri net generators usually assume that the firing of transitions may be observed through a static mask and that the marking of some places may be measurable. These observation structures, however, are rather limited, namely they do not cover all cases of practical interest where complex observations are possible. We consider in this paper more general ones, by correspondingly defining two new classes of Petri net generators: labeled Petri nets with outputs (LPNOs) and adaptive labeled Petri nets (ALPNs). To compare the modeling power of different Petri net generators, the notion of observation equivalence is proposed. ALPNs are shown to be the class of bounded generators possessing the highest modeling power. Looking for bridges between the different formalisms, we first present a general procedure to convert a bounded LPNO into an equivalent ALPN or even into an equivalent labeled Petri net (if any exists). Finally, we discuss the possibility of converting an unbounded LPNO into an equivalent ALPN.

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.

Petri nets are graphical and mathematical tools that are applicable to many systems for modeling, simulation, and analysis. With the emergence of the concept of partitioning in time and space domains proposed in avionics application standard software interface (ARINC 653), it has become difficult to analyze time–space coupling hazards resulting from resource partitioning using classical or advanced Petri nets. In this paper, we propose a time–space coupling safety constraint and an improved timed colored Petri net with imposed time–space coupling safety constraints (TCCP-NET) to fill this requirement gap. Time–space coupling hazard analysis is conducted in three steps: specification modeling, simulation execution, and results analysis. A TCCP-NET is employed to model and analyze integrated modular avionics (IMA), a real-time, safety-critical system. The analysis results are used to verify whether there exist time–space coupling hazards at runtime. The method we propose demonstrates superior modeling of safety-critical real-time systems as it can specify resource allocations in both time and space domains. TCCP-NETs can effectively detect underlying time–space coupling hazards.

This paper focuses on decentralised control of systems modelled by continuous Petri nets, in which a target marking control problem is discussed. In some previous works, an efficient ON/OFF strategy-based minimum-time controller was developed. Nevertheless, the convergence is only proved for subclasses like Choice-Free nets. For a general net, the pre-conditions of applying the ON/OFF strategy are not given; therefore, the application scope of the method is unclear. In this work, we provide two sufficient conditions of applying the ON/OFF strategy-based controller to general nets. Furthermore, an extended algorithm for general nets is proposed, in which control laws are computed based on some limited information, without knowing the detailed structure of subsystems.

In this paper we examine how it is possible to control Petri net behavior with the help of transition priorities. Controlling here means forcing a process to behave in a stable way by ascribing priorities to transitions and hence transforming a classic Petri net into a Priority Petri net. For Petri net models stability is often ensured by liveness and boundedness. These properties are crucial in many application areas, e.g. workflow modeling, embedded systems design, and bioin- formatics. In this paper we study the problem of transforming a given live, but unbounded Petri net into a live and bounded one by adding priority constraints. We specify necessary conditions for the solvability of this problem and present an algorithm for ascribing priorities to net transitions in such a way that the resulting net becomes bounded while staying live.

The reversible released form (RRF) of Petri nets is introduced as an extension of the released form. This new form introduces undo transitions in order to reverse the effect of some of the transitions of the original Petri net. It is shown that the RRF preserves the soundness property of workflow (WF) nets: a WF net is sound if and only if its RRF is sound too. Then, various properties of the RRF of circuit-based Petri nets are investigated, and complexity results of the soundness property of circuit-based WF nets are derived.

With the increasing complexity of the problems and systems arising nowadays, the use of multi-level models is becoming more frequent in practice. However, there are still few reports in the literature concerning methods for analyzing such models without flattening the multi-level structure. For instance, several variants of multi-level Petri nets have been applied for modeling interaction protocols and mobility in multi-agent systems and coordination of cross-organizational workflows. But there are few automated tools for analyzing the behavior of these nets. In this paper we explain how to detect faults in models based on a representative class of multi-level nets: the nested Petri nets. We translate a nested net into a verifiable model that preserves its modular structure, a PROMELA program. This allows the use of SPIN model checker to verify properties related to termination, boundedness and reachability.

Petri Nets (PNs) are an effective structure for modeling and analyzing asynchronous systems with concurrent and parallel activities. A Petri net models the static properties of a discrete event system concentrating on two basic concepts: events and conditions. Most of the theoretical work on Petri nets is a formal definition of Petri nets structures, which consist of a set of places, representing conditions, a set of transitions, representing events, an input function and an output function. For practical purposes, a graphical representation is more useful. Two types of nodes portray places and transitions. A circle is a place and a bar is a transition. There is no inherent measure of time in a classical Petri net. To approach time-based evaluation of system performances, Timed Petri Nets (TPNs) were introduced. Modeling the notion of time is not straightforward. There are several possibilities for introducing time in PNs, among them timed transitions and timed places. This paper reviews several published examples where Petri Nets were used in different circumstances such as estimating expected utilization of processing resources at steady state in open queueing networks, verifying computerized simulations and batch planning in textile industry.

12th IFAC Workshop on Intelligent Manufacturing Systems (IMS) -- DEC 05-07, 2016 -- Austin, TX, WOS: 000401260800021, Petri nets is a common formalism to model many manufacturing systems. Although Petri nets were originally introduced without the notion of time, time-delays in many processes in manufacturing systems makes it necessary to use this notion in Petri nets. Petri nets, in which the time-delays are also modeled are commonly reffered to as timed Petri nets (TPNs). The representation of the state of any system is necessary in order to simulate the system or to design a controller for it. The representation of the state of a TPN, however, is complicated. One method to overcomne this difficulty is stretching. In this paper, the method of stretching is introduced for TPNs where both transitions and places are timed. Supervisory controller design for TPNs using stretching is then discussed, Int Federat Automat Control, Tech Comm 5 1 Mfg Plant Control, Int Federat Automat Control, Tech Comm 4 2 Mechatron Syst, Int Federat Automat Control, Tech Comm 4 5 Human Machine Syst, Int Federat Automat Control, Tech Comm 5 2 Mfg Modelling Management & Control, Scientific Research Projects Commission of Anadolu University [1605F495], This work is supported by the Scientific Research Projects Commission of Anadolu University under grant number 1605F495.

This paper proposes a fully expanded tree (FET) approach for one-place-unbounded Petri nets. The FET of a one-place-unbounded Petri net consists of all and only reachable markings from its initial marking. Its applications to liveness and deadlock analysis for such Petri nets are developed. The proposed method has a larger application scope than all the existing methods for them. Several examples are provided to show its superiority over the state-of-the-art methods.

Liveness of Petri nets means all activities in a modeled system can potentially take place and thus implies deadlock freedom. The research on liveness analysis approaches is inadequate. This paper proposes a liveness judgment reachability graph (LJRG) approach to analyze the liveness of $ {\omega }$ -independent Petri nets. Such nets can be loosely explained as a class of unbounded Petri nets in which the changes of tokens in unbounded places are not related to each other. This paper proposes several algorithms to transform a new modified reachability tree to a new modified reachability graph and then transform it to an LJRG. It then develops the application of LJRG into the liveness analysis of $ {\omega }$ -independent unbounded Petri nets. The proposed method provides a new theoretical method and important tool for the liveness analysis of unbounded Petri nets. It is illustrated via some examples.

Workflow nets (WF-nets) as a class of Petri nets are widely used to model and analyze workflow systems. Soundness is an important property of WF-nets, which guarantees that the systems are deadlock- and livelock-free and each task has a chance to be performed. Van der Aalst has proven that the soundness problem is decidable for WF-nets and we have also shown that it is PSPACE-complete for bounded ones. Since the definition of soundness is based on reachability and Van der Aalst has proven that a sound WF-net must be bounded, the soundness detection can be carried out via the reachability graph analysis. However, the state explosion problem is a big obstacle to this technique. The unfolding technique of Petri nets can effectively avoid/alleviate this problem. This paper proposes an algorithm to generate a finite prefix of the unfolding of a WF-net, called basic unfolding . Furthermore, a necessary and sufficient condition is proposed to decide soundness based on basic unfolding. In addition, some examples illustrate that the unfolding technique can save the storage space effectively.

In this paper we contrast the application of two different methods for verifying soundness of workflow. The first approach considers the structure of the workflow net and proposes an analytical process that takes into account the incidence matrix and a strict positive vector to prove soundness. The second method is based on decision process Petri nets theory showing that the problem of finding an optimum trajectory for validation of well-formed workflow is solvable. The advantage of both solutions is that to tackle the soundness verification problem use the Lyapunov stability theory which corresponds to an analytical method for Petri nets. We validate our statement theoretically and by an application example.

Petri nets are a graph based formalism used for modelling concurrent systems. Binary Decision Diagrams or Multi-Valued Decision Diagrams can be used in the analysis of systems modelled by Petri nets. An encoding scheme is required to be able to map the Petri net state to decision diagram values. Various encodings like One-hot scheme, Logarithmic scheme and Mdd scheme exist for this purpose. This thesis compares the performance of the existing encodings based on time and space taken to represent and analyze the system modelled as Petri net. It also introduces and compares a new encoding scheme called k-hot encoding and shows a gradual improvement in performance of the scheme with increasing values of k. The process of analyzing properties like deadlock and starvation is explained and a comparison is made between the encoding schemes based on the time taken by each to analyze these properties.

Petri nets are used for describing, designing and studying discrete event-driven systems that are characterized as being concurrent, asynchronous, distributed, parallel, and/or nondeterministic. As a graphical tool, Petri net can be used for planning and designing a system with given objectives, more effectively than flowcharts and block diagrams. As a mathematical tool, it enables one to set up state equations and algebraic equations and other mathematical models which govern the behavior of systems. The aim of this paper is to present some basic results and necessary and sufficient condition for a 1-safe Petri net that generates all the binary nvectors as marking vectors, we shall call such Petri nets as Boolean Petri nets.

In this paper we verify certain properties of membrane systems through the use of specific techniques and a software tool developed for coloured Petri nets. We characterise some subclasses of membrane systems in which various qualitative properties (reachability, liveness) and quantitative properties (boundedness) are decidable. We establish a formal connection between membrane systems with delays and Petri nets with delays, and prove an operational correspondence between them. By assigning delays to rules and transitions, respectively, we make a distinction between the occurrence of the rule (transition) and its effects which become apparent after the delay. For both Petri nets and membrane systems we prove that adding finite delays does not increase their expressive power; however, both formalisms become more flexible in describing molecular phenomena where time represents a critical resource.

Grafcet standard (IEC60848) is a formalism used in the world of manufacturing control, at the behavioral specification stage of a system. For specifying safe-critical systems, mathematical models associated with model-checking tools are necessary for the validation of the correctness. However, grafcets (meaning grafcet diagrams) are only semiformal models since certain aspects may be a source of different interpretations. The usual practice is to go through an intermediate formalism. In this brief, time Petri nets (TPNs) are chosen because they combine simplicity with wide-spreading and they also allow quantitative time analyses useful for the verification of real-time specifications. The main goal is to propose a principle of transforming a grafcet into TPN and to define the rules of this translation. The obstacle to overcome is to conciliate synchronous semantics of grafcet with asynchronous semantics of TPN.

The reliability of the traffic signal in the intersection is extremely important to the safe and orderly urban traffic. In this paper, basing on the Classics Petri Nets, we put forward a kind of Extended Colored Petri Nets with the inhibitory and enable arc, so we built the traffic control model based on the improved Petri Nets to ensure the safe and orderly traffic; the model can reflect the dynamic process of intersection and realize the detection and processing of “green conflict”. From the angle of logical equivalence, we use digital logic circuit to simulate the traffic model which is built based on the Extended Colored Petri Nets with the inhibitory and enable arc. The simulation results show that the model based on improved Petri Nets can effectively detect and adjust “green conflict” together with other potential safety risks; also verify the validity of the Extended Colored Petri Nets and the traffic control model.

In this paper, a type of specifications called OR-AND Generalized Mutual Exclusion Constraints (GMEC) for place/transition nets is defined. Such a specification consists of a disjunction of conjunction of several single GMECs, i.e., the requirement is that, at any given time, the controlled system should satisfy at least one set of conjunctive GMECs. We show that a bounded OR-AND GMEC can be enforced by a special control structure composed by a set of AND-GMEC monitor places plus a switcher that determines the current active ones. We also show that such a simple control structure can be modified to ensure maximal permissiveness. This approach can be used in the framework of supervisory control in Petri nets.

In the paper, a family of trace equivalencies in the interleaving, step, partial order, and nondeterministic semantics is defined and studied in the context of time Petri nets. The equivalences studied are based both on the classical concept of transition firing sequences and on time processes, i.e., time extensions of net processes with global transition firing moments. Relationships between the equivalences are established, and a hierarchy of classes of equivalent time Petri nets is constructed.

In this paper we present a model of biometric identification system transformed into Petri Nets. Petri Nets, as a graphical and mathematical tool, provide a uniform environment for modelling, formal analysis, and design of discrete event systems. The main objective of this paper is to introduce the fundamental concepts of Petri Nets to the researchers and practitioners, both from identification systems, who are involved in the work in the areas of modelling and analysis of biometric identification types of systems, as well as those who may potentially be involved in these areas. In addition, the paper introduces high-level Petri Nets, as Colored Petri Nets (CPN). In this paper the model of Colored Petri Net describes the identification process much simpler.

Petri Nets (PNs) constitute a well known family of formalisms for the modelling and analysis of Discrete Event Dynamic Systems (DEDS). As general formalisms for DEDS, PNs suffer from the state explosion problem. A way to alleviate this difficulty is to relax the original discrete model and deal with a fully or partially continuous model. In Hybrid Petri Nets (HPNs), transitions can be either discrete or continuous, but not both. In Hybrid Adaptive Petri Nets (HAPNs), each transition commutes between discrete and continuous behaviour depending on a threshold: if its load is higher than its threshold, it behaves as continuous; otherwise, it behaves as discrete. This way, transitions adapt their behaviour dynamically to their load. This paper proposes a method to compute the Reachability Graph (RG) of HPNs and HAPNs.

Distributed system has the characteristic of high concurrency, which often leads to deadlock due to the execution of concurrent process. By applying Petri nets model can effectively solve this problem. In this paper, based on Petri nets model, we propose a new efficient deadlock avoidance policy for distributed system by using the Petri reachability graph. At last we analysis the different performance between this algorithm and the traditional method by using Matlab tool.

The main limitation of the verification approaches based on state enumeration is the state explosion problem. The partial order reduction techniques aim at attenuating this problem by reducing the number of transitions to be fired from each state while preserving properties of interest. Among the reduction techniques proposed in the literature, this article considers the stubborn set method of Petri nets and investigates its extension to time Petri nets. It establishes some useful sufficient conditions for stubborn sets, which preserve deadlocks and k-boundedness of places.