SI R
INSTITUTE FOR SYSTEMS RESEARCH
Sponsored by
the National Science Foundation
Engineering Research Center Program,
the University of Maryland,
Harvard University,
and Industry
TECHNICAL RESEARCH REPORT
Extension Based Limited Lookahead 
Supervision of Discrete Event Systems
by R. Kumar, H.M. Cheung, S.I. Marcus
T.R. 95-78
#5B13#5D R. Kumar and V. K. Garg. Extremal solutions of inequations over lattices with ap-
plications to supervisory control. Theoretical Computer Science, 148:67#7B92, November
1995.
#5B14#5D R. Kumar and V. K. Garg. Modeling and Control of Logical Discrete Event Systems.
Kluwer Academic Publishers, Boston, MA, 1995.
#5B15#5D R. Kumar, V. K. Garg, and S. I. Marcus. On controllability and normality of discrete
event dynamical systems. Systems and Control Letters, 17#283#29:157#7B168, 1991.
#5B16#5D S. Lafortune. Modeling and analysis of transaction execution in database systems. IEEE
Transactions on Automatic Control, 33#285#29:439#7B447, 1988.
#5B17#5D F. Lin and W. M. Wonham. On observability of discrete-event systems. Information
Sciences, 44#283#29:173#7B198, 1988.
#5B18#5D P. Liu. Goal-oriented behavior in autonomous systems. In Proceedings of the 2nd
International IEEE ConferenceonTools for Arti#0Ccial Intelligence, pages 2#7B8, Herndon,
VA, 1990.
#5B19#5D N. Viswanadham, Y. Narahari, and T. L. Johnson. Deadlock prevention and deadlock
avoidance in #0Dexible manufacturing systems using Petri net models. IEEE Transactions
on Robotics and Automation, 6#286#29:713#7B723, December 1990.
#5B20#5D P. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency Control and Recovery in
Database Systems. Addison-Wesley, Reading, MA, 1987.
#5B21#5D C. H. Papadimitriou. The Theory of Database Concurrency Control. Computer Science
Press, Rockville, MD, 1986.
#5B22#5D K. M. Passino and P.J.Antsaklis. A system and control theoretic perspectiveon
arti#0Ccial intelligence planning systems. International Journal of AppliedArti#0Ccial In-
telligence, 3:1#7B32, 1989.
#5B23#5D J. C. Pemberton and R. E. Korf. Incremental path planning on graphs with cycles.
In Proceedings of the 1st International ConferenceonArti#0Ccial Intelligence Planning
Systems, pages 179#7B188, College Park, MD, 1992.
#5B24#5D P. J. Ramadge and W. M. Wonham. Supervisory control of a class of discrete event
processes. SIAM Journal of Control and Optimization, 25#281#29:206#7B230, 1987.
#5B25#5D P. J. Ramadge and W. M. Wonham. The control of discrete event systems. Proceedings
of IEEE: Special Issue on Discrete Event Systems, 77:81#7B98, 1989.
#5B26#5D S. L. Chung, S. Lafortune, and F. Lin. Addendum to #5CLimited lookahead policies in
supervisory control of discrete event systems": Proofs of technical results. Technical
Report CGR-92-6, University of Michigan, Ann Arbor, Michigan, April 1992.
32
References
#5B1#5D Z. Banaszakand B. H.Krogh. Deadlockavoidancein #0Dexible manufacturing sytems with
concurrently competing process #0Dows. IEEE Transactions on Robotics and Automation,
6#286#29:724#7B734, December 1990.
#5B2#5D R. D. Brandt, V. K. Garg, R. Kumar, F. Lin, S. I. Marcus, and W. M. Wonham.
Formulas for calculating supremal controllable and normal sublanguages. Systems and
Control Letters, 15#288#29:111#7B117, 1990.
#5B3#5D E. Chen and S. Lafortune. Dealing with blocking in supervisory control of discrete event
systems. IEEE Transactions on Automatic Control, 36#286#29:724#7B735, 1991.
#5B4#5D S. L. Chung, S. Lafortune, and F. Lin. Limited lookahead policies in supervisory control
of discrete event systems. IEEE Transactions of Automatic Control, 37#2812#29:1921#7B1935,
December 1992.
#5B5#5D S. L. Chung, S. Lafortune, and F. Lin. Recursive computation of limited lookahead su-
pervisory controls for discrete event systems. Discrete Event Dynamic Systems: Theory
and Applications, 3#281#29:71#7B100, 1993.
#5B6#5D S. L. Chung, S. Lafortune, and F. Lin. Supervisory control using variable lookahead
policies. Discrete Event Dynamic Systems: Theory and Applications, 4#283#29:237#7B268,July
1994.
#5B7#5D A. Ghosh. Modeling and analysis of real-time database systems in the framework of
discrete event systems. Technical Report MS 95-6, Institute of Systems Research, Uni-
versity of Maryland, 1995.
#5B8#5D N. B. Hadj-Alouane, S. Lafortune, and F. Lin. Control of partially observed discrete
event systems with variable lookahead maximal policies. In Proceedings of 1991 Annual
Allerton Conference, Urbana, IL, October 1993. To appear.
#5B9#5D N. B. Hadj-Alouane, S. Lafortune, and F. Lin. Variable lookahead supervisory control
with state information. IEEE Transactions on Automatic Control, 39#2812#29:2398#7B2410,
December 1994.
#5B10#5D P. Kozak and W. M. Wonham. Synthesis of database management protocols. Technical
Report SCG-9311, UniversityofToronto, Toronto, CA, August 1993.
#5B11#5D B. H. Krogh and D. Feng. Dynamic generation of subgoals for autonomous mobile
robots using local feedback information. IEEE Transactions on Automatic Control,
34#285#29:483#7B493,May 1989.
#5B12#5D R. Kumar. Formulas for observability of discrete event dynamical systems. In Proceed-
ings of 1993 Conference on Information Sciences and Systems, pages 581#7B586, Johns
Hopkins University, Baltimore, MD, March 1993.
31
Proof: In the #0Crst assertion, the su#0Eciency is obvious. The necessity can be shown us-
ing induction on the length of traces as follows: Since supC#28K;P#29 6= ;, and since it is
pre#0Cx closed #28since K is pre#0Cx closed#29, #0F 2 supC#28K;P#29, which establishes the base step.
For the induction step consider s#1B 2 L#28P;#0B
N
#29, where #1B 2 #06. Then s 2 L#28P;#0B
N
#29 and
#1B 2 supC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29 #5B #5B#06
u
#5C #06
L#28P#29
#28s#29#5D. From induction hypothesis s 2 supC#28K;P#29.
Hence if #1B 2 #5B#06
u
#5C #06
L#28P#29
#28s#29#5D, the from the controllabilityofsupC#28K;P#29, s#1B 2 supC#28K;P#29.
Otherwise #28when #1B 62 #5B#06
u
#5C #06
L#28P#29
#28s#29#5D#29, suppose for contradiction that #1B 62 supC#28K;P#29ns.
Then there exists a sequence of uncontrollable events u 2 #06
#03
u
such that #1Bu 2 L#28P#29ns,Kns =
L#28P#29ns,K
legal
ns. Since L#28P#29ns #12
z #7D| #7B
#5BL#28P#29ns#5D
N
and
z #7D| #7B
#5BKns#5D
N
#12 K
legal
ns, it follows that
L#28P#29ns,Kns #12
z #7D| #7B
#5BL#28P#29ns#5D
N
,
z #7D| #7B
#5BKns#5D
N
:
So wehave that #1Bu 2
z #7D| #7B
#5BL#28P#29ns#5D
N
,
z #7D| #7B
#5BKns#5D
N
, which is contradictory to the fact that #1B 2
supC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29.
We prove the second assertion also by induction on the length of traces. By de#0Cnition
#0F 2 L#28P;#0B
N
#29 #5C L#28P;#0B
N+1
#29, which proves the base step. For induction step, consider s#1B 2
L#28P;#0B
N
#29 with #1B 2 #06. Then s 2 L#28P;#0B
N
#29, and so from induction hypothesis s 2 L#28P;#0B
N+1
#29.
If #1B 2 #06
u
#5C #06
L#28P#29
#28s#29, then by de#0Cnition #1B 2 L#28P;#0B
N+1
#29ns. Otherwise #28if #1B 62 #06
u
#29 #1B 2
L#28P;#0B
N
#29ns#5D if and only if
#1B#06
#03
u
#5C
z #7D| #7B
#5BPns#5D
N
#12
z #7D| #7B
#5BKns#5D
N
; #2815#29
and su#0Eces to show that #1B#06
#03
u
#5C
z #7D| #7B
#5BPns#5D
N+1
#12
z #7D| #7B
#5BKns#5D
N+1
.Wehave
#1B#06
#03
u
#5C
z #7D| #7B
#5BPns#5D
N+1
#12 #1B#06
#03
u
#5C
z #7D| #7B
#5BPns#5D
N
#28
z #7D| #7B
#5BPns#5D
N+1
#12
z #7D| #7B
#5BPns#5D
N
#29
#12
z #7D| #7B
#5BKns#5D
N
#28from 15#29
=
z #7D| #7B
#5BL#28P#29ns#5D
N
#5CK
legal
ns.
By intersecting each term in the above series of containments with
z #7D| #7B
#5BL#28P#29ns#5D
N+1
,we obtain
#1B#06
#03
u
#5C
z #7D| #7B
#5BPns#5D
N+1
#12
z #7D| #7B
#5BL#28P#29ns#5D
N+1
#5CK
legal
ns =
z #7D| #7B
#5BKns#5D
N+1
;
as desired.
Remark 4 Since the modi#0Ced N-step ELL supervisor is more permissive than the N-step
ELL supervisor, it follows that modi#0Ced N-step ELL is more permissive than the N-step
conservative LLP.However, unlike N-step ELL supervisor, which is less permissive than
#28N + 1#29-step conservative LLP, modi#0Ced N-step ELL is non-comparable to #28N + 1#29-step
conservative LLP #28in some situations modi#0Ced ELL is more permissive and in some its less
permissive#29.
30
B Modi#0Ced ELL for Pre#0Cx Closed Case
In this appendix we present another way of computing a lookahead supervisor. The
modi#0Ced ELL supervisor di#0Bers from the ELL supervisor only in the computation of the
estimate for the desired behavior, which is computed by simply considering the legal portion
of the marked plant language #28i.e., no truncation is involved#29, i.e.,
z #7D| #7B
#5BKns#5D
N
:= K
legal
ns#5C
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
:
Since no truncation is involved in computation of the estimate for the desired behavior, the
estimated desired behavior contains more traces, and as a result the supervisor becomes
more permissiveness #28compared to the ELL supervisor de#0Cned above#29. However, it is easy to
construct an example in which such a supervisor violates the desired behavior speci#0Ccation:
Example 4 Suppose #06 = fa;bg;#06
u
= ;, L#28P#29 = pr#28aa#29;L
complete
= faa;abg;K
legal
=
pr#28ab#29. Then L
m
#28P#29=faag and K = ;. With one step lookahead,
z #7D| #7B
#5BL#28P#29n#0F#5D
N
= pr#28a#29 #5Ba#06
#03
;
z #7D| #7B
#5BL
m
#28P#29n#0F#5D
N
= faa;abg;
z #7D| #7B
#5BKn#0F#5D
N
= ab:
So supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29 = ab, and the supervisor enables a initially. This, however,
violates the desired behavior speci#0Ccation since K = ;.
It turns out however that in the special case when the desired behavior is known to be a
pre#0Cx closed language, i.e., when it represents a safety property of the system, the modi#0Ced
ELL supervisor is indeed superior since as discussed above it is more permissive and yet
it possesses all the desired properties of ELL supervisor. Safety properties are speci#0Ced by
pre#0Cx closed languages since a pre#0Cx of a trace satisfying safetymust itself satisfy safety.
First note that when the desired behavior is pre#0Cx closed, the set of traces corresponding
to the completion of task equals the set of all traces, i.e., L
complete
=#06
#03
. So the modi#0Ced
estimates are given by:
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
=
z #7D| #7B
#5BL#28P#29ns#5D
N
; and
z #7D| #7B
#5BKns#5D
N
=#5BK
legal
#5Dns#5C
z #7D| #7B
#5BL#28P#29ns#5D
N
;
and supRC operation becomes same as the supC operation.
In the next theorem we prove the desired properties of this modi#0Ced ELL supervisor: the
#0Crst part is analog of Proposition 2, and the second part is the analog of Proposition 1. With
a slight abuse of notation, we use #0B
N
to denote the modi#0Ced ELL supervisor with N-step
lookahead.
Theorem 6 The following hold for N #15 0:
1. supC#28K;P#29 6= ; if and only if L#28P;#0B
N
#29 #12 supC#28K;P#29.
2. L#28P;#0B
N
#29 #12 L#28P;#0B
N+1
#29.
29
Also, since H
2
is controllable with respect to Pns,wehave
pr#28H
2
#29#06
u
#5CL#28P#29ns #12 pr#28H
2
#29;
or equivalently,
fsgpr#28H
2
#29#06
u
#5CL#28P#29 #12fsgpr#28H
2
#29: #288#29
By considering the unions of left as well as right hand sides of #287#29 and #288#29 and using the fact
that pr#28fsg#29#5Bfsgpr#28H
2
#29=pr#28fsgH
2
#29, we obtain
pr#28fsgH
2
#29#06
u
#5CL#28P#29 #12 pr#28H#29#5Bfsgpr#28H
2
#29: #289#29
Since H is controllable with respect to P,wehave
pr#28H#29#06
u
#5CL#28P#29 #12 pr#28H#29: #2810#29
By considering the union of left as well as right hand sides of #289#29 and #2810#29 and using the fact
that pre#0Cx operation distributes over the union operation, we obtain as desired:
pr#28H #5BfsgH
2
#29#06
u
#5CL#28P#29 #12 pr#28H #5BfsgH
2
#29:
Next we prove that H #5BfsgH
2
is relative closed with respect to P. Since s 2 pr#28H#29 and
H is relative closed, wehave
pr#28fsg#29#5CL
m
#28P#29 #12 H: #2811#29
Since H
2
is relative closed with respect to L
m
#28P#29ns,wehave
pr#28H
2
#29#5CL
m
#28P#29ns #12 H
2
;
or equivalently,
fsgpr#28H
2
#29#5CL
m
#28P#29 #12fsgH
2
: #2812#29
By considering the unions of left as well as right hand sides of #2811#29 and #2812#29 and using the
fact that pr#28fsg#29#5Bfsgpr#28H
2
#29=pr#28fsgH
2
#29, we obtain
pr#28fsgH
2
#29#5CL
m
#28P#29 #12 H #5BfsgH
2
: #2813#29
Since H is relative closed with respect to P,wehave
pr#28H#29#5CL
m
#28P#29 #12 H: #2814#29
By considering the union of left as well as right hand sides of #2813#29 and #2814#29 and using the
fact that pre#0Cx operation distributes over the union operation, we obtain as desired:
pr#28H #5BfsgH
2
#29#5CL
m
#28P#29 #12 H #5BfsgH
2
:
This completes the proof.
28
control scheme. The non-blocking requirement for ELL supervisor must be relaxed in
order to make a meaningful comparison.
5. Abort operation, system failure, and rollback are also importantevents in DBMS. It
will be useful to extend the application of ELL supervisor to include these events in
the system.
A Proof of Lemma 3
Proof of Lemma 3: For notational simplicity, let H := supRC#28K;P#29, H
1
:= Hns, and
H
2
:= supRC#28Kns;Pns#29.
1. We need to show that H
1
= Hns #12 H
2
. Since H
2
is the supremal relative closed and
controllable sublanguage of Kns with respect to Pns, it su#0Eces to show that H
1
is a relative
closed and controllable sublanguage of Kns with respect to Pns, i.e., #28i#29 H
1
#12 Kns, #28ii#29
pr#28H
1
#29#5CL
m
#28P#29ns #12 H
1
, and #28iii#29 pr#28H
1
#29#06
u
#5CL#28P#29ns #12 pr#28H
1
#29. Since H = supRC#28K;P#29 #12
K; clearly, H
1
= Hns #12 Kns.We #0Crst show that H
1
is relative closed with respect to Pns.
pr#28H
1
#29#5CL
m
#28P#29ns
= pr#28Hns#29#5CL
m
#28P#29ns #28H
1
= Hns#29
= pr#28H#29ns#5CL
m
#28P#29ns #28part 2, Lemma 1#29
=#28pr#28H#29#5CL
m
#28P#29#29ns #28part 1, Lemma 1#29
#12 Hns #28H is relative closed#29
= H
1
#28H
1
= Hns#29
Next we show that H
1
is controllable with respect to Pns.
pr#28H
1
#29#06
u
#5CL#28P#29ns
= pr#28Hns#29#06
u
#5CL#28P#29ns #28H
1
= Hns#29
=#28pr#28H#29ns#29#06
u
#5CL#28P#29ns #28part 2, Lemma 1#29
#12 pr#28H#29#06
u
ns#5CL#28P#29ns #28part 3, Lemma 1#29
=#28pr#28H#29#06
u
#5CL#28P#29#29ns #28part 1, Lemma 1#29
#12 pr#28H#29ns #28H is controllable#29
= pr#28Hns#29 #28part 2, Lemma 1#29
= pr#28H
1
#29 #28H
1
= Hns#29
2. The forward containment follows from part 1 above. Hence we only need to show the
reverse containment, i.e., H
1
= Hns #13 H
2
, or equivalently, H #13fsgH
2
. Since H is the
supremal relative closed and controllable sublanguage of K with respect to P, it su#0Eces to
show that H #5BfsgH
2
is relative closed and controllable sublanguage of K with respect to
P, which implies that H #5BfsgH
2
#12 H
1
; consequently, fsgH
2
#12 H
1
. It is easy to see that
H #5BfsgH
2
#12 K. We #0Crst prove that H #5BfsgH
2
is controllable with respect to P. Since
s 2 pr#28H#29 and H is controllable with respect to P,wehave
pr#28fsg#29#06
u
#5CL#28P#29 #12 pr#28H#29: #287#29
27
The complexity ofcomputing control action at eachpoint for the ELL supervisor#28whichis
that of computing the supremal relative closed and controllable sublanguage of the estimated
desired marked language with respect to the estimated plant behavior#29 is of the same order
as that of computing the control action at each point for the LLP supervisor. This is due to
the facts that #28i#29 the number of states in the estimate of the generated plant language is same
as that in its N-step truncation, since appending #06
#03
to the traces of length N is equivalent
to adding self-loops on eacheventateach of the leaf nodes in the N-tree representing the
N-step truncation; and #28ii#29 the complexity of computing a supremal relative closed and
controllable sublanguage is of the same order as that of computing a supremal controllable
sublanguage.
In deriving the properties of the ELL supervisor #28properties obtained in Section 5#29, we
did not directly use the de#0Cnition of estimates given in De#0Cnition 1; rather we used the
properties P1-P3 of estimates. Thus the properties of ELL supervisor derived in Section 5
hold true under any other estimation based technique that satis#0Ces the properties P1-P3.
Finally, there are many possible ways that this work presented here could be extended:
1. As in #5B5, 6, 9#5D, it is important to develop algorithm to perform recursive computation
of supRC#28#01;#01#29 from one N-level tree to another as the limited lookahead windows roll
through the execution of eachevent.
2. For some application areas, the representations of K
legal
and L
complete
may be too com-
plex. One possible solution to this implementation issue is that instead of taking set
intersection to compute
z #7D| #7B
#5BKns#5D
N
, it is possible to perform and implement a legality
test on
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
j
N
to generate
z #7D| #7B
#5BKns#5D
N
.For instance, in the case of DBMS, Serial-
ization Graph Testing #28SGT#29 #5B21,20#5D could be used to determine whichschedules are
serializable.
3. The non-blocking feature often results in restrictive control in the closed-loop behavior;
thus, the generated controlled behavior, although non-blocking, may be restrictive. As
noted by Chen and Lafortune#5B3#5D, it issometime better to allow somedegreesofblocking
if such blocking occurs very rarely, or the expense to correct such blocking situation
is minimal, so that the controlled plant can achieve more of the desired behavior.
For example in DBMS, rollback mechanism is used for recovery from blocking. #28A
rollback consists of undoing the e#0Bect of certain events until it is possible to resume
the execution of the system.#29 Thus, it is possible to modify the ELL supervisor to
allow blocking by rede#0Cning the function block g
N
#28s#29 so that the ELL supervisor is
even more permissive. However, appropriate mechanism for recovery from blocking
must be incorporated.
4. In concurrency control of DBMS, locking and time-stamping #5B20,21#5D are two popular
concurrency control techniques used by manyschedulers existing today. It is instructive
to compare the performance between these two techniques with our ELL based on-line
26
ical representation of the relevant portion of K
legal
is depicted in Figure 5. In the graph
of K
legal
, all states are marked. For simplicity,we assume that the commit operation c
i
performs self-loops around all nodes as it does not violate the criterion of serializability.
When the length of lookahead N =0;1, a starting error happens in L#28P;#0B
N
#29. Since all
events are controllable, wehave L#28P;#0B
0
#29=L#28P;#0B
1
#29=f#0Fg. There is no starting error for
N #15 2. The generated languages of the closed-loop controlled system L#28P;#0B
N
#29 #28for N =2;3;
and 4#29 are depicted in Figure 6. The closed-loop generated behavior L#28P;#0B
4
#29 is the set of
initial
state w1 c1
initial
state w1 c1
r2
w2
c2
w1
w1
c1
c1
c2
r2
w2
c2
initial
state w1 c1
r2
w2
c2
w1
w1
c1
c1
c1
r2
w2
c2
r2
w2
c2
N
NN
= 2
= 3 = 4
Figure 6: Closed-loop generated behavior L#28P;#0B
N
#29 of a simple DBMS as N increases.
all complete and serializable schedules, and thus equals the supremal relative closed and
controllable sublanguage of the desired behavior. Therefore, the ELL supervisor with 4-step
lookahead is valid and non-blocking in our example.
8 Conclusion and Discussion
In this paper, wehave presented a new approach for extension based limited lookahead
supervisor. The speci#0Cc contributions of our work include the following:
1. The ELL supervisor avoids the need to choose an #5Cattitude" regarding pending traces,
which is required in LLP supervisor. This results in a unique choice for the supervisor.
2. The ELL supervisor is compared with the conservative LLP supervisor; it is shown
that ELL supervisor is in general less restrictive than the conservative LLP supervisor.
3. The ELL supervisor is non-blocking even if the desired behavior is not a relative closed
language.
4. Alower bound for N has been obtained which guarantees in the absence of starting
error our on-line scheme performs as well as the traditional o#0B-line scheme.
25
c 1
o 1
o 1
o 2
o 2
o 2
c 2
c 1
o 1
o 2
o 2
o 1
{o1,o2}
c 2
c 1
c 2 o 1
initial
state
Figure 4: A graph representation for L
complete
of a simple DBMS.
r1
w1
w2
r2
r2
w2
w1
w1
r2
w2 r2
w2
r1
w2
r2
r1, w2
r2
initial state
r2
r1
w1
w1
r1
w2
w2
r1
r1
w1
w2
r2
w1
r1
r2, w1r1
w1
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
c i
Figure 5: A graph representation for K
legal
of a simple DBMS.
24
operations should be acyclic. The set of serializable schedules de#0Cnes the legal behavior of
the DBMS. Hence we de#0Cne:
K
legal
= fs 2 #06
#03
j s is serializableg:
The control objective of a concurrency controller is to ensure that only serializable schedule
occur in the DBMS. Note that L
complete
and K
legal
may contain traces that are not physically
possible schedules.
Since transactions start and terminate within the DBMS, it is not known a priori how
many transactions are involved in the interleaving language nor which T
i
's are involved. This
is an example of a time-varying discrete event system. The conventional supervisory control
approach is not applicable here because a plant P that models all possible future behavior
cannot feasibly be constructed.
Forthe purposeofillustrating the applicationofELL supervisor, we considerthe situation
where N
T
=2. We assume for simplicity that there is only one data item a. The set of
events consists of all read r
i
#28a#29 and write w
i
#28a#29 operations on data item a and the commit
operations c
i
of the transaction T
i
within the system. Thus, in our case wehave
#06=#06
c
= fr
1
#28a#29;w
1
#28a#29;r
2
#28a#29;w
2
#28a#29;c
1
;c
2
g:
Suppose the two transactions given in #286#29 simultaneously enter the database system.
#28These transactions are #0Cxed but not known to the ELL supervisor.#29 Since N
T
=2,nonew
transaction is allowed to enter the system until at least one of the existing ones terminates.
Suppose for simplicity that no new transaction enters the system until both the existing
transactions terminate. For notational simplicity,we omit the data item a in all the oper-
ations #28e.g., r
1
#28a#29 is denoted as r
1
#29. The generated language L#28P#29, which is the set of all
possible schedules of T
1
and T
2
, is depicted in Figure 3. The dark node is a marked state
which corresponds to complete schedules.
initial
state w1 c1
r2
w2
c2
w1
w1
w1
c1
c1
c1
r2
w2
c2
r2
w2
c2
Figure 3: A graph representation for L#28P#29 of a simple DBMS.
The relevant portion of the language L
complete
is shown in Figure 4. Similarly, the graph-
23
and c
i
are used to denote read operation on data item x, write operation on data item x,any
operation #28read or write#29 on data item x, and commit operation, respectively, of transaction
T
i
. We impose the natural requirement that each T
i
can only read and write at most once
per data item, i.e., no multiple reads and writes on the same data item for each T
i
is allowed,
and no operation of T
i
follows its commit operation c
i
.
Given a transaction T
i
, L#28T
i
#29 is the language consisting of all pre#0Cxes of the sequence of
operations from T
i
.For example, if T
i
= r
i
#28a#29w
i
#28a#29c
i
, then L#28T
i
#29=pr#5Br
i
#28a#29w
i
#28a#29c
i
#5D. Letting
P denote the DBMS, its generated language, denoted L#28P#29, is de#0Cned to be:
L#28P#29=k
N
T
i=1
L#28T
i
#29;
where the non-negativeinteger N
T
2Nrepresents the maximum number of active transac-
tions allowed in the DBMS, and the k operator denotes the interleaving of languages #5B14#5D.
The value of N
T
may be dictated by limitations of the DBMS in terms of processing power
or the amount of memory available. Thus the event set of DBMS P is given by:
#06=#06
c
=
#5B
i#14N
T
;x2X
fr
i
#28x#29;w
i
#28x#29;c
i
g:
Each memberofL#28P#29 is called a schedule; i.e., a schedule is a sequence of operationsobtained
byinterleaving operations from one or more T
i
.Aschedule is called complete if there are no
active transactions in it. The set of complete schedules denoted L
complete
is de#0Cned to be:
L
complete
:= fs 2 #06
#03
j o
i
in s implies c
i
also in sg:
Consider for example
T
1
= w
1
#28a#29c
1
; T
2
= r
2
#28a#29w
2
#28a#29c
2
; #286#29
where a is a data item in the database. Also, consider the following three sequences of
operations:
s
1
= w
1
#28a#29r
2
#28a#29c
1
w
2
#28a#29c
2
;
s
2
= w
1
#28a#29r
2
#28a#29c
1
;
s
3
= w
1
#28a#29w
2
#28a#29c
1
r
2
#28a#29c
2
:
s
1
is a complete schedule; s
2
is only a schedule but not complete since T
2
is not committed;
s
3
, on the other hand, is complete but not a schedule, as the order of operations r
2
#28a#29 and
w
2
#28a#29ins
3
is not the same as that in the transaction T
2
.
For each i;j #14 N
T
;i6= j and x 2 X, a pair of operations #28o
i
#28x#29;o
j
#28x#29#29 of a schedule s 2
L#28P#29 such that at least one of the operations is a write operation, is said to be a con#0Dicting
pair of operations of schedule s.Aschedule s is called serializable if all its con#0Dicting pairs
are consistently ordered, i.e., the graph representing the executional precedence of con#0Dicting
22
Proof: The forward containment follows from Theorem 3. We prove the reverse contain-
ment, i.e., pr#28supRC#28K;P#29#29 #12 L#28P;#0B
N
#29, using induction on the length of traces. Since #0F 2
L#28P;#0B
N
#29, the base step holds. For induction step, consider a trace s#1B 2 pr#28supRC#28K;P#29#29,
where #1B 2 #06. Then s 2 pr#28supRC#28K;P#29#29; so from induction hypothesis s 2 L#28P;#0B
N
#29. It
su#0Eces to show that #1B 2 pr#28supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29#29, whichwe know is nonempty since
there is no SE, and as a result no RTE.
Since #1B 2 pr#28supRC#28K;P#29ns#29, it follows from Lemma 7 that #28Kns#1B#29
nf
6= ;. Also, since
N #15 N
nf
+2,#1B#28Kns#1B#29
nf
#12
z #7D| #7B
#5BKns#5D
N
. So the controllability and relative-closure of the set of
marked pre#0Cxes of #28Kns#1B#29
nf
, absence of RTE, and the fact that N #15 N
nf
+2 together imply
#1B#28Kns#1B#29
nf
#12 pr#28supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29. This implies #1B 2 pr#28supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29#29,
as desired.
Remark 3 The bound on the length of lookahead in Theorem 5 can be improved from
N #15 N
nf
+2toN #15 N
nf
+1by noting the fact that no uncontrollable events are feasible
at the frontier traces, which can be used to re#0Cne the estimate of the plant language by
intersecting it with the set #28#06
#03
c
:#06
#14N
nf
u :#06
#03
c
#29
#03
as in Remark 1.
Under the assumption of absence of starting error, Theorem 5 gives a su#0Ecient condition
for the validity and non-blockingnessof the ELLsupervision. It can be shown in an analogous
manner that the same result can also be obtained under a weaker condition of existence of
a minimally restrictive supervision, i.e., under the condition of supRC#28K;P#29 6= ;.However,
as discussed above, due to limited lookahead it is not possible to compute supRC#28K;P#29,
hence it is not possible to verify its non-emptiness.
7 Application to Concurrency Control
This section presents an application of the ELL supervisor in concurrency control of
transactions in a simple database management system #28DBMS#29. Modeling of transaction
execution in database systems using discrete event framework has been studied in #5B16#5D for
the untimed issues and in #5B7#5D for the real-time issues. Both these work assume complete-
information structure for concurrency control. The use of limited lookahead for concurrency
control in the untimed setting has been considered very informally in #5B10, Section 5#5D. We
provide a formal treatment here via an example, and construct a ELL supervisor for control-
ling transaction execution. The example is worked out in detail to illustrate the application
of the ELL supervisor. Wehave made some simplifying assumptions so that we are able to
focus on the main issues.
In the following, weintroduce some terminologies for concurrency control of transaction
execution in DBMS; interested readers may refer to #5B20,21#5D for details. A transaction is
de#0Cned to be a sequence of read and write operations on the data items of the database.
The additional operation, called commit operation, is used to signify successful termination
of the transaction. A transaction that is not committed is called active. Let X denote the
set of data items of the database. For each i 2Nand x 2 X, notations r
i
#28x#29;w
i
#28x#29;o
i
#28x#29,
21
that if the number of steps of lookahead is larger than the longest neighboring frontier trace,
then the ELL supervisor will be valid and non-blocking.
De#0Cnition 4 Given s 2 pr#28K#29, the set of frontier traces in K after the trace s, denoted
#28Kns#29
f
#12 Kns, is de#0Cned as:
#28Kns#29
f
:= ft 2 Kns j8#1B 2 #06:#5Bt#1B 2 L#28P#29ns#5D #29 #5B#1B 62 #06
u
#5Dg:
K
f
is used to denoted #28Kn#0F#29
f
. The set of neighboring frontier traces in K after the trace s,
denoted #28Kns#29
nf
#12 #28Kns#29
f
, is de#0Cned as:
#28Kns#29
nf
:= ft 2 #28Kns#29
f
jjtj#151; and 8t
0
#3Ct: t
0
62 #28Kns#29
f
g:
The length of the longest neighboring frontier trace, denoted N
nf
, as:
N
nf
:=
#28
max
s2pr#28K#29
n
max
t2#28Kns#29
nf
jtj
o
if it exists
unde#0Cned otherwise.
Note that N
nf
is unde#0Cned when #28Kns#29
nf
= ; for some s 2 pr#28K#29. We #0Crst prove the
following lemma.
Lemma 7 Suppose s 2 pr#28supRC#28K;P#29#29, #1B 2 #06, and N
nf
is de#0Cned. Then the following
are equivalent:
1. #1B 2 pr#28supRC#28K;P#29ns#29.
2. There exists a nonempty H 2 RC#28Kns#1B;Pns#1B#29.
3. #28Kns#1B#29
nf
6= ;.
Proof: The equivalence of the #0Crst two assertions generalizes #5B9, Theorem 1#5D, and can be
proved analogously. In order to show the equivalence of the last two assertions, we #0Crst show
that the last assertion implies the second one. De#0Cne H := pr#5B#28Kns#1B#29
nf
#5D #5C Kns#1B, whichis
the set of marked pre#0Cxes of #28Kns#1B#29
nf
. Then it is easy to see that H 2 RC#28Kns#1B;Pns#1B#29,
and its nonemptiness follows from the last assertion. On the other hand, suppose there exists
a nonempty H 2 RC#28Kns#1B;Pns#1B#29. Pick a frontier trace t 2 H #28which exists since H is
nonempty and N
nf
is de#0Cned#29. So there exists a pre#0Cx of t
0
#14 t such that t
0
2 #28Kns#29
nf
,
showing that it is nonempty.
In the following theorem we give a condition for validity and non-blockingness of a ELL
supervisor. It generalizes a similar result #0Crst proved in #5B4, Theorem 5.5#5D in context of LLP
supervision.
Theorem 5 For N #15 0, if there is no SE in L#28P;#0B
N
#29 and N #15 N
nf
+ 2, then L#28P;#0B
N
#29=
pr#28supRC#28K;P#29#29.
20
#1B 2 pr#28L
m
#28P;#0B
N
#29#29n#16s
= pr#28L
m
#28P;#0B
N
#29n#16s#29 #28part 2, Lemma 1#29
= pr#28#5BL#28P;#0B
N
#29#5CL
m
#28P#29#5Dn#16s#29 #28de#0Cnition of L
m
#28P;#0B
N
#29#29
= pr#28L#28P;#0B
N
#29n#16s#5CL
m
#28P#29n#16s#29 #28part 1, Lemma 1#29
In other words, it su#0Eces to show that there exists a string
#16
t 2 #06
#03
such that t := #1B
#16
t 2
L#28P;#0B
N
#29n#16s#5CL
m
#28P#29n#16s. Since there is no SE in L#28P;#0B
N
#29, it follows from Proposition 3 that
there is no RTE at #16s in L#28P;#0B
N
#29. Hence it follows from Corollary 3 that #1B 2 pr#28g
N
#28#16s#29#29 #5C
#06
L#28P#29
#28#16s#29 #12 pr#28supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#29. This implies that there exists a trace
#16
t 2 #06
#03
such
that t := #1B
#16
t 2 supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29 #12 L
m
#28P#29n#16s. It can be proved in a manner analogous
to the proof of the base step that t 2 L#28P;#0B
N
#29n#16s, which establishes the induction step and
completes the proof.
6 Valid and Non-Blocking ELL Supervisor
It follows from Proposition 2 that a ELL supervisor is in general not maximally per-
missive. It is useful to determine any condition under which such a property #28introduced
as validityin#5B4#5D#29 will hold. In this section we obtain a su#0Ecient condition on the length of
lookahead for the ELL supervisor to be valid and non-blocking, so that the controlled plant
generated language under ELL supervision equals the controlled plant generated language
under minimally restrictive supervision.
De#0Cnition 3 A ELL supervisor with control policy #0B
N
: L#28P#29 ! 2
#06
is called valid and
non-blocking if L#28P;#0B
N
#29=pr#28supRC#28K;P#29#29.
One should note that for a valid and non-blocking ELL supervisor, wehave
L
m
#28P;#0B
N
#29 := L#28P;#0B
N
#29#5CL
m
#28P#29
= pr#28supRC#28K;P#29#29#5C L
m
#28P#29
= supRC#28K;P#29;
where the last equality follows from the fact that supRC#28K;P#29 is relative closed with respect
to P. This justi#0Ces the name non-blocking in De#0Cnition 3. For a ELL supervisor to be valid
and non-blocking it should have su#0Ecientlookahead to determine the existence or non-
existence of all in#0Cmal controllable and relative-closed sublanguage of the #5Cpost-behavior"
#28at every pre#0Cx of the desired behavior#29. This requires a lookahead window in which all the
in#0Cmal controllable and relative-closed sublanguages of the post-behavior are present. So
alookahead window in which all the maximal length traces in the union of all the in#0Cmal
controllable and relative-closed superlanguagesof the post-behaviorare presentwould su#0Ece.
We call such traces to be the #5Cneighboring frontier traces" borrowing the terminology #0Crst
introduced in #5B4#5D. These traces have the property that it is possible to terminate execution
at these traces without getting blocked, and these are the shortest such traces. It is expected
19
The following corollary can be obtained in a straightforward manner by combining the
results of Proposition 3 and Corollary 2:
Corollary 3 For N #15 0, if there is no SE in L#28P;#0B
N
#29, then for each s 2 L#28P;#0B
N
#29, #0B
N
#28s#29#5C
#06
L#28P#29
#28s#29=pr#28g
N
#28s#29#29#5C#06
L#28P#29
#28s#29.
Using the results of Proposition 3 and Corollary 3 we establish in the following theorem
that the ELL supervisor is non-blocking.
Theorem 4 For N #15 0, if there is no SE in L#28P;#0B
N
#29, then L#28P;#0B
N
#29=pr#28L
m
#28P;#0B
N
#29#29.
Proof: Since pr#28L
m
#28P;#0B
N
#29#29 #12 L#28P;#0B
N
#29, we only need to show that if s 2 L#28P;#0B
N
#29, then
s 2 pr#28L
m
#28P;#0B
N
#29#29. We use induction on the length of s to prove this. If jsj = 0, then
s = #0F. Since there is no SE in L#28P;#0B
N
#29, supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29 6= ;, i.e., there exists a
trace t 2 supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29. However,
supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29
#12 supRC#28Kn#0F;Pn#0F#29 #28part 2, Lemma 4#29
= supRC#28K;P#29 #28de#0Cnition of #28#01#29n#0F#29
#12 K #28de#0Cnition of supRC#28K;P#29#29
#12 L
m
#28P#29 #28K = K
legal
#5CL
m
#28P#29#29
Then, wehave that t 2 L
m
#28P#29. Thus it su#0Eces to show that t 2 L#28P;#0B
N
#29, so that t 2
L#28P;#0B
N
#29#5CL
m
#28P#29=L
m
#28P;#0B
N
#29, implying that #0F 2 pr#28L
m
#28P;#0B
N
#29#29, and thus establishing the
base step. If t = #0F, then clearly, t 2 L#28P;#0B
N
#29. Suppose t 6= #0F; and suppose for contradiction
that there exists t
0
#3Ctand #1B 2 #06 such that t
0
#1B #14 t, t
0
2 L#28P;#0B
N
#29 and t
0
#1B 62 L#28P;#0B
N
#29, i.e.,
#1B 62 pr#28supRC#28
z #7D| #7B
#5BKnt
0
#5D
N
;
z #7D| #7B
#5BPnt
0
#5D
N
#29#29: #284#29
On the other hand, since t 2 supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29, wehave that
#1B 2 pr#28supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29nt
0
#29: #285#29
From Corollary 1 wehave
supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29nt
0
#12 supRC#28
z #7D| #7B
#5BKnt
0
#5D
N
;
z #7D| #7B
#5BPnt
0
#5D
N
#29:
So #285#29 implies
#1B 2 pr#28supRC#28
z #7D| #7B
#5BKnt
0
#5D
N
;
z #7D| #7B
#5BPnt
0
#5D
N
#29#29;
which is contradictory to #284#29.
In order to prove the induction step, let s =#16s#1B, where #1B 2 #06. Since s 2 L#28P;#0B
N
#29, and
L#28P;#0B
N
#29 is pre#0Cx closed, it follows that #16s 2 L#28P;#0B
N
#29. Hence from induction hypothesis we
obtain that #16s 2 pr#28L
m
#28P;#0B
N
#29#29. Thus it su#0Eces to show that
18
The following theorem follows in a straightforward manner from Proposition 2 and
Lemma 6, and provides an upper bound for the controlled plant generated language when
ELL supervisor is employed, under the assumption of the absence of SE in L#28P;#0B
N
#29. It is
similar to #5B4, Corollary 4.2#5D obtained in context of LLP supervision.
Theorem 3 For N #15 0, if there is no SE in L#28P;#0B
N
#29, then L#28P;#0B
N
#29 #12 pr#28supRC#28K;P#29#29.
Proof: If there is no SE in L#28P;#0B
N
#29, it follows from Lemma 6 that supRC#28K;P#29 6= ;.
Hence from Proposition 2 wehave that L#28P;#0B
N
#29 #12 pr#28supRC#28K;P#29#29.
In the next propositionwe establish auseful consequence ofthe absence ofSE in L#28P;#0B
N
#29,
namely, the absence of RTE in L#28P;#0B
N
#29. A similar result was #0Crst proved in #5B4, Theorem
4.6#5D in context of LLP supervision.
Proposition 3 For N #15 0, if there is no SE in L#28P;#0B
N
#29, then there is no RTE in L#28P;#0B
N
#29.
Proof: We need to show that if there is no SE in L#28P;#0B
N
#29, then there is no RTE for all s
in L#28P;#0B
N
#29. We use induction on the length of trace s. If jsj = 0, then no SE in L#28P;#0B
N
#29
implies no RTE at s. This establishes the base step.
In order to prove the induction step, let s = #16s#1B 2 L#28P;#0B
N
#29, where #1B 2 #06. Since
L#28P;#0B
N
#29 is pre#0Cx closed, this implies that #16s 2 L#28P;#0B
N
#29. Hence it follows from the in-
duction hypothesis that there is no RTE at #16s, i.e., supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29 6= ;, which
implies that #0F 2 pr#28supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#29. Hence it follows from the controllabilityof
supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29 that
#06
u
#5C#06
L#28P#29
#28#16s#29 #12 pr#28supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#29 #5C#06
L#28P#29
#28#16s#29
= pr#28g
N
#28#16s#29#29#5C#06
L#28P#29
#28#16s#29: #283#29
Since #1B 2 L#28P;#0B
N
#29n#16s,wehave that
#1B 2 #0B
N
#28#16s#29#5C#06
L#28P#29
#28#16s#29 = #5B#5Bpr#28g
N
#28#16s#29#29 #5C#06#5D#5B#06
u
#5D#5C#06
L#28P#29
#28#16s#29#5D
= #5Bpr#28g
N
#28#16s#29#29 #5C#06
L#28P#29
#28#16s#29#5D#5B#5B#06
u
#5C#06
L#28P#29
#28#16s#29#5D
= #5Bpr#28g
N
#28#16s#29#29 #5C#06
L#28P#29
#28#16s#29#5D;
where the last equality follows from #283#29.
Thus wehave #1B 2 pr#28g
N
#28#16s#29#29#5C#06
L#28P#29
#28#16s#29=pr#28supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#29#5C#06
L#28P#29
#28#16s#29, which
implies that #5BsupRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#5Dn#1B 6= ;. Hence it followsfrom the third part of Lemma
4 that supRC#28
z #7D| #7B
#5BKn#16s#1B#5D
N
;
z #7D| #7B
#5BPn#16s#1B#5D
N
#29 6= ;, i.e., there is no RTE at s =#16s#1B.
The following result was proved in the course of the proof of Proposition 3.
Corollary 2 For N #15 0, if there is no RTE at #16s 2 L#28P;#0B
N
#29, then #0B
N
#28#16s#29 #5C #06
L#28P#29
#28#16s#29=
pr#28g
N
#28#16s#29#29 #5C#06
L#28P#29
#28#16s#29.
17
s = #0F. By de#0Cnition, #0F 2 L#28P;#0B
N
#29; and supRC#28K;P#29 6= ; implies #0F 2 pr#28supRC#28K;P#29#29.
Hence we trivially have the base step.
In order to prove the induction step, let s = #16s#1B, where #1B 2 #06. Since L#28P;#0B
N
#29is
pre#0Cx closed, s 2 L#28P;#0B
N
#29 implies #16s 2 L#28P;#0B
N
#29. Hence by the induction hypothesis
#16s 2 pr#28supRC#28K;P#29#29. Also, since s =#16s#1B 2 L#28P;#0B
N
#29, wehave #1B 2 #0B
N
#28#16s#29 #5C #06
L#28P#29
#28#16s#29=
#5Bpr#28g
N
#28#16s#29#29 #5C#06
L#28P#29
#28#16s#29#5D#5B #5B#06
u
#5C#06
L#28P#29
#28#16s#29#5D.
Let us suppose #1B 2 #06
u
#5C #06
L#28P#29
#28#16s#29. Then from the controllabilityofsupRC#28K;P#29 and
the fact that #16s 2 pr#28supRC#28K;P#29#29, it follows that s =#16s#1B 2 pr#28supRC#28K;P#29#29, as desired.
It remains to show that if #1B 2 pr#28g
N
#28#16s#29#29 #5C #06
#28L#28P#29
#28#16s#29, then #1B 2 pr#28supRC#28K;P#29#29n#16s, as this
is equivalenttos =#16s#1B 2 pr#28supRC#28K;P#29#29. Wehave
pr#28g
N
#28#16s#29#29#5C#06
L#28P#29
#28#16s#29
= pr#28supRC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#29 #5C#06
L#28P#29
#28#16s#29 #28de#0Cnition of g
N
#28#16s#29#29
#12 pr#28supRC#28Kn#16s;Pn#16s#29#29#5C#06
L#28P#29
#28#16s#29 #28part 2, Lemma 4#29
= pr#28supRC#28K;P#29n#16s#29#5C#06
L#28P#29
#28#16s#29 #28part 2, Lemma 3, as #16s 2 pr#28supRC#28K;P#29#29#29
= pr#28supRC#28K;P#29#29n#16s#5C#06
L#28P#29
#28#16s#29 #28part 2, Lemma 1#29
This completes the proof.
The result of Proposition 2 is of theoretical interest as it provides an upper bound for the
controlled plant generated language when ELL supervisor is employed, under the condition
for the existence of a minimally restrictive supervisor. However, due to limited lookahead
it is not possible to compute supRC#28K;P#29; consequently, it is not possible to check for its
non-emptiness. Thus the result of Proposition 2 does not bear any practical interest. It
turns out that a stronger condition of the absence of starting error in L#28P;#0B
N
#29 can be easily
veri#0Ced, so that the upper bound result of Proposition 2 can be concluded whenever there
is no starting error in L#28P;#0B
N
#29. The following de#0Cnition similar to that given in #5B4#5D de#0Cnes
starting error as well as run time error.
De#0Cnition 2 Wesay that there is a run time error #28RTE#29 in L#28P;#0B
N
#29 at trace s 2 L#28P;#0B
N
#29
if g
N
#28s#29=;; the RTE is said to be a starting error #28SE#29 if s = #0F. If there is no RTE in
L#28P;#0B
N
#29 at all traces in L#28P;#0B
N
#29, then wesay that there is no RTE in L#28P;#0B
N
#29.
Clearly, the absence of SE in L#28P;#0B
N
#29 can be easily veri#0Ced by testing the non-emptiness
of supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29. The next proposition states that the absence of SE in L#28P;#0B
N
#29
also implies the absence of RTE in L#28P;#0B
N
#29. For these reasons, all of the results that we
present below are obtained under the singleassumption of the absence of SE in L#28P;#0B
N
#29. We
#0Crst show that the absence of SE in L#28P;#0B
N
#29 is a stronger condition than the non-emptiness
of supRC#28K;P#29. A similar result was #0Crst proved in the context of LLP supervision in #5B4,
Lemma 3.5#5D.
Lemma 6 For N #15 0, if there is no SE in L#28P;#0B
N
#29, then supRC#28K;P#29 6= ;.
Proof: If there is no SE in L#28P;#0B
N
#29, then by de#0Cnition g
N
#28#0F#29 6= ;. This is equiva-
lenttosupRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29 6= ;. By the second part of Lemma 4, this implies that
supRC#28Kn#0F;Pn#0F#29=supRC#28K;P#29 6= ;, which completes the proof.
16
5 Properties of ELL Supervisor
In this section, we present some useful properties of the ELL supervisor. These prop-
erties are quite similar to some of those of the LLP supervisor obtained in #5B4#5D. The #0Crst
proposition of this section establishes the expected result that a larger lookahead results in a
less restrictive supervision. A similar result was #0Crst presented in #5B4, Theorem 4.5#5D in context
of LLP supervision.
Proposition 1 #28Monotonicity#29 For N #15 0, L#28P;#0B
N
#29 #12 L#28P;#0B
N+1
#29.
Proof: It su#0Eces to show that for each s 2 #06
#03
, #0B
N
#28s#29 #5C #06
L#28P#29
#28s#29 #12 #0B
N+1
#28s#29 #5C #06
L#28P#29
#28s#29.
From the #0Crst part of Lemma 4 wehave
g
N
#28s#29 #12 g
N+1
#28s#29;
which implies
#5Bpr#28g
N
#28s#29#29#5C#06#5D#5B#06
u
#12 #5Bpr#28g
N+1
#28s#29#29 #5C#06#5D#5B#06
u
:
Hence it follows from the de#0Cnition of #0B
N
#28#01#29 that
#0B
N
#28s#29 #12 #0B
N+1
#28s#29;
which implies
#0B
N
#28s#29#5C#06
L#28P#29
#28s#29 #12 #0B
N+1
#28s#29#5C#06
L#28P#29
#28s#29:
This completes the proof.
Proposition 1 establishes a monotonicity property of the controlled plant generated lan-
guage under increasing length of lookahead. However, it does not provide any clue to the
range in which the controlled plant generated language under ELL supervision lies. By def-
inition, the controlled plant generated language under ELL supervision is non-empty, i.e.,
it is bounded belowby the empty set. The next proposition establishes another expected
result that if a minimally restrictive supervisor exists #28namely,ifsupRC#28K;P#29 6= ;#29, then
the controlled plant generated language under ELL supervision is bounded aboveby the con-
trolled plant generated language under minimally restrictive supervision. In fact it proves
that the existence of a minimally restrictive supervisor is equivalent to the satisfaction of
such a bound. This result is similar to the one derived in #5B4, Theorem 4.4#5D in context of LLP
supervision.
Proposition 2 For N #15 0, supRC#28K;P#29 6= ; if and only if L#28P;#0B
N
#29 #12 pr#28supRC#28K;P#29#29.
Proof: In order to see su#0Eciency, suppose L#28P;#0B
N
#29 #12 pr#28supRC#28K;P#29#29. By de#0Cnition,
#0F 2 L#28P;#0B
N
#29. Hence it follows from the assumption that #0F 2 pr#28supRC#28K;P#29#29. This implies
supRC#28K;P#29 6= ;.
Conversely, suppose supRC#28K;P#29 6= ;. We need to show that if s 2 L#28P;#0B
N
#29, then
s 2 pr#28supRC#28K;P#29#29. We use induction on the length of s to prove this. If jsj = 0, then
15
Example 2 Let #06 = fcg,#06
u
= ;, and
K
legal
= c
#03
;L
complete
=#28c
M
#29
#03
;L#28P#29=pr#28#28c
M
#29
#03
#29;
where M #3E 1 is a #0Cxed number. Then L
m
#28P#29 = K = #28c
M
#29
#03
. Then for N = M,
L#28P;#0B
N
#29 = pr#28#28c
M
#29
#03
#29, but L#28P;#0D
N
cons
#29 = #0F, showing that the conservative LLP supervi-
sor is more restrictive than the ELL supervisor proposed here. Note that the same results
would be obtained if L
m
#28P#29 and K are speci#0Ced instead of L
complete
and K
legal
.
Remark 2 The above example can be easily modi#0Ced to illustrate that the ELL supervisor
is less restrictive than the conservative LLP supervisor even when the set of uncontrollable
events is non-empty and there is a known upper bound on the number of consecutive un-
controllable events that can occur in the plant so that the re#0Cned plant behavior estimate
of Remark 1 can be used in the computation of the ELL supervisor. In the special case
when the desired behavior is pre#0Cx closed #28i.e., when L
complete
is a pre#0Cx closed language#29,
and the length of the lookahead exceeds the maximum number of consecutive uncontrollable
events that can occur in the plant #28when such maximum exists#29, then both supervisors are
maximally permissive #28follows from #5B4, Corollary 5.1#5D and Theorem 1#29, and thus, equally
permissive.
Theorem 1 shows that a N-step lookahead based ELL supervisor is generally more per-
missive than a N-step lookahead based conservative LLP supervisor. In the next theorem
we show that it is generally less permissive than a #28N +1#29-step lookahead based conservative
supervisor.
Theorem 2 For N #15 1, L#28P;#0B
N
#29 #12 L#28P;#0D
N+1
cons
#29.
By de#0Cnition, the following holds for any trace s 2 #06
#03
:
Knsj
N
=
z #7D| #7B
#5BKns#5D
N
; Pnsj
N+1
#14
z #7D| #7B
#5BPns#5D
N
:
So by simply replacing
z #7D| #7B
#5BKns#5D
N+1
with Knsj
N
and
z #7D| #7B
#5BPns#5D
N+1
with Pnsj
N+1
in the proof steps
of the #0Crst part of Lemma 4 we can conclude that
supC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29 #12 supC#28Knsj
N
;Pnsj
N+1
#29:
A similar modi#0Ccation of the proof steps of Proposition 1 below yields the desired contain-
ment.
The following example illustrates that the reverse containment of Theorem 2 does not
generally hold.
Example 3 Let #06 = fa;bg,#06
u
= fbg, K
legal
= L
complete
= L#28P#29=pr#28aa#29, and N = 1 #28so
N+1 = 2#29. Then Kn#0Fj
N
= pr#28a#29 and L#28P#29n#0Fj
N+1
= pr#28aa#29. So supC#28Kn#0Fj
N
;L#28P#29n#0Fj
N+1
#29=
pr#28a#29. Hence a 2 L#28P;#0D
N+1
cons
#29.
On the other hand,
z #7D| #7B
#5BKn#0F#5D
N
= Kn#0Fj
N
= pr#28a#29, and
z #7D| #7B
#5BL#28P#29n#0F#5D
N
= pr#28a#29 #5B a#06
#03
. It fol-
lows that supC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29=#0F. Since the uncontrollable event cannot occur initially,
L#28P;#0B
N
#29=#0F.
14
Lemma 5 For N #15 1, supC#28Knsj
N,1
;Pnsj
N
#29 #12 supC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29.
Proof: Since Knsj
N,1
contains traces with length no more than N ,1, clearly
supC#28Knsj
N,1
;
z #7D| #7B
#5BPns#5D
N
#29 = supC#28Knsj
N,1
;
z #7D| #7B
#5BPns#5D
N
j
N
#29
= supC#28Knsj
N,1
;Pnsj
N
#29; #281#29
where the last equality follows from the fact that Pnsj
N
=
z #7D| #7B
#5BPns#5D
N
j
N
. Also, since Knsj
N,1
#12
z #7D| #7B
#5BKns#5D
N
,
supC#28Knsj
N,1
;
z #7D| #7B
#5BPns#5D
N
#29 #12 supC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29: #282#29
Hence it follows from #281#29 and #282#29 that
supC#28Knsj
N,1
;Pnsj
N
#29 #12 supC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29;
which completes the proof.
The following theorem states that the ELL supervisor is in general less restrictive than
the conservative LLP supervisor studied in #5B4#5D.
Theorem 1 For N #15 1, L#28P;#0B
N
#29 #13 L#28P;#0D
N
cons
#29.
Proof: We need to show that if s 2 L#28P;#0D
N
cons
#29, then s 2 L#28P;#0B
N
#29. We use induction on the
length of s to show this. If jsj = 0, then s = #0F. By de#0Cnition #0F 2 L#28P;#0B
N
#29, which establishes
the base step.
In order to prove the induction step, let s =#16s#1B, where #1B 2 #06. Since s 2 L#28P;#0D
N
cons
#29,
which is pre#0Cx closed, wehave#16s 2 L#28P;#0D
N
cons
#29. Hence it follows from induction hypothesis
that #16s 2 L#28P;#0B
N
#29. Since s =#16s#1B 2 L#28P;#0D
N
cons
#29, #1B 2 #0D
N
cons
#28#16s#29. On the other hand, since
#16s 2 L#28P;#0B
N
#29, it follows from the de#0Cnition of ELL supervisor that s =#16s#1B 2 L#28P;#0B
N
#29ifand
only if #1B 2 #0B
N
#28#16s#29 #5C #06
L#28P#29
#28#16s#29. Thus in order to show that s =#16s#1B 2 L#28P;#0B
N
#29, it su#0Eces to
show #0D
N
cons
#28#16s#29 #12 #0B
N
#28#16s#29#5C#06
L#28P#29
#28#16s#29. Wehave
#0D
N
cons
#28#16s#29 = #5Bf
N
cons
#28#16s#29#5C#06#5D#5B#5B#06
u
#5C#06
L#28P#29
#28#16s#29#5D
= #5Bpr#28supC#28Kn#16sj
N,1
;Pn#16sj
N
#29#29#5C#06#5D#5B#5B#06
u
#5C#06
L#28P#29
#28#16s#29#5D
#12 #5Bpr#28supC#28
z #7D| #7B
#5BKn#16s#5D
N
;
z #7D| #7B
#5BPn#16s#5D
N
#29#29#5C#06#5D#5B#5B#06
u
#5C#06
L#28P#29
#28#16s#29#5D
= #5Bpr#28g
N
#28#16s#29#29 #5C#06#5D#5B#5B#06
u
#5C#06
L#28P#29
#28#16s#29#5D
= #5B#5Bpr#28g
N
#28#16s#29#29#5C#06#5D#5B#06
u
#5D#5C#5B#5Bpr#28g
N
#28#16s#29#29#5C#06#5D#5B#06
L#28P#29
#28#16s#29#5D
= #5B#0B
N
#28#16s#29#5D#5C#5B#06
L#28P#29
#28#16s#29#5D;
where the containment follows from Lemma 5; and in the #0Cnal equalitywehave used the
fact that N #15 1, which implies that #5Bpr#28g
N
#28#16s#29#29 #5C #06#5D #12 #06
L#28P#29
#28#16s#29 so that #5B#5Bpr#28g
N
#28#16s#29#29 #5C #06#5D #5B
#06
L#28P#29
#28#16s#29#5D=#06
L#28P#29
#28#16s#29. This completes the proof.
The following example illustrates that in general the reverse containment of Theorem 1
does not hold, i.e., in general L#28P;#0B
N
#29 6#12 L#28P;#0D
N
cons
#29.
13
Lemma 4 Let s 2 #06
#03
and #1B 2 #06. Then for N #15 0,
1. supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29 #12 supRC#28
z #7D| #7B
#5BKns#5D
N+1
;
z #7D| #7B
#5BPns#5D
N+1
#29.
2. supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29 #12 supRC#28Kns;Pns#29.
3. #5BsupRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29n#1B #12 supRC#28
z #7D| #7B
#5BKns#1B#5D
N
;
z #7D| #7B
#5BPns#1B#5D
N
#29#5D.
Proof: We begin by proving the #0Crst part.
supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29
#12 supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N+1
#29 #28Lemma 2#29
#12 supRC#28
z #7D| #7B
#5BKns#5D
N+1
;
z #7D| #7B
#5BPns#5D
N+1
#29 #28
z #7D| #7B
#5BKns#5D
N
#12
z #7D| #7B
#5BKns#5D
N+1
#29
Next we prove the second part.
supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29
#12 supRC#28
z #7D| #7B
#5BKns#5D
N
;Pns#29 #28Lemma 2, as Pns #14
z #7D| #7B
#5BPns#5D
N
and
z #7D| #7B
#5BKns#5D
N
#12 L
m
#28P#29ns#29
#12 supRC#28Kns;Pns#29 #28
z #7D| #7B
#5BKns#5D
N
#12 Kns#29
Finally,we prove the last part.
supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29n#1B
#12 supRC#28
z #7D| #7B
#5BKns#5D
N+1
;
z #7D| #7B
#5BPns#5D
N+1
#29n#1B #28part 1, Lemma 4#29
#12 supRC#28
z #7D| #7B
#5BKns#5D
N+1
n#1B;
z #7D| #7B
#5BPns#5D
N+1
n#1B#29 #28part 1, Lemma 3#29
= supRC#28
z #7D| #7B
#5BKns#1B#5D
N
;
z #7D| #7B
#5BPns#1B#5D
N
#29 #28consistency property of estimates#29
Thethird part ofLemma4canbegeneralizedin astraightforward manner usinginduction
to obtain the following corollary.
Corollary 1 Let s 2 #06
#03
.For N #15 0,
#5BsupRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29nt #12 supRC#28
z #7D| #7B
#5BKnst#5D
N
;
z #7D| #7B
#5BPnst#5D
N
#29#5D:
4 Comparing Conservative LLP and ELL Supervisors
In this section, we compare the performance of the ELL supervisor with the conservative
LLP supervisor studied in #5B4#5D. Since the LLP supervisor assumes K is relative closed with
respect to P, in order to make the comparison, we also assume for our ELL supervisor that
K is relative closed with respect to P. This implies that supRC#28K;P#29=supC#28K;P#29.
12
Hence supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
= #0F. So #0B
N
#28#0F#29=fbg #28all uncontrollable events are always
enabled#29. However, since b is not physically possible, L#28P;#0B
N
#29=#0F.
Next suppose N = 2. Then
z #7D| #7B
#5BL#28P#29n#0F#5D
N
=
z #7D| #7B
#5BL
m
#28P#29n#0F#5D
N
= pr#28faa;abg#29 #5Bfaa;abg#06
#03
;
z #7D| #7B
#5B#28K#29n#0F#5D
N
= pr#28faa;abg#29:
Again, supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29=#0F, and hence L#28P;#0B
N
#29=#0F.
Consider a third case when N = 3. Then
z #7D| #7B
#5BL#28P#29n#0F#5D
N
=
z #7D| #7B
#5BL
m
#28P#29n#0F#5D
N
= pr#28H#29 #5BH#06
#03
;
z #7D| #7B
#5B#28K#29n#0F#5D
N
= pr#28H#29;
where H = faaa;aab;abag. So supRC#28
z #7D| #7B
#5BKn#0F#5D
N
;
z #7D| #7B
#5BPn#0F#5D
N
#29=pr#28ab#29. Hence initially both a
and b are enabled. Since a only is physically possible, wehave a 2 L#28P;#0B
N
#29. In order to
compute the next control action wehave
z #7D| #7B
#5BL#28P#29na#5D
N
=
z #7D| #7B
#5BL
m
#28P#29na#5D
N
= pr#28H
0
#29#5BH
0
#06
#03
;
z #7D| #7B
#5B#28K#29na#5D
N
= pr#28H
0
#29;
where H
0
= faaa;aab;aba;abb;baa;babg. It is easy to see that supRC#28
z #7D| #7B
#5BKna#5D
N
;
z #7D| #7B
#5BPna#5D
N
#29=
pr#28b#29. Hence ab 2 L#28P;#0B
N
#29. Continuing in this manner one can conclude that L#28P;#0B
N
#29=
#28ab#29
#03
.
Closed-loop behaviors for other values of N can be computed in a similar manner.
It is clear from the de#0Cnition of the estimates that the following properties hold for each
N #15 0, s 2 #06
#03
, and #1B 2 #06:
P1 #28Monotonicity#29:
z #7D| #7B
#5BKns#5D
N
#12
z #7D| #7B
#5BKns#5D
N+1
;
P2 #28Anti-Monotonicity#29:
z #7D| #7B
#5BL#28P#29ns#5D
N+1
#12
z #7D| #7B
#5BL#28P#29ns#5D
N
;
P3 #28Consistency#29:
z #7D| #7B
#5BL#28P#29ns#5D
N+1
n#1B =
z #7D| #7B
#5BL#28P#29ns#1B#5D
N
.
It follows from P2 that
z #7D| #7B
#5BL
m
#28P#29ns#5D
N+1
#12
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
:
Similarly, it follows from P3 that the following hold:
z #7D| #7B
#5BL
m
#28P#29ns#5D
N+1
n#1B =
z #7D| #7B
#5BL
m
#28P#29ns#1B#5D
N
;
z #7D| #7B
#5BKns#5D
N+1
n#1B =
z #7D| #7B
#5BKns#1B#5D
N
:
Consequently, from P2 and P3 wehave
z #7D| #7B
#5BPns#5D
N+1
#14
z #7D| #7B
#5BPns#5D
N
;
z #7D| #7B
#5BPns#5D
N+1
n#1B =
z #7D| #7B
#5BPns#1B#5D
N
:
The following lemma presents a few properties of g
N
#28s#29, which is de#0Cned as g
N
#28s#29:=
supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29.
11
plant behavior N steps beyond a previously executed trace s. It then generates the estimates
of the generated and marked plant language.
g
N
P
#28s#29 :=
z #7D| #7B
#5BPns#5D
N
#11 #28
z #7D| #7B
#5BL#28P#29ns#5D
N
;
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
#29:
The block g
N
K
determines which traces in the output of g
N
P
are desired.
g
N
K
#0Eg
N
P
#28s#29 := #28pr#28
z #7D| #7B
#5BKns#5D
N
#29;
z #7D| #7B
#5BKns#5D
N
#29:
The block g
N
*
computes the supremal relative closed and controllable sublanguage of
z #7D| #7B
#5BKns#5D
N
with respect to
z #7D| #7B
#5BPns#5D
N
.
g
N
#28s#29 := g
N
*
#0Eg
N
K
#0Eg
N
P
#28s#29
:= supRC#28
z #7D| #7B
#5BKns#5D
N
;
z #7D| #7B
#5BPns#5D
N
#29:
The control action #0B
N
#28s#29 is de#0Cned slightly di#0Berently from that in #5B4#5D since wedonot
require N #15 1, which is required in #5B4#5D. This requirement implies that the next event set
after the trace s, namely #06
L#28P#29
#28s#29, is known. We de#0Cne #0B
N
#28s#29 as follows:
#0B
N
#28s#29:=g
N
u
#0Eg
N
#28s#29:=#28pr#28g
N
#28s#29#29#5C#06#29#5B#06
u
:
Thus, since the next event set #06
L#28P#29
#28s#29may not be known, all the uncontrollable events
are enabled by the control action. However, only those uncontrollable events that are also
physically possible will occur in the controlled plant.
The generated language of the controlled plant under the control policy #0B
N
: L#28P#29 ! 2
#06
,
denoted L#28P;#0B
N
#29 #12 L#28P#29, is recursively de#0Cned as follows:
#0F #0F 2 L#28P;#0B
N
#29;
#0F 8s 2 #06
#03
;#1B2 #06:s 2 L#28P;#0B
N
#29;s#1B2 L#28P#29;#1B2 #0B
N
#28s#29 #29 s#1B 2 L#28P;#0B
N
#29.
The marked controlled plant behavior is de#0Cned as
L
m
#28P;#0B
N
#29:=L#28P;#0B
N
#29#5CL
complete
= L#28P;#0B
N
#29#5CL
m
#28P#29:
The ELL supervisor #0B
N
: L#28P#29 ! 2
#06
is non-blocking if pr#28L
m
#28P;#0B
N
#29#29 = L#28P;#0B
N
#29. In this
paper, we are interested in the synthesis of non-blocking ELL supervisors.
Example 1 Suppose #06 = fa;bg,#06
u
= fbg, and
L#28P#29=K
legal
= L
complete
= fs 2 #06
#03
j8t #14 s :#23#28a;t#29 ,#23#28b;t#29 #15 0g;
where #23#28x;t#29 denotes number of x's in trace t.
First suppose N = 1. Then
z #7D| #7B
#5BL#28P#29n#0F#5D
N
=
z #7D| #7B
#5BL
m
#28P#29n#0F#5D
N
= pr#28a#29 #5Ba#06
#03
;
z #7D| #7B
#5B#28K#29n#0F#5D
N
= pr#28a#29:
10
In other words, we append #06
#03
to all the traces of L#28P#29ns of length N to obtain the estimate
of the generated plant language. The estimate of the marked language equals that portion of
the estimate of the generated language which corresponds to the completion of a task, and
the estimate of the desired marked language equals the legal portion of the estimate of the
marked plant language truncateduptoN. A di#0Berent estimate of the desired behavior, that
is obtained by considering the #5Clegal" portion of the estimate of the plant behavior #28without
truncating it up to the next N-steps#29 has been studied in Appendix B.
Remark 1 It should be noted that the estimate of the plant behavior can be further re#0Cned
by incorporating any additional knowledge regarding the plant behavior. For instance, if
we know that the number of consecutive uncontrollable events that can occur in the plant
cannot exceed a #0Cxed value, say M, then our estimate of generated behavior can be re#0Cned
as:
z #7D| #7B
#5BL#28P#29ns#5D
N
:= #5BL#28P#29nsj
N,1
#5B#28L#28P#29nsj
N
#5C#06
N
#29#06
#03
#5D#5C#28#06
#03
c
:#06
#14M
u
:#06
#03
c
#29
#03
;
where #06
#14M
u
:= fs 2 #06
#03
u
: jsj#14Mg. For example, in the concurrency control of database
systems at most one consecutive #5Ccrash" event can occur, i.e., M =1.
The estimates of the marked plant language and the desired behavior are obtained using
the languages L
complete
and K
legal
.However, if these languages are not speci#0Ced and instead
L
m
#28P#29 and K are given #28as is the case in the setting of LLP #5B4#5D#29, then these estimates may
be de#0Cned as follows #28without resulting in loss of any of the results obtained in the paper#29:
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
:= L
m
#28P#29nsj
N,1
#5B#28L
m
#28P#29nsj
N
#5C #06
N
#29#06
#03
z #7D| #7B
#5BKns#5D
N
:= Knsj
N
:
Similar to a LLP supervisor in #5B4#5D, the ELL supervisor also consists of a series of blocks
which perform di#0Berent operations, and is depicted in Figure 2. The block g
N
P
knows the
P
event
real-time
knowledge
g ggg
N NNN
Ku
?
knowledge base about
L(P), L
complete
, K
legal
control action
(s)
N
?
ELL supervisor
P
Figure 2: Block diagram of the extension based limited lookahead supervisor
9
The block f
N
u
computes the control action #0D
N
#28s#29by including the next allowable events in
the tree output by f
N
"
and the set of all uncontrollable events that P can execute after s.
#0D
N
#28s#29 := f
N
u
#0Ef
N
#28s#29
:= #5Bpr#28f
N
#28s#29#29 #5C#06#5D#5B #5B#06
u
#5C#06
L#28P#29
#28s#29#5D;
where #06
L#28P#29
#28s#29:=L#28P#29ns#5C#06. Observe that the computation of the control action requires
the knowledge of the events that are immediately executable in plant, i.e., at least one-step
lookahead is needed.
The generated controlled plant language under the control policy #0D
N
: L#28P#29 ! 2
#06
,
denoted L#28P;#0D
N
#29, is de#0Cned recursively as follows:
#0F #0F 2 L#28P;#0D
N
#29;
#0F 8s 2 #06
#03
;#1B2 #06:s 2 L#28P;#0D
N
#29;s#1B2 L#28P#29;#1B2 #0D
N
#28s#29 #29 s#1B 2 L#28P;#0D
N
#29.
The marked controlled plant behavior, denoted L
m
#28P;#0D
N
#29, is de#0Cned as:
L
m
#28P;#0D
N
#29:=L#28P;#0D
N
#29#5CL
m
#28P#29:
The notation #0D
N
cons
and f
N
cons
#28respectively, #0D
N
optm
and f
N
optm
#29 is used to indicate that the
conservative #28respectively, optimistic#29 attitude is chosen in the module f
N
a
.
3 Extension based Limited Lookahead Supervision
In this section, we propose a new limited lookahead based supervisor, whichwe call the
extension based limitedlookahead #28ELL#29 supervisor. If the generated plant language L#28P#29is
known N steps beyond a previously executed trace, it is natural to assume that any sequence
of events could happen after the known N steps. Therefore, wehave the following de#0Cnition.
De#0Cnition 1 Given s 2 L#28P#29 and N #15 0, the estimates of the generated plant language,
marked plant language, and the desired marked language #28after the trace s based on N-step
lookahead#29, denoted
z #7D| #7B
#5BL#28P#29ns#5D
N
;
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
;
z #7D| #7B
#5BKns#5D
N
, respectively, are de#0Cned as:
z #7D| #7B
#5BL#28P#29ns#5D
N
:=
#28
L#28P#29nsj
N,1
#5B#28L#28P#29nsj
N
#5C#06
N
#29#06
#03
if N #15 1
#06
#03
otherwise,
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
:= #5BL
complete
#5Dns#5C
z #7D| #7B
#5BL#28P#29ns#5D
N
;
z #7D| #7B
#5BKns#5D
N
:= #5BK
legal
#5Dns#5C
z #7D| #7B
#5BL
m
#28P#29ns#5D
N
j
N
= #5BK
legal
#5Dns#5C#5BL
complete
#5Dns#5C
z #7D| #7B
#5BL#28P#29ns#5D
N
j
N
:
8
event
knowledge base about
L(P),Lm(P),K, and pr(K)
NNNNN
uaK
P
P
?
fffff
control action
N
(s)
?
LLP supervisor
real-time
knowledge
Figure 1: Block diagram of a limited lookahead supervisor.
The block f
N
K
determines which traces in the N-tree are legal.
2
f
N
K
#0Ef
N
P
:= #28pr#28K#29nsj
N
;Knsj
N
#29:
The legal traces of length N in the N-tree are called pending traces. The block f
N
a
decides
whether or not the pending traces are desired. Two attitudes are used, namely, conservative
and optimistic. For conservative attitude, all pending traces are considered as undesired.
This results in exclusion ofall pending traces from the legalbehavior. For optimistic attitude,
all pending traces are considered as desired and marked. This results in inclusion of all
pending traces into the desired behavior.
f
N
a
#0Ef
N
K
#0Ef
N
P
#28s#29:=
#28
conservative: Knsj
N,1
optimistic :
3
Knsj
N
#5B#28pr#28K#29nsj
N
,pr#28K#29nsj
N,1
#29:
If K is pre#0Cx closed, then
f
N
a
#0Ef
N
K
#0Ef
N
P
#28s#29:=
#28
conservative: Knsj
N,1
optimistic : Knsj
N
:
The block f
N
"
computes the supremal controllable sublanguage of the language marked by
the modi#0Ced tree output by f
N
a
with respect to the language generated by the tree output
by f
N
P
.
f
N
#28s#29 := f
N
"
#0Ef
N
a
#0Ef
N
K
#0Ef
N
P
#28s#29
:= supC#28f
N
a
#0Ef
N
K
#0Ef
N
P
#28s#29;Pnsj
N
#29:
2
Note that the computation of the next N-step continuations which belong to the pre#0Cx of the desired
behavior, i.e., traces belonging to the set pr#28K#29nsj
N
, requires the knowledge of continuations beyond the
next N-step. This is inadequate for the limited lookahead setting.
7
The after operation on a language L #12 #06
#03
by a trace s 2 #06
#03
, denoted Lns #12 #06
#03
,is
de#0Cned as Lns := ft 2 #06
#03
j st 2 Lg; the truncation operation on L by a non-negativeinteger
N 2N, denoted Lj
N
#12 #06
#03
, is de#0Cned as Lj
N
:= fs 2 L jjsj#14Ng. The following lemma
appeared in #5B4#5D, the proofs of which can be found in #5B26#5D.
Lemma 1 #5B4#5D Let K
1
;K
2
#12 #06
#03
and s 2 #06
#03
. Then
1. #28K
1
#5CK
2
#29ns = K
1
ns#5CK
2
ns,
#28K
1
#5BK
2
#29ns = K
1
ns#5BK
2
ns.
2. pr#28K
1
#29ns = pr#28K
1
ns#29.
3. #28K
1
ns#29K
2
#12 #28K
1
K
2
#29ns,
#5Bs 2 pr#28K
1
#29#5D #29 #5B#28K
1
ns#29K
2
=#28K
1
K
2
#29ns#5D.
In order to obtain our main results of Section 3, we need the results of the following two
lemmas, the proof of the #0Crst one is straightforward, whereas that of the second one is given
in Appendix A.
Lemma 2 Let P
1
;P
2
be two plants with P
1
#14 P
2
. Then for K #12 L
m
#28P
1
#29, supRC#28K;P
2
#29 #12
supRC#28K;P
1
#29.
The following lemma generalizes #5B4, Theorem A.1#5D.
Lemma 3 Let K #12 L
m
#28P#29, and s 2 #06
#03
. Then
1. supRC#28K;P#29ns #12 supRC#28Kns;Pns#29.
2. #5Bs 2 pr#28supRC#28K;P#29#29#5D #29 #5BsupRC#28K;P#29ns = supRC#28Kns;Pns#29#5D.
2.1 Review of LLP Supervision
For the LLP supervisor, it is assumed that pr#28L
m
#28P#29#29 = L#28P#29, K is relative closed with
respect to P,
1
and that the supervisor knows the possible future behavior of the plant within
the next N steps at any point during the execution. The LLP supervisor consists of #0Cve
di#0Berent blocks depicted in Figure 1. Each block performs a particular operation. The #0Crst
block f
N
P
computes the plant behavior N steps beyond the previously executed trace s, where
one step corresponds to the execution of one event. This block generates the corresponding
N-tree, which also contains the marking information, i.e.,
f
N
P
#28s#29 := Pnsj
N
#11 #28L#28P#29nsj
N
;L
m
#28P#29nsj
N
#29:
1
Note that these two assumptions cannot be veri#0Ced unless the entire plant and desired behavior is known
at the outset which is unrealistic in the limited lookahead setting and must be relaxed.
6
Let P denote a plant. The language pair #28L#28P#29;L
m
#28P#29#29 is used to denote the language
model of P, which is also denoted as P #11 #28L#28P#29;L
m
#28P#29#29. L#28P#29 #12 #06
#03
is called the generated
language of P, and represents the set of all #0Cnite traces of events which P can execute.
Clearly, L#28P#29 is pre#0Cx closed and nonempty. L
m
#28P#29 #12 L#28P#29 is called the marked language
of P, and represents the set of all those traces whose executions represent completion of a
certain task. We use L
complete
#12 #06
#03
to denote the set ofall traces correspondingto completion
of a task. Note that this set may contain traces which are not physically possible in the plant.
For example, in concurrency control for database transaction systems L
complete
equals the set
of all completed schedules #5B20#5D. Thus L
m
#28P#29=L
complete
#5CL#28P#29. In this paper we will assume
that the set of complete traces L
complete
is speci#0Ced. Hence if the generated language of a
plantisknown, its marked language can be determined. Given two plants P
1
and P
2
,we
use P
1
#14 P
2
to denote that L
m
#28P
1
#29 #12 L
m
#28P
2
#29 and L#28P
1
#29 #12 L#28P
2
#29; and P
1
= P
2
to denote
P
1
#14 P
2
and P
2
#14 P
1
.
Anonempty languageK #12 L
m
#28P#29 is usedtodenote thedesiredor targetmarked language.
We use K
legal
#12 #06
#03
to denote the set of all legal traces. Note that this language may contain
traces that are not physically possible in the plant. In database transaction systems, for
instance, K
legal
represents the set of all serializable and strict schedules #5B20#5D. Thus K =
K
legal
#5CL
m
#28P#29. In this paper we will assume that the set of legal traces is speci#0Ced so that
the desired marked language can be computed if the marked language of the plant is known.
As in #5B25#5D, the event set #06 is partitioned into the set of uncontrollable events, denoted
#06
u
#12 #06, and the set of controllable events #06
c
=#06, #06
u
. It is assumed that all events are
observable #5B17#5D. Given a language L #12 #06
#03
, it is said to be controllable with respect to plant P
if pr#28L#29#06
u
#5CL#28P#29 #12 pr#28L#29; it is said to be relative closed with respect to P if pr#28L#29#5CL
m
#28P#29=
L#5CL
m
#28P#29. Note that this is equivalenttopr#28L#29#5CL
m
#28P#29 #12 L when L #12 L
m
#28P#29. We use the
following notations to denote the set of controllable sublanguages, the set of relative closed
sublanguages, and the set of relative closed and controllable sublanguages of L with respect
to P, respectively:
C#28L;P#29 := fH #12 L#28P#29 j H #12 L;pr#28H#29#06
u
#5CL#28P#29 #12 pr#28H#29g;
R#28L;P#29 := fH #12 L
m
#28P#29 j H #12 L;pr#28H#29 #5CL
m
#28P#29 #12 Hg;
RC#28L;P#29 := C#28L;P#29#5CR#28L;P#29:
It is known that supC#28L;P#29;supR#28L;P#29;supRC#28L;P#29, namely, the supremal controllable
sublanguage, the supremal relative closed sublanguage, the supremal relative closed and
controllable sublanguage of L with respect to P, respectively, exist #5B24#5D. From de#0Cni-
tion, C#28L;P#29=C#28L #5C L#28P#29;P#29, R#28L;P#29=R#28L #5C L
m
#28P#29;P#29, and RC#28L;P#29=RC#28L #5C
L
m
#28P#29;P#29; hence supC#28L;P#29=supC#28L#5CL#28P#29;P#29, supR#28L;P#29=supR#28L#5CL
m
#28P#29;P#29, and
supRC#28L;P#29=supRC#28L#5CL
m
#28P#29;P#29. It is shown in #5B12#5D that supR#28L;P#29=L,#5B#28pr#28L#29#5C
L
m
#28P#29#29,L#5D#06
#03
. A formula for supC#28L;P#29 when L is pre#0Cx closed is given in #5B2#5D and a compu-
tationally optimal algorithm for computing it is given in #5B15#5D. Computations of supR#28L;P#29
andsupC#28L;P#29 canbeused tocompute supRC#28L;P#29, assupRC#28L;P#29=supC#28supR#28L;P#29#29
#5B13#5D.
5
would yield a pre#0Cx of the desired behavior actually requires the knowledge of the
desired behavior beyond the N-step window. #28Also refer to the remark below in Section
2.1.#29
These observations motivate us to consider a modi#0Ccation of the limited lookahead based
supervisor, whichavoids these limitations. We call it to be the extension based Limited
Lookahead #28ELL#29 supervisor. The proposed supervisor estimates the plant behavior as well
as the desired behavior based on its next N-step knowledge of the plant behavior. The
estimate of the plant behavior is obtained by appending the set of all #0Cnite length event
sequences beyond the N-step projection of the plant behavior. For example when N =0,
then the estimate of the plant behavior equals the set of all #0Cnite length event sequences.
The estimate of the desired behavior is obtained by considering the #5Clegal" portion of the
estimate of the plant behavior truncated up to the next N-steps. The next control action
is computed by computing the supremal relative closed and controllable sublanguage of the
estimated desired behavior with respect to the estimated plant behavior. Thus the ELL
supervisor is de#0Cned for eachvalue of the number of steps of lookahead, and we show that it
is non-blocking even when the desired behavior is not relative closed. The ELL supervisor is
in general more permissive than the conservative LLP supervisor. In some cases such as when
there are no uncontrollable events, or when an upper bound of the number of consecutive
uncontrollable events that can occur in the plantisavailable, the ELL supervisor is strictly
more permissive than the conservative LLP one. Moreover, the ELL supervisor possesses
many of the desirable properties of the conservative LLP supervisor, and is computationally
equally viable.
In Appendix B of the paper we examine another alternative for the estimate of the desired
behavior: It is obtained by simply considering the #5Clegal" portion of the estimate of the plant
behavior #28without truncating it to the next N-steps#29. The usage of such an estimate yields a
more permissive supervisor, but it may not be non-blocking in general. However, when the
legal behavior corresponds to safety speci#0Ccations so that it can be represented as a pre#0Cx
closed language, the usage of such an estimate for supervision is indeed a superior option as
the controlled system behaves legally as well as more permissively.
2 Notation and Preliminaries
Let #06 denote the set of events that occur in a given discrete event planttobecontrolled.
#06
#03
is used to denote the set of all #0Cnite length sequences of events from #06, including the
zero length sequence, denoted #0F. A member of #06
#03
is called a string or a trace, and a subset
of #06
#03
is called a language. Given a string s 2 #06
#03
, jsj2Nis used to denote the length of s;if
t 2 #06
#03
is a pre#0Cx of s, then it is written as t #14 s. t is said to be a proper pre#0Cx of s, denoted
t#3Cs,ift #14 s and jtj #3C jsj. The notation pr#28s#29 #12 #06
#03
denotes the set of all pre#0Cxes of s,
i.e., pr#28s#29:=ft 2 #06
#03
j t #14 sg. Given a language L #12 #06
#03
, the pre#0Cx closure of L denoted
pr#28L#29 #12 #06
#03
, is de#0Cned as pr#28L#29:=fs 2 #06
#03
j9t 2 L s.t. s #14 tg; L is said to be pre#0Cx closed
if L = pr#28L#29.
4
Lookahead policies have also been employed earlier for instance for deadlockavoidance
in #0Dexible manufacturing systems using Petri net models #5B1, 19#5D, for planning in arti#0Ccial
intelligence #5B23,18,22#5D, in robotics #5B11#5D, etc.
In an attempt to propose a modi#0Ccation of the limited lookahead supervision, we note
the following limitations of the limited lookahead policy based supervisor studied in #5B4#5D:
#0F Due to the presence of the pending sequences, the limited lookahead policy based su-
pervisor either takes an optimistic attitude whichmay result in violation of constraints
imposed by the desired speci#0Ccations, or it takes a conservative attitude whichmay re-
sult in a restrictive control policy. This is demonstrated by showing that the proposed
supervisor is in general more permissive.
#0F The assumption of the relative closure #28also known as the L
m
-closure in the literature#29
of the desired behavior can only be veri#0Ced if the entire plant and the desired behavior
is known at the outset. So such an assumption is not practical for the limited lookahead
setting, and should be relaxed.
#0F Similarly, the assumption that the plant is non-blocking, i.e., each generated trace is a
pre#0Cx of some marked trace cannot be veri#0Ced in the setting of limited lookahead and
must be relaxed to be realistic.
#0F The LLP supervisor becomes blocking if the target behavior is not a relative closed
language. As mentioned above an apriori assumption of relative closure is impractical
in the limited lookahead setting as it cannot be veri#0Ced. Moreover, such an assumption
may not even be realistic. To see this consider the following simple example from
Ramadge-Wonham #5B25#5D: In this example the plant consists of two tandemly operating
machines, where the #0Crst machine receives an incoming part, and upon processing,
puts it into a bu#0Ber from where the second machine fetches the part for the #0Cnal step
of processing. Each machine starts from its #5Cidle" state, which is also its only #5C#0Cnal"
or #5Cmarked" state. It is desired that the machines operate in a manner that the bu#0Ber
never over#0Dows#2Funder#0Dows. Suppose it is further required that upon completion of the
task all machines must be in their idle state and the bu#0Ber be in its empty state. Then
it is easy to see that this desired behavior is not relative closed: The event sequence
corresponding to arrival of a part into the #0Crst machine followed by departure from
that machine has the property that #28i#29 it is a pre#0Cx of the desired behavior #28it can
be extended by the trace arrival into the second machine and departure from the
second machine to yield a trace that satis#0Ces the given speci#0Ccation of the bu#0Ber
over#0Dow#2Funder#0Dow constraint and leaves the machines in their idle states and the
bu#0Ber in its empty state#29; and #28ii#29 it also leaves both the machines in their idle state,
i.e., it is a trace belonging to the #5Cmarked behavior" of the plant. However, this trace
does not belong to the desired behavior since the bu#0Ber state is not empty at this
point.
#0F The optimistic LLP supervisor requires the knowledge of the desired behavior beyond
the N-step lookahead window. Determination of whether a next N-step continuation
3
1 Introduction
Discrete Event Systems #28DESs#29 are those dynamical systems whichevolve according to
the asynchronous occurrence of certain discrete qualitativechanges, called events. Many
man made systems including manufacturing systems, communication protocols, database
transaction systems, tra#0Ec systems, etc., are examples of DESs. The theory of supervisory
control of DESs initiated by Ramadge and Wonham #5B24,25#5D deals with control of the #5Corderly
#0Dow" of events in such systems. The behavior of a DES, also called a plant, is described using
the set of all #0Cnite length sequences of events that it can execute, and a certain subset of the
plant behavior represents a desired or target behavior. A supervisor, based on its observation
of the sequence of events executed by the plant, dynamically disables some of the controllable
events from occurring, so that the constraints imposed by the desired behavior speci#0Ccation
are satis#0Ced.
In the conventional approach for supervisor synthesis, the entire control policy for the
given DES is computed o#0B-line. This requires automata models which describe the entire
behavior of the DES and the target behavior. However, in many situations it is di#0Ecult to
perform the o#0B-line computations:
#0F The DES is very complex and contains a large number of states. The o#0B-line compu-
tation for the entire control policy is computationally too complex to be feasible.
#0F The DES is time varying and its complete description cannot be given as a #0Cxed
automaton.
#0F Even if the DES is time invariant, the entire description of the DES is not known
initially but possibly becomes known during the execution time.
#0F Due to the complexity of the desired behavior constraints, it is di#0Ecult to construct
an automaton consistent with desired speci#0Ccations.
#0F The desired behavior itself may be time varying. The desired behavior is incompletely
speci#0Ced initially and must be speci#0Ced using sensory information during the execution
time.
In view of these observations, Chung-Lafortune-Lin #5B4#5D have proposed a control scheme
using LimitedLookahead Policy #28LLP#29. This control scheme allows control actions to be
calculated on-line instead of o#0B-line. The next control action is computed on the basis of the
DES behavior truncated up to the next N-steps. The control action can be computed based
on two extreme attitudes regarding the pending sequences|conservative and optimistic.In
#5B5#5D the authors have further studied how to use previous computations to help in the next
computation of the control action. E#0Bect of taking an undecided attitude to help improve the
computational complexity has been investigated by the authors in #5B6#5D, on-line computational
technique in which no constraint is imposed on the depth of the lookahead window has been
investigated in #5B9#5D assuming that the additional state-information is also available, and the
extension to the case of partial observation has been considered in #5B8#5D.
2
Extension based Limited Lookahead Supervision of
Discrete Event Systems
#03
Ratnesh Kumar, Hok M. Cheung
Department of Electrical Engineering
University of Kentucky, Lexington, KY 40506
Steven I. Marcus
Department of Electrical Engineering and ISR
University of Maryland, College Park, MD 20742
Abstract
Supervisory control of discrete event systems using limited lookahead has been
studied byChung-Lafortune-Lin, where control is computed by truncating the plant
behavior up to the limited lookahead window. We present a modi#0Ccation of this ap-
proach in which the control is computed by extending the plant behavior by arbitrary
traces beyond the limited lookahead window. The proposed supervisor avoids the no-
tion of pending traces. Consequently the need for considering either a conservativeor
an optimistic attitude regarding pending traces #28as in the work of Chung-Lafortune-
Lin#29 does not arise. It was shown that an optimistic attitude may result in violation of
the desired speci#0Ccations. We demonstratehere that a conservative attitude may result
in a restrictive control policy by showing that in general the proposed supervisor is less
restrictive than the conservative attitude based supervisor. Moreover, the proposed
approach uses the notion of relative closure to construct the supervisor so that it is
non-blocking even when the desired behavior is not relative closed #28Chung-Lafortune-
Linassume relativeclosure#29. Finally, the proposedsupervisorpossessesall the desirable
properties that a conservative attitude based supervisor of Chung-Lafortune-Lin pos-
sesses. We illustrate our approachby applying it to concurrency control in database
management systems.
Keywords: Discrete Events Systems, Supervisory Control, Limited Lookahead, Con-
trollability, Relative Closure.
#03
This researchwas supported in part by the Center for Robotics and Manufacturing Systems, University
of Kentucky, and in part by the National Science Foundation under the Grants NSF-ECS-9409712 and
NSF-EEC-9402384.
1