Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2811886

Formats

Article sections

- Abstract
- 1. Introduction
- 2. Detectability Based on Dynamic Event Observation
- 3. Minimal Event Observation Policy
- 4. Conclusions
- References

Authors

Related links

Syst Control Lett. Author manuscript; available in PMC 2011 January 1.

Published in final edited form as:

Syst Control Lett. 2010 January 1; 59(1): 9–17.

doi: 10.1016/j.sysconle.2009.11.001PMCID: PMC2811886

NIHMSID: NIHMS159204

Our previous work considers detectability of discrete event systems which is to determine the current state and subsequent states of a system based on event observation. We assume that event observation is static, that is, if an event is observable, then all its occurrences are observable. However, in practical systems such as sensor networks, event observation often needs to be dynamic, that is, the occurrences of same events may or may not be observable, depending on the state of the system. In this paper, we generalize static event observation into dynamic event observation and consider the detectability problem under dynamic event observation. We define four types of detectabilities. To check detectabilities, we construct the observer with exponential complexity. To reduce computational complexity, we can also construct a detector with polynomial complexity to check strong detectabilities. Dynamic event observation can be implemented in two possible ways: a passive observation and an active observation. For the active observation, we discuss how to find minimal event observation policies that preserve four types of detectabilities respectively.

Discrete event systems [1, 2, 3, 4, 5, 6] are often used to model complex man-made systems. Based on discrete event system framework, some important problems on complex systems, such as supervisory control and fault diagnosis, can be effectively addressed. Obtaining successful solutions of these problems often needs sufficient knowledge on system's behavior. There are two possible ways to study system s' behavior. One is to consider event sequences and inv estigate the properties such as observability [4, 5] and co-observability [6]. The other way is to consider state space and state trajectories. In [7, 8], we consider the problem of state estimation by investigating the property of detectability. For different applications, [7, 8] introduce four types of detectabilities.

In most prior works [4, 5, 6, 7, 8], event observation mapping is static: if an event is observable, then it can be observed whenever it occurs. However this may not be the best approach because in many practical systems, the occurrences of events are detected by sensors and then the information is transmitted to supervisors or other agents by communication channels. For such practical systems, static event observation means the corresponding sensors will always be active and all the data will be transmitted to supervisors or agents by the communication channels.

Take sensor networks for example, these systems often have a large number of sensor nodes. The available energy of the battery which provides power to these sensor nodes is limited, and the bandwidth of the communication channels between these sensor nodes and supervisors/agents is also limited. Therefore, we need to save the energy of battery and to utilize the communication channels effectively. Hence the sensors should not be always activated and/or data should not always be transmitted by the communication channels. That means even though an event is observable in principle, only some occurrences of the event may be observable to supervisors or agents. In such cases, event observation becomes dynamic. Hence investigating detectability of discrete event systems with dynamic event observation is important.

Furthermore, supervisors and agents often have the ability to decide when to activate the sensors and when to transmit the occurrences of events. In order to reduce the use of energy of the battery of the sensors and/or to maximize the efficiency of the communication channels, we want the duration in which the sensors are active to b e as short as possible and the information received by the supervisors to be as little as possible without violating detectabilities. This problem can be formulated as minimizing the event observation while preserving detectabilities.

In this paper, we first extend detectabilities from static event observation to dynamic event observation. Since event observation is now state-dependent, we need to consider both events and states. This makes the observation mapping more difficult to handle. We define detectability, strong detectability, periodic detectability and strong periodic detectability using the new dynamic observation mapping. We derive necessary and sufficient conditions for these four detectabilities based on observers. We also derive necessary and sufficient conditions for strong detectability and strong periodic detectability based on detectors. The advantage of using detectors is that while the complexity of constructing an observer is exponential, the complexity of constructing a detector is polynomial.

In the second part of the paper, we investigate the problem of minimizing event observation while preserving detectabilities. We consider various observation policies preserving detectabilities and would like to find a minimal policy that observes event occurrences as little as possible. The results allow us to provide sufficient state information for different purposes such as feedback control and diagnosis with a minimal cost.

The problem of minimization of event observation has been studied using discrete event system framework recently. Initial work on minimization of event observation is to minimize the set of events to be observed by the supervisors or agents [9, 10, 11, 12]. In its general form, this problem is known to be NP-complete [12]. Sequentially, minimization of dynamic event observation is investigated [13, 14, 15, 16, 17, 18, 19, 20, 21]. In [13, 14, 15], the problem of minimization of dynamic event observation to preserve diagnosability is considered. [16, 17, 18, 19, 20] consider how to minimize the communication of event occurrences among multi-agents for supervisory control. More recently, [21] discusses the sensor activation problem of finding a minimal sensor activation policy while preserving observability. [21] is mostly related to the second part of this paper. The main differences between [21] and this paper are as follows. (1) [21] deals with observability while this paper deals with detectability. (2) We assume that the initial state is uncertain.

The paper is organized as follows. Section 2 considers the detectability of discrete event systems with dynamic event observation. Definitions of detectabilities are given and necessary and sufficient conditions are derived. In Section 3, we investigate how to minimize event observation while preserving detectabilities. Algorithms are given to compute minimal event observation policies.

In this section, we investigate detectability of discrete event systems with dynamic event observation. As usual [1, 2, 3], a discrete event system is modeled by a deterministic automaton as follows:

$$G=(Q,\Sigma ,f,{q}_{0}).$$

where *Q* is the set of discrete states; Σ is the set of discrete event s; *f*: *Q* × Σ → *Q* is the transition function; *q*_{0} *Q* is the initial state of the system. The transition function describes the dynamics of the discrete event system. The transition function is extended to *f*: *Q* × Σ* → *Q* in the usual way. We use *f* (*q*, *s*)! to mean that *f* (*q*, *s*) is defined.

For different state estimation problems, we assume different knowledge on the initial state. We use *Q*_{0} ( *Q*) to denote the set of possible initial states. So the automaton used for state estimation can be re-written as:

$$G=(Q,\Sigma ,f,{Q}_{0}).$$

The language generated by *G* is defined as

$$L\left(G\right)=\{s{\Sigma}^{}$$

Static event observation is given by the natural projection *P*: Σ → Σ_{o}, where Σ_{o} is the set of observable events. Dynamic event observation means observable events may be observed for some time periods, but not for all time periods. We assume that dynamic event observation is state-dependent and we use the following mapping to describe this dependency:

$$\Phi :Q\to {2}^{{\Sigma}_{o}}.$$

Given a state *q*, Φ(*q*) is the set of events which can be observed when the system is in state *q*. Since the observation of events is state-dependent, the event observation can be described by observable transitions. In other words, all the transitions are divided into two disjoint sets: observable transition set and unobservable transition set.

As in [7, 8], we make the following two assumptions without loss of generality.

*G* is deadlock free, that is, for any state of the system, at least one event is defined at that state: (∀*q* *Q*)(σ Σ)*f*(*q*, σ)!.

No loops in *G* contain only unobservable events.

Compared with static event observation, dynamic event observation makes it more difficult to determine the current state of the system. To illustrate this difficulty intuitively, let us consider the following example.

Consider the discrete event system in Figure 1. We assume *Q*_{0} = {*q*_{1}} and the observable event set is Σ_{o} = Σ = {α, β}. Under static observation, we can determine the current state for any event sequence.

Now we assume that the events are dynamically observable and the dynamic event observation mapping is defined as: Φ(*q*_{1}) = {α}, Φ(*q*_{2}) = {α, β}, Φ(*q*_{3}) = {α, β}.

Initially, the system is in state *q*_{1}. Since the transition (*q*_{1}, β, *q*_{3}) is not observable, we cannot observe the occurrence of this transition when it occurs. So the system may go to *q*_{3} before we observe any event occurred. That means we cannot determine the initial state of the system.

However, the transition (*q*_{3}, β, *q*_{2}) is observable. That means if the system moves from state *q*_{3} to state *q*_{2}, we can observe the occurrence of transition (*q*_{3}, β, *q*_{2}) and know the system is now in state *q*_{2}. Though the two transitions (*q*_{1}, β, *q*_{3}) and (*q*_{3}, β, *q*_{2}) have the same event, one is observable and the other is unobservable. It makes it more difficult to check the detectability of the system.

Since the observation of events is dynamic and the initial state is uncertain (the initial state can be any one of the states in *Q*_{0}), for an event sequence *s*, the observed event sequence may not be unique. However, for a transition path ${q}_{i}\stackrel{{\sigma}_{1}}{\to}\stackrel{{\sigma}_{n}}{\to}{q}_{i+n}$, the observed event sequence is unique because the observability of any transition is certain. So we can define the information mapping

$$\theta :Q\times {\Sigma}^{}$$

in such a way that θ(*q*, *s*) is the observation when the system starts at *q* and *s* has occurred. θ(*q*, *s*) is defined recursively as follows (ε denotes the empty string)

$$\theta (q,\sigma )=\{\begin{array}{cc}\sigma \hfill & if\sigma \Phi \left(q\right)\hfill & \epsilon \hfill & if\sigma \Phi \left(q\right)\hfill \\ \phantom{\}}\end{array}$$

(1)

$$\theta (q,s\sigma )=\{\begin{array}{cc}\theta (q,s)\sigma \hfill & if\sigma \Phi \left(f(q,s)\right)\hfill & \theta (q,s)\epsilon \hfill & if\sigma \Phi \left(f(q,s)\right)\hfill \\ \phantom{\}}\end{array}$$

(2)

Based on the information mapping θ, we can define the observed language of a discrete event system *G* as:

$${L}_{o}\left(G\right)=\{s{\Sigma}_{o}^{}$$

Suppose that a discrete event system *G* is in a set of possible states *Q*′( *Q*), then the set of all possible states after observing *t* Σ* is denoted by

$$R(Q\prime ,t)=\{f(q\prime ,s):(q\prime Q\prime )(s{\Sigma}^{}\theta (q\prime ,s)=t\wedge f(q\prime ,s)!\}$$

In particular, the unobservable reach is defined as:

$$UR(Q\prime )=R(Q\prime ,\epsilon )$$

Detectability concerns with the state estimation after sufficient long sequences of observations. Therefore, let us denote the length of a string *s* by |*s*|, and the set of positive integers by *N*. If *x* is a set, then |*x*| denotes the number of elements in the set. We also denote the set of prefixes of *s* by Pr(*s*).

Since the initial state may be unknown and the information mapping depends on states, we need to describe a possible trajectory of the system by an infinite transition path:

$${q}_{0}\stackrel{{\sigma}_{1}}{\to}{q}_{1}\stackrel{{\sigma}_{2}}{\to}\stackrel{{\sigma}_{n}}{\to}{q}_{n}\stackrel{{\sigma}_{n+1}}{\to}.$$

where, *q*_{0} *Q*_{0}, and *s* = σ_{1}σ_{2}…σ_{n}σ_{n+1}… Σ^{ω} is an infinite sequence of events belonging to ω –language Σ^{ω}. We denote this infinite transition path by (*q*_{0}, *s*) *Q*_{0} × Σ^{ω}.

From Assumptions 1 and 2 in Section 2.1, we know that for an infinite transition path, the length of the observable event sequence is also infinite.

With these definitions and notations, we can now extend the definitions of various detectabilities of discrete event system to the case of dynamic event observation.

A discrete event system *G* is detectable with respect to Φ if we can determine, after a finite number of observations, the current state and subsequent states of the system for some trajectories of the system. That is,

$$(nN)((q,s){Q}_{0}\times {\Sigma}^{\omega})(\forall t\mathrm{Pr}\left(\theta (q,s)\right))tnR({Q}_{0},t)=1$$

A discrete event system *G* is strongly detectable with respect to Φ if we can determine, after a finite number of observations, the current state and subsequent states of the system for all trajectories of the system. That is,

$$(nN)(\forall (q,s){Q}_{0}\times {\Sigma}^{\omega})(\forall t\mathrm{Pr}\left(\theta (q,s)\right))tnR({Q}_{0},t)=1$$

A discrete event system *G* is periodically detectable with respect to Φ if we can periodically determine the current state of the system for some trajectories of the system. That is,

$$(nN)((q,s){Q}_{0}\times {\Sigma}^{\omega})(\forall t\mathrm{Pr}\left(\theta (q,s)\right))(t\prime {\Sigma}^{}tt\prime \mathrm{Pr}\left(\theta (q,s)\right)\wedge t\prime n\wedge R({Q}_{0},tt\prime )=1$$

A discrete event system *G* is strongly periodically detectable with respect to Φ if we can periodically determine the current state of the system for all trajectories of the system. That is,

$$(nN)(\forall (q,s){Q}_{0}\times {\Sigma}^{\omega})(\forall t\mathrm{Pr}\left(\theta (q,s)\right))(t\prime {\Sigma}^{}tt\prime \mathrm{Pr}\left(\theta (q,s)\right)\wedge t\prime n\wedge R({Q}_{0},tt\prime )=1$$

To find necessary and sufficient conditions for checking the four types of detectabilities under dynamic event observation, we first investigate the properties of observer. As in the case of static event observation, we can construct an observer, denoted by *G*_{obs}, from *G* as follows.

$${G}_{obs}=(X,\Sigma ,\delta ,{x}_{0})={A}_{c}({2}^{Q},\Sigma ,\delta ,UR\left({Q}_{0}\right))$$

where *Ac*(.) denotes the accessible part and δ(*x*,σ) = *UR* ({*f*(*q*,σ): (*q* *x*)*f*(*q*,σ)!∧σ Φ(*q*)}). Clearly, δ(*x*,σ) is defined if and only if {*f*(*q*,σ): (*q* *x*)*f*(*q*,σ)!∧σ Φ(*q*)} ≠ ϕ, which is denoted by δ(*x*,σ)!.

The observer *G*_{obs} characterizes the observed language of the discrete event system *G* as shown below.

*L*(_{o}*G*) =*L*(*G*)_{obs}- (∀
*s**L*(_{o}*G*))δ(*x*_{0},*s*) =*R*(*Q*_{0},*s*)

Proof:

Let us first prove

$$s{L}_{o}\left(G\right)sL\left({G}_{obs}\right)$$

by induction on the length | *s* | of string s Σ*.

Base: For | *s* |= 0, that is, *s* = ε, clearly both ε *L _{o}*(

$$\epsilon {L}_{o}\left(G\right)\epsilon L\left({G}_{obs}\right).$$

Induction Hypothesis: Suppose that for any *s* Σ* such that | *s* |≤ *n*,

$$s{L}_{o}\left(G\right)sL\left({G}_{obs}\right).$$

Induction Step: We need to prove that any *s*σ Σ* such that | *s*σ |= *n* + 1,

$$s\sigma {L}_{o}\left(G\right)s\sigma L\left({G}_{obs}\right).$$

Indeed,

$$\begin{array}{cc}\hfill & s\sigma {L}_{o}\left(G\right)\hfill & \hfill s{L}_{o}\left(G\right)\wedge s\sigma {L}_{o}\left(G\right)\hfill sL\left({G}_{obs}\right)\wedge s\sigma {L}_{o}\left(G\right)\text{by Induction Hypothesis}\hfill \delta ({x}_{0},s)!\wedge (q{Q}_{0})(t\sigma {\Sigma}^{}f(q,t\sigma )!\wedge \theta (q,t\sigma )=s\sigma \hfill \delta ({x}_{0},s)!\wedge (q{Q}_{0})(t\sigma {\Sigma}^{}f(q,t)!\wedge \theta (q,t)=s\wedge f(q,t\sigma )!\wedge \theta (q,t\sigma )=s\sigma \hfill \delta ({x}_{0},s)!\wedge (q{Q}_{0})(t\sigma {\Sigma}^{}\theta (q,t)=s\wedge f(q,t)\delta ({x}_{0},s)\wedge f(q,t\sigma )!\wedge \theta (q,t\sigma )=s\sigma \hfill \delta ({x}_{0},s)!\wedge (q{Q}_{0})(t\sigma {\Sigma}^{}\theta (q,t)=s\wedge q\prime =f(q,\sigma )\delta ({x}_{0},s)\wedge f(q\prime ,\sigma )!\wedge \sigma \Phi (q\prime )\hfill \delta ({x}_{0},s)!\wedge (q{Q}_{0})(t\sigma {\Sigma}^{}\theta (q,t)=s\wedge \{f(q\prime ,\sigma ):(q\prime \delta ({x}_{0},s))f(q\prime ,\sigma )!\wedge \sigma \Phi (q\prime )\}\ne \varphi \hfill \delta ({x}_{0},s)!\wedge (q{Q}_{0})(t\sigma {\Sigma}^{}\theta (q,t\sigma )=s\wedge \delta ({x}_{0},s\sigma )!\hfill \delta ({x}_{0},s\sigma )!\hfill & \hfill s\sigma L\left({G}_{obs}\right)\hfill \hfill \hfill \hfill \hfill \hfill \hfill \hfill \hfill \end{array}$$

This proves the first part of the theorem.

Now, let us prove the second part of the theorem, that is, for all *s* *L _{o}* (

$$\delta ({x}_{0},s)=R({Q}_{0},s)$$

by induction on the length | *s* | of string *s* *L _{o}* (

Base: For | *s* |= 0, that is, *s* = ε, we have, by definition

$$\delta ({x}_{0},\epsilon )={x}_{0}=UR\left({Q}_{0}\right)=R({Q}_{0},\epsilon ).$$

Induction Hypothesis: Suppose that for any *s* *L _{o}* (

$$\delta ({x}_{0},s)=R({Q}_{0},s).$$

Induction Step: We need to prove that any *s*σ *L _{o}* (

$$\delta ({x}_{0},s\sigma )=R({Q}_{0},s\sigma ).$$

Indeed,

$$\begin{array}{cc}\hfill & \delta ({x}_{0},s\sigma )\hfill \\ \hfill =& \delta (\delta ({x}_{0},s),\sigma )\hfill \\ \hfill =& \delta (R({Q}_{0},s),\sigma )\text{by Induction Hypotheis}\hfill \\ \hfill =& UR(\{f(q,\sigma ):(qR({Q}_{0},s))f(q,\sigma )!\wedge \sigma \Phi \left(q\right)\})\hfill =& R(\{f(q,\sigma ):(qR({Q}_{0},s))f(q,\sigma )!\wedge \sigma \Phi \left(q\right)\},\epsilon )\hfill =& R({Q}_{0},s\sigma )\hfill \hfill \hfill \end{array}$$

This proves the second part of the theorem.

To check detectabilities, we first mark the states in *G _{obs}* that contain singleton state and denote the set by:

$${X}_{m}=\{xX:x=1\}.$$

Clearly, if the observer *G _{obs}* is in any state belonging to

States involved in loops are of particular interest in determining detectabilities because *G _{obs}* can stay in these states forever. Therefore, let us denote the states involved in loops by

$${X}_{l}=\{x:(s{\Sigma}^{}s\ge 1\wedge \delta (x,s)=x\}$$

Also, the set of states reachable from some states in *X _{l}* is denoted by

$${X}_{c}=\{x:(x\prime {X}_{l})(s{\Sigma}^{}x=\delta (x\prime ,s)\}.$$

Note that *X _{l}*

A discrete event system *G* is detectable with respect to Φ if and only if there is at least one loop in *G _{obs}* which are entirely within

A discrete event system *G* is strongly detectable with respect to Φ if and only if in its observer *G _{obs}*, we have

A discrete event system *G* is periodically detectable with respect to Φ if and only if there exists at least one loop in *G _{obs}* which includes at least one state belonging to

A discrete event system *G* is strongly periodically detectable with respect to Φ if and only if there are no loops in *G _{obs}* which are entirely within

Checking detectabilities using Theorems 2–5 requires the construction of an observer. Since in the worst case, the cardinality of the state space of the observer is 2^{|Q|}, the computational complexity of constructing the observer is exponential. To reduce computational complexity, we can check strong detectability and strong periodical detectability with polynomial complexity by constructing a detector which is introduced in [8]:

$${G}_{\mathrm{det}}=(Y,\Sigma ,\xi ,{y}_{0})=Ac(Y\prime ,\Sigma ,\xi ,UR\left({Q}_{0}\right)).$$

The state space of the detector is

$$Y\prime =\{y:yQ\wedge y\le 2\}\left\{{y}_{0}\right\}.$$

The transition function ξ: *Y*′ × Σ_{o} → 2^{Y′} is defined as follows. For ξ (*y*,σ), first let

$$\mathit{Temp}=UR(\{f(q,\sigma ):(qx)f(q,\sigma )!\wedge \sigma \Phi \left(q\right)\})$$

Then according to the number of elements in *Temp*, we define

$$\xi (y,\sigma )=\{\begin{array}{cc}\left\{\mathit{Temp}\right\}\hfill & if\mathit{Temp}=1\{y\prime :y\prime \mathit{Temp}\wedge y\prime =2\}if\mathit{Temp}\ge 2\text{undefined}\hfill & if\mathit{Temp}=0.\hfill & \phantom{\}}\hfill \hfill \hfill \end{array}$$

As in the case of observer, we define:

$$\begin{array}{cc}\hfill {Y}_{m}=& \{yY:y=1\}\hfill {Y}_{l}=& \{y:(s{\Sigma}^{}s\ge 1\wedge y\xi (y,s)\}.\hfill {Y}_{c}=& \{y:(y\prime {Y}_{l})(s{\Sigma}^{}y\xi (y\prime ,s)\}\hfill \hfill \hfill \end{array}$$

Based on the detector, we can check strong detectability and strongly periodic detectability using the following two theorems, whose proofs are also om itted. Note that detectability and periodic detectability cannot be checked using detectors.

A discrete event system *G* is strongly detectable with respect to Φ if and only if in its detector *G*_{det}, we have: *Y*_{c} *Y*_{m}.

A discrete event system *G* is strongly periodically detectable with respect to Φ if and only if there are no loops in *G*_{det} which are entirely within *Y* − *Y*_{m}.

We continue Example 1. Let us construct the observer for the system in Example 1 as shown in Figure 2. We can see that the system is neither strongly detectable nor strongly periodically detectable. However, the system is detectable and periodically detectable.

We now construct the detector as shown in Figure 3.

We also can see that the system is neither strongly detectable nor strongly periodically detectable.

Dynamic event observation mapping Φ can be achieved or implemented in two possible ways: a passive way and an active way. In the passive way, the plant *G* reports to the supervisors or agents the occurrences of events according to Φ automatically without active involvement of the supervisors or agents. Therefore, from the view point of the supervisors or agents, the observation is passive. In the active way, the supervisors or agents activate sensors and control the communications between themselves and the sensors in order to observe the occurrences of events. Both passive observation and active observation are used in practice.

For passive observation, the observation problem is relatively simple from the viewpoint of a supervisor or agent: what it gets is what it has. On the other hand, the observation problem for active observation is more complex and interesting. We investigate this problem in this section. We assume that a set of sensors are available in the plant to detect the occurrences of observable events. For active observation, event observation mapping is achieved by an event observation policy Ω which is a mapping:

$$\Omega :Q\to {2}^{{\Sigma}_{o}}$$

Here Ω(*q*) is the set of events whose corresponding sensors are activated and the occurrences of events are transmitted to the agent at state *q*.

Event observation policies are the same as sensor activation policies discussed in [21] for observability. For two event observation policies Ω and Ω′, we say that Ω ≥ Ω′ if and only if (∀*q* *Q*) Ω(*q*) Ω′(*q*), and Ω > Ω′ if and only if Ω ≥ Ω′ (*q* *Q*)Ω(*q*) ⊃ Ω′(*q*). Similarly, we define Ω ≤ Ω′ and Ω < Ω ′. If Ω ≥ Ω′, we say the Ω is a super-policy of Ω′. If Ω ≤ Ω′, we say the Ω is a sub -policy of Ω′.

Given an event observation policy Ω, there is a corresponding information mapping, denoted by θ^{Ω} or θ if Ω is understood, as defined by Equations (1) and (2) (by taking Φ as Ω).

For any two transition paths, if they have the same observed event sequences, then they are indistinguishable. Obviously, we must make the same event observation decision after any two indistinguishable transition paths. This leads to the following definition:

An event observation policy Ω is feasible if

$$(\forall q,q\prime {Q}_{0})(\forall s,s\prime {\Sigma}^{}\theta (q,s)=\theta (q\prime ,s\prime )\Omega \left(f(q,s)\right)=\Omega \left(f(q\prime ,s\prime )\right)$$

(3)

Feasibility can be checked using observer as described in the following theorem.

An event observation policy Ω is feasible if and only if the corresponding observer *G _{obs}* = (

$$(\forall xX)(\forall q,q\prime x)\Omega \left(q\right)=\Omega (q\prime )$$

(4)

Proof:

We first prove the “If” part. Clearly

$$\begin{array}{cc}\hfill & (\forall xX)(\forall q,q\prime x)\Omega \left(q\right)=\Omega (q\prime )\hfill (\forall tL\left({G}_{obs}\right))(\forall q,q\prime \delta ({x}_{0},t))\Omega \left(q\right)=\Omega (q\prime )\hfill \hfill \end{array}$$

By Theorem 1, we have

$$(\forall t{L}_{o}\left(G\right))(\forall q,q\prime R({Q}_{0},t))\Omega \left(q\right)=\Omega (q\prime )$$

Hence, (∀ *q*, *q*′ *Q*_{0})(∀*s*, *s*′ Σ*) the following holds

$$\begin{array}{cc}\hfill & \theta (q,s)=\theta (q\prime ,s\prime )\hfill \\ \hfill f(q,s)R({Q}_{0},\theta (q,s))\wedge f(q\prime ,s\prime )R({Q}_{0},\theta (q,s))\hfill \Omega \left(f(q,s)\right)=\Omega \left(f(q\prime ,s\prime )\right)\hfill \hfill \end{array}$$

That is, Equation (3) is true and Ω is feasible.

Next, we prove the “Only if” part. Take any *t* *L _{o}*(

$$(s,s\prime L\left(G\right))({q}_{0},{q}_{0}^{\prime}{Q}_{0})f({q}_{0},s)=q\wedge f({q}_{0}^{\prime},s\prime )=q\prime \wedge \theta ({q}_{0},s)=\theta ({q}_{0}^{\prime},s\prime )=t$$

Assume Equation (3) is true, then

$$\theta ({q}_{0},s)=\theta ({q}_{0}^{\prime},s\prime )\Omega \left(f({q}_{0},s)\right)=\Omega \left(f({q}_{0}^{\prime},s\prime )\right)\Omega \left(q\right)=\Omega (q\prime )$$

Therefore,

$$(\forall t{L}_{o}\left(G\right))(\forall q,q\prime R({Q}_{0},t))\Omega \left(q\right)=\Omega (q\prime )$$

By Theorem 1,

$$(\forall t{L}_{o}\left(G\right))(\forall q,q\prime \delta ({x}_{0},t))\Omega \left(q\right)=\Omega (q\prime )$$

which implies

$$(\forall xX)(\forall q,q\prime x)\Omega \left(q\right)=\Omega (q\prime )$$

That is, Equation (4) is true.

In [21], it is shown that feasible sensor activation policies satisfy monotonicity. That is, activating more sensor leads to less confusion. The same is true for event observation policies. Moreover, let us define the union of event observation policies as follows. Ω = Ω_{1} Ω_{2} if and only if

$$(\forall qQ)\Omega \left(q\right)={\Omega}_{1}\left(q\right){\Omega}_{2}\left(q\right)$$

Then we have the following theorem.

If some finite event observation policies Ω_{1},Ω_{2},,Ω* _{n}* are all feasible, then ${i=1n}_{{\Omega}_{i}}^{}$ is also feasible.

Proof:

We first prove Ω = Ω_{1} Ω_{2} is feasible.

Denote the observers for Ω, Ω_{1}, and Ω_{2} by *G _{obs}* = (

$$\begin{array}{cc}\hfill & (\forall {x}^{1}{X}^{1})(\forall {q}_{i}^{1},{q}_{j}^{1}{x}^{1}){\Omega}_{1}\left({q}_{i}^{1}\right)={\Omega}_{1}\left({q}_{j}^{1}\right)\hfill & (\forall {x}^{2}{X}^{2})(\forall {q}_{h}^{2},{q}_{k}^{2}{x}^{2}){\Omega}_{2}\left({q}_{h}^{2}\right)={\Omega}_{2}\left({q}_{k}^{2}\right)\hfill \hfill \end{array}$$

We need to prove:

$$(\forall xX)(\forall q,q\prime x)\Omega \left(q\right)=\Omega (q\prime )$$

Because Ω_{1} ≤ Ω and Ω_{2} ≤ Ω, it is not difficult to show

- For the initial state, ${x}_{0}{x}_{0}^{1}\wedge {x}_{0}{x}_{0}^{2}$
- For any state
*x**X*, if (*x*_{1}*X*^{1},*x*_{2}*X*^{2})*x**x*_{1}∧*x**x*_{2}, then for any event σ satisfying (∀*q**x*)σ Ω_{1}(*q*) ∧ σ Ω_{2}(*q*), we have $({x}_{1}^{\prime}{X}^{1},{x}_{2}^{\prime}{X}^{2})\delta (x,\sigma ){x}_{1}^{\prime}\wedge \delta (x,\delta ){x}_{2}^{\prime}$.

By recursively applying the above facts, we have

$$(\forall xX)({x}^{1}{X}^{1},{x}^{2}{X}^{2})x{x}^{1}\wedge x{x}^{2}$$

Now (∀*x* *X*)(∀*q*,*q*′ *x*) the following is true

$$\begin{array}{cc}\hfill & ({x}^{1}{X}^{1},{x}^{2}{X}^{2})x{x}^{1}\wedge x{x}^{2}\hfill ({x}^{1}{X}^{1},{x}^{2}{X}^{2})q,q\prime {x}^{1}\wedge q,q\prime {x}^{2}\hfill ({x}^{1}{X}^{1},{x}^{2}{X}^{2}){\Omega}_{1}\left(q\right)={\Omega}_{1}(q\prime )\wedge {\Omega}_{2}\left(q\right)={\Omega}_{2}(q\prime )\hfill \Omega \left(q\right)=\Omega (q\prime )\hfill \hfill \hfill \hfill \end{array}$$

That is, Equation (3) is true and Ω = Ω_{1} Ω_{2} is feasible. Repeat this if necessary, we conclude that ${i=1n}_{{\Omega}_{i}}^{}$ is feasible.

Note that the minimal feasible event observation policy Ω_{min} is given by

$$(qQ){\Omega}_{\mathrm{min}}\left(q\right)=\varphi $$

and the maximal feasible event observation policy Ω_{max} is given by

$$(qQ){\Omega}_{\mathrm{max}}\left(q\right)={\Sigma}_{o}.$$

Our goal is to mini mize event observation while preserving detectabilities. This means to find a minimal feasible event observation policy under which the system is detectable (for different detectabilities respectively). Our approach is to start with the maximal feasible event observation policy Ω_{max} and try to remove event observations one by one until no further removal is possible. Since removing one event observation from a policy may make the resulting policy infeasible, we may have to remove more event observation to recover feasibility. Therefore, given an observation policy Ω, we would like to find the maximal feasible sub-policy of Ω. Let Ω_{1},Ω_{2},,Ω_{n} be all feasible sub-policy of Ω, then by Theorem 9, ${\Omega}^{\uparrow f}={i=1n}_{{\Omega}_{i}}^{}$ exists and is feasible. It has the property that (1) Ω^{↑f} ≤ Ω and (2) for all feasible Ω', Ω' ≤ Ω Ω' ≤ Ω^{↑f}. The following Algorithm calculates the maximal feasible sub-policy of a given event observation policy.

Input: a system *G* and an event observation policy Ω_{0};

Output: the maximal feasible sub-policy Ω^{↑f} of Ω_{0};

Step 1: Initially, set

$$\begin{array}{cc}\hfill & \Omega ={\Omega}_{0};\hfill \\ \hfill & P\leftarrow \{(q,q\prime ):q,q\prime {Q}_{0}\};\hfill \end{array}$$

Step 2: Recursively, based on the policy Ω, set

$$P\leftarrow P\{(q,q\prime )Q\times Q:(({q}_{i},{q}_{j})P)qUR\left({q}_{i}\right)\wedge q\prime UR\left({q}_{j}\right)\};$$

Step 3: Recursively, based on the policy Ω, set

$$P\leftarrow P\{(q,q\prime )Q\times Q:(({q}_{h},{q}_{k})P)(\sigma {\Sigma}_{o})\sigma \Omega \left({q}_{h}\right)\wedge \sigma \Omega \left({q}_{k}\right)\wedge qf({q}_{h},\sigma )\wedge q\prime f({q}_{k},\sigma )\}$$

Step 4: Iterate Steps 2 and 3 until no further changes to *P*;

Step 5: Recursively do

If (*q*, *q*′) *P*)(σ Σ_{o})σ Ω(*q*) ∧ σ Ω(*q*′), set

$$\Omega (q\prime )\leftarrow \Omega (q\prime )\sigma .$$

Step 6: Iterate Steps 2 to 5 until no further changes to Ω.

Step 7: Set

$${{\Omega}_{0}}^{\uparrow f}\leftarrow \Omega .$$

End.

Ω_{0}^{↑f} obtained by Algorithm 1 is the maximal feasible event observation sub-policy of the given event observation policy Ω_{0}.

Proof:

It is clear from Algorithm 1 that after the algorithm converges, the resulting Ω, which will be Ω_{0}^{↑f}, and the corresponding *P* will satisfy the following conditions.

$$\begin{array}{cc}\hfill & P=P\{(q,q\prime )Q\times Q:(({q}_{i},{q}_{j})P)qUR\left({q}_{i}\right)\wedge q\prime UR\left({q}_{j}\right)\}\hfill & P=P\{(q,q\prime )Q\times Q:(({q}_{h},{q}_{k})P)\sigma \Omega \left({q}_{h}\right)\wedge \sigma \Omega \left({q}_{k}\right)\wedge qf({q}_{h},\sigma )\wedge q\prime f({q}_{k},\sigma )\}\hfill \hfill \end{array}$$

(5)

$$(\forall (q,q\prime )P)(\forall \sigma {\Sigma}_{o})\sigma \Omega \left(q\right)\sigma \Omega (q\prime )$$

(6)

Equation (5) is true because otherwise Steps 2 and 3 will not converge. Equation (6) is true because otherwise Step 5 will not converge. From Equations (5) and (6), it is not difficult to see that, (∀ *q*, *q*′ *Q*_{0})(∀ *s*, *s*′ Σ*), we have

$$\begin{array}{cc}\hfill & \theta (q,s)=\theta (q\prime ,s\prime )\hfill \\ \hfill (f(q,s),f(q\prime ,s\prime ))P\hfill & \hfill (\forall \sigma {\Sigma}_{o})\sigma \Omega \left(f(q,s)\right)\sigma \Omega \left(f(q\prime ,s\prime )\right)\hfill \Omega \left(f(q,s)\right)=\Omega \left(f(q\prime ,s\prime )\right)\hfill \hfill \end{array}$$

That is, Equation (3) is true and Ω = Ω_{0}^{↑f} is feasible. Ω = Ω_{0}^{↑f} is the maximal sub-policy because Algorithm 1 starts with Ω = Ω_{0} and *P* = {(*q*, *q*′): *q*, *q*′ *Q*_{0}} and remove transitions from Ω only when it is necessary.

Let us now illustrate the use of Algorithm 1 by the following example.

Consider the discrete event system shown in Fig. 4.

We assume that the initial state set is *Q*_{0} = {*q*_{1}}. Consider the following event observation policy Ω: Ω(*q*_{1}) = {β, μ}, Ω(*q*_{2}) = {α, β, μ}, Ω(*q*_{3}) = {α, β, μ}. Let us see how to find the maximal feasible policy Ω^{↑f} using Algorithm 1. In Step 1, we have:

$$P=\left\{({q}_{1},{q}_{1})\right\}$$

Because transition (*q*_{1}, α, *q*_{2}) is unobservable, then in Step 2, the set *P* is changed into:

$$P=\{({q}_{1},{q}_{1}),({q}_{2},{q}_{2}),({q}_{1},{q}_{2})\}$$

In Step 3, the set *P* is changed into:

$$P=\{({q}_{1},{q}_{1}),({q}_{2},{q}_{2}),({q}_{1},{q}_{2}),({q}_{3},{q}_{3})\}$$

In Step 4, we get the set *P* as:

$$P=\{({q}_{1},{q}_{1}),({q}_{2},{q}_{2}),({q}_{1},{q}_{2}),({q}_{3},{q}_{3})\}$$

From the set *P*, we can see that state *q*_{1} and *q*_{2} are indistinguishable. So they should have the same observable event set. In Step 5, we change the event observation set for state *q*_{2} as:

$$\Omega \left({q}_{2}\right)\leftarrow \{\alpha ,\beta ,\mu \}\alpha $$

Then the new policy is:

$$\Omega \left({q}_{1}\right)=\{\beta ,\mu \},\Omega \left({q}_{2}\right)=\{\beta ,\mu \},\Omega \left({q}_{3}\right)=\{\alpha ,\beta ,\mu \}.$$

Repeat the process, we find that the new policy is feasible. So the above is the maximal feasible sub-policy Ω^{↑f}.

[21] considers the feasible event observation policy (called sensor activation policy) for control purpose. In [21], the initial state of the system is known, however, in our case of state estimation of discrete event systems, the initial state of the system is not known, what we know is a subset of states that the system may stay initially. So the above results on feasible event observation policy generalized the corresponding results of the paper [21]. Such generalization is necessary for investigating detectability of discrete event systems and cannot be obtained directly from [21].

To find a minimal feasible event observation policy under which the system is detectable, let us first define validity as follows.

A feasible event observation policy Ω is valid with respect to detectability, strong detectability, periodic detectability, and strong periodic detectability, respectively, if discrete event system *G* is detectable, strongly detectable, periodically detectable, and strongly periodically detectable, respectively, with respect to the feasible event observation policy Ω.

Unless otherwise stated, when we say a policy is valid, we mean it is valid with respect to a given detectability, which can be any of four detectabilities. The following theorem says that the union of two valid policies is also valid.

If some finite event observation policies Ω_{1}, Ω_{2}, , Ω_{n} are all valid with respect to a given detectability, then ${i=1n}_{{\Omega}_{i}}^{}$ is also valid with respect to the given detectability.

Proof:

Obviously Ω = Ω_{1} Ω_{2} is feasible by Theorem 9. We define the information mappings θ, θ_{1} and θ_{2} for Ω, Ω_{1} and Ω_{2} respectively. We construct the corresponding observers *G _{obs}*. ${G}_{\mathit{obs}}^{1}$ and ${G}_{\mathit{obs}}^{2}$ for Ω, Ω

By monotonicity, we have

$$\begin{array}{cc}\hfill & (\forall q{Q}_{0})(\forall s{\Sigma}^{}\delta ({x}_{0},\theta (q,s)){\delta}_{1}({x}_{0},{\theta}_{1}(q,s))\hfill & (\forall q{Q}_{0})(\forall s{\Sigma}^{}\delta ({x}_{0},\theta (q,s)){\delta}_{2}({x}_{0},{\theta}_{2}(q,s))\hfill \hfill \end{array}$$

This means that for any transition path, we have a smaller uncertainty about the system state with policy Ω = Ω_{1} Ω_{2} than with either Ω_{1} or Ω_{2}. If a transition path occurs and we know the current state with policy Ω_{1} or Ω_{2}, then we surely know the current state with the policy Ω = Ω_{1} Ω_{2}. Hence if Ω_{1} and Ω_{2} are both valid, then Ω = Ω_{1} Ω_{2} is also valid.

Repeating this argument if necessary, we conclude that ${i=1n}_{{\Omega}_{i}}^{}$

Let us now discuss the algorithm to find a minimal valid event observation policy with respect to a given detectability, which can be any of four detectabilities. Obviously, for a solution to exist, we must assume that the maximal feasible event observation policy Ω_{max} is valid with respect to the given detectability.

The Assumption 2 in Section 2.1 requires no loops in *G* that contain only unobservable events. However, reducing a given event observation policy Ω may result in the system *G* having loops which contain only unobservable transitions. It is not what we want to have. So when we try to find a minimal valid event obs ervation policy with respect to a given detectability, we should make sure that the policy does not result in the system having loops which contain only unobservable transitions.

The algorithm to compute a minimal valid event observation policy with respect to a given detectability is as follows.

Input: a system *G*;

Output: a minimal valid event observation policy Ω with respect to a given detectability;

Step 1: Initially, set

$$\begin{array}{cc}\hfill & \Omega \prime \leftarrow {\Omega}_{\mathrm{max}};\hfill \\ \hfill & \stackrel{\u2012}{\Omega}\leftarrow {\Omega}_{\mathrm{max}};\hfill \\ \hfill & \stackrel{~}{\Omega}\leftarrow {\Omega}_{\mathrm{min}};\hfill \end{array}$$

Step 2: Randomly pick *q* *Q* and σ Σ_{o} such that $\sigma \stackrel{\u2012}{\Omega}\left(q\right)\wedge \sigma \stackrel{~}{\Omega}\left(q\right)$. If no such pair exists, go to Step 6, else set

$$\begin{array}{cc}\hfill & \stackrel{\u2012}{\Omega}\left(q\right)\leftarrow \stackrel{\u2012}{\Omega}\left(q\right)\sigma ;\hfill & \hfill & \stackrel{~}{\Omega}\left(q\right)\leftarrow \stackrel{~}{\Omega}\left(q\right)\left\{\sigma \right\};\hfill \end{array}$$

Step 3: calculate the maximal feasible sub -policy ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ of $\stackrel{\u2012}{\Omega}$ using Algorithm 1.

Step 4: If policy ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ is valid with respect to the given detectability and there are no loops which contain only unobservable transitions, then go to Step 5, else set

$$\stackrel{\u2012}{\Omega}\leftarrow \Omega \prime ;$$

Go to St ep 2;

Step 5: Set

$$\begin{array}{cc}\hfill & \Omega \prime \leftarrow {\stackrel{\u2012}{\Omega}}^{\uparrow f};\hfill \\ \hfill & \stackrel{\u2012}{\Omega}\leftarrow {\stackrel{\u2012}{\Omega}}^{\uparrow f};\hfill \\ \hfill & \stackrel{~}{\Omega}\leftarrow {\Omega}_{\mathrm{min}};\hfill \end{array}$$

Go to Step 2;

Step 6: Set

$$\Omega \leftarrow \stackrel{\u2012}{\Omega}$$

End

The event observation policy Ω obtained by Algorithm 2 is a minimal valid policy with respect to the given detectability under Assumption 2.

Proof:

First, we prove that Ω is valid with respect to the given detectability. Initially Ω = Ω_{max} is valid by the assumption. Each time an event σ Σ_{o} is removed, $\stackrel{\u2012}{\Omega}\left(q\right)\to \stackrel{\u2012}{\Omega}\left(q\right)\sigma $, we calculate ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ which ensures feasibility. The removal is final if and only if ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ is valid wit h respect to the given detectability and there are no loops which contain only unobservable transitions. Therefore Ω is valid with respect to the given detectability under Assumption 2.

Next we prove Ω is minimal by contradiction. Assume that Ω is not minimal and there exists a sub-policy Ω′ < Ω that is valid with respect to the given detectability. Then there must exist *q* *Q* and σ Σ_{o} such that

$$\sigma \Omega \left(q\right)\wedge \sigma \Omega \prime \left(q\right).$$

Since Algorithm 2 checks all the observable events for all the states, Ω′ is valid with respect to the given detectability means that σ Σ_{o} will be removed from *q* *Q* by Algorithm 2. This leads to a contradiction.

We continue Example 3. We assume the initial state set is *Q*_{0} = {*q*_{1}}, and all the events are observable, that is, Σ_{o} = Σ = {α, β, μ}. It is easy to see that under the maximal feasible event observation policy Ω_{max}, the system is strongly detectable, that is, Ω_{max} is valid with respect to strong detectability. Let us see how to obtain a minimal valid event observation policy to preserve the strong detectability of the system.

Initially, we set

$$\begin{array}{cc}\hfill & \Omega \prime \leftarrow {\Omega}_{\mathrm{max}};\hfill \\ \hfill & \stackrel{\u2012}{\Omega}\leftarrow {\Omega}_{\mathrm{max}};\hfill \\ \hfill & \stackrel{~}{\Omega}\leftarrow {\Omega}_{\mathrm{min}};\hfill \end{array}$$

We randomly pick state *q*_{1} and observable event α. Set

$$\begin{array}{cc}\hfill & \stackrel{\u2012}{\Omega}\left({q}_{1}\right)\leftarrow \stackrel{\u2012}{\Omega}\left({q}_{1}\right)\alpha ;\hfill & \hfill & \stackrel{~}{\Omega}\left({q}_{1}\right)\leftarrow \stackrel{\u2012}{\Omega}\left({q}_{1}\right)\left\{\alpha \right\}.\hfill \end{array}$$

Using Algorithm 1 we obtain the maximal feasible policy ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ as follows.

$$\begin{array}{cc}\hfill & {\stackrel{\u2012}{\Omega}}^{\uparrow f}\left({q}_{1}\right)=\{\beta ,\mu \}\hfill \\ \hfill & {\stackrel{\u2012}{\Omega}}^{\uparrow f}\left({q}_{2}\right)=\{\beta ,\mu \}\hfill \\ \hfill & {\stackrel{\u2012}{\Omega}}^{\uparrow f}\left({q}_{3}\right)=\{\alpha ,\beta ,\mu \}\hfill \end{array}$$

The observer is constructed as shown in Figure 5. We can see from the observer that the system *G* is strongly detectable and has no loops which contain only unobservable events. Therefore, the policy is valid. We next set

$$\begin{array}{cc}\hfill & \Omega \prime \leftarrow {\stackrel{\u2012}{\Omega}}^{\uparrow f}\hfill \\ \hfill & \stackrel{\u2012}{\Omega}\leftarrow {\stackrel{\u2012}{\Omega}}^{\uparrow f}\hfill \\ \hfill & \stackrel{~}{\Omega}\leftarrow {\Omega}_{\mathrm{min}}\hfill \end{array}$$

and pick state *q*_{1} and observable event β in $\stackrel{\u2012}{\Omega}$. Set

$$\begin{array}{cc}\hfill & \stackrel{\u2012}{\Omega}\left({q}_{1}\right)\leftarrow \stackrel{\u2012}{\Omega}\left({q}_{1}\right)\beta .\hfill & \hfill & \stackrel{~}{\Omega}\left({q}_{1}\right)\leftarrow \stackrel{\u2012}{\Omega}\left({q}_{1}\right)\left\{\beta \right\}.\hfill \end{array}$$

Using Algorithm 1 we find the maximal feasible policy ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ as

$$\begin{array}{cc}\hfill & {\stackrel{\u2012}{\Omega}}^{\uparrow f}\left({q}_{1}\right)=\left\{\mu \right\}\hfill \\ \hfill & {\stackrel{\u2012}{\Omega}}^{\uparrow f}\left({q}_{2}\right)=\left\{\mu \right\}\hfill \\ \hfill & {\stackrel{\u2012}{\Omega}}^{\uparrow f}\left({q}_{3}\right)=\left\{\mu \right\}\hfill \end{array}$$

We construct the observer for the policy ${\stackrel{\u2012}{\Omega}}^{\uparrow f}$ as shown in Figure 6. From the observer, we conclude that the system is not strongly detectable. Therefore, we set back $\stackrel{\u2012}{\Omega}\leftarrow \Omega \prime $ and try the next event. Continue in this fashion, eventually, we will find a minimal event observation policy Ω as follows.

$$\begin{array}{cc}\hfill & \Omega \left({q}_{1}\right)=\{\beta ,\mu \}\hfill \\ \hfill & \Omega \left({q}_{2}\right)=\{\beta ,\mu \}\hfill \\ \hfill & \Omega \left({q}_{3}\right)=\left\{\beta \right\}\hfill \end{array}$$

The observer corresponding to this policy is the same as in Figure 5.

This paper discussed detectability of discrete event systems with dynamic event observation. For a given dynamic event observation, we constructed the corresponding observer and/or detector and derived the necessary and sufficient conditions to check the four types of detectabilities. Dynamic event observation can be achieved or implemented in two possible ways: a passive way and an active way. For the active observation, a minimal valid event observation policy was investigated and the algorithms to obtain a minimal valid event policy were presented.

This research is supported in part by NSF under grants ECS-0624828 and ECS-0823865, NIH under grant 1R01DA022730, NSFC under grants 60904019 and 60804042, Key Project of Chinese Ministry of Education under grant 306023, and by Program for Young Excellent Talents in Tongji University.

**Publisher's Disclaimer: **This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the manuscript. The manuscript will undergo copyediting, typesetting, and review of the resulting proof before it is published in its final citable form. Please note that during the production process errors may be discovered which could affect the content, and all legal disclaimers that apply to the journal pertain.

[1] Ramadge PJ, Wonham WM. Supervisory control of a class of discrete event processes. SIAM J. Control and Optimization. 1987;25(1):206–230.

[2] Ramadge PJ, Wonham WM. The control of discrete event systems. Proceedings of the IEEE. 1989;77(1):81–98.

[3] Cassandras CG, Lafortune S. Introduction to discrete event systems. Kluwer. 1999

[4] Lin F, Wonham WM. On observability of discrete event systems. Information Sciences. 1988;44(3):173–198.

[5] Cieslak R, Desclaux C, Fawaz A, Varaiya P. Supervisory control of discrete event processes with partial observations. IEEE Transactions on Automatic Control. 1988;33(3):249–260.

[6] Lin F, Wonham WM. Decentralized supervisory control of discrete-event systems. Information Sciences. 1988;44(3):199–224.

[7] Shu S, Lin F, Ying H. Detectability of discrete event systems. IEEE Transactions on Automatic Control. 2007;52(12):2356–2359.

[8] Shu S, Lin F. Generalized Detectability for Discrete Event Systems. Submitted for publication. [PMC free article] [PubMed]

[9] Haji-Valizadeh A, Loparo KA. Minimizing the cardinality of an event set for supervisors of discrete-event dynamical systems. IEEE Transactions on Automatic Control. 1996;41(11):1579–1593.

[10] Jiang S, Kumar R, Garcia H. Optimal sensor selection for discrete-event systems with partial observation. IEEE Transactions on Automatic Control. 2003;48(3):369–381.

[11] Debouk R, Lafortune S, Teneketzis D. On an optimization problem in sensor selection. Discrete Event Dynamic Systems: Theory and Applications. 2002;12(4):417–445.

[12] Yoo TS, Lafortune S. NP-completeness of sensor selection problems arising in partially-observed discrete event systems. IEEE Transactions on Automatic Control. 2002;47(9):1495–1499.

[13] Thorsley D, Teneketzis D. Active acquisition of information for diagnosis of discrete event systems. Proceedings of the Allerton Conference on Control, Communication, and Computing.Sept., 2004.

[14] Thorsley D, Teneketzis D. Active acquisition of information for diagnosis and supervisory control of discrete event systems. Discrete Event Dynamic Systems:Theory and Applications. 2007;17(4):531–586.

[15] Thorsley D, Teneketzis D. Diagnosis of cyclic discrete-event systems using active acquisition of information. Proc. of 8th International Workshop on Discrete Event Systems (WODES06); Ann Arbor: University of Michigan; 2006.

[16] Rudie K, Lafortune S, Lin F. Minimal communication in a distributed discrete-event system. IEEE Transactions on Automatic Control. 2003;48(6):957–975.

[17] Lin F, Rudie K, Lafortune S. Minimal communication for essential transitions in a distributed discrete-event system. IEEE Transactions on Automatic Control. 2007;52(8):1495–1502.

[18] Wang W, Lafortune S, Lin F. On the minimization of communication in networked systems with a central station. Discrete Event Dynamic Systems: Theory and Applications. 2008;18(3):415–443.

[19] Wang W, Lafortune S, Lin F. Minimization of communication of event occurrences in acyclic discrete event systems. IEEE Transactions on Automatic Control. 2008;53(11):2197–2202.

[20] Wang W. Ph.D. dissertation. Department of Electrical Engineering and Computer Science; University of Michigan: 2007. Optimization of communication and coverage in classes of distributed systems.

[21] Wang W, Lafortune S, Lin F. Optimal Sensor Activation in Controlled Discrete Event Systems; Proceedings of the 45th IEEE Conference on Decision and Control; 2008. pp. 877–882.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |