1
$\begingroup$

Can anyone please help me understand the quasi-liveness and liveness properties of petri nets. Suppose that you explain that to a person with 10 years old.

For my part, i have the following definitions. - quasi-liveness petri net: its mean that every transition in the net can be enabled at least one time for specific marketing. So may be enabled many times. -liveness petri net: its mean that every transition in the net can be rechargeable from any marketing.

Am i right ?, can you give me a simple example. Finally what is the best method to find these properties ?

$\endgroup$
2
$\begingroup$

Here are three examples that exhibit the properties you wondered about. The background colour of every enabled transition is green. The background colour of every non-enabled transition is white – the same background colour as the rest of the corresponding diagram.

The Petri Net and its initial marking in Figure 1 is quasi-live. It is not live because after changing from green to white once transition 1 will never change colour from green to white again.

Figure 1 A Petri Net that is Quasi-Live

A Petri Net that is Quasi-Live

The Petri Net and its initial marking in Figure 2 is live and quasi-live. Every transition in the net can change colours from green to white more than once.

Figure 2 A Petri Net that is Live and Quasi-Live

A Petri Net that is Live and Quasi-Live

The Petr Net and its initial marking in Figure 3 is neither live nor quasi-live. Transition 1 will never change colour from green to white.

Figure 3 A Petri Net that is neither Live nor Quasi-Live

enter image description here

It may not be easy to imagine the colour changes; so I also created a dynamic and interactive PDF version of this reply. With the PDF version you can control the animation of each figure and see the colour changes.

$\endgroup$
3
$\begingroup$

To answer your first question:

An attempt to explain Petri nets in terms some 10-year olds will understand (see, for instance, Murata's well-known description):

a simple lightswitch model

  1. A Petri net is a diagram that consists of three kinds of elements. We call them transitions, places, and arcs. In the example above, the transitions are green boxes and the places are white rounds. The arcs are arrows that run from places to transitions and from transitions to places. Transitions and places have names. A place may contain tokens. A token is usually drawn as a little dot.
  2. A Petri net describes a set of circumstances in which changes can happen in certain ways. It describes exactly how the changes can happen. For each change, it describes the conditions under which it can occur, and the conditions that result from the change.
  3. A transition describes a possible change. Its name should name that change. For example: a customer arrives, or: switch the light off, or: the light breaks, or: the sun goes down.
  4. A place describes a possible condition. Its name should name that condition and should be of the form: something (for example: a person, thing, place, etc.) is something (a condition that that person, thing, place, etc. is in). For example: the sun is shining, or: a customer is waiting, or: a spot is available, or: the light is broken.
  5. A token describes a particular something for which the condition holds, and to which the change applies. For instance: the sun shining, or: a customer waiting, or: a spot being available, or: the light being broken.
  6. The arcs describe which conditions must hold for a change to occur, by running from exactly those places to that transition. They describe which conditions will hold as a result of the change, by running from that transition to exactly those places. In the example given above: switch light on is only possible if the light is off; after switch light on, the light is on. Etcetera.
  7. As we said above, the places of a Petri net can contain tokens. In some Petri nets, like the example above, they never contain more than one token; in other examples they do contain more than one token. When a change occurs (we say: a transition fires), usually the count of tokens changes: some places get fewer tokens and other places get more. We can describe the state we are in by saying how many tokens are in each place. We call such a listing a marking of the Petri net. So a marking lists for each place how many tokens are in that place.

In the example above, the marking has only one token, in light is on. Only two transitions can fire: the upper light breaks and light is off.

If light breaks fires, we end up in the marking that has one token in light is broken and no tokens elsewhere. After that, no transition can ever fire again.

If instead, switch light off fires, we end up in the marking that has one token in light is off and no tokens elsewhere. In that marking, two transitions can fire, namely the lower light breaks and switch light on.

If light breaks fires, we end up in the marking that has one token in light is broken and no tokens elsewhere. After that, no transition can ever fire again.

If instead, switch light on fires, we end up in the marking that we started with.

With that out of the way, we can describe quasi-liveness and liveness:

A transition is said to be quasi-live if it can be fired at least once. That is, from the present marking, either it can fire directly, or by firing transitions it is possible to arrive in a marking in which it can fire directly. In other words: in the present situation, there is a way in which this change can occur, either now or in the future.

In the example above, every transition is quasi-live: as we have seen, two transitions can fire directly, while for the other two, a transition can fire such that they can then fire.

A marking is said to be quasi-live if all transitions are quasi-live for that marking. In other words: in the present situation, all changes can still occur, either right away or later. This is the case in the example above.

A marking is said to be dead, a deadlock, if no transitions can fire. No changes can ever occur. This is the case for the marking we reach after firing one of the light breaks transitions.

A transition is said to be live if it is quasi-live in every possible marking. That is to say: in any situation, that change can still occur, either right away or later. In the example above, no transition is live: we have found a dead marking, in which none of them can fire.

A Petri net is said to be live if all of its transitions are live. In any situation, all of the changes can still occur. Clearly this is not the case in the example above.

We can change the example by adding new transitions: repair light. That would give us a live Petri net.

To answer your second question: a standard reference for how to determine liveness of Petri nets is Murata's article mentioned above. I recommend it; it is readable and the techniques it describes are readily applicable.

Deciding whether an arbitrary Petri net is live is possible, but very hard. See, for instance, this informal discussion by prof. Javier Esparza. A fairly recent article (E. Best and H. Wimmel, Structure Theory of Petri Nets in: Transactions on Petri Nets and Other Models of Concurrency VII, 2013) says:

For liveness we know that it is at least as hard as the reachability problem. The latter is EXPSPACE-hard, and no upper complexity bounds are known at the present time.

So researchers have focused on defining limited classes of Petri nets for which properties such as liveness are easier to decide; for instance, it is co-NP-complete for free-choice nets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.