Petri net

From Exampleproblems

Jump to: navigation, search

A Petri net (also known as a place/transition net or P/T net) is one of several mathematical 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:

  • (i) a required number of tokens appears in every one of its input places, and
  • (ii) the number of tokens in each of its output places falls below some threshold.

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.

Contents

A Formal definition

A Petri net is a tuple (S,T,F,M0,W,K), where (see Desel and Juhás [1])

  • S is a set of places.
  • T is a set of transitions.
  • F is a set of arcs known as a flow relation. It is subject to the constraint that no arc connects two places or two transitions, or more formally: F \subseteq (S \times T) \cup (T \times S).
  • M_0 : S \to \mathbb{N} known as an initial marking, where for each place s \in S, there are n \in \mathbb{N} tokens.
  • W : F \to \mathbb{N^+} known as a set of arc weights, assigns to each arc f \in F some n \in \mathbb{N^+} denoting how many tokens are consumed from a place by a transition, or alternatively, how many tokens are produced by a transition and put into each place.
  • K : S \to \mathbb{N^+} known as capacity restrictions, assigns to each place s \in S some positive number n \in \mathbb{N^+} denoting the maximum number of tokens that can occupy that place.

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.

A Petri net consists of places, transitions and directed arcs. 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 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, by constructing the 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 space. Further details may be found in this survey [2] 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

  1. ARP
  2. COOPN Language and COOPNTools
  3. CPN-AMI
  4. CPN Tools
  5. CPN ML
  6. DescoGUI
  7. DPNSchematic
  8. ExSpecT
  9. EZPetri
  10. HiQPN-Tool
  11. HPSim
  12. Integrated Net Analyzer
  13. JARP
  14. JFern
  15. JPetriNet
  16. LoLA
  17. Maria
  18. Marigold
  19. Model-Checking Kit
  20. NEPTUN
  21. PED
  22. PEP
  23. PetriEdiSim
  24. Platform Independent Petri Net Editor
  25. Petrigen
  26. PetriSim
  27. Petri Net Browser
  28. Petri Net Kernel
  29. Petri Net Simulator
  30. PNES
  31. PNSim
  32. PNtalk
  33. Poseidon
  34. Poses++
  35. Predator
  36. PROD
  37. Romeo
  38. Renew
  39. SEA
  40. SimPRES
  41. SIPN-Editor
  42. SimulaWorks
  43. StpnPlay
  44. Tina
  45. Visual Object Net ++
  46. Visual SimNet
  47. Visual Simulation Objects - VSO
  48. WebSPN
  49. WINSIM
  50. Woflan
  51. WoPeD
  52. Yasper
  53. XPetri
  54. XRL

See also

References

  • Mengchu Zhou. Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach, World Scientific Publishing. ISBN 981023029X.
  • ^ Jörg Desel and Gabriel Juhás, "What Is a Petri Net? -- Informal Answers for the Informed Reader", Hartmut Ehrig et al. (Eds.): Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001.

External links

es:Red de Petri hu:Petri-háló nl:Petrinet pl:Sieć Petriego ro:Reţea Petri zh:Petri网

Retrieved from "http://www.exampleproblems.com/wiki/index.php/Petri_net"
Argan Oil
Natural Skin Care
Organic Skin Care
visitor stats