Need help understanding place invariants as used in place-transition nets

Question

Suppose I know the markings of a given place-transition net.

How do I determine which of the markings is a place invariant? I also know the initial marking. I will appreciate a very easy-to-digest explanation.

I have read page 17 of this paper, where the formula for finding place invariants is described but I do not understand it fully.

Please do not simply tell me what the place invariants are. Explain to me how I can find them so that I can always do this in the future.

Initial marking for a set of places (U,V,W,X,Y,Z):

• (0,1,1,1,0,0)

Other markings:

1. (0,1,0,0,1,0)
2. (0,1,0,1,0,1)
3. (1,0,0,1,0,0)

Answer 1

I later learned that if the set of places is (U,V,W,X,Y,Z), then the place invariants are the sets for which the sum of tokens remains the same for every marking.

So, the sets of places that form place invariants are:

1. (U,V) - sum of tokens is 1 for every marking.
2. (U, W, Y, Z) - sum is 1.
3. (U, V, X, Y) - sum is 2.
4. (X, Y) - sum is 1.

Answer 2

I see that you have answered your question, but in case others are also wondering... I'm responding to the title, "Need help understanding", rather than the specific example in the question.

Think of place invariants as a region of the net, a subset of the places, in which the number of tokens remains constant. Tokens may move from one place to another within the region, but none are created, and none vanish. Transitions are either not connected to any place in an invariant, then they cannot change the number of tokens there. Or else they take exactly as many tokens as they put back within the place invariant. These transitions may additionally change places outside of the invariant, but that doesn't matter.

My favorite way to visualize place invariants is with an overhead projector. I put the places, transitions and arcs on a slide, and use tacks for tokens. And I prepare paper cutouts for the place invariants of my examples. The paper blacks out the whole slide, except for the cutout region which shows the places of an invariant, and the transitions connected to those places.

Of course, this trick works only to some degree. Place invariants are actually multisets, so you may have to count the tokens in some places of an invariant double or triple.

Answer 3

SHORT ANSWER:

The place invariant is the set of vectors γ=transpose([γ0 γ1 ... γN]) such that Aγ=0, where A is the incidence matrix of the Petri Net. So, solving the system of equations Aγ=0 will give you the set of the place invariants.

LONGER ANSWER:

I later learned that if the set of places is (U,V,W,X,Y,Z), then the place invariants are the sets for which the sum of tokens remains the same for every marking.

I think this is not exactly right. In my understanding (from chapter 4 of this book), the place invariant is a n x 1 weighting vector γ=transpose([γ0 γ1 ... γN]) such that A*γ=0, where A is the incidence matrix of the Petri Net.

The state equation of some net is written as x = x0 + vA (with x0 the marking of the initial state, x the marking of some other state, v the sum of the firing vectors to reach the marking x). From there, we can write x*γ = x0*γ + vAγ ==> xγ = x0*γ. The last equation is derived by definition, as A*γ=0. As the equation x = x0 + vA holds for any subsequent state reachable from x0, this means that the number of tokens weighted with the place invariant will reamain the same (it's a constant) for all reachable states. It has to be noted though that for different initial markings, this constant will usually not be the same.

Answer 4

those slides explain what place invariants are pretty well