A **Petri net** (also known as a **place/transition net** or **P/T net**) is one of several mathematical modeling languages for the description of discrete distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions (i.e. discrete events that may occur, signified by bars), places i.e. conditions, signified by circles, and directed arcs that describe which places are pre- and/or postconditions for which transitions, signified by arrows.

Like industry standards such as UML activity diagrams, BPMN and EPCs, Petri nets offer a graphical notation for stepwise processes that include choice, iteration, and concurrent execution. *Unlike these standards, Petri nets have an exact mathematical definition of their execution semantics, with a well-developed mathematical theory for process analysis.*

*Because of its executability Petri net is an interesting formalism compared with the symbolic atomistic model.*

*Formalism for Petri nets*

*Formalism for Petri nets*

A Petri net consists of *places*, *transitions*, and *directed arcs*. Arcs run from a place to a transition or vice versa, never between places or between transitions. The places from which an arc runs to a transition are called the *input places* of the transition; the places to which arcs run from a transition are called the *output places* of the transition.

Places may contain a natural number of tokens. A distribution of tokens over the places of a net is called a *marking*. A transition of a Petri net may *fire* whenever there is a token at the end of all input arcs; when it fires, it consumes these tokens, and places tokens at the end of all output arcs. A firing is atomic, i.e., a single non-interruptible step.

Execution of Petri nets is nondeterministic: when multiple transitions are enabled at the same time, any one of them may fire. If a transition is enabled, it may fire, but it doesn’t have to. Since firing is nondeterministic, and multiple tokens may be present anywhere in the net (even in the same place), Petri nets are well suited for modeling the concurrent behavior of distributed systems.

The following formal definition is loosely based on (Peterson 1981). Many alternative definitions exist.

### Syntax

A **Petri net graph** (called *Petri net* by some, but see below) is a 3-tuple , where

*S*is a finite set of*places**T*is a finite set of*transitions**S*and*T*are disjoint, i.e. no object can be both a place and a transition- is a multiset of arcs, i.e. it defines arcs and assigns to each arc a non-negative integer
*arc multiplicity*; note that no arc may connect two places or two transitions.

The *flow relation* is the set of arcs: . In many textbooks, arcs can only have multiplicity 1, and they often define Petri nets using *F* instead of *W*.

A Petri net graph is a bipartite multidigraph with node partitions *S* and *T*.

The *preset* of a transition *t* is the set of its *input places*: ; its *postset* is the set of its *output places*:

A *marking* of a Petri net (graph) is a multiset of its places, i.e., a mapping . We say the marking assigns to each place a number of *tokens*.

A **Petri net** (called *marked Petri net* by some, see above) is a 4-tuple , where

- (
*S*,*T*,*W*) is a Petri net graph; *M*_{0}is the*initial marking*, a marking of the Petri net graph.

### Executablity of Petri nets

Petri nets include a specific logic, with some variations. Shortly said:

- firing a transition
*t*in a marking*M*consumes*W*(*s*,*t*) tokens from each of its input places*s*, and produces*W*(*t*,*s*) tokens in each of its output places*s* - a transition is
*enabled*(it may*fire*) in*M*if there are enough tokens in its input places for the consumptions to be possible, i.e. iff .

We are generally interested in what may happen when transitions may continually fire in arbitrary order.

We say that a marking *M*‘ *is reachable from* a marking *M* *in one step* if ; we say that it *is reachable from* *M* if , where is the transitive closure of ; that is, if it is reachable in 0 or more steps.

For a (marked) Petri net , we are interested in the firings that can be performed starting with the initial marking *M*_{0}. Its set of *reachable markings* is the set

The *reachability graph* of *N* is the transition relation restricted to its reachable markings *R*(*N*). It is the state space of the net.

A *firing sequence* for a Petri net with graph *G* and initial marking *M*_{0} is a sequence of transitions such that . The set of firing sequences is denoted as *L*(*N*).

Types of different levels of Petri nets are shown below:

### Comparing Petri nets and Symbolic Atomistic Model

Formalism of Petri nets is different from the one of computer programming languages, because in each place there is a contents, which is a set of tokens. The purpose is to study firing and balance between modeling and analyzability.

**In spite of the differences, I argue that Petri nets can be converted into the symbolic atomistic model (AHO objects) by some arrangements:**

- Each place reserves an AHO object.
- Each transition reserves so many AHO’s that it requires when the semantics are converted atomistic (atomic formula).
- Contents of each place is a separate dynamic AHO – object.
- Code for transitions are written in a high level language.
- The executing logic will be programmed into the run – methods for AHO’s allowing nondeterminism.
**Otherwise, the logic of SimulationWare could be used.**

There is no demonstration that it works, but** it seems evident that a modified atomistic model (the architecture of AHO’s) should simulate Petri nets, too.**

**Some links:**

- See more about Petri nets from: http://en.wikipedia.org/wiki/Petri_net
- About a tool Maria (in Finnish): http://www.tcs.hut.fi/Software/maria/petri.fi.pdf

## Leave a comment

Comments feed for this article