2
$\begingroup$

I am learning something about P/T petri nets from the book from Wolfgang-Reisig authors and on the seventh chapter's end there is an exercise I can not really work out.

It asks me to construct initial marking such that the following marked graph is live and safe. Note that yellow highlighted place is for the latter part of the question and does not bear any other special significance.

enter image description here

Right after this exercise, there is following task, which asks me to do this: Show that the initial marking of each marked graph can be modified such that live and safe marked graph is obtained.

Based on that, I assume that it must be possible for any marked graph to have initial marking such that the graph is live and safe. But still I was not able to construct such initial marking. Is there an algorithmic approach to the task? And if I were to remove the highlighted part of the marked graph, would it still be possible to construct such graph?

$\endgroup$
1
$\begingroup$

Why can't you find a live and safe marking?

Number the transitions from left to right $t_1,t_2,t_3,t_4,t_5$ and the places from left to right $p_1, \ldots, p_{12}$,

We need to find a firing sequence that is possible, fires all transitions at least once, has net effect zero, and never produces an unsafe marking.

It doesn't matter where we start: if the net is live, we can "cycle" any such firing sequence by moving its starting transition to the end or vice versa.

So we may as well start with the "thick" transition in the middle, $t_2$. For it to be enabled, its input places must be marked. For the firing sequence we'll construct to be safe, its output places must be empty. So let's fire it. Now, its input places are empty, and its output places are marked. We must now be able to fire $t_3,t_4,t_5$. This is possible iff exactly one of $p_9,p_{10},p_{12}$ was (and is) marked. We can then fire all three in a row. So let's pick $p_9$ as the one that was set. Then, after firing $t_2$, $t_3$ will be able to fire; firing it will enable $t_5$; firing that will enable $t_4$; firing that will put the token back into $p_9$.

After firing $t_3$, $p_4$ will be set, enabling $t_1$. The firing of $t_1$ and of $t_3,t_5,t_6$ are independent: they don't influence each other.

Having fired both $t_1$ and $t_3,t_5,t_6$, we're back at our initial marking. The net doesn't actually give us a choice: we must fire $t_3$ first, and then both $t_1$ and the sequence $t_5,t_6$ to enable $t_2$, and no alternative firing sequences exist.

So with the initial marking $p_2,p_6,p_8,p_9$, the only possible firing sequences of this net are given by the regular language $(t_2t_3(t_1|t_5t_4))^* = (t_2t_3(t_1t_5t_4 \cup t_5t_1t_4 \cup t_5t_4t_1))^*$. All of the reachable markings are safe.

By the way the example is drawn, there appears to be theory behind this example. This marked graph is special in that it is composed from three plain cycles (the ovals) by fusing some of their transitions. I'll bet Reisig's book proves that all marked graphs constructed in such a way are live and safe.

Your second question: what if we remove the place marked in yellow? Well, this only removes a constraint on the firing sequences: all existing firing sequences will continue to exist, but new ones may arise.

Indeed: after $t_4$ has fired, or in the initial marking above, $t_3$ can now already fire before $t_2$. However, this is merely a relaxing of the order in which transitions are fired, and it doesn't produce any unsafe or unlive markings. So the net remains live and safe. I suppose you'll have to prove this.

I'll guess there is another lemma in the book proving that this is true in general: that removing places from a live and safe marked graph always leaves it live and safe. I haven't read the book, so I'm not sure.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I really appreciate the extent to which you went explaining how it gets done. Thank you. $\endgroup$ – FanaticD May 9 '18 at 3:50

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.