Petri net

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

1 Formal definition (after Desel and Juhás) 2 Basic Petri nets 3 Extensions 4 Petri net theory 5 Application areas 6 Programming tools 7 See also 8 References 9 External links

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

• Software design
• Workflow management
• Data analysis
• Concurrent programming

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

• Finite state machine

References

• Harald Störrle: Models of Software Architecture - Design and Analysis with UML and Petri-Nets, Books on Demand GmbH, ISBN 3-8311-1330-0
• Robert-Christoph Riemann: Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus, Herbert Utz Verlag, ISBN 3-89675-629-X
• Kurt Jensen: Coloured Petri Nets, Springer Verlag, ISBN 3-540-62867-3
• Janette Cardoso, Heloisa Camargo: Fuzziness in Petri Nets, Physica-Verlag, ISBN 3-7908-1158-0
• James Lyle Peterson: Petri Net Theory and the Modeling of Systems, Prentice Hall, ISBN 0136619835
• Wolfgang Reisig: A Primer in Petri Net Design, Springer-Verlag, ISBN 3-540-52044-9
• Mengchu Zhou, Frank Dicesare: Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic Publishers, ISBN 0792392892
• Mengchu Zhou: Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach, World Scientific Publishing Company, 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

• Petri Nets World (http://www.daimi.au.dk/PetriNets/)
• Petri Net Markup Language (http://informatik.hu-berlin.de/top/pnml/about.html)
• exchangeable Routing Language (http://tmitwww.tm.tue.nl/staff/anorta/XRL/xrlHome.html)
• Citations from CiteSeer (http://citeseer.ist.psu.edu/cs?q=Petri+net)

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