Structuring Acyclic Petri Nets for Reachability Analysis and Control.
The incidence matricesfrom places to transitions and vice versaof an acyclic Petri net can obtain a block-triangular structure by reordering their rows and columns. This allows the efficient solution of some reachability problems for acyclic Petri nets. This result is further used in supervisory control of Petri nets; supervisors for Petri nets with uncontrollable transitions are constructed by extending the method of Yamalidou et al. (1996) to Petri nets where transitions can be executed simultaneously. A large class of Petri nets with uncontrollable transitions is given for which the maximally permissive supervisor can be realized by a Petri net. The original specification is algorithmically transformedby using the results for acyclic Petri netsinto a new specification to take the presence of uncontrollable transitions into account. The supervisor is obtained by simple matrix multiplications and no linear integer programs need to be solved. Furthermore, a class of Petri nets is given for which the supervisor can be realized by extending the enabling rule with OR-logic.
on-line computations for implementing the feedback controller are reduced signicantly and properties
of the closed-loop system can be studied using standard techniques for Petri nets. For Petri nets in
which all transitions are controllable and observable, and legal markings have to satisfy a conjunction
of linear inequalities, the controller design problem was solved by Yamalidou et al. (1996) using place
invariants (Giua et al. (1992) obtained the same result using a dierent methodology). The controller
is found by simple matrix multiplication.
When some transitions in the Petri net are uncontrollable, the construction of maximally permissive
Petri net supervisors becomes much more dicult. This problem was studied by Giua et al. (1992) and
Giua et al. (1993). A class of systems for which a maximally permissive supervisor can be realised by
a Petri net was obtained by Li and Wonham (1994) based on a linear integer programming approach.
In (Moody and Antsaklis, 1998) eorts were made to extend the supervisor design of Yamalidou et
al. (1996) to Petri nets with uncontrollable transitions. However, they do not specify a class of Petri
nets and of legal sets for which a maximally permissive Petri net supervisor can be constructed.
The goal of this paper is two-fold. In the rst part we study acyclic Petri nets and in the second
part we construct maximally permissive Petri net supervisors for a large class of Petri nets with
uncontrollable transitions. Our motivation for studying acyclic Petri nets |which form by themselves
a very restricted class of Petri nets| is that a lot of Petri nets have an acyclic uncontrollable part. We
partition the set of places and the set of transitions of an acyclic Petri net. This partition indicates how
tokens
ow through the net and is used to order rows and columns such that both the incidence matrix
from places to transitions and the incidence matrix from transitions to places obtain a block-triangular
structure. This allows us to give a direct proof for the necessary and sucient condition for point to
point reachability which was given by Ichikawa and Hiraishi (1987) and by Li and Wonham (1994).
It also shows that in an acyclic Petri net every reachable marking can be reached in as many steps as
there are sets in the partition of the transitions set. Moreover, it overcomes the problem studied by
Kostin (1997) of not knowing in which order transitions should be executed when one already has a
solution of the Petri net state equation. Also, a new algorithm for checking point to point reachability
in acyclic Petri nets is presented.
In the second part of the paper we construct supervisors for Petri nets. By using a dierent
technique we show that the result of Yamalidou et al. (1996) also holds for Petri nets in which several
transitions can be executed simultaneously and one transition can be executed more than once at
the same time. A class of Petri nets is specied for which a maximally permissive supervisor can be
realised by a Petri net even when uncontrollable transitions are present in the Petri net. This class
is more general than the one of Li and Wonham (1994). The Petri nets obtained by applying the
supervisory control reduction result of Stremersch and Boel (1999) to Petri nets belonging to this
class have an acyclic uncontrollable part. The block-triangular structure of its incidence matrices
|obtained in the rst part of the paper| is used to obtain an algorithm transforming the legal set
into a specication which takes the presence of uncontrollable transitions into account without loss
of maximal permissiveness, i.e. without becoming more restrictive than necessary. Then we apply
the supervisor design method of Yamalidou et al. (1996) to the new specication. The Petri net
supervisor is obtained by simple matrix multiplication and no linear integer programmes need to be
solved. Finally, a class of Petri nets is given for which the supervisor can be realised by extending the
standard enabling rule for Petri nets with OR-logic.
The outline of the paper is as follows. Section 2 introduces Petri net denitions and notations. In
Sections 3 and 4 the incidence matrices of an acyclic Petri net are structured and some reachability
issues for acyclic Petri nets are studied respectively. Section 5 generalises the result of Yamalidou
et al. (1996), discusses conditions under which maximally permissive Petri net supervisors can be
constructed when not all transitions are controllable and reviews the reduction result of Stremersch
and Boel (1999). A class of Petri nets for which a maximally permissive supervisor can be realised
by a Petri net is given in Section 6. This class is made more general in Section 7. Supervisors with
OR-logic in their enabling condition are studied in Section 8. Final conclusions are given in Section 9.
denitions
A Petri net is a tuple are disjoint, nite sets of places and
transitions respectively. Further, are the incidence
functions from transitions to places and from places to transitions respectively. Each transition
corresponds to an event in the discrete event system.
For each is the set of input (output)
places of t: Similarly,  denotes the set of input
(output) transitions of p 2 P: Analogous denitions are used for sets of transitions and sets of places.
Dene the incidence matrices F (from transitions to places) and F (from places to transitions) as
Further dene F
A marking is a function M be the set of all markings. It can be identied with
bag for short| is a function as the set of all transition
bags. A bag  2  is state-enabled under The set of state-enabled bags under
is denoted by m : The marking of N evolves in the following way. If m is the marking, then
a bag  2 m can be executed and the marking changes to m when  is executed. It is
said that m 0 is reached from m by the execution of : This is denoted by m Note that this
notation implies that  From the denition of  it follows that transitions are allowed to be
executed simultaneously and that the same transition is allowed to be executed more than once at the
same time. This assumption is referred to as the transition bag assumption (see also (Peterson, 1981)
and (Ushio, 1990)).
Denition 1 introduces for each k 2 N and m 2 M the set R k (m)  M: It contains the markings
reachable from m in at most k successive executions of transition bags.
Denition
The innite sequence (R i
0 is non-decreasing. Consequently, R1 (m) is well dened for each m:
For subsets M 0 of M dene R k
A path  in N is a nite, nonempty sequence of places (2 P ) and transitions (2 T ) such that for
each two consecutive elements a and b in ; b 2 a  (Desel and Esparza, 1995). Let  be the set of all
paths in N . A path  2  from a 2 P [T to b 2 P [T is a cycle if no element occurs more than once
in  and a 2 b  : A Petri net is called acyclic if it does not contain any cycles.
3 Structural analysis of acyclic Petri nets
In this section it is shown in a constructive manner that by properly ordering the rows and columns
of the incidence matrices F + and F of an acyclic Petri net these matrices obtain a block-triangular
structure.
1 For a set X; ]X denotes its cardinality. Both markings and transition bags can also be written as column matrices.
Both notations will be used interchangeably. Except for column and row matrices, matrices are set bold. The notation
is used for the subset and  for the proper subset relation.
Denition 2 For an acyclic Petri net recursively dene for all k 2 N n f0g the
mutually disjoint sets of transitions T k  T and sets of places P k
The set T 1 is the set of source transitions |transitions without input places (Murata, 1989)| of N :
The set P 1 is the set of places of which the set of input transitions is a subset of In particular, all
places without input transitions are in
Lemma 1 For each acyclic Petri net it holds that
Proof. (i) Assume that T Denition 2 this implies that
or, equivalently, that
As
holds that
(Denition 2) or that
This argument can be repeated for t 1 (see (3)). As [ k 1
in this way one can construct an
arbitrarily long path Consequently  contains at least ]T +1 transitions
and thus at least two of them will be equal. Hence,  and N contain a cycle. This contradicts N
being acyclic.
(ii) The proof is analogous to that of part (i). 2
For the result of Lemma 1(i) is that, if T 1 6= T then T 2 6= ;: For the innite sequence
mutually disjoint sets of transitions one can dene  s.t. T k
and can be empty. If T 1 6= ;; resp.
sets. For the result of Lemma 1(ii) is that, if P For the
innite sequence mutually disjoint sets of places one can dene
partitioned into  0 sets.
Proposition 1 For an acyclic Petri net N it holds that
Proof. From Denition 2 it follows that for each k 2 N
Together with the denition of  and  0 this nishes the proof.
Corollary 1 For an acyclic Petri net it holds for each k 2 that
and for each k 0 that
Corollary 2 Every path in an acyclic Petri net, with
and
; is
such that
Similar properties for paths beginning or ending in a transition follow immediately. Note that for every
pair of places (transitions) belonging to the same set P i (T i ); there exists no path which connects these
two places (transitions).
Next the consequences of the partitioning of P and T for the matrices F (from transitions to
places) and F (from places to transitions) are studied. For simplicity of notation assume that T 1
and that rows (columns) in F + and F are ordered such that places (transitions) in P 1
places (transitions) in P 2 (T 2 ) and so forth, then F + and F have the following

Figure

1: Petri net of Example 1.
block-triangular structure (see Corollary 1):
1;1 O 1;2 O
. O
O 1;1 F 1;2
O 2;1 O 2;2 F
O
. F
O
The matrices F
i;j and F i;j are in N ]P i ]T j and the matrices O i;j are zero matrices of dimension ]P i
The i-th row of block matrices (i corresponds to places in
i-th column of block matrices (i corresponds to transitions in T
The denitions of the sets P i and T i imply that each row in F
i;i with i > 1 contains at least one
nonzero element (if not the corresponding place would belong to a set P i 0 with i 0 < i) and each column
in F i 1;i with i > 1 contains at least one nonzero element (if not the corresponding transition would
belong to a set T i 0 with
then the last row (rst column) of F + and F has to be left out.
Example 1. For the acyclic Petri net of Figure 1 in which all arcs have weight 1,
When bringing rows and columns in the order the
Reachability issues for acyclic Petri nets
Reachability issues for acyclic Petri nets are studied in this section. Theorem 1 which gives a necessary
and sucient condition for a marking to be reachable from a given marking in an acyclic Petri net
can be found in (Ichikawa and Hiraishi, 1987). Here a constructive proof is given based on the results
of Section 3. In (Li and Wonham, 1994) this theorem was also proven. The present proof is in the
same spirit, but is written out in detail because it allows to formulate useful reachability properties
for acyclic Petri nets and to construct Petri net supervisors in Sections 6, 7 and 8.
For such that
0: (7)
Theorem 1 Given an acyclic Petri net It holds that
there exists a  2  such that
Proof. The 'only if'-part follows from the state evolution of a Petri net. For the 'if'-part, (8) implies
that
Partition P and T as in Section 3. We prove that  (see (6)-(7)) is a valid sequence of transition
bags starting from the initial marking This is equivalent to
which in turn follows from
We prove (11) by induction on i: Because  1 holds that
for each p 2 or that  induction hypothesis is that
To prove that
one has to check that (see (6) and (7))
Equation (12) implies that (see (6) and (7) for the second equality)
From Corollary 1 we have that  (  T i
Consequently,
If this is substituted in (13), it is left to check that
This follows from (9). As
for each t 2 T (see (6) and (7)) it holds that m
(10).
For each T 0  T dene R T 0
k (m) as the set of markings which are reachable from m in at most k
successive executions of transition bags with a zero image on T n T only transitions in T 0 are
executed. It is clear that R T
From the proof of Theorem 1 one immediately
obtains the following important result.
Corollary 3 For an acyclic Petri net holds that
(R
(R
Starting from a given marking m 0 in an acyclic Petri net, every reachable marking m f can be reached
in at most  successive executions of transition bags in the order T that  only depends
on the structure of the Petri net, i.e. only on F + and F ; and is independent of both the initial and
the nal marking. Corollary 3 solves the problem studied by Kostin (1997) in which, starting from
a solution  of (8), an algorithm is constructed for deciding in which order transitions have to be
executed to reach m f from one can do one step better than the result in Corollary 3,
i.e. every reachable marking can be reached in at most  1 successive executions of transition bags.
Proposition 2 Given an acyclic Petri net marking
(R T3
(R T1[T2
Proof. By using the notation of (6)-(7) and of the proof of Theorem 1 we prove that if
Because of  using (6)-(7) for suces to show that
From (10) we have that
It follows that
As  (  the second term in the left hand side of (15) is equal to zero. This implies (14).
Note that if T i.e. if there are no source transitions, then  For the Petri net in Figure 1
it holds that  P each reachable marking can be reached in at most two executions of transition
bags.
The results presented so far are for the transition bag assumption (see Section 2). More restrictive
assumptions were dened by Holloway et al. (1997). Under the concurrency assumption multiple
transitions are allowed to be executed simultaneously but each transition not more than once, i.e.
is the set of binary valued functions on Under the no concurrency assumption only one transition
at a time can be executed, i.e.  is the set of binary functions on T for which at most one transition
has image 1. It is clear that Theorem 1 also holds in case these assumptions are used by decomposing
the transition bags in (10) in components which satisfy these limitations.
Proof. As  1   it is clear that  1 From its denition,  2 2  ~
~
From
it follows that ~
Consequently, we have
together with
If  satises (8), then under the concurrency assumption m f can be reached in
steps and under the no concurrency assumption in
t2T (t) steps (see also (Li and Wonham, 1994)).
Note that both these numbers |in contrast with the result of Corollary 3| depend on  and thus
also on m 0 and on m f : Proposition 3 gives a necessary and sucient condition for the set of reachable
markings in an acyclic Petri net to be nite.
Proposition 3 In an acyclic Petri net N in which every source transition has at least one output
place (to rule out trivial cases), the set of reachable markings R1 (m) is nite for each m 2 M; i
there are no source transitions in N ; i.e. i
Proof. 'If'-part: As T we have that (R T 2(m))    ) (see Proposition 2) and
that the set of transition bags which are zero on T n T 2 and state-enabled under m is nite. This
also holds for all sets of transition bags which are zero on T n T i+1 and state-enabled under m i with
(R T 2(m))    Together with the fact that  is nite this nishes the
proof.
'Only if'-part: By contraposition. Assume T 1 6= ;: As each source transition has at least one output
place the marking of these places can grow unbounded.
Thus, if there are no source transitions in an acyclic Petri net, then the set of reachable markings is
nite and reachability questions can be answered via enumeration. The enumeration process can be
structured by using the result of Proposition 2.
The results presented so far only solve the problem of ordering events for a given solution  of (8).
Propositions 4 and 5 give an alternative for checking if a system of linear equalities has a nonnegative
integer valued solution to decide whether m f is reachable from m 0 in an acyclic Petri net.
Proposition 4 Consider an acyclic Petri net. If ~
(R
and there exists a place
(R T i+1
m))
Proof. As each place p in [ i
its input transitions in [ i
holds for each marking m in
R T
(R T i+1
m))    ) that m(p)  ~
Thus, if there exists a place p in [ i
then we have for this p that m(p) < m f (p); from which the result follows.
Intuitively this result follows from the fact that when executing transition bags as in (10) the marking
of a place increase or remain constant until the execution of  i and thereafter will decrease
or remain constant.
Dene for each the natural number
All input and output transitions of a place p in P i belong to [ !(p)
Proposition 5 Consider an acyclic Petri net. If ~
(R T 1(m 0
and if there exists a place
(R T i+1( ~
m))
Proof. If
(R T i+1
m))    ) it holds that
~
Together with ~
this nishes the proof.
Propositions 4 and 5 can be used in a branch and bound algorithm for checking wether m f is reachable
from m 0 in the case First construct the set R T 2
which are reachable from m 0 by the execution of one transition bag with transitions in T 2 and which
are not rejected by Propositions 4 and 5. Analogously, the set R T 3
(R T 2
procedure is repeated until m f is found, until for the set R T j
(R T 2
empty or until m f is not found in R T (R T  1
(R T 2
The usefulness of this approach will
depend on the values of !(p) i with Proposition 5) and the number of choice places. An
example where this approach is benecial is when all but the matrices F
i;i and F i 1;i
with
are zero. The generalised tree structure of Li and Wonham (1994) belongs to this class of
acyclic Petri nets. This tree structure is dened with the additional constraint that none of its places
has more than one output transition.
5 Petri net supervisors
In the second part of this paper we design maximally permissive supervisors for a class of Petri nets
containing uncontrollable transitions. Consider a Petri net which we refer to as
the Petri net plant. The control goal is that |by dynamically disabling controllable transitions|
the marking of the Petri net plant can never leave a given legal set A  M; which is dened by an
inequality with integer coecients: 2
Intersections of sets of this type are handled by successively applying the method of this paper. Assume
that A is a nonempty proper subset of M: Legal sets which are unions of sets of this type are discussed
in Section 8.
When all transitions in the Petri net plant are controllable and observable this problem was solved
by Yamalidou et al. (1996) by a method based on place invariants. They used the no concurrency
assumption: only one transition can be executed at a time. By using a dierent technique, it is shown
in x5.1 that their result also holds under the more general transition bag assumption. In x5.2 we
discuss Petri net supervisors for Petri nets with uncontrollable transitions and in x5.3 the reduction
result of Stremersch and Boel (2000) for supervisory control of Petri nets is reviewed.
5.1 All transitions controllable and observable
Consider the legal set A as in (17) and an initial marking m 0 2 A; i.e. Am 0  b: For the supervisor to
allow the execution of  2  under m 0 ; not only A(m+F)  b should hold but also A(m+F 0
for each  0 2  with  This is because the supervisors considered here cannot force events to
they can only disable them. Thus  2  can be allowed if and only if
Dene the row matrix B 2 Z 1]T as: 3
Because of 0   0 and  0  ; (19) is equivalent to
As b Am 0  0 and B  0 this condition is in the standard form of the Petri net enabling condition.
Thus, to guarantee that (18) holds the condition B   b Am 0 is added to F   This can be
seen as an extra place p c with marking b Am 0 and outgoing arcs As the above reasoning can
be repeated for m 1 the marking of p c evolves to:
when the plant's marking changes from m 0 to contains the outgoing arcs
of Consequently, the incidence matrices of the closed-loop Petri net (plant and supervisor) are@ F
The supervisor is obtained via a simple matrix multiplication. Because (18) and (21) are equivalent,
this supervisor only disables transition bags if this is necessary in order to achieve the control goal A;
i.e. it is maximally permissive. It is clear that supervisors for legal sets dened by the intersection of
a nite number of sets as in (17) can be designed by successively applying this method. In x5.2 we
3 For is the element of X which corresponds to t 2 T:
discuss how this result can be generalised to Petri net plants with uncontrollable transitions.
5.2 Some transitions uncontrollable
as the set of uncontrollable (controllable) transitions. If uncontrollable
transitions are present in the Petri net plant and the marking has always to be in some set A (not
necessarily dened as in (17)), the control specication has to be changed from A to its subset (see
(Holloway and Krogh, 1990))
A  :=
in order to avoid that a marking outside A could be reached via the execution of a sequence of
uncontrollable transition bags. As dened above, the set R T u
1 (m) is the set of markings which can be
reached from m by any nite sequence of bags containing only uncontrollable transitions.
As shown in x5.1, when A  can be described by the intersection of linear inequalities then the
supervisor for A  can be realised by a Petri net. In general, even if A is as in (17), this will not
be the case. This problem was studied in (Giua et al., 1992) and (Giua et al., 1993). In (Li and
Wonham, 1994) Petri net supervisors were constructed in the presence of uncontrollable transitions
by using linear integer programmes.
In Sections 6 and 7 we will dene a class of Petri nets |more general than the one in (Li and
Wonham, 1994)| for which the supervisor for A  can be realised by a Petri net. To construct this
supervisor no linear integer programmes need to be solved.
5.3 Reduction result for supervisory control
In this section we review the supervisory control reduction result of Stremersch and Boel (1999) and
Stremersch and Boel (2000). Note that the following results are valid for general legal sets A: Introduce
for every p in P the order relation  p in M:
Denition in M and p in
For every p in partially ordered set.
Let (X; ) be a partially ordered set and X 0  X: Then X 0 is an up-set (down-set) in (X; ) if
(Davey and Priestley, 1990). Dene O " (X;
the set of all up-sets (down-sets) in (X;
Denition 4 For A  M dene the sets of places
The sets of Denition 4 are mutually disjoint and their union is equal to P:
A path  in N is uncontrollable if all transitions in  are uncontrollable, i.e. if all transitions in it
belong to T as the set of all uncontrollable paths in N : For all
the rst (last) element of :
Dene for each p 2 P the sets (p) := fp
In words, (p) is the set of places belonging to
uncontrollable paths ending in p; (p) is the set of uncontrollable input transitions of (p) and (p) is
the set of input places of uncontrollable output transitions of p together with the singleton fpg (fpg is
added to guarantee p 2 (p) in case p  \T ;). For each holds that p 2 (p) (the sequence
which only consists of p is an uncontrollable path).
Next, we dene for each of the sets set of places and a set of uncontrollable
transitions.
Denition 5 Dene for each A  M the sets
I
I d := [
U d := [ p2P d
Proposition 6 8A
Dene the sets
I := I # [ I " [ I d and
Theorem 2 formulates the reduction result.
Theorem 2 8A  M;8m
Thus, we get from (22) and Theorem 2 that
U
If
then it is easier to construct A  with (27) than with (22). To check whether R
only transitions in
U are needed. To decide whether transitions in
U are state-enabled the marking
of places in
U is needed and to check whether
the marking of places in
needed. The union of these two sets is
I (see
Proposition 6). The set of places
I; the set of transitions
U and the functions f
A
U
I and
f A := f j
I
U form the Petri net NA := (
I ;
which is a sub-Petri net of N : Note that all
transitions in NA are uncontrollable. The structure of NA will determine the class of Petri nets with
uncontrollable transitions for which a Petri net supervisor can be obtained. To avoid confusion in the
remainder of the paper all sets of input and output places (transitions) of transitions (places) in
U
I) are taken in the original net N and not in the subnet NA :
6 Design of a Petri net supervisor
In this section we will dene a class of Petri nets (x6.1) for which the maximally permissive supervisor
can be realised by a Petri net. It is constructed in x6.2.
6.1 A class of Petri nets with uncontrollable transitions
In this section, A is dened by a linear inequality with integer coecients as in (17).
Proposition 7 Consider A as in (17). If A 6= ; and A 6= M; then we have for the sets of Denition 4
that
Proof. See Appendix A.
Thus I
Introduce the following three hypotheses:
(H1) NA is acyclic,
When hypotheses (H1) to (H3) hold, we will construct in x6.2 for A as in (17) a row matrix A  2 Z 1]P
and a number b  2 Z such that A Thus, the supervisor for the Petri net
plant N with set of uncontrollable transitions T u can then be realised by a Petri net (see x5.2). From
it follows that  0 This implies that I
(25) and (26)). In Section 7 conditions (H2) and (H3) will be further weakened.
Reorder rows and columns in F + and F such that places in
I and transitions in
U come rst.
Consequently, F + and F can be written as
where both F
A ; which contains arcs from transitions in
U to places in
I; and F A ; which contains arcs
from places in
I to transitions in
are in N ]  I ]
The matrix F 2 ; which contains arcs from places
in P n
I to transitions in
U ; is zero because of
I (see Proposition 6).
Because of (H1) we can |following the procedure of Section 3| partition the set of places
I in
nonempty sets and the set of transitions
U in nonempty sets T
implies that there are no source transitions in NA ). Assume rst that It will be shown in
Remark 1 that the conclusions also hold for
A and F A such that
places (transitions) in P 1 places (transitions) in P 2 (T 3 ) and so forth.
Because of the partitions of
I and
U and because of (H2), F
A and F A obtain the following block
structure:
O 1;2 O
O
O  1;C C C C C C C A
F 1;2
O
O 2;2 F
O
As was pointed out in Section 3, the i-th row (column) of block matrices with
A and F A corresponds to places (transitions) in P i (T i+1 ). The denitions of the sets P i and
imply that each row in F
i;i with 2  i   1 contains at least one nonzero element, and that each
column in F i;i+1 with 1  i   1 contains at least one nonzero element.
p3
c
p6
c

Figure

2: The Petri net of Example 2.
Moreover, because of (H2), (H3) and the denition of NA in x5.3, each column in F A is zero, apart
from one element in F i 1;i
which is equal to 1. This implies that the (unique) input place of t 2
is an element of P i 1 and that all output transitions of which belong to
U are in T
Example 2. Consider the Petri net in Figure 2. Controllable and uncontrollable transitions have a
label 'c' and 'u' respectively. The legal set is
Hence,
I
The sub-net NA is indicated in Figure 2. Since NA is acyclic, one can partition
into sets explained in Section 3:
and
into sets T
By bringing rows and columns respectively in the order
we obtain from (31) that
Compare the structure of these matrices with (28)-(30). 4
Lemma 3 will be used in Theorem 3.
Lemma 3 Given integers c positive integers d and a nonnegative integer c: If 4 d
for each i 2
i2f1;:::;kg
Proof. As the set described by the linear inequalities 5
is a polytope in R k and each of its vertices has integer valued coordinates. Therefore,
The left hand side of (34) is a linear programme over a polytope. If c > 0; then this polytope
vertices. With each of them corresponds a candidate optimal solution X
4 If a nonzero integer a divides an integer b; this is denoted as a j b: On the other hand, a does not divide b is denoted
as a - b:
5 R is the set of real numbers.
c
Consequently,
c
c
i2f1;:::;kg
both the left and the right hand side of (32) are equal to zero.
Corollary 4 is a direct generalisation of the necessary and sucient condition for reachability in acyclic
Petri nets of Theorem 1.
Corollary 4 Given a Petri net If the
sub-Petri net N
a  2  with j TnT
6.2 Construction of a Petri net supervisor
From (H1) and a direct generalisation of Proposition 2, we can rewrite A  in (27) by using the
partitions of
I and
U as:
(R T  1
(R
Introduce the set A
recursively dene the sets A
i as
A
g: (36)
It is immediately clear that
and that A
When hypotheses (H1) to (H3) hold, we will prove by induction on i that there exists for each
holds because A
I : The induction hypothesis is that there exists a
matrix A
Based on A
construct a matrix A
such that A
From (36), a marking m belongs to A
Using the induction hypothesis this
is equivalent to
A
As
) is an acyclic sub-Petri net of NA (see Proposition 6 and
(H1)), (38) is equivalent to (see Corollary 4):
By using the structure of F + and F (see (28)-(30)), it holds for each  2  with j TnT  i
denote the elements of j T  i
Then, (39) is equivalent to (recall that A
for each
I
A
I
A
For
I A
Because of (H3), (41) is equivalent to
I
A
Because of (H2), it holds for dierent places p 1 and p 2 in
I that p \ p \
Therefore, (42) is
equivalent to
I
A
Applying Lemma 3 for each we see that (43) is equivalent to
I
A
b; (44)
I
A
A
b:
This can be written as
A
A
where A
I n P
A
Consequently, we have obtained a matrix A
such that A
Bringing the results for all holds for
A
Theorem 3 states the main result of this section.
Theorem 3 If conditions (H1) to (H3) hold, then the row matrix A  2 Z 1]P with
A
U
I A  (p
U
is such that A
Remark 1. The result in Theorem 3 also covers the case
Remark 2. If the legal set A is equal to
then the presented theory can be applied successively if for each of the subnets NA i
(as dened in
hypotheses (H1)-(H3) hold.
Example 2 (continued). Consider again the Petri net in Figure 2. Using the result of Theorem 3 one
obtains:
A  (p 7
A  (p 8
A  (p 5
A  (p 6
A  (p 2
A  (p 3
A  (p 1
Therefore,
and the supervisor is
The closed-loop system can be found in Figure 3. The supervisor consists of one control place p c and
the arcs connected to it. Note that none of the uncontrollable transitions has an incoming arc from
the control place. 4
Because legal sets which are down-sets in (M;) form an important class of specication sets, we
formulate Proposition 8.
c
c

Figure

3: Closed-loop Petri net of Example 2.
Proposition 8 If 0  A and A 6= 0; then 0 < A  j
Proof. As 0  A it is true that Proposition 7) and thus
As A 6= 0 it is
true that P # 6= ; and thus also that
I
I: From the denition of I # and of (:) it follows
that for each p 2
I we have p  \
I 6= ;: Since NA is acyclic, one can construct
an uncontrollable path in N such that
\
It is clear that  will be less than ]P: As p  2
I and p
\
holds that A  (p
Next, we prove by induction that A  (p then we prove
A  (p i ) > 0: From Theorem 3,
A  (p i
U
I
A  (p
I
A  (p
7 Weaker hypotheses for the construction of a Petri net supervisor
7.1 Hypothesis (H2): source transitions in NA
In this section condition (H2) is replaced by the weaker condition (H2')
In contrast to (H2) source transitions, these are transitions with an empty set of input places, are now
allowed in
as the set of source transitions in N ; i.e. T s :=
can be applied to A  to obtain from (27) that
(R
Dene the set A ] as
A
By using Theorem 3 a matrix A can be constructed such that A
From (46) and (47) it follows that A
It follows immediately that
If there exists a t 2
U \ T s such that 0 < In particular, this is the case if
Proposition 8). On the other hand, if for each
7.2 Hypothesis (H3)
In this section it is shown that it is possible to weaken hypothesis (H3). In (43), we used Lemma 3 with
all d i 's, i.e. all f (p; t) with
I and t 2 p  \
equal to 1. Next, we study conditions under which
Lemma 3 can be used when more general arc weights occur. Going through the proof of Theorem 3
again, the summand of the second term in the left hand side of (43) is then
I
A
To be able to apply Lemma 3 we should have that
U
U

Figure

4: Diagram for
I when NA is acyclic.
U
We introduce hypothesis (H3b) because (H3a) should also hold for each m which can be
reached from m by the closed-loop system, i.e. the original system synchronised with the supervisor.
The condition (H3b) is not only sucient but also necessary if each output and each input transition
of p is executed at least once in one of the possible trajectories of the closed-loop system.
U in (H3b), then f because NA is acyclic and (H3b) implies
that
For
I with p  \
U as the integer which is equal to f (p; t); 8t 2 p  \
U . The
conjunction of conditions (48) and (49) is equivalent to (H3b):
I
Consider the diagram for
I in

Figure

4. It holds that  p \ p  \ T This is because for each
I; it holds that  p\T u
U or p  \T u
U (see (23)-(26)). Thus,  p\p  \T u would contradict
NA being acyclic. Therefore, together with the denition of f p ; (49) is equivalent to the conjunction
of the following three conditions
There are two cases to consider:
Case 1. If in (52) f imply that
Consequently the discrete event system modeled by N with initial marking m can be modeled by the
simpler controlled Petri net
f ) with initial marking
m; where
and
Hypothesis (H3) holds for the new model
Consequently, the results of Section 6 can be used to
construct a supervisor for it.
Case 2. If in (52) f a generalisation of hypothesis (H3) is obtained: it can
be replaced by the conjunction of (H3a) and (H3b). The construction of the row matrix A  is done in
a similar way as above.
8 Petri net supervisors with OR-logic
8.1 Unions of linear inequalities as a legal set
For Petri nets with all transitions controllable and observable it was discussed in x5.1 how for legal sets
described by the conjunction of linear inequalities the corresponding maximally permissive supervisor
can be realised by a Petri net. However if the legal set is described by the disjunction of linear
inequalities, it is necessary to extend the Petri net enabling condition with OR-logic as was pointed
out by Li and Wonham (1994).
Consider a legal set
where for each i 2
Consider an initial marking m 0 2 A; i.e. it satises
As discussed in x5.1, for the
supervisor to allow the execution of  2  under m 0 ; not only should
hold but
also
should hold for each  0 2  with  Transforming this condition to a
simpler one |as was done in x5.1| is in general very dicult or even impossible under the transition
bag assumption. Hence, we adopt the no concurrency assumption in this section: we only consider
's in  noc Moreover, we assume that
the Petri net does not contain any self-loops. Then, the enabling condition F   m is equivalent to
To allow  2  noc it should hold that
_
Because of the denition of  noc and because m 0 2 A; this is equivalent to
_
Condition (61) should be added to the enabling condition 0  m+ F: This supervisor is maximally
permissive because (60) and (61) are equivalent. The closed-loop system is no longer a Petri net.
8.2 Not all transition controllable
In this section not all transitions are controllable. Here, the legal set is
where for each i 2
and any of the sets A i is redundant. (Note that, in contrast to (58)-(59), 0  A i and 0  b i :) For
these legal sets we dene a class of Petri nets with uncontrollable transitions for which a closed-form
description of A  is given. This extends the result of Li and Wonham (1994) to Petri nets of which
the (acyclic) uncontrollable part does not have a generalised tree structure.
Dene for each i 2
i as those of Denition 4 for A i in (63).
From (63) and Propositions 12 and 13 in Appendix B it follows that A i
Together with Proposition 7 it follows that P #
Proposition 9 Consider A as in (62)-(63). If
for each i 2 holds for the sets of Denition 4 that P
Proof. See Appendix B.
For the sets P the sub-Petri net NA can be built as in x5.3. Theorem 4 gives conditions
under which A  can be written in a form as in (62)-(63).
Theorem 4 Given a legal set A as in (62)-(63). If
(i) NA is acyclic,
then the following proof species an algorithm for constructing row matrices A
numbers b
In contrast to the conditions (H1)-(H3) of Section 6 now there can be synchronisations in NA : Hypothesis
(H4) is related to the precedence path condition in (Holloway and Krogh, 1990) and (Holloway
et al., 1996).
Proof. Assume that NA does not contain any source transitions, i.e. ;: The case T 1 6= ; is treated
as in x7.1. Because the sets of reachable markings under the transition bag assumption and under the
no concurrency assumption are equal, we can use the transition bag assumption to construct A  :
Because of (i), one can partition
U in sets T
Introduce the notation
such that t  0
k (m) as shorthand for R ftg
k (m): For
each m 2 M; it follows directly from Corollary 3 and Lemma 2 that
R
U
(R t 1(m))
Recursively dene for the sets of markings A
A
where A
(see (63)). For each we
will construct by induction matrices A
and numbers b
such that
A
A
I
A
From (62),(63) and Proposition 9, it is clear that the assertion holds for 0: The induction hypothesis
is that this is true for i:
From (66), m 2 A
By the induction hypothesis, this is equivalent to
_
A
Because
is an acyclic sub-Petri net of NA (see (i)) and
because of (iv) and Corollary 4, (70) is equivalent to (F(t  i ) is the column of F which corresponds
to t  i )
_
A
Next, we prove that A
Because of (69) a sucient condition is
that for each p 2
As NA is acyclic, it is true that F(p; t  i
it is true that  t  i
I (see Proposition 6(i)), thus p 2
I: Because of (iii),
it holds that  t k 1
This implies that p 62 [
also have that p 62
I
thus A
Consequently, (71) is equivalent to
_
A
And this can be rewritten as:
_
A
where
A
I
A
The proof suggests a more direct method for constructing the set A  : For each marking m in M a
marking mm can be dened in the following way
with for each
The validity of the sequence in (74) follows from the proof of Theorem 4. For
+)-polynomial 6 in the marking m of places in
I (see also (Boel et al., 1998)). Moreover, m 2 A
From which one obtains the result of the theorem.
From the invariance property (this follows directly from (74)-(76))
U
it follows that transitions in
U do not have to be observed by the supervisor.
Example 3. Consider the Petri net in Figure 5 with legal set
From Proposition 9 it follows that P
We have that
and
g: The sub-Petri net NA is acyclic with
the marking mm is constructed as
6 In (min; +)-algebra ordinary addition is replaced by the minimum operation, and ordinary multiplication is replaced
by the ordinary addition.
c
c
p6
c
p3
c
c

Figure

5: Petri net of Example 3.
in (74)-(76):
with other elements in  2 and  3
are zero. One obtains
This also results from mm j
inserting mm in (77) it follows that A
Remark 3. For legal sets of the form
rst Petri net supervisors with OR-logic as above can be constructed for each of the specications
These controllers are then to be combined: the enabling rule for the controller part is
described by the conjunction of the enabling rules for each of the A i -supervisors.
9 Conclusion
We have structured the incidence matrices of acyclic Petri nets. This has resulted in a new proof for the
well-known necessary and sucient condition for reachability in these Petri nets, and in the solution
of other reachability issues. This result was further used to construct maximally permissive Petri net
supervisors which guarantee that the marking of the original Petri net never leaves a given set. For a
large class of Petri nets the method based on place invariants wass extended to Petri nets in which not
all transitions are controllable. The original specication was algorithmically transformed into a new
specication which takes the presence of uncontrollable transitions into account. Moreover, a class of
systems was dened for which the maximally permissive supervisor can be realised by extending the
standard Petri net enabling condition with OR-logic.

Acknowledgement

This paper presents research results of the Belgian Programme on Interuniversity Poles of Attraction,
initiated by the Belgian State, Prime Minister's Oce for Science, Technology and Culture. The
scientic responsibility rests with its authors. This work was partially supported by the European
Community Esprit-LTR Project 26270 VHS (Verication of Hybrid Systems). R.K. Boel is supported
by the Flemish Foundation for Scientic Research as Senior Research Associate.



--R


Introduction to lattices and order.
Free choice Petri nets.
Generalized mutual exclusion constraints on nets with uncontrollable transitions.
Petri net supervisors for generalized mutual exclusion constraints.

A survey of Petri net methods for controlled discrete event systems.
A generalization of state avoidance policies for controlled Petri nets.
Analysis and control of discrete event systems represented by Petri nets.
The novel algorithm for determining the reachability in acyclic Petri nets.
Control of vector discrete-event systems|Part 2: controller syn- thesis
Petri net supervisors for DES with uncontrollable and unobservable transitions.
Petri nets: properties
Petri Net Theory and the Modelling of Systems.
Controlled Petri nets and general legal sets.
Reduction of the supervisory control problem for Petri nets.
ieee Transactions on Automatic Control.
Maximally permissive feedback and modular control synthesis in Petri nets with external input places.
Feedback control of Petri nets based on place invariants.
--TR
uncontrollable transitions;acyclic Petri net;petri net;supervisory control