Centralized and Decentralized Supervisory Control of Nondeterministic Systems Under Partial Observation.
In this paper we extend our earlier work on supervisory control of nondeterministic systems using prioritized synchronization as the mechanism of control and trajectory model as the modeling formalism by considering design of supervisors under partial observation. We introduce the notion of observation-compatible systems and show that prioritized synchronous composition (PSC) of observation-compatible systems can be used as a mechanism of control of nondeterministic systems under partial observation in presence of driven events. Necessary and sufficient conditions that depend on the trajectory model as opposed to the language model of the plant are obtained for the existence of centralized as well as decentralized supervision. Our work on centralized control shows that the results of the traditional supervisory control can be ``extended" to the above setting, provided that the supervisor is deterministic and the observation mask is projection type. On the other hand, our work on decentralized control is based on a new relation between controllability, observability, co-observability, and PSC that we derive in this paper.
Introduction
Supervisory control of discrete event systems (DES's) has been studied using prioritized
synchronous composition (PSC) [4] in [5, 15, 10, 11, 12, 1, 3]. In PSC, each system component
possesses an event priority set specifying the set of events whose execution in the environment
requires its participation. Thus, when many systems are interacting, an event can occur if
and only if all the systems having priority over the event can actively participate. In this
case, the event occurs synchronously in all such systems; otherwise the event is \blocked"
from occurring. The systems which do not have priority over the event will also participate
in the event execution if they can, which is known as broadcast synchronization; otherwise
the event takes place without the participation of such systems. Thus the systems with
no priority over an event cannot block its execution. The event control function of Inan [7]
assigns state dependent event priority sets, thereby generalizing the notion of PSC. However,
when applied to supervisory control, the event control functions are taken to be constant,
thus becoming equivalent to PSC. It should be noted that in the PSC formalism each system
is associated with an event priority set, and the events that belong to that set is determined
by the application. For example in the context of supervisory control this is determined by
the controllability/drivability property of the events as explained below.
The formalism of PSC, models the interaction between discrete event plants and supervisors
quite eectively when all the events are completely observable at their interface, and
the need to ensure that interacting systems are control compatible [16, 17] is eliminated. In
this setting the priority set of the plant includes the events that are uncontrollable (such
as sensor and failure events) and controllable (such as actuator events), whereas that of
the supervisor includes the events that are controllable and driven (such as command and
control-policy switch events). Thus the controllable events are in the priority sets of both
the plant and supervisor, and can be blocked by either of them, whereas the uncontrollable
(resp. driven) events can only be blocked by the plant (resp. supervisor).
In many situations, systems interact via interfaces. For example in an elevator system
when a user requests an elevator, one of the elevators responds to the request. An internal
logic decides which elevator should respond, but this information is masked from the user.
Similarly, in a pumping station consisting of several pumps, a command to start a pump may
be non-specic, and the decision which pump to start may be resolved by an internal logic
that is masked from the agent issuing the command. These examples illustrate that certain
events of the system may be masked at the system interface from the control perspective.
Similarly, events may also be masked from the observation perspective. For example, dierent
kinds of failure events may be reported to the environment as the same type of failure; thus
masking the dierence between the failure events from the environment. In fact we can view
unobservable events as those that are masked to be indistinguishable from \silent" events.
When systems interact through non-identity interface masks, then their interaction through
PSC requires that the systems be observation compatible with respect to their interface
masks, which is a limitation of PSC [16, 17]. Thus it is sensible to generalize the notion
of PSC to describe prioritized synchronization of systems interacting through non-identity
interface masks. This then will allow us to model interactions of systems without the need
to ensure that they are control or observation compatible [16, 17].
An eort to generalize PSC in such a direction was rst presented in [16, 17], and the
generalization was called masked composition (MC). In MC, each system was associated with
two types of mask functions: a control mask that identied events \from the control perspec-
tive", and an observation mask that identied events \from the observation perspective".
Modeling the interaction of systems in this formalism is di-cult owing to its complexity.
In the present paper we introduce a very intuitive generalization of PSC, which we call
masked prioritized synchronous composition (MPSC). MPSC retains the basic concept of
PSC in that each system has its own event priority set, i.e., the set of events in which it
must participate in order for them to occur in the composition (equivalently, the set of events
it can block by not participating). The new concept that we add here to generalize PSC, is
that each system is allowed to interact with its environment via interfaces that are modeled
as event mask functions. (The masks are similar in spirit to the masks introduced in [2, 13]
but were restricted there to the observation process). Event mask functions as presented
here constitute \static" interfaces, in that they mask the events independently of the system
evolution history. It is possible to consider more general \dynamic", trace-dependent, event
masks such as the \reporter maps" in the work on hierarchical supervisory control [19, 18].
This however we do not explore in this paper.
Since a system may have multiple interfaces, the mask functions are not unique to the
system, but rather to the particular interface of the system. When two or more systems
interact at a common interface, they use their respective mask functions to map their respective
\internal" events to the \external" or interface events. Since internal events of a
system that are masked to a common external event interact with the environment indistin-
guishably, there is no loss in assuming that a mask function respect the priority partition of
the events, i.e., two events can be masked to a common external event if and only if they are
either both or none in the priority set of the system.
Below, we formally dene masked prioritized synchronization of discrete event systems
modeled by nondeterministic state machines. MPSC can be used to model the interaction
of systems at multiple interfaces. We show that the MPSC of systems can alternatively be
computed by \unmasking" the PSC of suitably \masked" systems, thereby establishing a
link between MPSC and PSC. We prove that when systems are connected at a common
interface, their MPSC satises the desirable property of associativity, showing that MPSC
provides a useful formalism for modeling system interaction. Finally, we study the problem
of MPSC based control of a discrete event plant with priority set being the entire event set.
The plant interacts via MPSC with a supervisor, modeled as a deterministic state machine,
for which the event priority set and the interface mask are given. Under the assumption
that the set of driven events is empty, we show that there exists a supervisor so that the
behavior of the MPSC of the plant and the supervisor projected onto the event set of the
plant equals a specication language if and only if the specication language is controllable
and normal. (The more general case of nonempty driven events set is reported in a recent
paper [8].) The proof of this existence result is constructive and provides a way to compute
a supervisor whenever one exists. These results extend the existing results on supervisory
control that permits control masks (limited to projection type) and observation masks to be
associated with the plant only. We illustrate our design via a simple example. In particular
this example shows the eect of having masks associated also with the supervisor, and of
having general non-projection type control mask associated with the plant.
Notation and Preliminaries
Given an event set , we let   denote the set of all nite-length sequences of events
from , called traces, including the trace of zero length, denoted . For an event set , we
use  to denote  [ fg. A subset of   is called a language. Given trace s 2   , we let jsj
denote its length. For a language H    , the prex-closure of H, denoted pr(H), is the set
of all prexes of traces from H. H is called prex-closed if
Nondeterministic state machines (NSM's) are used to model discrete event systems. A
NSM P is a ve tuple: P := (X
its set of states,  P is its
set of events, - its transition function, x 0
state, and X m
its set of marked, or nal, states. For any set of states X  X P
and set of events    P , the notation - P (X; ) is used to denote S
is called deterministic if j- P (x; )j  1 for all x
triple called a transition if x
transition is called silent or an -transition. Given an interface mask
from the internal events  P to external interface events , the \masked" NSM M(P ) :=
obtained by replacing each transition
of P by the transition (x; M(); x 0 ). The interface mask M P is extended to be dened over
traces in
P as follows:
For the -closure of x, denoted
P (x), is the set of states reached by the execution
of zero or more -transitions from the state x, and is dened recursively as:
The -closure map can also be used to extend the denition of transition function from events
to traces. Thus we obtain -
which is dened inductively as
where for any ^
Using this extended transition function,
the generated and the marked languages of P , denoted, respectively, L(P ) and Lm (P ), are
dened as:
When two systems P and Q interact via prioritized synchronization, their interface events
are the same as their own internal events since in PSC the interface masks of both P and
Q are the identity function, i.e.,  Letting A; B   denote the event
priority sets of P and Q respectively, their PSC, denoted P A k B Q, is the NSM dened as
the transition function dened as:
otherwise,
The event priority set of P A k B Q is given by A [ B.
Thus, if an event is executable in both systems, then it occurs synchronously with the
participation of both the systems. Otherwise if it is executable in only one of the systems,
and the other system cannot block it (it is not in the event priority set of the other system),
then it occurs without the participation of the other system. Finally, the composition can
execute -transitions asynchronously. In the special case when the event priority sets of
both systems are the entire event set , then in their composition each event can only occur
synchronously, resulting in the reduction of the PSC to the strict synchronous composition
(SSC).
We recall the conditions of controllability and normality of discrete event systems which
we shall need later. Given an event set , a prex-closed language H    , a set of events
, and a mask function M dened over , a language K  H is said to be (H; ^
controllable [14] if
and it is said to be (H; M)-normal [13] if
We further recall that controllability (resp. normality) is preserved under language union.
Consequently, the supremal controllable (resp. the supremal normal) sublanguage of a given
language exists. Similarly, controllability (resp. normality) of prex-closed languages is
preserved under language intersection, whence the inmal prex-closed and controllable
(resp. the inmal prex-closed and normal) superlanguage of any given language exists.
Masked Prioritized Synchronization
In this section we formalize the notion of masked prioritized synchronous composition
(MPSC) of two systems as discussed in the introduction. Two systems, modeled as NSM's
I
System, P
Event set, S
Mask, M
Event set, S
System, Q
Mask, M
Interface event set,

Figure

1: P and Q interacting at a common interface
P and Q, are connected as shown in Figure 1. P and Q evolve over their \internal" events
P and Q respectively, and their event priority sets are A   P and B  Q respectively.
The systems interact at a common interface consisting of the interface (or \external") events
I . The interface mask of P is given by M and that of Q is given by
[fg. The composed system is denoted by P A [] B Q, where the two interface
masks M P and MQ are not explicitly included in the notation (to keep the notation simple).
The interface masks respect the event priority-partition consistency condition, that is,
A similar condition is satised by the interface mask MQ . Interface masks that respect
the event priority-partition consistency condition are called priority consistent masks. If we
then the priority consistency
conditions can be rewritten as M 1
Remark 1 The formalism of MPSC is also applicable to systems interacting at multiple
interfaces. For example in Figure 2 P and Q interact at a pair of interfaces. The interface
mask of P for the two interfaces are respectively, and
similarly those for Q are MQ1 respectively. This scenario
System, P
Event set, S P
Mask, M
Interface event set,
Mask, M
Mask, M
Mask, M
Interface event set, S
Event set, S
System, Q

Figure

2: P and Q interacting at two interfaces
where P and Q interact at two interfaces can be transformed into the one where they interact
at a single interface through masks M P and MQ , respectively, dened as follows:
Example 1 Consider for example a pumping station G consisting of two identical pumps
a synchronizer R sharing a common interface, as shown in Figure 3. (In all
our examples we assume that all states are marked and omit indicating the markings from
the gures.) The event set of pump i consists of fa representing start, stop, fail,
Interface
Pumping Station, G
Synchronizer, R
a
f
f
r
Controlling Station, S
a
a 2
a 2
a 1

Figure

3: Interacting pumping and controlling stations
and repair respectively, and that of the synchronizer consists of g. The synchronizer
assures that the two pumps are started alternately, and the rst pump is started initially.
The priority set of pump i consists of fa g, and that of the synchronizer consists of
g. Also the three systems interact with each other via the identity interface mask. So
the MPSC of the three systems is equivalent to their PSC, and can be obtained using the
denition of PSC. The event priority set of the pumping station G is given by the union of
the event priority sets of its three subsystems.
The pumping station G interacts with a controlling station S at a dierent interface and
oers a start, and a stop button, and a fail indicator at this interface. The controlling station
can start (event a), stop (event b), or issue a repair command (event r) whenever a fail (event
f) is indicated. The priority set of the controlling station consists of fa; b; rg, and its interface
mask is the identity function. The interface mask MG of the pumping station identies a i 's
to a, b i 's to b, f i 's to f , and r i 's to r, at the interface with the controlling station. Clearly,
MG is priority consistent. Since a i 's and b i 's are priority events of G, and are masked to
a and b respectively, which are priority events of S, a i 's and b i 's are controllable events.
However, they are only non-uniquely controllable since both a i 's (resp. b i 's) are enabled in
G when a (resp. b) is enabled in S. On the other hand, f i 's are uncontrollable events since
they are in the priority set of G, and are masked to f which is a non-priority event of S.
Similarly, r i 's are the driven events since they are non-priority events of G, and are masked
to r which is a priority event of S.
Denition 1 Consider systems P and Q interacting at a common interface with events
I as shown in Figure 1, their respective event priority sets A and B, and their respective
priority consistent interface masks M P and MQ . Then the masked prioritized composition of
P and Q is given by P A [] B Q := (X; ; -; x
dened as follows:
The event priority set of P A [] B Q is given by
Intuitively, P and Q interact by either executing synchronously events  p and  q , respec-
tively, whenever these are executable in the respective states and are masked to a common
interface event that is observable at the interface or, alternatively, they execute individual
events (without participation of the other system) whenever the event is either unobservable
at the interface, or no event of the other system that has the same observation as the former
event is executable at the current state, and the event cannot be blocked by the other
system (in the sense of PSC). An -transition can, of course, occur asynchronously in the
composition. Note that if P and Q have m and n states respectively, then the number of
states in their MPSC is O(mn), and hence there can be O(mn) transitions dened at each
state.
Example 2 Consider the state machines P and Q shown in Figure 4(a)-(b). We have
g. The masked prioritized composition, P A [] B Q is
e
e,
4,4
e
(c,
e
(c,
(c, )2 3 41,1
e
f
c
a (b,e)
(b,f) (a,e) (a,f)
e
2,3 4,1
e
f(b) (c)
(a)
(b,
(b,f)
4,2
e

Figure

4: Illustration of MPSC
shown in Figure 4(c). The transitions labeled (b; e); (b; f); (a; e); (a; f) are as in the rst case
of Denition 1, those labeled (c; ); (b; ) are as in the second case of the denition, that
labeled (; g) is as in the third case of the denition, and nally that labeled  is as in the
fourth case of the denition.
Remark 2 Note that in the second clause of Denition 1, M 1
only
similar statement applies to the third clause. So it
follows that
Q; (1)
and hence there is no loss of generality in requiring that the masks be priority consistent.
(If the masks are not priority consistent, then the priority sets can be redened as ^
so that the MPSC remains unaltered but the masks
become priority consistent.)
The \external" behavior of the MPSC of P and Q observed at the interface, called the
projection of P A [] B Q on  I and denoted (P A [] B Q)" I , is obtained by replacing transitions
of P A [] B Q as follows:
1. replace it by (x; M P ( p ); x
2. replace it by (x; M P ( p
3. 8(x; (;  q replace it by (x; MQ ( q
Thus the behavior observed at the interface consists of only the external events  I .
Similarly, the behavior of the MPSC of P and Q projected to the events of P , denoted
obtained by \erasing" each Q -event label from all transitions of P A [] B Q
as follows:
replace it by (x;
It is easily seen that the generated (resp. marked) language of (P A [] B Q)" P is contained in
the generated (resp. marked) language of P . Thus MPSC of P with Q restricts the behavior
of P . This fact can be used to employ MPSC as a mechanism of control.
Example 3 The MPSC of the pumping station G and the controlling station S of Example 1
is shown in Figure 5. In each state number of the composition, the rst index denotes the221223151122 11131135f ,f
r ,r
a ,a
a ,a
a ,a
b ,b a ,a
f ,f
r ,r1f ,f21112(

Figure

5: MPSC of pumping and controlling stations
state of the synchronizer, the second that of the pump 1, the third that of the pump 2, and
the fourth that of the controlling station. Each transition is labeled by a pair of symbols|the
rst (resp. second) is the event label of the corresponding transition in G (resp. S).
In the initial state (1111), a 1 is enabled in R and P 1 , a 2 in P 2 , and a in S. Since a 1 is
in the priority set of R and P 1 , and it is masked to a which is in the priority set of S, a 1
synchronizes with a causing a transition to the state (2212). On the other hand, since a 2 is
in the priority set of R also, which refuses it in its initial state, a 2 is initially blocked in the
composition. Similar analysis can be used to derive the entire NSM of the composed system
as depicted in Figure 5.
Next we show that the MPSC of two systems can alternatively be obtained by rst
\masking" the individual systems, next computing their PSC, and nally relabeling the
transitions by \unmasking" them as described in the following algorithm.
Algorithm 1 Consider systems P and Q interacting at a common interface with events  I
as shown in Figure 1, their respective event priority sets A and B, and their respective priority
consistent interface masks M P and MQ . Then their MPSC P A [] B Q := (X; ; -; x
be obtained as follows:
1. Compute the \masked" NSM's M P (P ) and MQ (Q), and masked event priority sets
2. Compute the
3. Replace each transition in M P
to obtain NSM R as follows:
(a)
replace it by the set of transitions
ii.
iii.
(b)
add the set of transitions
ii.
Note that the complexity of Algorithm 1 is of the same order as the number of transitions
in the MPSC of P and Q. (if P and Q have m and n states respectively, then there are
transitions in their MPSC.)
The following theorem proves the correctness of Algorithm 1.
Theorem 1 Let R be as in Algorithm 1. Then P A [] B
Proof: Since the two NSM's P A [] B Q and R have identical states X := X P XQ , identical
events  identical initial state x 0 :=
nal
states
Q , we only need to show that they also have the identical set of
transitions. We rst show that each transition of R is also a transition of P A [] B Q.
Consider rst a transition ((x
of R as in clause
3(a)i. of Algorithm 1. Then from this clause, x 0
. So from the rst clause in Denition 1 it follows that ((x
is a transition of P A [] B Q.
Next consider a transition ((x
R as in clause
3(a)ii or 3(b)i. of Algorithm 1. In the rst case from clause 3(a)ii. we have x 0
and - Q
in the second case from clause
. So in either case, it follows from the second clause in
Denition 1 that ((x
is a transition of P A [] B Q. By symmetry a transition
of R is also a transition of P A [] B Q.
Finally, consider a transition ((x
of R as in clause 3(b)i.
of Algorithm 1. Then from this clause x 0
from the last clause of De-
nition 1, ((x
transition of P A [] B Q. By symmetry, a transition
of R is also a transition of P A [] B Q.
It remains to prove the converse that each transition of P A [] B Q is also a transition of
R. Consider rst a transition ((x
as in the rst clause of Denition 1. Then from this clause x 0
and x 0
it follows from the rst clause in the denition of PSC that
q )) is a transition of M P
applying clause
3(a)i. of Algorithm 1 we conclude that the transition ((x
q )) is also a
transition of R.
Next consider a transition ((x
as in the second clause of Denition 1. Then from this clause we have x 0
either - Q
We consider the two
cases separately. In the rst case when M
it follows from the second clause in the denition of PSC
that
applying the
clause 3(a)ii. of Algorithm 1 we conclude that the transition ((x
a transition of R. On the other hand, in the second case when M , from the
last clause in the denition of PSC, we have ((x
is a transition of
by applying the clause 3(b)i. of Algorithm 1 we conclude
that
is a transition of R. By symmetry we have that a transition
of P A [] B Q is also a transition of R.
Finally, consider a transition ((x
from the last clause in Denition 1, x 0
Hence
from the last clause in the denition of PSC we have that ((x p ; x q
of M P
by applying the clause 3(b)i. of Algorithm 1 we conclude
that
is a transition of R. By symmetry we have that a transition
of P A [] B Q is also a transition of R. This completes the
proof.
Theorem 1 establishes a link between MPSC and PSC. By denition MPSC generalizes
conversely, it follows from Theorem 1 that MPSC can be computed using the denition
of PSC by applying Algorithm 1, which requires a \pre-masking" and a \post-unmasking"
operation. This fact is not explored in this paper any further. A consequence of Theorem 1,
however, is that P A [] B Q"
which can be used to derive
results regarding the control of the behavior observed at the interface.
We next investigate the associativity of MPSC. It is known from [5], Theorem 13.4 (see
also [10] where a detailed proof was given) that PSC is associative, i.e., given NSM's
that evolve over a common event set  along with their respective priority sets A; B; C
the following holds:
Thus associativity lets us compute the composition of several systems by computing it two
at a time.
We show that the property of associativity also holds for MPSC of systems interacting at
a common interface. Consider for example three NSM's with respective event priority
set A   interacting at a common interface as shown in Figure 6. The
interface masks of are given by M P ; MQ ; MR respectively.
System, P
Event set, S P
Mask, M
Event set, S
Mask, M Q
Event set, S
System, Q
System, R
R
R
Interface event set, S I

Figure

R interacting at a common interface
In order to demonstrate associativity of MPSC we show that MPSC of can be
computed by rst computing the MPSC of any of the two systems and next composing this
with the third system. Two ways of achieving this are shown in Figure 7. In Figure 7(a)
composition of rst obtained and next this is composed with R, whereas in Figure 7(b)
composition of Q; R is rst obtained which is then composed with P . We use the mask
function to denote the mask function of the composition P A [] B Q, the rst
second) component of which applies to transitions with an event label in  P (resp.
that whenever a transition in P A [] B Q is labeled by an event pair (
both the events are masked to the same interface
event which is observable at the interface. So there is no confusion of event synchronization
when the composed system P A [] B Q interacts with R.
Theorem 2 Consider systems R interacting at a common interface with events  I ,
their respective event priority sets A; B; C, and their respective priority consistent interface
masks
I
MPSC of Q&R
MPSC of P&Q
R
R
(a)
(b)
R
Mask,
Mask,
Mask,
Interface event set,

Figure

7: Two ways of associating composition of
denote the state set and the event
set of the composition. Then the proof follows from the fact that the composition of the
three systems in either of the two congurations of Figure 7(a)-(b) has identical transition
function and is given by:
R
Finally the event priority set of the composition of the three systems in either of the two
congurations of Figure 7(a)-(b) equals
Remark 3 The transition function of the three systems given in the proof of Theorem 2
also denes the transition function of the composition of the systems shown in Figure 6.
In this section we extend the supervisory control theory to the present setting where
a supervisor controls a discrete event plant by interacting with it at a common interface
via masked prioritized synchronization similar to that shown in Figure 1 under the restriction
that the set of driven events is empty. The plant is modeled by a NSM G :=
G ) having event priority set A  G and priority consistent interface
I is the set of interface events. Since the supervisor exercises
its control based on its observation of the event-traces generated by the plant, it is modeled
by a deterministic state machine S :=
). The event priority set of the
its interface mask are given.
It is natural to require that each event of the plant be either in the priority set of the
plant or be identied via the interface masks with some event that is in the priority set of the
supervisor, i.e., G A  M 1
G In other words, the
set of plant events is the union of controllable events: A\M 1
G (M S (B)), the uncontrollable
events: A M 1
G (M S (B)) :=  u , and the driven events: M 1
G A.
This requirement is consistent with the corresponding requirement in the setting of PSC
that each event of the plant is either in its own priority set or in the priority set of the
supervisor, and rules out the possibility that a non-priority event of the plant is identied
with no priority event of the supervisor or is masked to . The above requirement together
with the assumption that there are no driven events implies that A.

Table

1 summarizes the controllability and observability property of each event of the
plant that results from the event priorities and interface masks of the plant and the super-
visor. Similarly Table 2 summarizes the properties of the events of the supervisor. Note
plant event identied with supervisor event event type
priority priority controllable & observable
priority non-priority uncontrollable & observable
priority no event (epsilon) uncontrollable & unobservable
non-priority priority driven & observable
non-priority non-priority non-existent
non-priority no event (epsilon) non-existent

Table

1: Controllability & observability property of plant events
that while the supervisor can execute an observable driven event to issue a command, it can
execute an unobservable driven event to change its control policy.
supervisor event identied with plant event event type
priority priority controllable & observable
priority non-priority driven & observable
priority no event (epsilon) driven & unobservable
non-priority priority uncontrollable & observable
non-priority non-priority non-existent
non-priority no event (epsilon) non-existent

Table

2: Controllability & observability property of supervisor events
The control specication is given by a language K
G describing the permitted event
sequences of the controlled plant (G A [] B S)"G . The control task is to design a deterministic
supervisor S such that the controlled plant behavior satises the specication under the
restriction that no driven events are present.
Example 4 Consider the pumping station G and interface MG of Example 1 as the uncontrolled
plant. The control task is to design a controlling station S that restricts the plant
to operate so that at least one pump is idle at any given time. This desired specication is
shown in Figure 8. The event priority set and the interface mask function of a controlling
station to be designed enforcing such a specication are as given in Example 3, except we
assume that the repair events are also controllable. (Recall our assumption for this section
that the set of driven events is empty.)
a 1
a 2
G

Figure

8: Design specication for the pumping station
We are interested in obtaining a necessary and su-cient condition for the existence of a
supervisor for the supervisory control problem described above. Under the assumption of no
driven events we show that (L(G);  u )-controllability together with (L(G); MG )-normality
of the desired behavior K, serves as a necessary and su-cient condition for the existence of
a supervisor. We rst prove two preliminary results about controllability and normality.
The rst lemma provides an alternate characterization of (
G , and a mask MG . Then the following are equivalent:
1. K is (
2. 8s; s
3.
Proof: We begin by showing the equivalence of the rst two assertions. To see that the rst
assertion implies the second, it su-ces to note that MG so from (
normality of K, it follows that s 0 t 2 pr(K). To see the converse, pick s 2 pr(K); s
G
such that MG setting t :=  in the second assertion it follows that
Next we prove the equivalence of the last two assertions. To see that the second assertion
implies the third, simply set s := v. Then from the hypothesis of the
third assertion MG from second assertion s To prove the
converse we x t and proceed by induction on jsj+js 0 j. For the base step, let jsj+js
without loss of generality let s From the hypothesis of
the second assertion st 2 pr(K), and MG
the third assertion u pr(K). Next for the induction step let s := s; s 0 := s 0  0 ,
. Then we have three possible case: (i) MG
We only analyze the rst case; the others can be analyzed similarly. In the rst case since
and since from the hypothesis of the second assertion st = st 2 pr(K),
it follows from the induction hypothesis that s t. Then since
it follows from the third assertion that
completing the induction step.
Remark 4 Let S be a trim [6] deterministic state machine that accepts a (
language K
G so that it follows from the third assertion of Lemma 1
that for any u 2 L(S) and indistinguishable events ;  0 2 G , u and u 0 are Nerode-
equivalent. Hence S can be chosen such that transitions on a pair of indistinguishable events
(under MG ) from any state whenever dened have the same successor state, and transitions
on unobservable events (under MG ) from any state whenever dened are self-loops. We
exploit this fact in constructing a supervisor for our supervisory control problem.
Let K u;MG denote the inmal prex-closed (
superlanguage of K. Then the next lemma states that K u;MG \ L(G) equals pr(K) if and
only if K is (L(G);  u )-controllable and (L(G); MG )-normal.
Lemma 2 Consider plant G, language K  L(G), set of uncontrollable events  u  G ,
and interface mask MG . Then K u;MG \ only if K is (L(G);  u )-
controllable and (L(G); MG )-normal.
Proof: We rst prove the necessity. To see the (L(G);  u )-controllability of K, pick s 2
pr(K) and  2  u such that s 2 L(G). Then from (
)-controllability of K u;MG ,
desired. Similarly to see the
)-normality of K, pick s 2 pr(K) and t 2 L(G) such that MG
from the (
)-normality of K u;MG , t 2 K u;MG . This implies t 2 K u;MG \
pr(K) as desired.
Next to prove su-ciency it is enough to show that K u;MG \ L(G)  pr(K), since the
reverse inclusion holds trivially. Clearly, this is true for we assume K 6= ;. We
prove the desired inclusion by induction on the length of traces. Since  2 pr(K) (recall
K 6= ;), it su-ces to show that for any s 2
G such that s 2 K u;MG \ L(G),
pr(K). By the induction hypothesis, s 2 pr(K), and since s 2 K u;MG , it follows from
its denition that either (i)  2  u , or (ii) there exists t 2 pr(K) such that MG
(Otherwise the proper sublanguage of K u;MG , K u;MG fsg
G , obtained by disabling
after s is a prex-closed, (
)-normal superlanguage of K,
a contradiction.) Since we also have s 2 L(G), (L(G);  u )-controllability of K in case (i)
)-normality of K in case (ii)) implies s 2 pr(K) as desired.
We next state the result for the existence of the supervisor.
Theorem 3 Consider a plant G with priority set A = G and priority consistent interface
I . Let K  L(G) be a prex-closed nonempty desired language,  S
be the event set of the supervisor, B   S its event priority set, and its
priority consistent interface mask. Then there exists a deterministic supervisor S such that
only if K is (L(G);  u )-controllable and (L(G); MG )-normal,
where  u := A M 1
G
Proof: We rst prove the necessity. Let G A []
To see (L(G);  u )-controllability and (L(G); MG )-normality of
pick
since must participate in the execution of every event in the trace u. This
together with the fact that u 2 implies that there
exists x since
every event in M 1
is dened at every state of S, it follows that either
(which is the case when MG
In either case, we have proving that u 2
K. Next since v 2 L(G) there exists x 0
2 XG such that x 0
Moreover, since MG it follows from the determinism of S that the same set of
states are reached by \tracking" the two traces u and v in S, including the state x s . This
implies
Next to prove the su-ciency construct a deterministic supervisor as follows. First construct
a deterministic trim state machine
that generates K u;MG , the inmal prex-closed (
superlanguage of K. Then as explained in Remark 4 since K u;MG is (
can be chosen so that transitions on indistinguishable events on any state whenever dened
have the same successor state, and transitions on unobservable events on any state whenever
dened are self-loops.
Next obtain a supervisor
by modifying each transition (x;  of S as follows:
1. if MG ( g ) 6= , then replace it by a transition (x;  s
2. if MG ( then delete this transition
Then it is easy to see that S is deterministic. It remains to show that L((G A [] B S)"G
Since K is (L(G);  u )-controllable and (L(G); MG )-normal, from Lemma 2 it su-ces to show
As before let G A []
We rst prove the forward containment in Equation (2). Since L((G A [] B S)"G )  L(G)
it su-ces to show that L((G A [] B S)"G )  K u;MG . First consider a trace s that G A [] B S
generates. Then since G has priority over each event (the set of driven events is empty),
it participates in each transition of the trace. On the other hand, since S has priority over
controllable events and has transition dened on every observable uncontrollable event at
each state, it participates in the execution of each observable event of the trace. We show by
induction on length of s 2 L((G A [] B S)"G ) that s 2 K u;MG . Clearly, this holds for length
zero since K u;MG is nonempty and prex-closed, which establishes the base step. For the
induction hypothesis let . If  g is uncontrollable or unobservable, then by denition
of K u;MG and induction hypothesis (which implies s 2 K
On the other hand if  g is controllable and observable, then a corresponding
event occurs synchronously in S. This means that if x is the state reached by the execution
of s in S, then  g is dened at x, which of course implies that
This proves the induction hypothesis.
To complete the proof of the su-ciency part we next need to show the reverse containment
in Equation (2). Pick u L(G). Then there exists unique state
and a state x g 2 XG such that - S
be the trace corresponding to u g obtained by relabeling/deleting the various transitions
of u g in S. Then M S (u s
it is easy to see that
The supervisor constructed in the proof of Theorem 3 is based upon a generator of
. The following lemma provides a modular way of doing that. We let K u
denote the inmal prex-closed (
)-controllable and the inmal prex-closed (
normal superlanguage of K, respectively. It is known that K
u and K
G MG (pr(K)).
Lemma 3 Consider K
G , a set of uncontrollable events  u  G and a mask MG over
G . Then K
Proof: The backward containment can be shown as follows. By denition we have K u
K u;MG , which implies (K u where the last equality follows
from the fact that K u;MG is prex-closed and (
)-normal. For the forward
containment, it su-ces to show that (K u ) MG is a prex-closed (
)-normal superlanguage of K since K u;MG is the inmal such language. By de-
nition (K u ) MG is a prex-closed and (
)-normal superlanguage of K, and it remains
to show that it is also (
To see this, pick s 2 (K u ) MG and  2  u .
Then there exists t 2 K u such that MG prex-closure and (
controllability of K u it follows that t 2 K u . Finally since MG
that s 2 (K u ) MG as desired.
Remark 5 Lemma 3 provides a modular way of constructing K u;MG . Given a trim acceptor
for K (which generates pr(K)), we rst obtain a generator for K
u by
augmenting the state space of the acceptor of K with a \dump" state, and then by adding
transitions from each state to the dump state on those uncontrollable events that are undened
at that state. Next we obtain the generator for (K u
G MG (K u ) by replacing
the event label  of any transition in the generator of K u by event labels in the set M 1
G (),
and also adding self-loops on all unobservable events at each state of the generator of K u .
Example 5 We now return to Example 4 where a specication for the pumping station
G of Example 1 was formulated, with a slight modication that the events r 1 and r 2 are
controllable events (instead of being the driven events) so that we can apply the results of
Theorem 3 (recall that Theorem 3 requires the restriction that the set of driven events be
empty). This specication, shown in Figure 8, when intersected with the generated language
of the pumping station imposes the language K  L(G) as shown in Figure 9. In this gure22131122a1132 1
r 2b

Figure

9: Specication K  L(G) for pumping station G
each state has four components, the rst component denotes the state of the synchronizer

Figure

3), the second that of the pump 1 (Figure 3), the third that of the pump 2 (Figure 3),
and the last that of the specication (Figure 8).
Since K is prex-closed and nonempty, from Theorem 3 there exists a deterministic
supervisor S such that L((G A [] B S)"G only if K is (L(G);  u )-controllable
and (L(G); MG )-normal. In this case  and MG identies a i 's to a, b i 's to b, f i 's
to f , and r i 's to r. We use Lemma 2 to verify (L(G);  u )-controllability and (L(G); MG )-
normality of K. The generator for K u;MG is shown in Figure 10(a). Then it is easy to
see that the synchronous composition of this with G yields the same state machine as the
generator for K shown in Figure 9. This establishes that K is (L(G);  u )-controllable and
Using the procedure described in the su-ciency part of the proof of Theorem 3 we arrive
at the supervisor shown in Figure 10(b) that enforces K as the projected behavior on the
event set G of the composed system G A [] B S.
Remark 6 Theorem 3 provides a necessary and su-cient condition for the existence of a
deterministic supervisor S with event priority set B and interface mask M S for a given plant
G with event priority set A = G and interface mask MG so that the projected behavior
on the plant events of the composed system equals a given specication language K, i.e.,
in terms of the familiar conditions of controllability and normality.
The existing tests for controllability and normality, which are of polynomial complexity, can
thus be applied to verify the existence of a supervisor (see for example [9, Sections 3.2.3,
4.2.3]).
r ,r
r ,r
f ,f
a ,a
a ,a
f ,f
f ,f
f ,f
(a)24
a
f
f
a b
r
(b)
f

Figure

10: Generator for K u;MG and supervisor S
In the proof of the su-ciency part of Theorem 3 we also provide a technique to obtain
a supervisor whenever it exists: First obtain a minimal deterministic state machine S that
generates K u;MG , the inmal prex-closed (
perlanguage of the specication language, where  u := A M 1
G
replace each observable event label  g 2 G of any transition in S by an event label  s 2  S
such that M S ( s all transitions of S on unobservable events.
In case the specication language does not satisfy either controllability or normality con-
dition, a maximally permissive supervisor can be obtained by replacing the specication
language by its supremal prex-closed (L(G);  u )-controllable and (L(G); MG )-normal sub-
language, which can be computed using the existing algorithms (see for example [9, Section
4.2.2]).
5 Conclusion
In this paper we introduced the notion of masked prioritized synchronous composition
(MPSC), to model the mechanism of interaction of discrete event systems that interact with
the environment through interfaces. This extends the formalism of prioritized synchronous
composition (PSC) which assumes the identity interface mask function. This extension is
particularly useful in supervisory control where the limited control and observation capabilities
of a supervisor are captured in the external interconnection mechanism of MPSC rather
than the internal state logic of the supervisor.
We established a link between MPSC and PSC by showing that MPSC of two systems can
be computed using PSC, by applying a \pre-masking" and a \post-unmasking" operation.
We also showed that whenever three or more systems interact at a common interface, their
MPSC possesses the desired property of associativity. This is specially useful in context
of supervisory control where the plant and supervisor are distributed consisting of several
interacting components.
We also studied the problem of obtaining a supervisor that controls a given discrete
event plant by the MPSC based interaction when there are no driven events, so that the
behavior of the composed system, when projected on the events of the plant, equals a given
specication language. The familiar conditions of controllability and normality were found
to be necessary and su-cient for the existence of a supervisor. A recent paper [8] studies
the more general case of supervisory control when the set of driven events is nonempty.



--R

Input/output discrete event processes and communication delays.
Supervisory control of discrete event processes with partial observation.
On Object Oriented Nondeterministic Supervisory Control.
Concurrency and discrete event control.
Algebra of discrete event processes.
Introduction to Automata Theory
An algebraic approach to supervisory control.
Supervisory control of nondeterministic discrete event systems with driven events via masked prioritized synchronization.
Modeling and Control of Logical Discrete Event Systems.

Supervisory control of real-time systems using prioritized synchronization
Centralized and decentralized supervisory control of nondeterministic systems under partial observation.
On observability of discrete-event systems
Supervisory control of a class of discrete event processes.
Supervisory control of nondeterministic systems with driven events via prioritized synchronization and trajectory models.
A new framework for supervisory control.
Process objects/masked composition: An object oriented approach for modeling and control of discrete event systems.
Hierarchical control of discrete event systems.
On the consistency of hierarchical supervision in discrete-event systems
--TR

--CTR
Stavros Tripakis, Undecidable problems of decentralized observation and control on regular languages, Information Processing Letters, v.90 n.1, p.21-28, 15 April 2004
T.-S. Yoo , Stphane Lafortune, A General Architecture for Decentralized Supervisory Control of Discrete-Event Systems, Discrete Event Dynamic Systems, v.12 n.3, p.335-377, July 2002
observability;controllability;discrete event systems;driven events;trajectory models;co-observability;partial observation;prioritized synchronization;supervisory control;nondeterministic automata