Principles and engineering of process control with Petri nets

Event-related control is considered in which process and related process control can be described by states and transitions that can be represented concisely by a Petri net (PN). Both process and related process control systems are event-related, causal, and concurrent and define a special type of PN using a few primitives that are assembled to form a net for which structural and dynamic invariants apply. The PNs can be used for a general approach to event-related process control in simulating, checking, debugging, and stating the quantitative deviations from the ideal solution for any given process control system. The technique can be applied to continuous or discrete processes, and provides formal checks at all development stages. It allows for components with nonideal behavior and yields numerical performance criteria. The invariants allow the PN to be structured in such a way that even complex process control systems become manageable. Examples are presented for the control tasks in an electrical substation     

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.     

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.     

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.     

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.     

基于对象的扩展Petri网协同设计过程分析

针对协同设计中任务的执行流程缺乏柔性,不利于分析实际设计过程的现状,提出一种单元调用变迁对与决策变迁相集成的基于对象的扩展Petri网,扩展了Petri网的可达图以适应分析OEPNs模型.采用OEPNs中的过程网和单元阿对协同设计过程楚模,利用模型中的单元调用变迁对和决策变迁对过程本身和可能状态进行分析.最后与相关的研究工作进行比较并给出了结论.     

应急预案流程的Petri网建模方法研究

为了提高应急信息系统模型的语义基础,提出了一种基于Petri网的应急预案流程的建模方法。以ABC模型为上位本体建立了应急预案流程本体,提出了应急预案流程的Petri网建模过程,并定义了应急预案流程中本体和层次Petri网的映射规则。使用该方法对某公路桥梁抢修应急预案流程进行Petri网建模,并通过仿真分析验证了建模方法的有效性。     

Decomposing Petri nets for process mining: A generic approach

The practical relevance of process mining is increasing as more and more event data become available. Process mining techniques aim to discover, monitor and improve real processes by extracting knowledge from event logs. The two most prominent process mining tasks are: (i) process discovery: learning a process model from example behavior recorded in an event log, and (ii) conformance checking: diagnosing and quantifying discrepancies between observed behavior and modeled behavior. The increasing volume of event data provides both opportunities and challenges for process mining. Existing process mining techniques have problems dealing with large event logs referring to many different activities. Therefore, we propose a generic approach to decompose process mining problems. The decomposition approach is generic and can be combined with different existing process discovery and conformance checking techniques. It is possible to split computationally challenging process mining problems into many smaller problems that can be analyzed easily and whose results can be combined into solutions for the original problems.     

Marking fairness in Petri nets

We study fairness with respect to markings in Petri nets, which means no infinite execution sequence such that in the sequence some marking occurs only finitely often but it is an element of the forward set of a marking M which occurs infinitely often. First we show the transition strong fairness implies the marking fairness although the transition fairness and the marking fairness are quite different matters. And we find some relationship between the marking fairness and the frozen tokens. Then we prove that it can be controlled locally to make marking fairness.     

Concurrent bisimulations in Petri nets

Summary After various attempts, an equivalence relation is defined for labelled Petri nets, on the base of the concurrency semantics of net theory. This relation, called Fully Concurrent bisimulation and abbreviated FC-bisimulation, preserves the level of concurrency of visible operations and, under some conditions, allows to enforce injective labelling on them. Refinements of a visible operation are also defined and we show that, under some conditions, they preserve FC-bisimulation.Research partly supported by ESPRIT Basic Research Action, project 3148: DEMON     

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     

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.     

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.     

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.     

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