Petri Net

[From PetriNets]

Petri nets date back to Prof. Dr. CarlAdamPetri?'s ( http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri_eng.html) thesis "Kommunikation mit Automaten" (Communication with Automata, published in 1962), where he set out to develop a description technique for computational tasks that is firmly based on and realizable with elementary physical phenomena. Petri nets were in the subsequent years refined by both Petri and his scholars, who worked on the theoretical foundations, but also on extensions and possible applications of Petri nets.

A Petri net is assembled from places and transitions. Places represent resources that can be available or not. Places are depicted in diagrams as circles or ellipses. The availability of a resource is shown by a black dot inside the circle. If more than one resource of a given type is available, more than one dot will be present. When resources are available, we also say that the place is marked. Individual resources are abstractly referred to as tokens.

Conditions that might be satisfied in a system can also be shown as places. If the condition is a global one, there will never be more than a single token in the place. When the place can have multiple tokens, each token usually represents a particular object for which the condition holds. For example, in modeling a car assembly process, cars are likely to be represented as tokens, and the places they visit will be states of completion that the car can be in , while additional states represent the states and availability of auxiliary resources such as components, machinery and assembly line workers. A particular distribution of tokens among the places (known as a marking) represents a particular complete state of the whole system.

Transitions are the active elements of a net. Rectangles or squares denote transitions in net diagrams. A transition that occurs (or fires) can remove tokens from some places and insert tokens into other places. In order to denote the tokens that are moved by a transition, arrows, so-called arcs, are drawn from places to transitions and from transitions to places. Each arrow can be annotated by a number that indicates the number of tokens that are moved by this arc.

More information about Petri nets is available from the World of Petri nets at http://www.informatik.uni-hamburg.de/TGI/PetriNets/

Petri nets have recently become more popular due to their appropriateness for describing concurrent behaviour, especially in WorkFlow systems. --OlafKummer

PetriNets are much more powerful than other popular process modeling techniques. StateMachines, for instance, can be regarded as Petri nets in which all branching is done on places only. As a result, the marking always consists of a single token. A state machine can express choice and iteration, but no parallelism or resource contention. FlowCharts are another example of a technique subsumed by Petri nets; they are fundamentally the same as state machines. More recent techniques exist that can be considered special types of Petri nets, such as UML ActivityDiagram?s or BizTalk's XLANG specification technique.

However, powerful as they may be, basic Petri nets are not a true UniversalModellingLanguage?: certain patterns of process logic cannot be expressed in terms of them. Many extensions of Petri nets have been developed such as the addition of stochastic time for use by automatic simulation, additional types of connections to express more types of process logic, support for hierarchy and modularity, etcetera.

I often wonder if these would be a good design tool if they were adopted into common use?

Things that look like suspiciously like petri nets include the primitives of QnxOperatingSystem, and maybe Erlang and CommunicatingSequentialProcesses.

A class of rewriting systems has been proposed called BetaRewritingSystems? of which petri nets, SemiThueGrammar? s and RewriteRules are subclasses see http://www.informatik.uni-hamburg.de/TGI/pnbib/a/akama_k2.html

CategoryConcurrencyPatterns