Introduction

• Introduced by Carl Adam in 1962
• A diagrammatic tool to model concurrency and synchronization in systems
• Fairly similar to UML state Machines
• based on strong mathematical foundation

Components

• Places represent possible states of the system
• Transitions are vents or actions which cause the change of state
• Every arc simply connects a place with a transition or a transition with a place.

Change of State

A change of state is denoted by a movement of tokens from place to place. This is caused by the firing of a transition. The firing represents an occurrence of the event or an action taken. The firing is subject to the input conditions, denoted by token availability. A transition is firable or enabled when there are sufficient tokens in its input places. After firing, tokens will be transferred from the input places (old state) to the output places, denoting the new state.

Multiple Local States

Petri nets can be modelled to handle concurrent events.

Behavioral Properties

• Reachability
  • "can we reach one particular state from another"
• Boundedness
  • can the number of tokens in a place increase infinitely
  • A Petri net is said to be k-bounded or simply bounded if the number of tokens in each place does not exceed a finite number $k$ for any marking reachable from M0
• Liveness
  • will the system die in a particular state
  • A Petri net with initial marking M0 is live if, no matter what marking has been reached from M0, it is possible to ultimately fire at least a single transition by progressing through some further firing sequence.
  • A live Petri net guarantees deadlock-free operation, no matter what firing sequence is chosen.
  • A transition is dead if it can never be fired in any firing sequence