Petri net

A Petri net is a mathematical representation of discrete distributed systems. Petri nets were defined in the 1960s by Carl Adam Petri. Because of their ability to express concurrent events, they generalize automata theory.

A Petri net consists of places, transitions and directed arcs. Arcs connect a place to a transition and vice versa. There are no arcs between two places, nor between two transitions. Places may contain any number of tokens. Transitions fire, that is consume tokens from input positions and produce tokens in output positions. A transition is enabled if there are tokens in every input position.

More complex Petri nets add hierarchy to the network.

Tokens in a standard Petri net are indistinguishable from each other. Coloured Petri Nets, often designated with the acronym CPN, add token coloring. Firing of a transition in both standard and coloured Petri nets is fully determined by the presence of tokens in the input places. Stochastic Petri Nets add non-deterministic timing.

Most problems for Petri Nets are decidable, such as Boundedness and Covering by constructing the Karp-Miller Tree. The reachability problem 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] 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. CoopnTools
3. CPN-AMI
4. CPN Tools
5. CPN ML
6. DPNSchematic
7. EZPetri
8. HiQPN-Tool
9. HPSim
10. Integrated Net Analyzer
11. JARP
12. JFern
13. JPetriNet
14. LoLA
15. Maria
16. Marigold
17. Model-Checking Kit
18. NEPTUN
19. PED
20. PEP
21. PetriEdiSim
22. Platform Independent Petri Net Editor
23. Petrigen
24. PetriSim
25. Petri Net Browser
26. Petri Net Kernel
27. Petri Net Simulator
28. PNES
29. PNSim
30. PNtalk
31. Poseidon
32. Poses++
33. Predator
34. PROD
35. Romeo
36. Renew
37. SEA
38. SimPRES
39. SIPN-Editor
40. SimulaWorks
41. StpnPlay
42. Tina
43. Visual Object Net ++
44. Visual SimNet
45. WebSPN
46. WINSIM
47. Woflan
48. XPetri
49. 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

External links

• Petri Nets World
• Petri Net Markup Language
• exchangeable Routing Language
• Citations from CiteSeer