Petri net |
A Petri net (also known as a place/transition net or P/T net) is one of several mathematical knowledge representations of discrete distributed systems. As a modeling language, it graphically depicts the structure of a distributed system as a directed bipartite graph with annotations. As such, a Petri net has place nodes, transition nodes, and directed arcs connecting places with transitions.
At any one time during a Petri net s execution, each place can hold zero or more tokens. Unlike more traditional data processing systems that can process only a single stream of incoming tokens, Petri net transitions can consume tokens from multiple input places, act on them, and output tokens to multiple output places. Before acting on input tokens, a transition waits until the following two conditions are met:
Transitions act on input tokens by a process known as firing . When a transition fires, it consumes the tokens from its input places, performs some processing task, and places a specified number of tokens into each of its output places. It does this atomically, namely in one single non-preemptible step. Since more than one transition on a net can be firing at any one time, Petri nets are well suited for modeling concurrent behavior of a (geographically) distributed system.
=A Formal definition=
A Petri net is a Tuple (S,T,F,M_0,W,K), where (see Desel and Juhás )
A variety of other formal definitions exist. This definition is for a place-transition (or P-T ) net. Most other definitions do not include arc weights or capacity restrictions .
=Basic Petri nets=
Petri nets, defined in 1962 by Carl Adam Petri, extend state machines with a notion of Concurrency (computer science).
A Petri net consists of places , transitions and graph theorys . Arcs run between places and transitions - not between places and places or transitions and transitions. The input places of a transition are the places from which an arc runs to it; its output places are those to which an arc runs from it.
Places may contain any number of tokens. A distribution of tokens over the places of a net is called a marking . Transitions can fire, that is, execute: when a transition fires, it consumes a token from each of its input places, and produces a token on each of its output places. A transition is enabled if it can fire, i.e., there are tokens in every input place.
Execution of Petri nets is nondeterministic, since multiple transitions can be enabled at the same time.
If every transition in a Petri net has exactly one input place and exactly one output place, the net is in effect a finite state machine!
=Extensions=
In a standard Petri net, tokens are indistinguishable. In a coloured Petri net, every token has a value. In popular tools for colored Petri nets such as CPN Tools, the values of tokens are typed, and can be tested and manipulated with a functional programming language. Firing of a transition in both standard and coloured Petri nets is fully determined by the presence of tokens in the input places.
Another popular extension of Petri nets is hierarchy: elements in the Petri net that contain Petri nets.
A high level Petri net is a hierarchical, coloured Petri net.
Stochastic Petri nets add non-deterministic time.
A Vector Addition System with States (VASS) can be seen as a generalization of a Petri net. Consider a finite state automaton where each transition is labeled by a transition from the Petri net. The Petri net is then synchronized with the finite state automaton, i.e., a transition in the automaton is taken at the same time as the corresponding transition in the Petri net. It is only possible to take a transition in the automaton if the corresponding transition in the Petri net is enabled, and it is only possible to fire a transition in the Petri net if there is a transition from the current state in the automaton labeled by it. (The definition of VASS is usually formulated slightly differently.)
Many more extensions exist.
=Petri net theory=
The theoretical properties of Petri nets have been studied extensively.
A marking of a Petri net is reachable if, starting in the initial marking, a sequence of transition firings exists that produces it. A Petri net is bounded if there is a maximum to the number of tokens in its reachable markings.
Boundedness is decidable by looking at Covering Problem, by constructing the Richard Karp-Miller Tree. Reachability is known to be decidable, however in at least exponential time. All known general algorithms so far, however, employ non-Primitive recursive function space. Further details may be found in this survey [http://citeseer.ist.psu.edu/226920.html ] and in Kurt Jensen Coloured Petri Nets, and in M. Ajmone Marsan et al. Modelling with Generalized Stochastic Petri Nets.
= Subsequent models of concurrency =
Subsequent to the invention of Petri nets, other models of concurrency based on message passing (e.g. Actor model and Process calculi) have been introduced that feature compositionality. Robin Milner and Carl Hewitt have argued that the lack of compositionality is a serious limitation of Petri nets because the deficiency limits modularity.
In addition, Hewitt has argued that Petri nets lack locality because input tokens of a transition disappear simultaneously, which limits the realism of the model. He acknowledged the counterargument that the proper use of Petri nets is to obey the single event restriction which is that every transition should model a single event. An example of such a transition would be one with two input places, one representing the month being September 2005, and the other representing the date being September 30, 2005. If the event being modeled were the passing of midnight on that day, obviously both tokens would disappear at the same time. However obeying the single event restriction drastically limits the applications of Petri nets.
= Application areas =
= Programming tools =
#Analisador de Redes de Petri #COOPN #CPN-AMI #CPN Tools #CPN ML #DPNSchematic #ExSpecT #EZPetri #HiQPN-Tool #HPSim #Integrated Net Analyzer #JARP #JFern #JPetriNet #Low Level Petri net Analyzer #Maria (reachability analyzer) #Marigold #Model-Checking Kit #NEPTUN #PED #PEP tool #PetriEdiSim #Platform Independent Petri Net Editor #Petrigen #PetriSim #Petri Net Browser #Petri Net Kernel #Petri Net Simulator #PNES #PNSim #PNtalk #Poseidon (program) #Posespp #Predator #PROD #Romeo #Renew (program) #SEA #SimPRES #SIPN-Editor #SimulaWorks #StpnPlay #Tina #Visual Object Net plus plus #Visual SimNet #Visual Simulation Objects - VSO #WebSPN #WINSIM #Woflan #WoPeD #Yasper #XPetri #XRL
= See also =
= References =
= External links =
|
|