Are Petri nets complete

Petri nets

Petri nets were developed in 1962 by C. A. Petri on the basis of graph theory. They are suitable for modeling, analyzing and simulating dynamic systems with concurrent and non-deterministic processes, e.g. in operating systems or real-time systems, but also organizational processes such as in offices or manufacturing processes.

Elements of the Petri Net

A Petri net is a directed graph, which consists of edges and two different kinds of nodes, places and transitions.

Elements of a Petri net

Elementary links

The dynamic behavior

The network can serve as the basis for the representation of dynamic processes. For this purpose, the structural properties are supplemented by rules for dynamic behavior. The net can be seen as a game board on which a game of tokens is played. The net describes the basic behavior of a system, the game simulates a certain process.

The example in the system model of a petrol station as a Petri network gives a first impression. It fulfills the following task:

A self-service petrol station has two dispensers. Everyone has a parking space so that a car can be refueled, provided that the petrol pump is approved. The fuel pump is released by a gas station attendant after he has cashed after refueling.

System model of a petrol station as a Petri network

A distinction is made between two rules of the game regarding the allocation of the positions with brands:

  • strong rule: this special rule stipulates that each position may be assigned a maximum of one label (data type boolean). A position thus fulfills a condition that is either fulfilled or not. This corresponds to the state graph of automata theory. One speaks of a condition-event system or bool-Petri net.
  • soft rule: with the general rule, one position can be assigned several marks (data type natural). An upper limit can be set individually for each position or any number of brands can be approved. Here one speaks of a place transition network or nat-Petri network.

With transitions you have to switch between the

  • Activation (cocession) and the
  • Switching (firing) differentiate.

A transition is activated:

  • with the strong rule, if all of their input points are marked and all of their output points are not marked,
  • with the soft rule, if all input points are occupied with at least one label and all output points can accept at least one label.

A transition can only be switched if it is activated. A mark is removed from all input locations, a mark is set in all output locations.

There are no general rules for the start and duration of the switching process.

In the following, examples for activation and switching are shown in switching processes in Petri nets.

Switching processes in Petri nets

In certain situations conflicts arise in a network, but these can be resolved by inserting controlling extensions.

Conflicts in Petri nets

In addition to the basic types shown, there are various modifications. For example, in addition to the data types boolean and nat, more general data types are also permitted. In the office world, the types of forms and files are common.

Often other types of positions and transitions are also permitted, e.g. positions describing case distinctions. This means a change in the general switching rule.

Depending on their location in the network, places or transitions can have different meanings. All possibilities are shown and explained with the meaning of places and transitions according to the position in the network

Significance of places and transitions according to their location in the network

Hierarchy building

Transitions and places can be broken down into subnetworks, just as subnetworks can be combined into places or transitions. It should be noted:

  • The interface of the sub-network to the rest of the network remains unchanged, i.e. the sub-network that replaced a point has one point as an input and one point as an output. The subnetwork that replaces a transition has a transition as an input and a transition as an output.

Hierarchies in Petri nets

A few more comments on the system model of a petrol station as a Petri network, for example.

  • The parallelism of processes becomes clear, because the doubling of the fuel pump and parking space means that two vehicles can be refueled at the same time.
  • The place car in "driveway" is a branching conflict that will hopefully be resolved by the driver of the car.
  • The gas station attendant will solve the competitive conflict at the position "Tank attendant available". Small problems such as missing change are not taken into account in the model, you can think about it.
  • The problem of the endless queues of cars in front of the petrol stations, the "queues", is also not taken into account in our system. As is so often the case, it has been shifted to the street play our model according to the soft rule. The position "car in driveway" could then contain 5 brands = cars. With that we would have created a queue.

Modeling procedure

When modeling, one starts with a very abstract network, the instance-channel network. Instances correspond to the transitions, they are the active parts of the network; something is going on in them. The channels, they correspond to the places, are the passive parts. They pass something on or they save something. The Petri net with instances and channels shows such an example.

Petri net with instances and channels

In a second step, the channels are specified. The customer channel can for example consist of incoming mail or phone calls for the orders and outgoing parcel post for the delivery of goods.

Refinement of a channel

In the third step, the instances are refined from the outside in. First, one looks for an instance for each of these refined channels. If necessary, these new instances are connected via new channels within the instance to be refined. The example of the refinement of an instance makes the procedure clear.

Refinement of an instance

These refinements of channels and instances are continued until the existing or planned system is fully described. In this case, the channel-entity network changes into a place-tronsition network or even a condition-event network.

Data structuring

In the original form of the Petri nets, no language elements are provided for the specification and structuring of data.

Aptitude priorities

With the help of Petri nets, a system can be modeled very quickly as a sequence of states and events. With the brand game "the behavior or the malfunction of the system can be checked.