On Event Reduction in Localization of DES Supervisory
Control
Vahid Saeidi1, Ali A. Afzalian2 and Davood Gharavian3
Department of Electrical Eng., Abbaspour School of Engineering,
Shahid Beheshti University, Tehran, Iran
1

v_saeidi@sbu.ac.ir, 2 Afzalian@sbu.ac.ir, 3 d_gharavian@sbu.ac.ir

Abstract
Supervisor localization procedure can be used to construct local controllers
corresponding to each component agent in discrete-event systems. This procedure is
based on state reduction of a monolithic supervisor with respect to each set of
controllable events corresponding to each component agent. State reduction from the
reduced supervisor to each local controller is an important criterion. In this paper, we deal
with event reduction. It is proved that the number of events in each local controller is less
than the event cardinality in the reduced supervisor, provided that each local controller
has less number of states comparing to the reduced supervisor. It shows that each local
controller needs less number of events to make consistent decisions. Having this
property, we can evaluate the localizability of a supervisor by event reduction criteria
instead of state reduction criteria. State reduction facilitates the implementation of local
controllers on industrial systems. Whereas, event reduction reduces communication
traffic between each pair of local controllers.

Key words: Control equivalent, event reduction, state reduction, supervisor
localization, supervisor reduction.

1. Introduction
The state size of the monolithic supervisory controller increases with state sizes of the
plant and specification which increases the computational complexity and may lead to
state explosion [1]. Thus, the application of this theory is restricted [2, 3]. Although,
modular [4-7] and incremental [8, 9] approaches try to overcome the complexity of the
supervisor synthesis, other approaches tend to reduce the supervisor for simple
implementation [10]. Supervisor localization procedure, introduced in [11], is a method
to distribute the supervisory control of discrete-event system. This procedure achieves
two goals: i) it preserves the optimality and non-blocking of the monolithic supervisor,

and ii) it dramatically simplifies each local controller based on the state size criteria.
Namely, a supervisor is localizable if the state size of each local controller is less than the
state size of the reduced state supervisor. This procedure is carried out using control
information relevant to the target agent. As the result, each agent obtains its own local
controller. Some applications of supervisor localization can be found in [12].
Supervisor localization procedure can be employed to construct a distributed
supervisory control for a monolithic specification associated with component agents. To
the best of the author’s knowledge, no work has been carried out on event reduction
properties of this procedure. On the other hand, decomposition of a supervisor [13] is an
alternative method to reduce the number of events, considered in decision making by
each decentralized supervisor in large scale discrete-event systems (DES). This method
constructs a distributed supervisory control with restricted control authority and restricted
observation scope.
In this paper, we investigate the event reduction in the localization of a monolithic
supervisor. The main common concepts in the supervisor reduction and supervisor
localization procedures are control consistency of states, control cover, and normality of
an induced generator which is control equivalent to the supervisor w.r.t. the plant.
Moreover, a constructed induced generator is deterministic automata.
We prove that, if a supervisor is localizable, (i.e. the state size of each local controller
corresponding to each component of the plant is less than the state cardinality of the
reduced supervisor), then at least one controllable event corresponding to other
components appears as self loop transition at all states of the corresponding local
controller (in the sense of normality [14, 15]). It is an important result. However, event
reduction in each local controller does not guarantee decomposability of the supervisor.
Moreover, each local controller needs fewer events for consistent decision making,
comparing to the reduced state supervisor. It reduces the communication traffic between
local controllers in a distributed supervisory control. Examples 4.2 and 4.3, show that
decomposition of a supervisor is stronger than event reduction in each local controller of
a distributed supervisory control.
The rest of the paper is organized as follows: In Section 2, the necessary preliminaries
are reviewed. In this section, we review the formulation of supervisor reduction and
supervisor localization procedures, by which one can prove required propositions. In
Section 3, we prove that, state reduction leads to event reduction in each local controller.
In Section 4, we compare state reduction and event reduction by some examples, and
show that event reduction is more practical criteria for localizability of a supervisor.
Finally, concluding remarks and future work are given in Section 5.

2. Preliminaries
A discrete-event system is presented by an automaton = ( , , , ,
), where is
a finite set of states, with
∈ as the initial state and
⊆ being the marker states;
is a finite set of events ( ) which is partitioned as a set of controllable events
and a
set of uncontrollable events , where = ⨃ . is a transition mapping : × →
, ( , ) = ′ gives the next state ′ is reached from by the occurrence of . is
discrete-event model of the plant. In this context ( , )! means that is defined for at
( ) ≔ ∈ ∗ | ( , )!
.
is
the
closed
behavior
of
and
( ) ≔ ∈ ( )| ( , ) ∈
is the marked behavior of [17, 18]. In this paper,
we assume that consists of component agents
defined on pairwise disjoint events
| ∈ ! . Let
sets
( ∈ !, ! an index set), i.e. = ⨃
≔ ( ) and
, ≔
( ) =∥
| ∈ ! and
( ), the closed and marked behaviors of are ( ) =∥
+ , , ∈ !-. We assume that for every ∈ !, . , =
is true. Then is necessarily
nonblocking (i.e. . ( ) = ( )).
A set of all control patterns is denoted with / = 0 ∈ 123( )|0 ⊇
. A supervisor
of a plant , is a map 5: ( ) → / where 5( ) represents the set of enabled events after
the occurrence of the string ∈ ( ). A pairs ( , 5) is written by V/ and called is
under supervision by 5. A behavioral constraint on is given by specification language
( ) ∩ 8 be the supremal controllable sublanguage of 8 w.r.t. ( )
8 ⊆ ∗ . Let 9 ⊆
and , i.e. 9 = ;<=( ( ) ∩ 8). If 9 ≠ ∅, @AB = (C, , D, E , C ) is recognizer of
9. If and F are finite-state DES, then 9 is regular language. Write | . | for the state size
of DES. Then |@AB| ≤ | ||F|. In applications, engineers want to employ the reduced
supervisor I@AB, which has a fewer number of states ( i.e. |I@AB| ≪ |@AB|) and is
control equivalent to @AB w.r.t. [10], i.e.
( ) ∩ (I@AB) =
(@AB)
( ) ∩ (I@AB) = (@AB)
A generator KLM over , is a local controller for agent
events in . Precisely, for all ∈ ∗ and ∈ , there holds
∈ ( ) & ∈ (KLM )&

(1)
(2)
, if KLM can disable only

∉ (KLM ) ⇒

∈

The observation scope of KLM is not limited to . But, the control authority of a local
controller is strictly local [11].
A set of local controllers KLM = KLM | ∈ ! is constructed, each one for an agent,
with (KLM) =∩ (KLM )| ∈ ! and (KLM) =∩
(KLM )| ∈ ! such that the
following relationships hold,

( ) ∩ (KLM) =
(@AB)
( ) ∩ (KLM) = (@AB)

(3)
(4)

We say that, KLM is control equivalent to @AB w.r.t. , if (3) and (4) are satisfied. This
formulation is based on state reduction of a monolithic supervisor with respect to
disabled controllable events of each component agent.
The natural projection is a mapping 1: ∗ → ∗ where (1)1(R): = R , (2) for ∈ ∗ ,
∈ , 1( ): = 1( )1( ), and (3) 1( ): = if ∈
and 1( ): = R if ∉
. The
∗
effect of an arbitrary natural projection 1 on a string ∈
is to erase the events in ,
that do not belong to observable events set, . The natural projection 1 can be extended
and denoted by 1: 123( ∗ ) → 123( ∗ ). For any ⊆ ∗ , 1( ) ≔ 1( )| ∈ . The
inverse image function of 1 is denoted by 1WX : 123 ( ∗ ) → 123 ( ∗ ) for any ⊆ ∗ ,
1WX ( ) ≔ ∈ ∗ |1( ) ∈ . The synchronous product of languages X ⊆ X∗ and Y ⊆
WX
WX
∗
∗
, where 1Z : ∗ → Z∗ , [ = 1,2 for the
Y is defined by X ∥ Y = 1X ( X ) ∩ 1Y ( Y ) ⊆
union = X ∪ Y [7].

It was defined in [16], that 9 is relative observable w.r.t. =̅ , and 1 (or simply =̅ ^ and =̅ are prefix closed languages, if for every
( ), where 9
observable) for 9 ⊆ = ⊆
pair of strings , ′ ∈ ∗ such that 1( ) = 1( ′), the following two conditions hold:
^ , ′ ∈ =̅ , ′ ∈ ( ) ⟹ ′ ∈ 9
^
• (∀ ∈ )
∈9
•
∈ 9, ′ ∈ =̅ ∩ ( ) ⟹ ′ ∈ 9
In the special case, if = = 9, then the relative observability property is tighten to the
observability property. An observation property called normality was defined in [14], that
is stronger than the relative observability. 9 is said to be normal w.r.t. ( ( ), 1), if
^) ∩ ( ) = 9
^, where ( ) is a prefix closed language and 1 is a natural
1WX 1(9
projection.
2.1.

Supervisor reduction procedure

A procedure was proposed in [10], to reduce the state size of a monolithic supervisor.
This method constructs a generator which is control equivalent to the monolithic
supervisor w.r.t. the plant. Let @AB = (C, , D, E , C ) and define 8: C → 123( ) as
8 (E ) =
∈ |D (E, )! . 8 (E) denotes the set of events enabled at state E. Next, define
b: C → 123( ) as b (E) = + ∈ │¬D (E, )! &(∃ ∈ ∗ )[D (E , ) = E & ( , )!]-.
b (E) is the set of events which are disabled at state E. Define g: C → 1,0 according to
g(E) = 1 iff E ∈ C , namely the flag of g determines if a state is marked in @AB. Also,
define i: C → 1,0 according to i(E) = 1 iff (∃ ∈ ∗ )D (E , ) = E & ( , ) ∈
,
namely the flag of i determines if some corresponding state is marked in . Let ℛ ⊆ C ×

C be the binary relation such that for E, E ′ ∈ C, (E, E ′ ) ∈ ℛ. E and E ′ are called control
consistent, if
8 (E ) ∩ b (E ′ ) = 8 (E ′ ) ∩ b (E ) = ∅
(5)
′
′
i (E ) = i (E ) ⇒ g (E ) = g (E )
(6)
Informally, a pair of (E, E ′ ) is in ℛ if, by (3), there is no event enabled at E but disabled
at E ′ , and by (4), (E, E ′ ) are both marked (unmarked) in @AB, provided that they are both
marked (unmarked) in . While ℛ is reflexive and symmetric, it need not be transitive,
consequently it is not an equivalence relation. This fact underlies the next definition. A
cover m = CZ ⊆ C|[ ∈ n of C is called a control cover on @AB if [10],
(∀[ ∈ n)CZ ≠ ∅ ∧ (∀E, E ′ ∈ CZ )(E, E ′ ) ∈ ℛ
(∀[ ∈ n)(∀ ∈ )(∃p ∈ n)q(∀E ∈ CZ )D (E, )! ⟹ D (E, ) ∈ Cr s,

(7)
(8)

Where, n is an index set.
A control cover m lumps states of @AB into cells CZ ([ ∈ n) if they are control
consistent. A control cover m is control congruence if CZ are pairwise disjoint. According
to (5), each cell of m is nonempty and each pair of states in one cell should be consistent.
According to (6), all states that can be reached from any states in CZ by one step transition
is covered by some Cr .
Given control cover m = CZ ⊆ C|[ ∈ n on @AB, an induced supervisor is constructed
as t = (n, , u, [ , n ) where [ = some [ ∈ n with E ∈ CZ , n = [ ∈ n|CZ ∩ C ≠ ∅
and u: n × → n with u([, ) = p provided, for such choice of p ∈ n,
(∃E ∈ CZ )D (E, ) ∈ Cr & (∀E′ ∈ CZ )[D (E y , )! ⇒ D (E ′ , ) ∈ Cr ]

(9)

Overlapping of some states results that [ and u may not be uniquely determined, thus t
may not be unique. If m is control congruence, then t is uniquely determined by m.
Generally, t is control equivalent to @AB w.r.t .
A DES I@AB = (z, , {, | , z ) is normal w.r.t @AB if,
([)(∀| ∈ z)}∃ ∈ (@AB)~{ (| , ) = |
([[)(∀| ∈ z)(∀ ∈ )[{ (|, )! ⇒ }∃ ∈ (@AB)~[
([[[)(∀| ∈ z )}∃ ∈
(@AB)~{ (| , ) = |

∈ (@AB)& { (| , ) = |]] (10)

Given two generators I@AB = (z, , {, | , z ) and t = (n, , u, [ , n ) are DESisomorphic with isomorphism • if there exists a map •: z → n such that

([) •: z → n is a bijection
([[) •(| ) = [ and • (z ) = n
([[[ ) (∀| ∈ z)(∀ ∈ ){ (|, )! ⇒ qu (•(|), )! & u(•(|), ) = •}{ (|, )~s
([ƒ)(∃[ ∈ n)(∀ ∈ )u ([, )! ⇒ [(∃| ∈ z){ (|, )! & •(|) = []

(11)

It was proved in [10], if @AB is supremal supervisor for and I@AB is any normal
supervisor w.r.t @AB such that it is control equivalent to @AB w.r.t , then there exists a
control cover m on @AB for which some induced supervisor t is DES-isomorphic to
I@AB.
2.2.

Supervisor localization procedure

A procedure was proposed in [11], to construct a set of local controllers which their
synchronization with the plant is equivalent to the monolithic supervisor. This method
| ∈ ! that the set
⊆ | ∈ ! make a partition on .
follows from = ⨃
This method employs control consistency and control cover from supervisor reduction
procedure, proposed in [10].
Define 8: C → 123( ) as 8 (E) =
∈ |D (E, )! . Next, define b : C → 123( ) as
b (E) = + ∈ │¬D (E, )! &(∃ ∈ ∗ )[D (E , ) = E & ( , )!]-. The flag of gand
i are defined same as the ones defined in the supervisor reduction procedure. Let
ℛ ⊆ C × C be the binary relation such that for E, E ′ ∈ C, (E, E ′ ) ∈ ℛ . E and E ′ are
called control consistent w.r.t. , if
8 (E ) ∩ b (E ′ ) = 8 (E ′ ) ∩ b (E ) = ∅
i (E ) = i (E ′ ) ⇒ g (E ) = g (E ′ )
A cover m = +CZ „ ⊆ C,[ ∈ n - is a control cover on C w.r.t.

(12)
(13)
if,

(∀[ ∈ n ) CZ „ ≠ ∅ ∧ }∀E, E ′ ∈ CZ „ ~(E, E ′ ) ∈ ℛ

(14)

(∀[ ∈ n )(∀ ∈ )(∃p ∈ n ) …}∀E ∈ CZ „ ~D (E, )! ⟹ D (E, ) ∈ Cr „ †,(15)

Where, n is some index set [11].

Given a control cover m on C, based only on the control information of
generator t = (n , , u , [ , n ) is obtained by the following construction

, an induced

([)[ ∈ n such that E ∈ CZ „
ˆ

([[)n = +[ ∈ n ,CZ „ ∩ C ≠ ∅([[[ )u : n × → n with u ([ , ) = p , if
}∃E ∈ CZ „ ~D (E, ) ∈ Cr „ & }∀E′ ∈ CZ „ ~[D(E y , )! ⇒ D (E ′ , ) ∈ Cr „ ]

(16)

Overlapping of some states results that [ and u may not be uniquely determined, and
t may not be unique. If m is control congruence, then t is uniquely determined by m .
We can obtain a set of induced generators t = t | ∈ ! . Let (t) ≔∩ (t )| ∈ !
(t) ≔∩
and
(t )| ∈ ! . t is a solution to the distributed supervisory control
problem.
A DES KLM = (z‰ , , {‰ , |‰, , z‰, ) is normal w.r.t @AB if,
([)(∀| ∈ z‰ )}∃ ∈ (@AB)~{}|‰, , ~ = |
([[)(∀| ∈ z‰ )(∀ ∈ )[{ (|, )! ⇒ }∃ ∈ (@AB)~q
([[[)}∀| ∈ z‰, ~}∃ ∈
(@AB)~{}|‰, , ~ = |

∈ (@AB)& {}|‰, , ~ = |s](17)

Given two generators KLM = (z‰ , , {‰ , |‰, , z‰, ) and t = (n, , u, [ , n ) are DESisomorphic with isomorphism •, if there exists a map •: z‰ → n such that
([) •: z‰ → n is a bijection
([[) •}|‰, ~ = [ and •}z‰, ~ = n
([[[) (∀| ∈ z‰ )(∀ ∈ ){‰ (|, )! ⇒ qu (•(|), )! & u (•(|), ) = •}{‰ (|, )~s
([ƒ)(∃[ ∈ n)(∀ ∈ )u([, )! ⇒ [(∃| ∈ z‰ ){‰ (|, )! & •(|) = []

(18)

Under normality and DES-isomorphism, let KLM be a set of normal generators that is
control equivalent to @AB w.r.t. . Then, there exists a set of control covers m ≔
m | ∈ ! on C with a corresponding set of induced generators t ≔ t | ∈ ! such
that, for every ∈ !, t and KLM are DES-isomorphic.
3. Event reduction in local controllers
The aim of supervisor localization procedure is to reduce the state size of a supervisor
corresponding to each component of the plant. Thus, when a pair of states are control
consistent in m, they are also control consistent in m , ∀ ∈ !. On the other hand, if the
state size of a local controller is less than the state cardinality of the reduced supervisor,
then a pair of states which are not control consistent in m may be control consistent in m ,
where ∈ !. In the following proposition, we prove that, if a local controller has fewer
states comparing to the reduced supervisor, then there exists at least one self-looped
event, which occurs at one state of the local controller.
Proposition 1: Let be a non-blocking plant, consists of components , ∈ !, @AB
be a supervisor of , I@AB be the reduced supervisor, and KLM be a local controller
corresponding to . If KLM has less number of states than I@AB, then ∃ ∈
such that is self-looped at one state of KLM .
Proof: Assume that EZ ∈ C, such that (∃

Z

∈

∗)

, EZ = D(E , Z ).

r

,p ≠

Fig. 1. A set of states and strings in @AB

From the typical setup, shown in Fig. 1, we substitute lumped control consistent states
EX , EY and EX , EŠ , by ‹ and Œ, respectively in I@AB (Fig. 2).

Fig. 2. A set of states and strings in I@AB

Also, we substitute lumped control consistent states EX , EY , EŠ by g in KLM (Fig. 3).

Fig. 3. A set of states and strings in KLM

We prove that

Š

is self-looped at state g.

In Fig. 1, assume that EŠ is not control consistent with EY . Since (6) and (13) are the
same, we employ only (5) and (12) for proving the claim. Thus, we can write,
8 (EX ) ∩ b (EŠ ) = 8 (EŠ ) ∩ b (EX ) = ∅ ⟹ Š ∉ b (EX ), and X ∉ b (EŠ )
8 (EY ) ∩ b (EŠ ) ≠ ∅ or 8 (EŠ ) ∩ b (EY ) ≠ ∅ ⟹ Š ∈ b (EY ), or Y ∈ b (EŠ )

(19)
(20)

From (19), we can write,
If Š ∈ b (EY ), then
( ).

Š

∉ 8 (EX ). Because EX and EY are control consistent. Thus,

X Š

∉

X Y

∉

From (20), we can write,
If Y ∈ b (EŠ ), then
( ).

Y

∉ 8 (EX ). Because EX and EŠ are control consistent. Thus,

From (19) and (20), we can write,
If

Š

∈ b (EY ), and

Y

∈ b (EŠ ), then

Y, Š

∉ 8 (EX ). Thus,

X Y, X Š

∉ ( ).

Let Š ∈ b (EY ). It means that Š is a controllable event. But, Š ∉ b (EY ). It means
that Y Š ∈ ( ), the monolithic supervisor disables Š at EY , and the local controller is
not authorized to disable Š at EY . Hence, Š is not an enabled transition by the
monolithic supervisor at EY , and it must be self-looped at state g in KLM (Fig. 4).
From (17), a set of local controllers, constructed by supervisor localization procedure,
are normal w.r.t. @AB. It means that, each string belongs to a local controller and the
plant must be enabled in the monolithic supervisor. Thus, Š cannot be self-looped at
state g, while being a transition to E• . Therefore, Š is self-looped at state g, only.

Fig. 4. A set of states and strings in KLM , where

Š

is self-looped at g

Corollary 1: In Proposition 1, since Š is disabled at some states of the supervisor, its
observation affects the behavior of the supervisor. It means that, if Š is not observed,
then the supervisor make inconsistent decisions (in the sense of normality).
In order to prove the main claim of the paper, we show that Š appears as a self loop
transition at all states of KLM . Since KLM is not authorized to disable the controllable
event Š , it is sufficient to prove that Š appears as a self loop transition at states, where it
is enabled. In Lemma 1, we prove the claim in a special case.
Lemma 1: Let

be a non-blocking plant, consists of components
r

,

∈ !, and KLM

be a local controller corresponding to each . Let ∈ , p ≠ , and one string belongs
)!, ¬ ( , X )!, ∃[, |Z =
to (KLM ) be as shown in Fig. 5. If [(∃ ∈ ∗ ), ( ,
{‰ }|‰, , ~ ⟹ |Z = {‰ (|Z , )], then [∀[, {‰ (|Z , )! ⟹ |Z = {‰ (|Z , )].
Proof: Assume the set of states and strings, are shown in Fig. 5. Define 1: ∗ → ∗ ,
= −
. We should prove that each pair of states where
occurs between them,
can be considered one state. We know that 1(
X ′ ) = 1( X ′). Since a language,
which is constructed by local controllers in the plant are same as the language of the
monolithic supervisor (see (3) and (4)), we can extend the observability property of the
monolithic supervisor to each local controller. Thus, from Fig. 5, we can write,
∀ ∈ ,
(KLM )

X

y

∈ (KLM ) ∩ ( ),

X

y

∈ (KLM ),

X

y

∈ ( )⟹

X

y

∈
(21)

The string, which occurs in both the local controller and the plant is shown in the first
term of the antecedent in (21). Since X ∉ ( ), then X y ∉ ( ). Thus, (21) is true.
Similarly, we can write,
X

y

(KLM ) ∩

∈

( ),

X

y

∈ (KLM ) ∩

( )⟹

X

y

(KLM )

∈

(22)
( ). Thus, (22) is true. Therefore, |• and |••X can
Since X y ∉ ( ), then X y ∉
be considered one state, where is a self-looped transition.

Fig. 5. A set of states and strings in KLM , where

is self-looped at |Z

However, the supervisor reduction and the supervisor localization procedures consider
the plant cyclic (the task of the plant is assumed cyclic), even if it is not cyclic (see
example 4.2), we assume
is a cyclic plant. Thus, ∀[, {‰ (|Z , )! we use the above
argument and conclude that |Z = {‰ (|Z , ). Since KLM is not authorized to disable , it
can be considered a self loop transition at other states, where
is not defined in ,
correspondingly, i.e.
(∃ ∈

∗)

q ( , )=

)!s ⟹ |Z = {‰ (|Z ,

& |Z = {‰ }|‰, , ~ & ¬ ( ,

is self-looped at all states in KLM . Informally,

Therefore,

Now, we relax the assumption

X

)

(KLM ) is normal.

∉ ( ), and show that Lemma 1 still does hold.

Theorem 1: Let be a non-blocking plant, consists of components , ∈ !, described
by closed and marked languages ( ), ( ) ⊆ ∗ and @AB = (C, , D, E , C ) be the
supervisor of . From Proposition 1, If Š is self-looped at one state g in KLM , ∈ !,
then Š is self-looped at all states in KLM .
Proof: Following the proof in Lemma 1, clearly, if
true, in Fig. 6.
′
(KLM )

Š Š •

′
(KLM )

Š Š •

∈ (KLM ) ∩ ( ),

Š

Š •

′ ∈ (KLM ),

Š •

∉ ( ), then (23) and (24) are

Š •

′ ∈ ( )⟹

Š •

′ ∈
(23)

Š

∈

(KLM ) ∩

( ),

Š •

′ ∈ (KLM ) ∩

( )⟹

Š •

′∈
(24)

Now, we want to prove that (23) and (24) are true, even if Š • ∈ ( ). From Figs. 4, 6,
we know that Š • ∈ (KLM ). Thus, • is enabled at state g in KLM . Since KLM is
deterministic automata, • is a transition from g to only one state in KLM . There may
be two cases related to • : (a) • is a transition from EŠ to E‘ , in @AB (Fig. 4), (b) • is a
transition from EŠ to another state except E‘ , in @AB.

Fig. 6. A set of states and strings in KLM , where

Š

is self-looped at g

(a) • is a transition from EŠ to E‘ : If Š is enabled at E• , then EŠ , E• are control
consistent and E• and g become one state in KLM . In this case, we have a transition
Š from g to another state (e.g. E’ ), which is shown in Fig. 7(a). But, such transition
makes KLM a non-deterministic automata. Thus, E’ and g must become one state
(Fig. 7(b)). Obviously, Š cannot be disabled at E’ , because KLM is not authorized to
disable it.

⟹

a.

Š

is self-looped at g and is also a
transition from g to E’
Fig. 7. Transition

b. KLM , as a deterministic automata
Š

from g to E’ , in KLM

Also, Š may be a transition from g to E‘ , which is shown in Fig. 8(a). In this case,
KLM is also a non-deterministic automata. Thus, E‘ and g must become one state (Fig.
8(b)), and • is also a self loop transition at g.
This argument can be continued for other states which may be control consistent with g,
until either all subsequent transitions become self-looped at g (in this case, KLM is
reduced to one state with self loop transitions, and the claim is proved), or some enabled
events can be found at a control consistent state with state g, such that they are not
defined at corresponding state in . The latter was proved in Lemma 1. It means that,
= Z ∪ Š and 1( Š Š • … •WX ) =
there is a natural projection 1: ∗ → ∗ ,
1( Š • … •WX ), such that ∃ • ∈ , Š • … •WX • ∉ ( ) and

Š Š •

…

∈ (KLM ) ∩ ( ), Š • …
⟹ Š • … •WX • ∈ (KLM )

•WX •

•WX

∈ (KLM ),

Š •

…

•WX •

∈ ( )

⟹
a.

Š

is self-looped at g and is also a transition
from g to E‘
Fig. 8. Transition

Š

b. KLM , as a deterministic automata
from g to E‘ , in KLM

(b) • is a transition from EŠ to another state except E‘ (e.g. EZ ): Since KLM is a
deterministic automata, EZ and E‘ must be control consistent states and EZ , E‘ become a
new state ”, constructed in KLM . Two cases can be considered in Fig. 9.
(b.1)

Š • ‘

∉ ( )

Assume Š • ‘ ∉ ( ). Following the proof in Lemma 1, we see that,
at all states in KLM .

Š

is self-looped

⟹
a. KLM , as a non-deterministic automata
Fig. 9. Transition

(b.2)

Š • ‘

b. KLM , as a deterministic automata
•

from g to E‘ and EZ in KLM

∈ ( )

By substituting • by • ‘ , (23) and (24) can be rewritten. Thus, the claim is proved by
an iterative procedure.
We summarize the above argument in the following statement:
If an event Š which is not disabled in KLM , is self-looped at one state, e.g. g, then
some other events may be self-looped at g, until we can find some enabled events at a
control consistent state with g, such that they are not defined at corresponding state in .
Thus, there is a natural projection 1: ∗ → ∗ , = Z ∪ Š , such that 1( ) = 1( ′),
∈ (KLM ) ∩ ( ), ′ ∈ (KLM ), ′ ∈ ( ) ⟹ ′ ∈ (KLM ), and ′ ∉ ( ).

Remark 1: The reverse of Theorem 1 is not true. It means that, the event reduction may
occur in a local controller, but the state reduction may not.
We will show in example 4.2 that, the number of events used in each local controller is
less than the event cardinality of the reduced supervisor (according to Corollary 1), but
the state size of each local controller is same as the state size of the reduced supervisor.
However, we prefer a set of local controllers, with fewer states than the reduced
supervisor; each local controller needs fewer events comparing to the number of events
used by the reduced supervisor in order to make consistent decisions. This gives us new
criteria for evaluating the localizability of a supervisor. We can relax the definition of
localizability according to event reduction criteria, i.e. a monolithic supervisor is
localizable, if each local controller has fewer events comparing to the event cardinality of
the reduced state monolithic supervisor.
Corollary 2: Comparing to a decomposable supervisor, we may find some local
controllers corresponding to each component of the plant, such that each local controller
has fewer events comparing to the reduced state original supervisor.
4. Examples
In this section, we consider examples in order to verify the extended theory in the paper.
4.1.

Non-localizable case- Supervisory control of a shared common resource

The hard case in localization is where the component agents are coupled so tightly that
each one has to be globally aware [11]. In Fig. 10 two agents Z , [ = 1,2 share a common
resource that is not allowed to be occupied simultaneously. It is easy to see that @AB is
the recognizer of a monolithic supervisor which enforces the mutual exclusion
specification. Then by applying the localize procedure in TCT software [19], we
construct KLM Z , [ = 1,2 corresponding to each agent Z . We can see that each local
controller is the same as @AB (Fig. 11). Thus, not only the state size is not reduced but
also the event cardinality is not reduced. In this case, we say the monolithic supervisor is
not localizable.

Fig. 10. DES model of agents,

4.2.

Z

, [ = 1,2

Fig. 11. The monolithic supervisor @AB and
local controllers KLM Z , [ = 1,2

Localizable case in the term of event reduction criteria- Supervisory
control of a guide way

Consider a guide way with two stations A and B, which are connected by a single oneway track from A to B on a guide way, as shown in Fig. 12. The track consists of 4
sections, with stoplights (*) and detectors (!) installed at various section junctions [18].
Two vehicles •– , •— use the guide way simultaneously. •Z , [ = 1, 2 may be in state 0 (at
A), state p (while travelling in section p = 1, … . ,4), or state 5 (at B). The generator of
•Z , [ = 1,2 are shown in Fig. 13.

Fig. 12. Schematic of a guide way

Fig. 13. DES model of each vehicle

The plant to be controlled is = ˜™š›(•– , •— ). In order to prevent collision, control of
the stoplights must ensure that •– and •— never travel on the same section of track
simultaneously. Namely •Z , [ = 1,2 are mutual exclusion of the state pairs ([, [), [ =
1, . . ,4. The supremal relative observable supervisor and its corresponding reduced
supervisor are shown in Figs. 14 and 15, respectively, where 1: ∗ → ∗ ,
= −
13,23 .

Fig. 14. The relative observable supervisor of guide way (œ ˜ )

Fig. 15. The reduced supervisor of guide way (œ • )

Local controllers which are constructed by localize procedure are shown in Fig. 16.
Since the number of states of each local controller is equal to the state cardinality of œ • ,
the relative observable supervisor 9ž is not localizable, with state reduction criteria. But,
we see the reduced supervisor employs some events which are not used by at least one
local controller. For example, the reduced supervisor employs events 10, 12, 23 in
decision making, but the local controller •– do not use them. Also, the local controller •—
does not use events 13, 20, 22 in order to make decisions. Thus, we can say œ ˜ is
localizable in the term of event reduction criteria. Moreover, we can see that the
monolithic supervisor
(œ ˜ ) is decomposable w.r.t. , 1X , 1Y , X , Y , where 1X : ∗ → X∗ ,
− 10,12,23 and 1Y : ∗ → Y∗ , Y = − 13,20,22 .
X =

(a) Local controller of V1

(b) Local controller of V2

Fig. 16. Local controllers of each component of guide way

In the next example, we consider a case which the monolithic supervisor is localizable in
the terms of state reduction and event reduction criteria. Moreover we will see that the
number of events is reduced in each local controller, but the original supervisor is not
decomposable.
4.3.

Localizable case in the term of state reduction criteria- Supervisory
control of transfer line

Industrial transfer line consisting of two machines M1, M2 and a test unit TU, linked by
buffers B1 and B2, is shown in Fig. 17. If a work piece is accepted by TU, it is released
from the system; if rejected, it is returned to B1 for reprocessing by M2. The specification
is based on protecting the B1 and B2 against underflow and overflow [18]. All events
involved in the DES model are = 1,2,3,4,5,6,8 , where controllable events are oddnumbered. After the synthesis of the supremal controllable supervisor, we obtain the
reduced supervisor by supervisor reduction procedure in TCT software, shown in Fig. 18.
Moreover, we construct local controllers for each component M1, M2 and TU, as shown in
Figs. 19-21.

Fig.17. Transfer Line

Fig. 18. Reduced supervisor for transfer line

Fig. 19. Local controller M1

Fig. 20. Local controller M2

Fig. 21. Local controller TU

Obviously, we see that each local controller has lees number of states and less number of
events, comparing to the reduced supervisor. In this example, the local controller M1 does
not use events 3, 4, 5, 8. Also, events 1, 6 are not used by the local controller M2 and
events 1, 2, 3, 6, 8 are not used by the local controller TU for decision making. Thus the
synthesized supervisor for industrial transfer line is localizable in terms of state reduction
and event reduction criteria. Whereas, we can see that the monolithic supervisor is not

decomposable w.r.t.
, 1X , 1Y , 1Š , X ,
∗
∗
1Y : → Y , Y = − 1,6 , and 1Š :

Y,
∗

where 1X : ∗ → X∗ , X =
→ Š∗ , Š = − 1,2,3,6,8 .
Š,

− 3,4,5,8 ,

5. Conclusion
This paper addresses the new property of event reduction in the supervisor localization
procedure. We proved that if each local controller has less number of states comparing to
the reduced supervisor, then such local controller has fewer events than the reduced state
monolithic supervisor. In fact, localization procedure provides fewer states, for easier
implementation of each local controller on industrial systems, and provides fewer events,
in order to reduce the communication traffic between local controllers. The least
communicated events between local controllers are important for efficiency of a
distributed supervisory control. Thus, we can use the event reduction criteria for checking
localizability of a supervisor. Localizability is satisfied by state reduction in each local
controller, in the sense of [11], whereas event reduction satisfied the reduced
communication traffic between local controllers, in the sense of this paper. By event
reduction property, we can investigate and compare the localization and decomposition of
a supervisor, in future work.
References
[1] W. M. Wonham and P. J. Ramadge, "Modular supervisory control of discrete-event systems," Math.
Control Signal Syst., vol.1, no.1, pp.13-30, 1988.
[2] R. J. M. Theunissen, M. Petreczky, R. R. H. Schiffelers, D. A. van Beek, and J. E. Rooda,
"Application of Supervisory Control Synthesis to a Patient Support Table of a Magnetic Resonance
Imaging Scanner", IEEE Trans. Autom. Sci. Eng., vol.11, no.1, pp.20-32, 2014.
[3] A. Afzalian, A. Saadatpoor and W. M. Wonham, "Systematic supervisory control solutions for underload tap-changing transformers", Control Engineering Practice, vol.16, no.9, pp.1035-1054, 2008.
[4] Y. Willner and M. Heymann, "Supervisory control of concurrent discrete-event systems",
International Journal of Control, vol.54, no.5, pp.1143-1169, 1991.
[5] J. Komenda, and J. H. Van Schuppen, "Modular Control of Discrete-Event Systems with Coalgebra",
IEEE Trans. Autom. Control, vol.53, no.2, pp.447-460, 2008.
[6] F. Lin and W. M. Wonham, "Decentralized control and coordination of discrete-event systems with
partial observation", IEEE Trans. Autom. Control, vol.35, no.12, pp.1330-1337, 1990.
[7] L. Feng and W. M. Wonham, "Supervisory Control Architecture for Discrete-Event Systems", IEEE
Trans. Autom. Control, vol.53, no.6, pp.1449-1461, 2008.
[8] H. Marchand and S. Pinchinat, "Supervisory control problem using symbolic bisimulation
techniques", in Proc. of Amer. Control Conf., Chicago, IL, June. 2000, pp. 4067–4071.
[9] A. Vahidi, M. Fabian, B. Lennartson, "Efficient supervisory synthesis of large systems", Control
Engineering Practice, vol.14 (10), pp.1157-1167, 2006.
[10] R. Su and W. M. Wonham, "Supervisor reduction for discrete-event systems", Discrete-event Dyn.
Syst., vol.14, no.1, pp.31–53, 2004.
[11] K. Cai and W. M. Wonham, " Supervisor Localization: A Top-Down Approach to Distributed
Control of Discrete-Event Systems", IEEE Trans. Autom. Control, vol.55, no.3, pp.605-618, 2010.
[12] K. Cai and W. M. Wonham, "New results on supervisor localization, with case studies", Discreteevent Dyn. Syst., vol.25, no.1, pp.203-226, 2015.

[13] K. Rudie and W. M. Wonham, "Think globally, act locally: decentralized supervisory control", IEEE
Trans. Autom. Control, vol.37, no.11, pp.1692-1708, 1992.
[14] F. Lin, W. M. Wonham, On observability of discrete-event systems, Information Sciences, 44(1988),
173-198.
[15] R. Cieslak, C. Desclaux, A. S. Fawaz, P. Varaiya, Supervisory control of discrete-event processes
with partial observations, IEEE Trans. Autom. Control, 33(1988), 249-260.
[16] K. Cai, R. Zhang, W.M. Wonham, Relative Observability of Discrete-Event Systems and its
Supremal Sublanguages, IEEE Trans. Autom. Control, 60(2015), 659- 670.
[17] C.G. Cassandras and S. Lafortune, "Introduction to Discrete-event Systems", 2nd edn. Springer,
NewYork, 2008.
[18] W. M. Wonham, "Supervisory control of discrete-event systems", Lecture Notes University of
Toronto, 2014, http://www.control.utoronto.ca/DES.
[19] W. M. Wonham, Control Design Software: TCT. Developed by Systems Control Group, University
of Toronto, Canada, Updated 1st July 2014, http://www.control.utoronto.ca/cgi-bin/dlxptct.cgi.

