Petri

A Petri net is a mathematical or graphic representation of a discrete event system in which the topology of a distributed, parallel or concurrent system can be described

The essential Petri net was defined in the 1960s by Carl Adam Petri

They are a generalization of automata theory which allows to express a system of events concurrent

A Petri net is made up of places, transitions, directed arcs and marks or tokens that occupy positions within the places

The rules are: Arches connect a place to a transition as well as a transition to a place

There can be arcs between places or between transitions

The sites contain a finite number or countable infinity of marks

Transitions are triggered, that is, they consume marks from a start position and produce marks at an end position. A transition is enabled if it has marks at all its input positions

In its most basic form, the marks that circulate in a Petri net are all identical

A variant of Petri nets can be defined in which the marks can have a color (information that distinguishes them), an activation time and a hierarchy in the network

Most of the problems on Petri nets are decidable, such as the limited nature and the coverage

To solve them, a Karp-Miller tree is used. The scope problem is known to be decidable, at least in exponential time

Useful in the qualitative analysis

Petri nets can be used to perform the qualitative analysis of a network, since they are bipartite graphs

Depending on how we analyze the Petri net, we can find:

• Structural analysis (depend on the structure)
  They have the following properties:
  • Repetitive
    There is a sequence of shots, including all transitions, that if they can be triggered leave the system the same as at the beginning \Longleftrightarrow There is a vector that is null right of the matrix of incidence with all its terms positive integers
  • Conservative
    There is a combination of positive integer weights that if applied to the places, the sum of the marking of all the places weighted by their weights is invariant (always the same) \Longleftrightarrow There exists a vector null left of the matrix of incidence with all its terms positive integers
  • Locks
    Place or set of places in which the marks they contain cannot diminish, because the exit transitions of those places are also entrance, with greater total weight in the entrance arches (to the places of the trap) than the output. A row or sum of rows with negative or zero values in the incidence matrix, will contain a lock
  • Traps
    Place or set of places where the marks they contain cannot increase, because the entry transitions to those places are also exiting, with greater total weight in the exit arches (of the trap places) than the input. A row or sum of rows with positive or zero values in the incidence matrix, will contain a trap
  • Lock / Trap
    It is both a lock and a trap. A row or sum of rows with all zero values in the incidence matrix, will contain a lock / trap
• Dynamic analysis (depend on the initial markup)
  They have the following properties:
  • Cyclic
    Given an initial state, from any accessible state you can always return to the initial state
  • Live
    Given an initial state, from any accessible state there will never be a transition that can no longer be triggered later
  • Limited
    All places have an upper bound finite