Deterministic weak-and-marked Petri net languages are regular

The intersection of the class of deterministic weak and the class of deterministic marked Petri net languages is the class of regular languages. We prove this result using a lemma that characterizes regular deterministic Petri net languages     

Supervisory control of deterministic Petri nets with regularspecification languages

Algorithms for computing a minimally restrictive control in the context of supervisory control of discrete-event systems have been well developed when both the plant and the desired behaviour are given as regular languages. In this paper the authors extend such prior results by presenting an algorithm for computing a minimally restrictive control when the plant behaviour is a deterministic Petri net language and the desired behaviour is a regular language. As part of the development of the algorithm, the authors establish the following results that are of independent interest: i) the problem of determining whether a given deterministic Petri net language is controllable with respect to another deterministic Petri net language is reducible to a reachability problem of Petri nets and ii) the problem of synthesizing the minimally restrictive supervisor so that the controlled system generates the supremal controllable sublanguage is reducible to a forbidden marking problem. In particular, the authors can directly identify the set of forbidden markings without having to construct any reachability tree     

层次结构的Petri网

Petri网是一个很好地描述与分析并行系统的模型。但在实际应用中,如果系统过大或较复杂时,会遇到结点数过多的问题。介绍了着色网和几种层次结构的Petri网,包括位置/转移精化网、对象网以及开放网等;分析和比较了这几种模型用以减少结点数和引入层次结构的方法,而且从结构上讨论了它们相互之间的关系。     

Statechartable Petri nets

Petri nets and statecharts can model concurrent systems in a succinct way. While translations from statecharts to Petri nets exist, a well-defined translation from Petri nets to statecharts is lacking. Such a translation should map an input net to a corresponding statechart, having a structure and behaviour similar to that of the input net. Since statecharts can only model a restricted form of concurrency, not every Petri net has a corresponding statechart. We identify a class of Petri nets, called statechartable nets, that can be translated to corresponding statecharts. Statechartable Petri nets are structurally defined using the novel notion of an area. We also define a structural translation that maps each statechartable Petri net to a corresponding statechart. The translation is proven sound and complete for statechartable Petri nets.     

Error-correcting Petri nets

The paper introduces error-correcting Petri nets, an algebraic methodology for designing synthetic biologic systems with monitoring capabilities. Linear error-correcting codes are used to extend the net’s structure in a way that allows for the algebraic detection and correction of non-reachable net markings. The presented methodology is based on modulo-p Hamming codes—which are optimal for the modulo-p correction of single errors—but also works with any other linear error-correcting code.     

Recursive Petri nets

In order to design and analyse complex systems, modelers need formal models with two contradictory requirements: a high expressivity and the decidability of behavioural property checking. Here we present and develop the theory of such a model, the recursive Petri nets. First, we show that the mechanisms supported by recursive Petri nets enable to model patterns of discrete event systems related to the dynamic structure of processes. Furthermore, we prove that these patterns cannot be modelled by ordinary Petri nets. Then we study the decidability of some problems: reachability, finiteness and bisimulation. At last, we develop the concept of linear invariants for this kind of nets and we design efficient computations specifically tailored to take advantage of their structure.     

Possibilistic Petri nets

This paper presents the possibilistic Petri net model which combines possibility logic with Petri nets with objects. The main feature of this model is to allow one to reason about the aspects of uncertainty and change in dynamic discrete event systems. The paper presents relevant concepts of Petri nets with objects and possibility logic and how imprecision and vagueness are introduced in the marking of a Petri net with objects. The marking of a net is imprecise, or in a more general way, fuzzy, in order to represent an ill-known knowledge about a system state. A new marking updating according to the fuzzy marking such defined is also discussed. An example of shop door monitoring is presented that illustrates our approach.     

Normal Petri nets

A class of Petri nets, called normal Petri nets, is introduced, and it is shown that, for each initial marking, the reachability set of a normal marked Petri net is an effectively computable semilinear set. More generally, we show that the reachability set of a marked Petri net is an effectively computable semilinear set unless the total number of tokens in a minimal circuit is decreased to 0. We also show that a Petri net is normal if and only if it is weakly persistent for each initial marking without token-free circuits.     

Fuzzy reasoning Petri nets

This paper presents a fuzzy reasoning Petri net (FRPN) model to represent a fuzzy production rule-based system. The issues of how to represent and reason about rules containing negative literals are addressed in the proposed PN model. The execution rules based on the model are defined formally using the operators in max-algebra. Then, a fuzzy reasoning algorithm is proposed to perform fuzzy reasoning automatically. The algorithm is consistent with the matrix equation expression method in the traditional PNs and allows one to exploit the maximum parallel reasoning potential embedded in the model. The legitimacy and feasibility of the proposed approach are proved and validated through a turbine fault diagnosis expert system.     

Priority conflict-free Petri nets

A number of problems concerning priority conflict-free Petri nets are investigated in this paper. We show the reachability problem for such Petri nets to be NP-complete. (Using a similar technique, the NP-completeness result applies to the class of priority BPP-nets as well.) As for the boundedness problem, an NP-completeness result is demonstrated for priority conflict-free Petri nets with two types of prioritized transitions. (In contrast, the problem is known to be P-complete for conflict-free Petri nets without priorities.) We also investigate the home state problem, i.e., the problem of determining whether home states exist in a given a Petri net, for conflict-free Petri nets with and without priorities. As it turns out, home states always exist for bounded conflict-free Petri nets without priorities. If an additional liveness constraint is imposed, such Petri nets are guaranteed to be ‘reversible’ (i.e., their initial states are home states). For priority conflict-free Petri nets, being bounded and live is sufficient for the existence of home states. However, if the liveness assumption is dropped, the existence of home states is no longer guaranteed. Received: 1 April 1997 / 8 December 1997     

Asymptotic continuous Petri nets

A Petri net is basically a discrete model. However, continuous Petri nets, such that the markings are real numbers have been defined. Two continuous Petri net models involving time have been drawn up. They differ by the calculation of the instantaneous firing speeds of the transitions. Both can be used to approximate a timed Petri net. The former considers constant firing speeds (CCPN) and is very easy to simulate (few events have to be considered, even when it approximates a timed Petri net with many reachable markings). The latter considers firing speeds depending on the marking (VCPN). Although it provides a better approximation, its simulation is longer because the markings and speeds are given by differential equations. This paper introduces a third model (ACPN) which presents the advantages of the two preceding ones. In most cases, this model represents the asymptotic behavior of the VCPN. Then their precisions are similar. Since the firing speeds of the ACPN are constant, it is as easy to simulate as the CCPN.     

Bounded self-stabilizing Petri nets

We investigate the property of self-stabilization in bounded Petri nets. We give characterizations for both self-stabilizing bounded ordinary Petri nets (i.e., Petri nets without multiple arcs) and self-stabilizing bounded general Petri nets (i.e., Petri nets with multiple arcs). These characterizations allow us to determine the complexity of deciding self-stabilization for each of these classes. In particular, we show the self-stabilization problem to be PTIME-complete for bounded ordinary Petri nets and PSPACE-complete for bounded general Petri nets.Louis Rosier passed away on May 6, 1991, while this paper was under review     

Decomposition of Petri nets

The problem of splitting any given Petri net into functional subnets is considered. The properties of functional subnets and sets that induce them are investigated. An algorithm of polynomial complexity is constructed for decomposition of nets.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 131–140, September–October 2004.     

Complex-valued token Petri nets

This paper presents a new extension to ordinary Petri nets (PNs) that uses complex-valued tokens. By allowing two kinds of tokens, "real" and "imaginary," each place marking contains both quantity and type information. Complex-valued token PNs were designed to integrate seamlessly with other popular Petri net extensions such as timed nets, stochastic nets, and colored nets. This simple and intuitive application of complex numbers and complex arithmetic to PNs provides a unique modeling tool. Some examples show the capabilities of this proposed class of PNs. Note to Practitioners-Discrete-event systems are often man-made systems such as transportation systems, computer communication networks, distributed software, and manufacturing systems. They typically involve the flow of information and physical goods through a network. The flow itself evolves in continuous time but the initiation or completion of the event happens at a discrete point in time. Analyzing the system's performance is key to their successful operation. This paper presents a new approach to performance analysis with application to supply-chain management.