Petri net

From Academic Kids

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 modelling 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 modelling concurrent behavior of a (geographically) distributed system.

Contents

Formal definition (after Desel and Juhás)

A Petri net is a tuple <math>(S,T,F,M_0,W,K)<math>, where

  • <math>S<math> is a set of places.
  • <math>T<math> is a set of transitions.
  • <math>F<math> 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: <math>F \subseteq (S \times T) \cup (T \times S)<math>.
  • <math>M_0 : S \to N<math> known as an initial marking, where for each place <math>s \in S<math>, there are <math>n \in \mathbb{N}<math> tokens.
  • <math>W : F \to \mathbb{N^+}<math> known as a set of arc weights, assigns to each arc <math>f \in F<math> some <math>n \in \mathbb{N^+}<math> 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.
  • <math>K : S \to \mathbb{N^+}<math> known as capacity restrictions, assigns to each place <math>s \in S<math> some positive number <math>n \in \mathbb{N^+}<math> denoting the maximum number of tokens that can occupy that place.

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 place. 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.

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 [1] (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.

Application areas

Programming tools

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

See also


References

External links

de:Petri-Netz es:Red de Petri hu:Petri-háló pl:Sieć Petriego zh:Petri网

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools