Model Uncertainty in Discrete Event Systems.
Earlier work concerning control of discrete event systems usually assumed that a correct model of the system to be controlled was available. A goal of this work is to provide an algorithm for determining the correct model from a set of models. The result of the algorithm is a finite language that can be used to test for the correct model or notification that the remaining models cannot be controllably distinguished. We use the finite state machine model with controllable and uncontrollable events presented by Ramadge and Wonham.
Introduction
A discrete event system (DES) is one which responds to distinct events
occurring at asynchronous times [7]. Examples of such systems include
computer networks, manufacturing systems, and other dynamic systems
which require high level coordinated control. There has been some success
recently in developing a theory for the control of such systems (see [13] and
the references therein). Most of this work has assumed that an accurate
model for the system of interest is available.
The motivation for this work is the desire to control systems in the
presence of uncertainty in the model of the system and environment in
which the system operates. Part of this work is an extension of learning
and inference theory [6, 2, 16] to the domain of discrete event systems.
This work is also related to recent results concerning the determination
of a system model when certain assumptions are made about the model
and type of experiments [14, 15]. In both the learning theory and system
determination work, an assumption is that all events are controllable. The
uncontrollability of certain events figures prominently in this work. The
approach taken in this paper is similar to the approach used for system
identification in [17] in that any model which is falsified is dropped from
consideration as a correct model.
There are many different types of uncertainty which might occur in a
system model. To discuss such uncertainties, a model representation must
be chosen. In this work, we investigate uncertainty in a deterministic finite
state machine. An example of such uncertainty is an uncertainty in the
transitions of a system which can be described as a state which has a single
event specified as providing transitions to at least two different resulting
states; however, only one of the transitions is actually present in the sys-
tem. Other examples are discussed in Section 3. Such uncertainty results
in multiple models of the system which might potentially be correct. The
goal is to specify conditions and algorithms which enable the identification
of the correct model in a finite number of transitions despite the presence
of uncontrollable actions. In particular, an algorithm provides either notification
that no more models may be controllably distinguished or a finite
distinguishing language which can be used to remove an incorrect model.
Section 2 describes the method used to model the plant and the relevant
controllability results. Section 3 gives some examples of how a set of
potentially correct models for a system might arise. Section 4 describes the
concepts and techniques used to identify a correct model from a given set
of models. Section 5 provides example applications of the results.
2 Description of the Model
We use the deterministic finite state machine as a model for system be-
havior. In what follows, only the main features of the finite state machine
model related to this work are covered in a condensed manner. A more complete
development related to the finite state machine model can be found in
[5, 9]. More complete descriptions of the controllability and related results
can be found in [13, 3, 11].
2.1 Finite State Machines and Regular Languages
A finite state machine is represented by either a four or five tuple. Specifi-
cally, if M is a finite state machine (FSM), then one writes
or
a finite set of states,
a finite set of transition labels or events,
the transition function,
the initial state, q 0 2 Q; and
the marked states, Qm ' Q:
The transition function ffi is in general a partial function: ffi(q; oe)! denotes
that the transition event oe is defined from state q. The marked states
signify a subset of the state set which is used to determine acceptance of a
given string. A string is accepted if the machine executing the string stops
in a marked state.
A finite state machine, can also be represented
as a directed graph are the sets of nodes and
arcs, respectively, or states and transitions in this instance [1, 4]. Q is the
set of states in the machine and T ' Q \Theta A \Theta Q is the set of transitions.
If one denotes the transition by the three
tuple
A   is used to denote the set of all finite sequences of symbols from the
alphabet A. A language is a set of strings of elements from an alphabet. If
denotes the length of u, u(j) denotes the j th element of the
string, and the set pr(u) denotes the set of all strings which are prefixes of
u, i.e. for u 2 A
The notation s - u is used to denote that s is a prefix of u. Note that
the empty string, ", is the length zero prefix of all strings. The concept of
prefix can be extended to a language in the following manner. The prefix
closure of a language L is defined by
We use the notation s 2 ppr(u) or s ! u to signify that s is a proper prefix
of u, i.e. that s - u and s 6= u. This concept is extended to a language,
in the following manner:
For this work, we restrict our attention to the class of regular languages
which is a strict subset of the class of formal languages. A basic
result relates regular languages and finite state machines: a language
is regular if and only if it is generated by a finite state machine
[9]. Language Lm (M) is the language marked or recognized by machine
where ffi is extended in the usual manner, language
L(M) is the language generated by machine M if
The product machine is a single machine which can be used to represent
the synchronous behavior of two original machines. If machines
have the same event
set, A, then the product of the two machines is denoted
where,
defined
undefined otherwise,
and,
The languages generated and marked by the product machine have a specific
relation to the languages of the machines from which they are com-
posed. If M
2.2 Control of Discrete Event Systems
The event set, A, can be partitioned into two sets: A c and A u representing
controllable and uncontrollable events, respectively. A language K is
controllable with respect to language L if
K:A
where a:b denotes concatenation and is often denoted by ab. A supervisor
for a plant, modeled with finite state machine P , where
which specifies a set of inputs enabled by the supervisor which can be applied
as a function of the string in L of events which the plant has previously
executed. The closed loop system consisting of a supervisor, f , and plant,
P , has the closed loop behavior denoted by L f , and is defined as follows:
2. woe 2 L f if and only if w 2 L f ; oe 2 f(w); and woe 2 L:
A supervisor, f , is complete with respect to a given plant P , with
uncontrolled actions of the plant are respected, i.e., if x 2 L f and
xoe A u and L f is the closed loop behavior
as discussed above. The following result is a basic theorem relating these
concepts.
Theorem 2.1 ([12]) For non-empty K ' L, there exists a complete supervisor
f such that L only if K is prefix closed and controllable

The region of weak attraction, as discussed in [3, 11], can be directly
related to distinguishing different machines. The region of weak attraction
for a specified set of states can be described informally as the set of states
from which the system can be controlled so as to enter the set of specified
states in a finite number of transitions.
The region of weak
attraction,\Omega M (G), for a machine,
or in graph notation, specified subset of states, G ' Q,
can be determined by the algorithm in [3]. For a specific calculation of the
region of weak attraction of a given set of states, G, the transitions used
in its construction are denoted by
T\Omega (G). This algorithm builds the region
of weak attraction starting from G. Each iteration of the algorithm adds
states to the region defined in the previous iteration. A state is added to
the region of weak attraction only if there is an event oe which describes a
transition into the region defined in the previous iteration and there does
not exist an uncontrolled event to a state not in the region defined by the
previous iterations of the algorithm. The transition labeled by this oe is
added to
T\Omega (G) as are the uncontrolled transitions from this state. The
states
in\Omega M (G) are well defined; as discussed in [3], the transitions chosen
for
T\Omega (G) are not necessarily uniquely defined. The algorithm is guaranteed
to terminate by the finite state description of the machine. An efficient
algorithm in [11] computes the region of weak attraction in O(jQj \Delta jAj)
time.
The characteristics of the region of weak attraction are most easily described
by certain conditions on the directed graph which describes the finite
state machine. Let the machine be described by the graph
with G ' Q. The region of weak attraction satisfies three main criteria as
described in the following proposition.
Proposition 2.1 ([3])
if and only if
A graph -connected if F ' Q and from every state in
there exists a path to a state in F . A subgraph M
is realizable if
A realizable subgraph includes all uncontrollable arcs which are defined
from any state in the state set of the subgraph.
If the initial state, q 0 , for the machine, M , is in the region of weak
attraction, i.e., q 0
2\Omega M (G), then we also define a machine based on the
region of weak attraction,
M\Omega (G), where
M\Omega (G) is formally defined by the
tuple:
And
is an arc defined in the construction
of the region of weak attraction, i.e. (q
T\Omega (G). With
M\Omega defined, the language recognized by the resulting machine is denoted by
L(M\Omega (G)). As mentioned above and in [3],
M\Omega (G), and hence
L(M\Omega (G)),
is not unique.
3 Model Uncertainty
Uncertainties in the plant model provide a set of models which are potentially
correct models of the plant. Each model in this set is obtained
by assuming that the uncertainty results from a specific lack of knowledge
about the structure of the plant.
Example 3.1 Consider an automatic guided vehicle system guided by
wires in the floor of a manufacturing facility. The model of the guidance
system may contain errors. Each error will produce an uncertain model of
the correct system. For instance, two branch nodes in the wiring may be
combined into a single node in the model, an extra branch may be in the
model which is not installed in the plant, or the model may be lacking a
branch which is installed in the plant. Each of these errors generates an
uncertain model which can be used to define a set of potentially correct
models.
Example 3.2 Model (A) in Figure 1 gives an example of a system with
uncertainty in the transitions. For this transition uncertainty, there is a
single state, q 0 , in the model which has "b" transitions defined to k different
states, yet, in the actual system, only one of these "b" transitions
is defined.
a,b a,b
a,b
a
a

Figure

1: Model for Transition Uncertainty. (A) Model with transition
uncertainty, (B) One of the possibly correct models.Example 3.3 Assume that the set of events which a system can accomplish
is known and that there is a known upper bound on the size of the
state space. Using these two assumptions, one can construct all possible
models for the system. After all unique models have been constructed, a
technique is required to generate tests which can distinguish the correct
model.4 Distinguishing Between Models
We present deterministic techniques which provide an easily checked condition
and an algorithm for correctly removing inconsistent models from
consideration and identifying the correct model.
Certain concepts will provide a unified framework for the development
which follows. For the following definitions, we assume that there are models
have states and an event oe 2 A.
Definition 4.1 Given M 1 and M 2 , the predicate different(z; w) holds if
where
predicate depends on both the state in the product machine and the
string chosen to differentiate the states which make up the product state.
Example 4.1 For the machines defined in Example 3.2, let M i and M j
be the possible models which have the b transition defined to states q i and
does not hold, where (q i0 ; q j0 ) is the product initial state.In the following A4B denotes the symmetric difference of the two sets
A and B, i.e.
Definition 4.2 A string w is a distinguishing string for languages L 1 and
(w ):Definition 4.3 A string w is a minimally distinguishing string for languages
(w minimally distinguishing string is minimal in the sense that no prefix is
also a distinguishing string.
Definition 4.4 A non-empty language L is a distinguishing language for
implies that w is a minimally distinguishing string for
string in a distinguishing language is one which uses the last
event to distinguish between L 1 and L 2 . Note that, in general, there is not
a unique distinguishing language for two machines M 1 and M 2 .
Example 4.2 Let L be two languages which describe
the behavior of two possible models of a black box machine. For these
languages,
For a distinguishing language L to satisfy (ppr(L) ' must have
that L ' a   b.
Observe that if the machine executes the final b, then L 2 is the correct
language, and if not, then L 1 is the correct language.For languages generated by a state machine, we have the following result

Proposition 4.1
Let L 1 and L 2 be languages generated by the machines M 1 and M 2 .
There exists a distinguishing language, L, for L 1 and L 2
if and only if
Proof:
immediately have that different(z 0 ; w)
holds.
Let w be the string which satisfies different(z 0 ; w). From the definition of
different(\Delta; \Delta), there is some v 2
that voe 62 fvoeg. It is clear that L is a
distinguishing language for L 1 and L 2 .
End proof of Proposition 4.1.
Example 4.3 For the machines in Example 4.1, different((q
holds; consequently, there is a distinguishing language,
Distinguishing Between Two Models
Assume that machine M has an uncertainty which causes the set of potentially
correct models to consist of the models M 1 and M 2 . We assume that
one of these models is correct. The models are specified by the following
tuples:
The languages generated by these models are referenced by L(M 1 ) and
We also refer to the standard synchronous product machine:
The set of states in the product machine which can be used to controllably
distinguish the two models is defined in the following manner.
Definition 4.5 G is the controllably distinguishing set of states for M 1 and
event which can be used to distinguish two states is called a
controllably distinguishing event. Hence, an event oe is a controllably distinguishing
event for z if different(z; oe) holds and there is not an uncontrolled
event oe u defined in the product machine from z.
Example 4.4 For the machines given in Figure 2, let A fbg. The controllably
distinguishing state set is q)g. In this example,
the set of controllably distinguishing states is the entire product space.
a
a

Figure

2: Machines for controllably distinguishing state set calculation.
Example 4.5 Consider the same machines as Example 4.4, but let A
fag. In this instance, the set of controllably distinguishing states is
controllably distinguish states in the product machine, a string must
be found which leads to a state in G. Note that G is a superset of states
which can be used to distinguish states in the product machine and reached
from the initial state. This inclusion is a result of defining G to be all
states in the product machine which have controllably distinguishing events
defined without consideration of reachability constraints.
Proposition 4.2 states that there is a finite controllable method for distinguishing
between two finite state machines if and only if the initial state
of the product machine is in the region of weak attraction of the set of
states which can be used to distinguish between the two machines.
Proposition 4.2
be two machines.
There exists a finite language L which satisfies:
1. L is controllable with respect to L(M 1
2. L is a distinguishing language for
if and only if
z 0
(G),
where
1. z
2. G is the controllably distinguishing set of states, and
(G) is the region of weak attraction of G in M 1 kM 2 .
for M 1 and M 2 .
Proof:
(=:
We will demonstrate a language L which satisfies Definition 4.4 with
respect to L(M 1 ) and L(M 2 ), and is controllable with respect to L(M 1
(G), we can define a machine
M\Omega (G), as discussed in
Section 2.2, and let Lm
(M\Omega ) be the language marked by this machine with G
as the marked states. Define X ' A such that if t 2 Lm
to satisfy the definition of G, i.e. that (ffi k (z
Such a symbol is defined for every string in Lm
(M\Omega ) by the definition of G.
Further define L ' Lm
(M\Omega )X by toe 2 L if t 2 Lm
(M\Omega
oe is a controllably distinguishing event for z.
We must show that this language is finite, satisfies the definition for
controllability and satisfies the definition of a distinguishing language.
1. L finite:
of\Omega M (G)g
no cycles in
(G)j
finite:
2. L controllable with respect to L(M 1
Let
T\Omega (G)) and assume that
(M\Omega ):X and definition of Lm
(M\Omega )g
T\Omega ) fdefinition of Lm
(M\Omega )g
Hence L is controllable with respect to L(M 1
3. L non-empty:
z 0
fM\Omega is G-connectedg
fdefinition of G and Xg
(M\Omega ):X
4. ppr(L) '
(M\Omega ):X
fdefinition of
M\Omega and M k g
fproperty of regular languages and FSMg
5.
fdefinition of G and Lg
fdefinition of G and Xg;
different(z; oe)
fdefinition of Gg
The last three items combine to show that L satisfies the conditions for
being a distinguishing language.
Let (V; T ) denote the graph representation of the product machine M 1 kM 2 .
Consider the subgraph, obtained by running all strings
in L on (V; T ). Define
Any state in the product machine reached by a string in the closure of L
is included in V 0 and any transition traversed by a string in the closure
of L in included in T 0 . Since L is finite and ppr(L) '
that defined and that a simple algorithm will generate this
subgraph.
Consider the states reached by string in L=A. (Recall, L=A denotes
strings in L with the last symbol removed.) The following lemma follows
easily from the definition of a distinguishing language and controllability.
Lemma 4.1 With L as assumed in the statement of the proposition,
where z 0 and G are as defined in the statement of Proposition 4.2.
The following lemma provides the realizability of (V
to (V; T ) and A u .
Lemma 4.2 realizable with respect to (V; T ) and A u .
Proof:
From
these facts, we must show that (z 1 Notice that from the construction
of V 0 , we have that w 2 ppr(L) implies that z
controllable with respect to
End proof of Lemma 4.2.
By Lemma 4.1,
realizable. If there are no cycles in (V Proposition 2.1 we
have that z 0
(G) as desired.
If there are cycles, more work is required. The idea is to disable a cycle
and show that the remaining subgraph is still G-connected and realizable.
finite graph, there are only finitely many cycles; con-
sequently, after disabling all cycles, we have a subgraph remaining which
is G-connected, realizable, and acyclic. By Proposition 2.1, we have that
z 0
(G) as desired.
Now we must show that cycles may be removed while retaining the
connectedness and realizability of the subgraph
We start by classifying all transitions in T 0 . A transition is included
in class C if it must be included in T 0 for controllability reasons, i.e. if
the subgraph would lose the realizability characterization by not having a
specific transition, then that transition is included in C. Hence,
A transition is included in class R if it must be included in T 0 for reachability
reasons, i.e. if a node would no longer be G-connected without
the presence of a specific transition, then that transition is included in R.
Hence, only if there does not exist a w 2 A   such that
there is a path labeled by w from z 1 to G in the subgraph
Assume that there is a cycle in (V there is a transition (z
on the cycle which is not in C[R, then we can clearly remove this transition
and retain the G-connectivity and realizability. This fact follows from the
facts that any transition, (z 1 ; oe; z 2 ), not in C [R is controllable and there is
another path in the subgraph from z 1 to G which does not use the transition
in question.
Hence, if we can remove all cycles by deleting transitions which are not
in C [ R, then we are done.
Assume that there is a cycle remaining which only has transitions in
a transition on this cycle. From the construction of
the subgraph have that there is a string s 2 ppr(L) such that
. The following lemma provides the crucial result.
Lemma 4.3 Let L and C [ R be as above.
If there is a cycle which has transitions only in C [R, then there are strings
of arbitrary length in L.
Proof:
Let x 2 A   be the labels of the transitions on this cycle, i.e.
denote the state immediately preceding label x(i), i.e.
a transition on this cycle. Note that z
From the controllability of L with respect to
the fact that every transition on the cycle is in C [ R, it is clear that
ppr(L). The same result holds for each i, i.e.
implying that sx   ' ppr(L).
End proof of Lemma 4.3.
This last statement contradicts the finiteness of L; consequently, there
can be no cycle consisting only of transitions from C [ R. As a result of
Lemma 4.3, any cycle in the subgraph can be removed while retaining G-
connectivity and realizability. Hence, the conditions of Proposition 2.1 are
satisfied and we get that z 0
(G).
End proof of Proposition 4.2.
Based on Proposition 4.2, we define a predicate which is true if two
machines can be distinguished as described in the proposition.
Definition 4.6 Given machines M 1 and M 2 , where
and
(:9oe
:If two machines satisfy this predicate, then the machines, or their languages,
are said to be controllably distinguishable.
The following corollary provides the application of Proposition 4.2 to
resolving an uncertainty which gives two potentially correct models. If
z 0
(G), then a supervisor corresponding to the machine represented
by the graph created by the algorithm which generates the region of weak
attraction can be built which will constrain the behavior of the unknown
system such that an incorrect model can be identified in a finite number
of transitions. (See [13] for details on how a machine representation of a
supervisor is used to control a plant.)
Corollary 4.1 Let M 1 and M 2 be two models, such that one of them
correctly models the plant, M . Let M
be the controllably distinguishing set of states for M 1 and M 2 .
z 0
if and only if
the correct model can be chosen in a finite number of transitions.
Proof:
By Proposition 4.2, if z 0
(G), then there exists a finite non-empty controllable
language, L, such that any string in the language can distinguish
Theorem 2.1, a supervisor f can be constructed such
that hence, the plant can be controlled so as to execute strings from
L. Since one of the models correctly models the plant, ppr(L) ' L(M ),
and any proper prefix of a string t in L can be executed by the plant. Since
last symbol in the string will either be executed
or not depending on whether which model has t
defined in its language.
By Proposition 4.2, if z 0
(G), then we can construct a string of arbitrary
length which the plant can execute such that no supervisor may
disable events such that an inconsistency is observed.
End proof of Corollary 4.1.
The complexity of this approach is governed by the necessity to consider
the product machine for M 1 and M 2 in order to determine the distinguishing
language. This operation requires O(jQ 1 jjQ 2 operations. In this paper,
the dependency of the complexity on the size of the event set A is assumed
to be a constant factor; hence is not included in the expression for the
order of complexity. As shown in Section 5.1, this is a sharp bound on the
complexity.
4.2 Distinguishing Multiple Models
The technique for distinguishing between multiple models with a reset capability
available is an extension of the technique used to distinguish between
two models. The strategy is to construct a product machine from two
models in the set of models which results from considering all possible permutations
of the uncertainties. Then, from this product machine, calculate
the region of weak attraction for the set of controllably distinguishing states
for these two models as described in Corollary 4.1. By using the machine
generated by the region of weak attraction as a supervisor for the plant, at
least one of these models can be removed from the set of possibly correct
models by controlling the plant to enter a state which is a component of
one of the product states in the set of controllably distinguishing states.
Then, after at least one of these models has been eliminated as a possibly
correct model, reset the plant and start the procedure over with another
pair of models. Note that it is possible that neither of the models which
are chosen is the correct model for the system; hence, the plant might generate
a string which is not defined in either of the models used to generate
the supervisor. In this case, both models are removed and the procedure
continues by choosing another two models. This procedure continues until
all uncertainties have been resolved or until no pair of models can be found
which satisfy the conditions of Corollary 4.1.
We denote each possible model as: M
is the initial number of models from which the correct
model is to be chosen. We denote the initial set of all possible models by
. Using the notation given,
where each model is in minimal canonical form [5, 9].
The following algorithm specifies the procedure given above. P denotes
the actual machine or the plant which is to be correctly modeled.
Algorithm 4.1
Input:
S 0 as given above.
Output:
additional uncertainties can be resolvedg:
Algorithm:
While (jS
Use
Determine which model is still a possibly correct model and
which model is not consistent with the plant.
which have been determined to be
inconsistent with plant g.
Reset the plant.
End while.
End of algorithm.
In the worst case, the product for every pair of models would need to
be calculated to check for pairs which satisfy z 0
there
are k models in S, this calculation of products results in an algorithm with
A slight modification of the proposed algorithm is to simulate, on all
models in S p , the strings which result from using
for the plant. Using this technique, any model which cannot successfully
simulate the activity of the plant can be eliminated from consideration and
need not be considered in any future pairing.
This modified approach also has worst case complexity of O(k 2 jQj 2 )
since there is no guarantee that more than one model will be eliminated
on each iteration. Also the actual complexity to accomplish the simulation
results in an additional O(kjQj 2 ) term in the operation count. These counts
are a result of the following reasoning. Each calculation
adds
a to the count. There are at most k 2 pairs which have to be
calculated, hence, the O(k 2 jQ 2 j) term in the count. To simulate any test
string on all remaining potential models, O(kjQ 2 j) operations are necessary,
hence, this term is added to the count retaining an overall complexity of
To demonstrate the correctness of the algorithm, several points must
be addressed: insuring that only bad models are removed from S i , that the
order of choosing models for the test disting(M does not affect the
output, and that there is no other technique which might produce a smaller
set of potential models.
4.2.1 Only Bad Models Removed
The first point is easily addressed. A model is removed if it is inconsistent
with the plant. An inconsistency arises from either the plant executing a
transition which is not in the model, such as an uncontrolled transition,
or the plant not executing a transition which is defined in the model, such
as from a state at which a single controlled or uncontrolled transition is
defined in the model but is not executed by the plant. Hence, only "bad"
models are removed from the set used to keep potentially correct models.
Note that a consistent model will not be removed from this set.
4.2.2 Order Does Not Affect the Result
The second point is more subtle. A priori it appears that the order of
testing models might be significant. I.e. there might be some incorrect
model A which, when combined with another incorrect model B, generates
a test string which provides that model B is removed, but that when model
B is combined with the correct model a test string cannot be generated.
That the order does not matter follows from the following proposition.
Proposition 4.3 states that if a pair of models, M i and M j , satisfy z 0 2
is removed from the set of possibly correct models,
then the correct model M c and M i satisfy z 0
model M j can be used to remove M i , then model M c can be used instead.
In the statements of the following propositions, the language generated
by model M i which is usually denoted by L(M i ) is denoted by L i . In the
proof of Proposition 4.3, a language L is used to link the fact that the
initial state is in the region of attraction of each of the product machines.
The conditions on L are very similar to the conditions for a distinguishing
language for M i and M j ; however, the fact that neither M i nor M j might
be the correct model requires that slightly different characteristics describe
how M j can be used with M i to generate a supervisor which will cause M i
to be removed from the set of possibly correct models. In the following, M c
denotes the correct model. z 0;i;j is the initial state of M i kM j . z 0;i;c is the
initial state of M i kM c . G i;j is the set of controllably distinguishing states
for M i kM j . G i;c is the set of controllably distinguishing states for M i kM c .
Proposition 4.3 If z 0;i;j
is removed from the set
of possible machines, then z 0;i;c
Proof:
Consider the language L marked by the supervisor generated
and used to remove M i . By the assumptions in the proposition statement,
this language generates tests which are used to remove M i from the set of
potentially correct models.
We first describe some characteristics which this language satisfies.
Lemma 4.4
(a) L controllable with respect to L
(b)
(c) ppr(L) '
(d) L is finite and non-empty.
Proof:
The controllability of L with respect to L i "L j follows from the construction
and the fact
That L is controllable
with respect to L follows from the fact that all prefixes of the
closed loop behavior are necessarily constrained to L c .
The strings which occur in the distinguishing language generated by
consist of the following types:
(1) strings which occur in the plant, M i , and M j , i.e.
(2) strings which occur in the plant and M j but not in M i , i.e. L c "L j "L c
(3) strings which occur in M i and M j but not in the plant, i.e. L c
and
(4) strings which occur in the plant but not in M i and M j , i.e.
For this supervisor to cause M i to be removed from the set of possibly
correct machines, the strings which occur in all three must be in the prefix
of strings which will cause M i to be removed. Hence, ppr(L) '
For this supervisor to cause M i to be removed from the set of possibly
correct machines in a controllable fashion, we claim that only the strings
in (2), (3), and (4) above can occur as strings in the language. (See shaded
areas in Figure 3.) No other string can occur and still allow M i to be
removed from the set of possibly correct machines. Any other string would
not allow M i to be removed.
From this observation we have that:
which gives part b).
The finiteness of L is a result of the fact
That L is non-empty is a result of the fact that M i is removed, i.e. at least
one event must be used to determine that M i is not correct.
End proof of Lemma 4.4.
We now use this language to demonstrate that z 0;i;c
We demonstrate this fact by verifying that L satisfies the requirements of
Proposition 4.2 for M c and M i .
c

Figure

3: Parts of languages which allow removal of M i .
1. L finite and non-empty:
L is finite and non-empty by hypothesis.
2. L controllable w.r.t. L c "
From the definition of L, we have that (t 2 L)
(toe
toe
controllable w.r.t.
3.
4. ppr(L) ' L c "
Since L satisfies the requirements for Proposition 4.2 with respect to
immediately have that z 0;i;c
End proof of Proposition 4.3.
Proposition 4.3 provides that the order does not matter when choosing
which pair of models to use to generate the next test. When combined
with the first point, that only "bad" models are removed, we have that it
is sufficient to test bad models with the correct model, which will never be
removed from the set of potentially correct models.
4.2.3 Optimal Complexity of Algorithm
Now we address the question of whether some other procedure might be
used to generate a smaller set of potentially correct models.
Proposition 4.4
Algorithm 4.1 provides a minimal set of potentially correct models.
(Minimal in the sense that there does not exist another technique to
controllably remove more models than are removed by Algorithm 4.1
from the set of potentially correct models in a finite number of transitions
.)
Proof:
Let S be the set of potentially correct models output by Algorithm 4.1.
If then we are done, i.e. g.
If jSj ? 1, then we know that since the test disting(M
satisfied for any pair of models in S and consequently
In particular, we know that
z o;i;c
Assume that there is some other technique which controllably removes
c from S. To remove M i , a test must cause M i to reach a state
at which an inconsistency with the plant arises. This state in M i is a
component to a state in G i;c , otherwise by controllability constraints M i
cannot be removed by this test. By (1), we know that we can construct a
behavior for M i which never enters G. Hence, we have a contradiction and
there cannot be any technique which can controllably generate a smaller
set of potentially correct models.
End proof of Proposition 4.4.
4.2.4 Resolving Uncertainty Without Reset
To resolve uncertainty without a reset capability, a slight modification must
be made to the algorithms given previously. The modification consists of
updating the models still under consideration to reflect any actions which
the actual plant has taken. This update is manifested by modifying the
model descriptions so that the initial state has a dependence on events
which have already occurred.
Hence, the old model is modified to
s is the string which has been executed to this
point. Note that only the initial state needs to have this dependence. The
other components of the model do not need to be modified.
Note that for this modification, all models must be updated to determine
if the new initial state after a test string has been executed is in the region
of attraction for the set of distinguishing states. However, the actual region
of attraction does not need to be recalculated because the states which can
be attracted to the distinguishing states do not change with each test string,
only the initial state changes.
The need to simulate the test strings does not increase the complexity
of the algorithm. In the worst case, this algorithm could require that O(k 2 )
regions of weak attraction be calculated to find enough test strings. Hence,
this algorithm also has O(k 2 jQj 2 ) complexity.
5 Examples
5.1 Optimality for Single Transition Uncertainty
This example demonstrates that resolving a single uncertainty has complexity
at least as great as that of creating the product machine for the two
potentially correct models. This complexity arises from the fact that the
product machine is used to generate the set of controllably distinguishing
states and hence the minimally distinguishing language. For this example,
z is the event for the uncertain arcs and A dg. Figure 4 illustrates
the two possible transition functions for the machine.
a
d
c
a
d
c
a
d
d
c
a
a
c
z
z
Figure

4: Set of models for which product method is optimal.
Following the procedure specified in Proposition 4.2, we create the product
machine (Figure 5) and calculate the states G which can be used to
distinguish q 11 and q 21 and the region of weak attraction for G.
From the graph representation of the transition function for the product
machine, we can determine that
From

Figure

5, we observe that the only state in the current G which can
have q 0;0 in the region of weak attraction is q 1m;2n ; hence, we will limit our
calculations for a new set G g. Some of the iterations of the
algorithm to calculate the region of weak attraction are given:
Hence, by Proposition 4.2, since z 0
the two states q 11 ; q 21 are
controllably distinguishable, and the uncertain arc can be resolved. Observe
that q 1m;2n 2 G 0 and that there is a string z(c n ad n a) m which can occur
uncontrollably before reaching q 1m;2n ; hence, to resolve the uncertainty,
every state which can be reached in the product machine from the initial
state might be visited. This fact demonstrates that resolving this uncertain
transition requires O(mn) operations.
To resolve the uncertainty, construct a supervisor with finite state machine
representation as shown in Figure 5 and run the unknown plant and
supervisor as a closed loop system. (See [13] for more detail on this proce-
dure.) A distinguishing language for this example is
5.2 Finiteness of Languages in Proposition 4.2
This example demonstrates the requirement for finiteness in Proposition 4.2.
1m,22 . q
1m,2n
. 0,1m
0,22
a
a
a
c
d
c
c
d
c
c
d
c
a
a
a
z

Figure

5: Product machine for system for which product method is optimal.
be the languages for two possible
models where a 2 A and u; v 2 A u . See Figure 6 for the machine
representation for these languages.
Ma
a
a
z zM || M
Figure

System to Demonstrate Requirement for Finiteness
For this example, if then L is controllable with respect
to required for a language
which can be used to distinguish L 1 and L 2 as described in Proposition 4.2;
however, the initial state of the product machine is not in the region of weak
attraction of the set of controllable distinguishing states, which is empty in
this example.
6 Conclusions
In this paper we have presented a model of uncertainty related to the transitions
of systems modeled with finite state machines. We developed a test
for determining whether or not such uncertainty can be controllably re-
solved. The test using a region of weak attraction calculation also provides
an algorithm for constructing a supervisor which can resolve the uncer-
tainties. An example demonstrating the optimality of the deterministic
approach for a single uncertainty is provided. Also an example is given
which demonstrates how the controllability and finiteness requirements are
both necessary for Proposition 4.2. This approach to choosing the correct
model can be applied in any situation which has a set of models from which
the correct one should be chosen.
Several possibilities exist for extensions to this work. One possibility
is to expand the model used to describe a discrete event system to one
which can describe a broader category of systems, such as a Petri net [8] or
algebraic [10] models. Another direction of current interest is the influence
which different uncertainty models have on the control and stabilization
of systems modeled with discrete event system formalisms. This influence
incorporates the effect that limiting the behavior of a system to a desired
constraint language would have on correctly controlling the system and
resolving any uncertainty in the model. A further extension is to consider
how the addition of unobserved events affects the problem described in this
work.

Acknowledgements

The authors would like to thank Ratnesh Kumar, Steve Marcus, Alex Tom-
linson, and other reviewers for critically reading and assisting in the preparation
of this paper.



--R

The Design and Analysis of Computer Algorithms.
"Inductive Inference: Theory and Meth- ods"
"On Stabilization of Discrete Event Pro- cesses"
Graph Theory with Applications to Engineering and Computer Sciences.

"System
"Scanning the Issue"
"Synthesis of feedback control logic for a class of controlled Petri nets"
Introduction to Automata Theory
"Algebras of Discrete Event Models"
Language stability and stabilizability of discrete event systems.
"Supervisory control of a class of discrete event processes"
"The control of discrete event systems"
"Diversity-Based Inference of Finite Automata"
"Inference of Finite Automata Using Homing Sequences"
"A Theory of the Learnable"
"Paradigms and Puzzles in the Theory of Dynamical Systems"
"Transition Uncertainty in Discrete Event Systems"
--TR

--CTR
Henrik Jacobsson, The Crystallizing Substochastic Sequential Machine Extractor: CrySSMEx, Neural Computation, v.18 n.9, p.2211-2255, September 2006
system identification;discrete event systems