Characterizations and Effective Computation of
Supremal Relatively Observable Sublanguages*

arXiv:1609.02251v1 [] 8 Sep 2016

Kai Cai1 and Renyuan Zhang2 , W.M. Wonham3

Abstract
Recently we proposed relative observability for supervisory control of discrete-event systems under
partial observation. Relative observability is closed under set unions and hence there exists the supremal
relatively observable sublanguage of a given language. In this paper we present a new characterization
of relative observability, based on which an operator on languages is proposed whose largest fixpoint
is the supremal relatively observable sublanguage. Iteratively applying this operator yields a monotone
sequence of languages; exploiting the linguistic concept of support based on Nerode equivalence, we
prove for regular languages that the sequence converges finitely to the supremal relatively observable
sublanguage, and the operator is effectively computable. Moreover, for the purpose of control, we propose
a second operator that in the regular case computes the supremal relatively observable and controllable
sublanguage. The computational effectiveness of the operator is demonstrated on a case study.
Keywords
Supervisory control, partial-observation, relative observability, regular language, Nerode equivalence
relation, support relation, discrete-event systems, automata

I.

I NTRODUCTION

In [3] we proposed relative observability for supervisory control of discrete-event systems (DES)
under partial observation. The essence of relative observability is to set a fixed ambient language relative
*This work was supported in part by JSPS KAKENHI Grant no. JP16K18122 and Program to Disseminate Tenure Tracking
System, MEXT, Japan; the National Nature Science Foundation, China, Grant no. 61403308; the Natural Sciences and
Engineering Research Council, Canada, Grant no. 7399.
1

K. Cai is with Urban Research Plaza, Osaka City University, Japan (kai.cai@eng.osaka-cu.ac.jp)

2

R. Zhang is with School of Automation, Northwestern Polytechnical University, China (ryzhang@nwpu.edu.cn)

3

W.M. Wonham is with the Systems Control Group, Department of Electrical and Computer Engineering, University of

Toronto, Canada (wonham@control.utoronto.ca).

to which the standard observability conditions [8] are tested. Relative observability is proved to be
stronger than observability [5], [8], weaker than normality [5], [8], and closed under arbitrary set unions.
Therefore the supremal relatively observable sublanguage of a given language exists, and we developed
an automaton-based algorithm to compute the supremal sublanguage.
In this paper and its conference precursor [2], we present a new characterization of relative observability.
The original definition of relative observability in [3] was formulated in terms of strings, while the
new characterization is given in languages. Based on this characterization, we propose an operator on
languages, whose largest fixpoint is precisely the supremal relatively observable sublanguage. Iteratively
applying this operator yields a monotone sequence of languages. In the case where the relevant languages are regular, we prove that the sequence converges finitely to the supremal relatively observable
sublanguage, and the operator is effectively computable.
This new computation scheme for the supremal sublanguage is given entirely in terms of languages, and
the convergence proof systematically exploits the concept of support ( [9, Section 2.8]) based on Nerode
equivalence relations [7]. The solution therefore separates out the linguistic essence of the problem from
the implementational aspects of state computation using automaton models. This approach is in the same
spirit as [10] for controllability, namely operator fixpoint and successive approximation.
Moreover, the proposed language-based scheme allows more straightforward implementation, as compared to the automaton-based algorithm in [3]. In particular, we show that the language operator used in
each iteration of the language-based scheme may be decomposed into a series of standard or well-known
language operations (e.g. complement, union, subset construction); therefore off-the-shelf algorithms may
be suitably assembled to implement the computation scheme. On the other hand, both the language
and automaton-based algorithms have (at least) exponential complexity in the worst case, which is the
unfortunate nature of supervisor synthesis under partial observation. Our previous experience with the
automaton-based algorithm in [3] suggests that computing the supremal relatively observable sublanguage
is fairly delicate and thus prone to error. Hence, it is advantageous to have two algorithms at hand so
that one can double check the computation results, thereby ensuring presumed correctness based on
consistency.
Finally, for the purpose of supervisory control under partial observation, we combine relative observability with controllability. In particular, we propose an operator which in the regular case effectively
computes the supremal relatively observable and controllable sublanguage. We have implemented this
operator and tested its effectiveness on a case study.
The rest of the paper is organized as follows. In Section II we present a new characterization of relative
2

observability, and an operator on languages that yields an iterative scheme to compute the supremal
relatively observable sublanguage. In Section III we prove that in the case of regular languages, the
iterative scheme generates a monotone sequence of languages that is finitely convergent to the supremal
relatively observable sublanguage. In Section IV we combine relative observability and controllability,
and propose an operator that effectively computes the supremal relatively observable and controllable
sublanguage. Section V presents illustrative examples, and finally in Section VI we state conclusions.
This paper extends its conference precursor [2] in the following respects. (1) In the main result of Section III, Theorem 1, the bound on the size of the supremal sublanguage is tightened and the corresponding
proof given. (2) The effective computability of the proposed operator is shown in Subsection III-C. (3)
Relative observability is combined with controllability in Section IV, and a new operator is presented
that effectively computes the supremal relatively observable and controllable sublanguage. (4) A case
study is given in Subsection V-B to demonstrate the effectiveness of the newly proposed computation
schemes.
II.

C HARACTERIZATIONS

OF

R ELATIVE O BSERVABILITY

AND ITS

S UPREMAL E LEMENT

In this section, the concept of relative observability proposed in [3] is first reviewed. Then we present
a new characterization of relative observability, together with a fixpoint characterization of the supremal
relatively observable sublanguage.

A. Relative Observability
Let Σ be a finite event set. A string s ∈ Σ∗ is a prefix of another string t ∈ Σ∗ , written s ≤ t,
if there exists u ∈ Σ∗ such that su = t. Let L ⊆ Σ∗ be a language. The (prefix) closure of L is
L := {s ∈ Σ∗ | (∃t ∈ L) s ≤ t}. For partial observation, let the event set Σ be partitioned into Σo ,
˙ uo ). Bring in the natural
the observable event subset, and Σuo , the unobservable subset (i.e. Σ = Σo ∪Σ

projection P : Σ∗ → Σ∗o defined according to
P (ǫ) = ǫ, ǫ is the empty string;

 ǫ, if σ ∈
/ Σo ,
P (σ) =
 σ, if σ ∈ Σ ;
o

(1)

P (sσ) = P (s)P (σ), s ∈ Σ∗ , σ ∈ Σ.

In the usual way, P is extended to P : P wr(Σ∗ ) → P wr(Σ∗o ), where P wr(·) denotes powerset. Write
P −1 : P wr(Σ∗o ) → P wr(Σ∗ ) for the inverse-image function of P .

3

Throughout the paper, let M denote the marked behavior of the plant to be controlled, and C ⊆ M
an imposed specification language. Let K ⊆ C . We say that K is relatively observable (with respect to
M , C , and P ), or simply C -observable, if the following two conditions hold:

(i) (∀s, s′ ∈ Σ∗ , ∀σ ∈ Σ) sσ ∈ K, s′ ∈ C, s′ σ ∈ M , P (s) = P (s′ ) ⇒ s′ σ ∈ K
(ii) (∀s, s′ ∈ Σ∗ ) s ∈ K, s′ ∈ C ∩ M, P (s) = P (s′ ) ⇒ s′ ∈ K.
In words, relative observability of K requires for every lookalike pair (s, s′ ) in C that (i) s and s′ have
identical one-step continuations, if allowed in M , with respect to membership in K ; and (ii) if each
string is in M and one actually belongs to K , then so does the other. Note that the tests for relative
observability of K are not limited to the strings in K (as with standard observability [5], [8]), but apply
to all strings in C ; for this reason, one may think of C as the ambient language, relative to which the
conditions (i) and (ii) are tested.
We have proved in [3] that in general, relative observability is stronger than observability, weaker than
normality, and closed under arbitrary set unions. Write
O(C) = {K ⊆ C | K is C -observable }

(2)

for the family of all C -observable sublanguages of C . Then O(C) is nonempty (the empty language ∅
belongs) and contains a unique supremal element
sup O(C) :=

[

{K | K ∈ O(C)}

(3)

i.e. the supremal relatively observable sublanguage of C .
B. Characterization of Relative Observability
For N ⊆ Σ∗ , write [N ] for P −1 P (N ), namely the set of all lookalike strings to strings in N . A
language N is normal with respect to M if [N ] ∩ M = N . For K ⊆ Σ∗ write
N (K, M ) = {K ′ ⊆ K | [K ′ ] ∩ M = K ′ }.

(4)

Since normality is closed under union, N (K, M ) has a unique supremal element sup N (K, M ) which
may be effectively computed [1], [4].
Write
C.σ := {sσ | s ∈ C}, σ ∈ Σ.

4

(5)

Let K ⊆ C and define
D(K) :=

[
[K ∩ C.σ] ∩ C.σ | σ ∈ Σ .

(6)

Thus D(K) is the collection of strings in the form tσ (t ∈ C , σ ∈ Σ), that are lookalike to the strings
in K ending with the same event σ . Note that if K = ∅ then D(K) = ∅. This language D(K) turns out
to be key to the following characterization of relative observability.
Proposition 1. Let K ⊆ C ⊆ M . Then K is C -observable if and only if
(i′ ) D(K) ∩ M ⊆ K

(ii′ ) [K] ∩ C ∩ M = K.

Note that condition (i′ ) is in a form similar to controllability of K [10] (i.e. KΣu ∩ M ⊆ K , where
Σu is the uncontrollable event set), although the expression D(K) appearing here is more complicated

owing to the presence of the normality operator [·]. Condition (ii′ ) is normality of K with respect to
C ∩ M.

Proof of Proposition 1. We first show that (i′ ) ⇔ (i), and then (ii′ ) ⇔ (ii).
1. (i′ ) ⇒ (i). Let s, s′ ∈ Σ∗ , σ ∈ Σ, and assume that sσ ∈ K , s′ ∈ C , s′ σ ∈ M , and P (s) = P (s′ ). It
will be shown that s′ σ ∈ K . Since K ⊆ C , we have K ⊆ C and
sσ ∈ K ⇒ sσ ∈ K ∩ C.σ
⇒ s′ σ ∈ [K ∩ C.σ]
⇒ s′ σ ∈ [K ∩ C.σ] ∩ C.σ
⇒ s′ σ ∈ D(K)
⇒ s′ σ ∈ D(K) ∩ M
⇒ s′ σ ∈ K

(by (i′ )).

/ D(K); thus s 6= ǫ. Let s = tσ for some t ∈ Σ∗
2. (i′ ) ⇐ (i). Let s ∈ D(K) ∩ M . According to (6) ǫ ∈

5

and σ ∈ Σ. Then
s ∈ D(K) ∩ M ⇒ tσ ∈ [K ∩ C.σ] ∩ C.σ ∩ M
⇒ t ∈ C, tσ ∈ M ,
(∃t′ ∈ Σ∗ )(P (t) = P (t′ ), t′ σ ∈ K ∩ C.σ)
⇒ tσ ∈ K,

(by (i))

⇒ s ∈ K.

3. (ii′ ) ⇒ (ii). Let s, s′ ∈ Σ∗ and assume that s ∈ K , s′ ∈ C ∩ M , and P (s) = P (s′ ). Then
s ∈ K ⇒ s′ ∈ [K]
⇒ s′ ∈ [K] ∩ C ∩ M
⇒ s′ σ ∈ K

(by (ii′ )).

4. (ii) ⇒ (ii′ ). (⊇) holds because K ⊆ [K] and K ⊆ C ∩ M . To show (⊆), let s ∈ [K] and s ∈ C ∩ M .
Then there exists s′ ∈ K such that P (s) = P (s′ ). Therefore by (ii) we derive s ∈ K .



Thanks to the characterization of relative observability in Proposition 1, we rewrite O(C) in (2) as
follows:

O(C) = {K ⊆ C | D(K) ∩ M ⊆ K & [K] ∩ C ∩ M = K}.

(7)

In the next subsection, we will characterize the supremal element sup O(C) as the largest fixpoint of a
language operator.
C. Fixpoint Characterization of sup O(C)
For a string s ∈ Σ∗ , write s̄ for {s}, the set of prefixes of s. Given a language K ⊆ Σ∗ , let
F (K) := {s ∈ K | D(s̄) ∩ M ⊆ K}.

(8)

Lemma 1. F (K) is closed, i.e. F (K) = F (K). Moreover, if K ∈ O(C), then F (K) = K .
Proof. First, let s ∈ F (K); then there exists w ∈ Σ∗ such that sw ∈ F (K), i.e. sw ∈ K and
D(sw) ∩ M ⊆ K . It follows that s ∈ K and D(s) ∩ M ⊆ K , namely s ∈ F (K). This shows that
F (K) ⊆ F (K); the other direction F (K) ⊇ F (K) is automatic.

6

Next, suppose that K ∈ O(C); by (7) we have D(K) ∩ M ⊆ K . Let s ∈ K ; it will be shown that
D(s̄) ∩ M ⊆ K . Taking an arbitrary string t ∈ D(s̄) ∩ M , we derive
t∈

[

[s ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M

⇒t ∈

[

[K ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M

⇒t ∈ K.

This shows that s ∈ F (K) by (8), and hence K ⊆ F (K). The other direction F (K) ⊇ K is automatic.

Now define an operator Ω : P wr(Σ∗ ) → P wr(Σ∗ ) according to

Ω(K) := sup N K ∩ F (K), C ∩ M ,

K ∈ P wr(Σ∗ ).

(9)

A language K such that K = Ω(K) is called a fixpoint of the operator Ω. The following proposition
characterizes sup O(C) as the largest fixpoint of Ω.
Proposition 2. sup O(C) = Ω(sup O(C)), and sup O(C) ⊇ K for every K such that K = Ω(K).
Proof. Since sup O(C) ∈ O(C), we have
Ω(sup O(C)) = sup N sup O(C) ∩ F (sup O(C)), C ∩ M



= sup N (sup O(C) ∩ sup O(C), C ∩ M )
= sup N (sup O(C), C ∩ M )
= sup O(C).

Next let K be such that K = Ω(K). To show that K ⊆ sup O(C), it suffices to show that K ∈ O(C).
From
K = Ω(K) := sup N K ∩ F (K), C ∩ M



we have K ⊆ K ∩ F (K). But K ∩ F (K) ⊆ K . Hence, in fact, K = K ∩ F (K). This implies that

K = sup N K, C ∩ M ; namely K is normal with respect to C ∩ M .
On the other hand, by K = K ∩ F (K) ⊆ F (K), we have K ⊆ F (K) = F (K). But F (K) ⊆ K by
definition; therefore K = F (K). In what follows it will be shown that D(F (K)) ∩ M ⊆ F (K), which
is equivalent to D(K) ∩ M ⊆ K . Let s ∈ D(F (K)) ∩ M . As in the proof of Proposition 1 (item 2), we

7

know that s 6= ǫ. So let s = tσ for some t ∈ Σ∗ and σ ∈ Σ. Then
s ∈ D(F (K)) ∩ M ⇒ tσ ∈ [F (K) ∩ C.σ] ∩ C.σ ∩ M
⇒ (∃t′ ∈ C)P (t) = P (t′ ), t′ σ ∈ F (K)
⇒ D(t′ σ) ∩ M ⊆ K (by definition of F (K)).

Then by (6)
[
[t′ σ ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M ⊆ K.
Since tσ belongs to the left-hand-side of the above inequality, we have tσ ∈ K = F (K). Therefore
D(F (K)) ∩ M ⊆ F (K); equivalently D(K) ∩ M ⊆ K . This completes the proof of K ∈ O(C).



In view of Proposition 2, it is natural to attempt to compute sup O(C) by iteration of Ω as follows:
(∀j ≥ 1) Kj = Ω(Kj−1 ),

K0 = C.

(10)

It is readily verified that Ω(K) ⊆ K ; hence
K0 ⊇ K1 ⊇ K2 ⊇ · · ·

Namely the sequence {Kj } (j ≥ 1) is a monotone (descending) sequence of languages. This implies that
the (set-theoretic) limit
K∞ := lim Kj =
j→∞

∞
\

Kj

(11)

j=0

exists. The following result asserts that if K∞ is reached in a finite number of steps, then K∞ is precisely
the supremal relatively observable sublanguage of C , i.e. sup O(C).
Proposition 3. If K∞ in (11) is reached in a finite number of steps, then
K∞ = sup O(C).

Proof. Suppose that the limit K∞ is reached in a finite number of steps. Then K∞ = Ω(K∞ ). As in
the proof of Proposition 2, we derive that K∞ ∈ O(C).
It remains to show that K∞ is the supremal element of O(C). Let K ′ ∈ O(C); it will be shown that
K ′ ⊆ K∞ by induction. The base case K ′ ⊆ K0 holds because K ′ ⊆ C and K0 = C . Suppose that

8

K ′ ⊆ Kj−1 . Let s ∈ K ′ . Then s ∈ Kj−1 and
D(s) ∩ M ⊆ D(K ′ ) ∩ M

(by K ′ ∈ O(C))

⊆ K′

⊆ Kj−1 .

Hence s ∈ F (Kj−1 ). This shows that
K ′ ⊆ F (Kj−1 )
⇒ K ′ ⊆ F (Kj−1 )
⇒ K ′ ⊆ Kj−1 ∩ F (Kj−1 ).

Moreover, since K ′ ∈ O(C), K ′ is normal with respect to C ∩ M . Thus K ′ ⊆ sup N Kj−1 ∩

F (Kj−1 ), C ∩ M = Kj . This completes the proof of the induction step, and therefore confirms that
K ′ ⊆ K∞ .



In the next section, we shall establish that, when the given languages M and C are regular, the limit
K∞ in (11) is indeed reached in a finite number of steps.

III.

E FFECTIVE C OMPUTATION

OF

sup O(C) IN THE R EGULAR C ASE

In this section, we first review the concept of Nerode equivalence relation and a finite convergence
result for a sequence of regular languages. Based on these, we then prove that the sequence generated by
(10) converges to the supremal relatively observable sublanguage sup O(C) in a finite number of steps.
Finally, we show that the computation of sup O(C) is effective.
A. Preliminaries
Let π be an arbitrary equivalence relation on Σ∗ . Denote by Σ∗ /π the set of equivalence classes of
π , and write |π| for the cardinality of Σ∗ /π . Define the canonical projection Pπ : Σ∗ → Σ∗ /π , namely

the surjective function mapping any s ∈ Σ∗ onto its equivalence class Pπ (s) ∈ Σ∗ /π .
Let π1 , π2 be two equivalence relations on Σ∗ . The partial order π1 ≤ π2 holds if
(∀s1 , s2 ∈ Σ∗ ) s1 ≡ s2 (mod π1 ) ⇒ s1 ≡ s2 (mod π2 ).

The meet π1 ∧ π2 is defined by
(∀s1 , s2 ∈ Σ∗ ) s1 ≡ s2 (mod π1 ∧ π2 ) iff s1 ≡ s2 (mod π1 ) & s1 ≡ s2 (mod π2 ).

9

For a language L ⊆ Σ∗ , write Ner(L) for the Nerode equivalence relation [7] on Σ∗ with respect to
L; namely for all s1 , s2 ∈ Σ∗ , s1 ≡ s2 (mod Ner(L)) provided
(∀w ∈ Σ∗ ) s1 w ∈ L ⇔ s2 w ∈ L.

Write ||L|| for the cardinality of the set of equivalence classes of Ner(L), i.e. ||L|| := |Ner(L)|. The
language L is said to be regular [7] if ||L|| < ∞. Henceforth, we assume that the given languages M
and C are regular.
An equivalence relation ρ is a right congruence on Σ∗ if
(∀s1 , s2 , t ∈ Σ∗ ) s1 ≡ s2 (mod ρ) ⇒ s1 t ≡ s2 t(mod ρ).

Any Nerode equivalence relation is a right congruence. For a right congruence ρ and languages L1 , L2 ⊆
Σ∗ , we say that L1 is ρ-supported on L2 [9, Section 2.8] if L1 ⊆ L2 and
{L1 , Σ∗ − L1 } ∧ ρ ∧ Ner(L2 ) ≤ Ner(L1 ).

(12)

The ρ-support relation is transitive: namely, if L1 is ρ-supported on L2 , and L2 is ρ-supported on L3 , then
L1 is ρ-supported on L3 . The following lemma is central to establish finite convergence of a monotone

language sequence.
Lemma 2. [9, Theorem 2.8.11] Given a monotone sequence of languages K0 ⊇ K1 ⊇ K2 ⊇ · · · with
K0 regular, and a fixed right congruence ρ on Σ∗ with |ρ| < ∞, suppose that Kj is ρ-supported on
Kj−1 for all j ≥ 1. Then each Kj is regular, and the sequence is finitely convergent to a sublanguage
K . Furthermore, K is supported on K0 and
||K|| ≤ |ρ| · ||K0 || + 1.

In view of this lemma, to show finite convergence of the sequence in (10), it suffices to find a fixed
right congruence ρ with |ρ| < ∞ such that Kj is ρ-supported on Kj−1 for all j ≥ 1. To this end, we
need the following notation.
Let µ := Ner(M ), η := Ner(C) be Nerode equivalence relations and
ϕj := {F (Kj ), Σ∗ − F (Kj )}, κj := {Kj , Σ∗ − Kj }

(j ≥ 1)

also stand for the equivalence relations corresponding to these partitions. Then |µ| < ∞, |η| < ∞, and
|ϕj | = |κj | = 2. Let π be an equivalence relation on Σ∗ , and define fπ : Σ∗ → Pwr(Σ∗ /π) according to


(∀s ∈ Σ∗ ) fπ (s) = {Pπ (s′ ) | s′ ∈ [s] ∩ C ∩ M }
10

(13)

where [s] = P −1 P ({s}). Write ℘(π) := ker fπ . The size of ℘(π) is |℘(π)| ≤ 2|π| [9, Ex. 1.4.21].
Another property of ℘(·) we shall use later is [9, Ex. 1.4.21]:
℘(π1 ∧ ℘(π2 )) = ℘(π1 ∧ π2 ) = ℘(℘(π1 ) ∧ π2 )

where π1 , π2 are equivalence relations on Σ∗ .
B. Convergence Result
First, we present a key result on support relation of the sequence {Kj } generated by (10).
Proposition 4. Consider the sequence {Kj } generated by (10). For each j ≥ 1, there holds that Kj is
ρ-supported on Kj−1 , where
ρ := µ ∧ η ∧ ℘(µ ∧ η).

(14)

Let us postpone the proof of Proposition 4, and present immediately our main result.
Theorem 1. Consider the sequence {Kj } generated by (10), and suppose that the given languages M
and C are regular. Then the sequence {Kj } is finitely convergent to sup O(C), and sup O(C) is a regular
language with
|| sup O(C)|| ≤ ||M || · ||C|| · 2||M ||·||C|| + 1.

Proof. Let ρ = µ ∧ η ∧ ℘(µ ∧ η) as in (14). Since µ and η are right congruences, so are µ ∧ η and
℘(µ ∧ η) ( [9, Example 6.1.25]). Hence ρ is a right congruence, with
|ρ| ≤ |µ| · |η| · 2|µ|·|η|
= ||M || · ||C|| · 2||M ||·||C||.

Since the languages M and C are regular, i.e. ||M ||, ||C|| < ∞, we derive that |ρ| < ∞.
It then follows from Lemmas 3 and 2 that the sequence {Kj } is finitely convergent to sup O(C), and
sup O(C) is ρ-supported on K0 , i.e.

Ner(sup O(C)) ≥ {sup O(C), Σ∗ − sup O(C)} ∧ ρ ∧ Ner(K0 )
= {sup O(C), Σ∗ − sup O(C)} ∧ µ ∧ η ∧ ℘(µ ∧ η) ∧ Ner(K0 )
= {sup O(C), Σ∗ − sup O(C)} ∧ µ ∧ ℘(µ ∧ η) ∧ Ner(K0 ).

11

Hence sup O(C) is in fact (µ ∧ ℘(µ ∧ η))-supported on K0 , which implies
|| sup O(C)|| ≤ |µ ∧ ℘(µ ∧ η)| · ||K0 || + 1
≤ ||M || · ||C|| · 2||M ||·||C|| + 1 < ∞.

Therefore sup O(C) is itself a regular language.



Theorem 1 establishes the finite convergence of the sequence {Kj } in (10), as well as the fact that an
upper bound of || sup O(C)|| is exponential in the product of ||M || and ||C||.
In the sequel we prove Proposition 4, for which we need two lemmas.
Lemma 3. For each j ≥ 1, the Nerode equivalence relation on Σ∗ with respect to F (Kj−1 ) satisfies
Ner(F (Kj−1 )) ≥ ϕj ∧ Ner(Kj−1 ) ∧ ℘(Ner(Kj−1 ) ∧ µ ∧ η).
Proof. First, let s1 , s2 ∈ Σ∗ − F (Kj−1 ); then for all w ∈ Σ∗ it holds that s1 w, s2 w ∈ Σ∗ − F (Kj−1 ).
Thus s1 ≡ s2 (mod Ner(F (Kj−1 ))).
Next, let s1 , s2 ∈ F (Kj−1 ) and assume that
s1 ≡ s2 (mod Ner(Kj−1 ) ∧ ℘(Ner(Kj−1 ) ∧ µ ∧ η)).

Also let w ∈ Σ∗ be such that s1 w ∈ F (Kj−1 ). It will be shown that s2 w ∈ F (Kj−1 ). Note first that
s2 w ∈ Kj−1 , since s1 w ∈ F (Kj−1 ) ⊆ Kj−1 and s1 ≡ s2 (mod Ner(Kj−1 )). Hence it is left to show that
D(s2 w) ∩ M ⊆ Kj−1 , i.e.

[
[s2 w ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M ⊆ Kj−1 .
It follows from s2 ∈ F (Kj−1 ) that
[
[s2 ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M ⊆ Kj−1 .
Thus let s′2 ∈ [s2 ], x′ ∈ [w], and s′2 x′ ∈ [s2 w ∩C.σ]∩C.σ ∩M for some σ ∈ Σ. Write x′ := y ′ σ , y ′ ∈ Σ∗ .
Since s1 ≡ s2 (mod ℘(Ner(Kj−1 ) ∧ µ ∧ η)), there exists s′1 ∈ [s1 ] such that s′1 ≡ s′2 (mod Ner(Kj−1 ) ∧
µ ∧ η). Hence s′1 x′ ∈ M and s′1 y ′ ∈ C , and we derive that s′1 x′ = s′1 y ′ σ ∈ [{s1 w} ∩ C.σ] ∩ C.σ ∩ M .

It then follows from s1 w ∈ F (Kj−1 ) that s′1 x′ ∈ Kj−1 , which in turn implies that s′2 x′ ∈ Kj−1 . This
completes the proof of s2 w ∈ F (Kj−1 ), as required.
Lemma 4. For Kj (j ≥ 1) generated by (10), the following statements hold:
[


Kj =
[s] ∩ C ∩ M | s ∈ Σ∗ & [s] ∩ C ∩ M ⊆ Kj−1 ∩ F (Kj−1 ) ;
Ner(Kj ) ≥ µ ∧ η ∧ ℘(Ner(Kj−1 ) ∧ Ner(F (Kj−1 )) ∧ µ ∧ η).
12



Proof. By (9) we know that Kj is the supremal normal sublanguage of Kj−1 ∩ F (Kj−1 ) with respect
to C ∩ M . Thus the conclusions follow immediately from Example 6.1.25 of [9].



Now we are ready to prove Proposition 4.
Proof of Proposition 4. To prove that Kj is ρ-supported on Kj−1 (j ≥ 1), by definition we must show
that
Ner(Kj ) ≥ κj ∧ µ ∧ η ∧ ℘(µ ∧ η) ∧ Ner(Kj−1 ).
It suffices to show the following:
Ner(Kj ) ≥ κj ∧ µ ∧ η ∧ ℘(µ ∧ η).
We prove this statement by induction. First, we show the base case (j = 1)
Ner(K1 ) ≥ κ1 ∧ µ ∧ η ∧ ℘(µ ∧ η).
From Lemma 3 and K0 = C (thus Ner(K0 ) = η ) we have
Ner(F (K0 )) ≥ ϕ1 ∧ Ner(K0 ) ∧ ℘(Ner(K0 ) ∧ µ ∧ η)
= ϕ1 ∧ η ∧ ℘(µ ∧ η).

It then follows from Lemma 4 that
Ner(K1 ) ≥ µ ∧ η ∧ ℘(Ner(K0 ) ∧ Ner(F (K0 )) ∧ µ ∧ η)
≥ µ ∧ η ∧ ℘(η ∧ ϕ1 ∧ η ∧ ℘(µ ∧ η) ∧ µ ∧ η)
= µ ∧ η ∧ ℘(ϕ1 ∧ µ ∧ η) ∧ ℘(µ ∧ η)
= µ ∧ η ∧ ℘(ϕ1 ∧ µ ∧ η).

(15)

We claim that
Ner(K1 ) ≥ κ1 ∧ µ ∧ η ∧ ℘(µ ∧ η).
To show this, let s1 , s2 ∈ Σ∗ and assume that s1 ≡ s2 (mod κ1 ∧ µ ∧ η ∧ ℘(µ ∧ η)). If s1 , s2 ∈ Σ∗ − K1 ,
then for all w ∈ Σ∗ , s1 w, s2 w ∈ Σ∗ − K1 ; thus s1 ≡ s2 (mod Ner(K1 )). Now let s1 , s2 ∈ K1 . By


Lemma 4 we derive that for all s′1 ∈ [s1 ] ∩ C ∩ M and s′2 ∈ [s2 ] ∩ C ∩ M , s′1 , s′2 ∈ K1 . Since
K1 ⊆ F (K0 ), s′1 , s′2 ∈ F (K0 ) and hence



{Pϕ1 ∧µ∧η (s′1 ) | s′1 ∈ [s1 ] ∩ C ∩ M } = {Pϕ1 ∧µ∧η (s′2 ) | s′2 ∈ [s2 ] ∩ C ∩ M }.

13

Namely s1 ≡ s2 (mod ℘(ϕ1 ∧ µ ∧ η)). This implies that s1 ≡ s2 (mod Ner(K1 )) by (15). Hence the above
claim is established, and the base case is proved.
For the induction step, suppose that for j ≥ 2, there holds
Ner(Kj−1 ) ≥ κj−1 ∧ µ ∧ η ∧ ℘(µ ∧ η).
Again by Lemma 3 we have
Ner(F (Kj−1 )) ≥ ϕj−1 ∧ Ner(Kj−1 ) ∧ ℘(Ner(Kj−1 ) ∧ µ ∧ η)
≥ ϕj−1 ∧ κj−1 ∧ µ ∧ η ∧ ℘(µ ∧ η) ∧ ℘(κj−1 ∧ µ ∧ η ∧ ℘(µ ∧ η) ∧ µ ∧ η)
= ϕj−1 ∧ κj−1 ∧ µ ∧ η ∧ ℘(µ ∧ η) ∧ ℘(κj−1 ∧ µ ∧ η)
= ϕj−1 ∧ κj−1 ∧ µ ∧ η ∧ ℘(κj−1 ∧ µ ∧ η)

Then by Lemma 4,
Ner(Kj ) ≥ µ ∧ η ∧ ℘(Ner(Kj−1 ) ∧ Ner(F (Kj−1 )) ∧ µ ∧ η)
≥ µ ∧ η ∧ ℘(ϕj−1 ∧ κj−1 ∧ µ ∧ η ∧ ℘(κj−1 ∧ µ ∧ η))
= µ ∧ η ∧ ℘(ϕj−1 ∧ κj−1 ∧ µ ∧ η).

(16)

We claim that
Ner(Kj ) ≥ κj ∧ µ ∧ η ∧ ℘(µ ∧ η).
To show this, let s1 , s2 ∈ Σ∗ and assume that s1 ≡ s2 (mod κj ∧ µ ∧ η ∧ ℘(µ ∧ η)). If s1 , s2 ∈ Σ∗ − Kj ,
then for all w ∈ Σ∗ , s1 w, s2 w ∈ Σ∗ − Kj ; hence s1 ≡ s2 (mod Ner(Kj )). Now let s1 , s2 ∈ Kj . By


Lemma 4 we derive that for all s′1 ∈ [s1 ] ∩ C ∩ M and s′2 ∈ [s2 ] ∩ C ∩ M , s′1 , s′2 ∈ Kj . Since
Kj ⊆ F (Kj−1 ) ⊆ Kj−1 ,


{Pϕj−1 ∧κj−1 ∧µ∧η (s′1 ) | s′1 ∈ [s1 ] ∩ C ∩ M }

={Pϕj−1 ∧κj−1 ∧µ∧η (s′2 ) | s′2 ∈ [s2 ] ∩ C ∩ M }.
Namely s1 ≡ s2 (mod ℘(ϕj−1 ∧κj−1 ∧µ∧η). This implies that s1 ≡ s2 (mod Ner(Kj )) by (16). Therefore
the above claim is established, and the induction step is completed.


14

C. Effective Computability of Ω
We conclude this section by showing that the iteration scheme in (10) yields an effective procedure
for the computation of sup O(C), when the given languages M and C are regular. For this, owing to
Theorem 1, it suffices to prove that the operator Ω in (9) is effectively computable.
Recall that a language L ⊆ Σ∗ is regular if and only if there exists a finite-state automaton G =
(Q, Σ, δ, q0 , Qm ) such that
Lm (G) = {s ∈ Σ∗ | δ(q0 , s) ∈ Qm } = L.

Let O : (P wr(Σ∗ ))k → (P wr(Σ∗ )) be an operator that preserves regularity; namely L1 , ..., Lk regular
implies O(L1 , ..., Lk ) regular. We say that O is effectively computable if from each k-tuple (L1 , ..., Lk )
of regular languages, one can construct a finite-state automaton G with Lm (G) = O(L1 , ..., Lk ).
The standard operators of language closure, complement,1 union, and intersection all preserve regularity
and are effectively computable [6]. Moreover, both the operator sup N : P wr(Σ∗ ) → P wr(Σ∗ ) given
by
sup N (L) :=

[
{L′ ⊆ L | [L′ ] ∩ H = L′ },

for some fixed H ⊆ Σ∗

and the operator sup F : P wr(Σ∗ ) → P wr(Σ∗ ) given by
sup F(L) :=

[

{L′ ⊆ L | L′ = L′ }

preserve regularity and are effectively computable (see [4] and [10], respectively).
The main result of this subsection is the following theorem.
Theorem 2. Suppose that M and C are regular. Then the operator Ω in (9) preserves regularity and is
effectively computable.
The following proposition is a key fact.
Proposition 5. For each K ⊆ Σ∗ ,
F (K) = K ∩ sup F

\


{sup N (K ∪ (M ∩ C.σ)c ) ∪ (C.σ)c | σ ∈ Σ} .

Proof. By (8) and (6),
F (K) = {s ∈ K |
1

[
[s ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M ⊆ K}.

For a language L ⊆ Σ∗ , its complement, written Lc , is Σ∗ − L.

15

Hence
[
[s ∩ C.σ] ∩ C.σ | σ ∈ Σ ∩ M ⊆ K
[
[s ∩ C.σ] ∩ C.σ | σ ∈ Σ ⊆ K ∪ (M )c
⇔ s ∈ K and

s ∈ F (K) ⇔ s ∈ K and

⇔ s ∈ K and (∀σ ∈ Σ) [s ∩ C.σ] ∩ C.σ ⊆ K ∪ (M )c
⇔ s ∈ K and (∀σ ∈ Σ) [s ∩ C.σ] ⊆ K ∪ (M )c ∪ (C.σ)c
⇔ s ∈ K and (∀σ ∈ Σ) [s ∩ C.σ] ⊆ K ∪ (M ∩ C.σ)c
⇔ s ∈ K and (∀σ ∈ Σ) s ∩ C.σ ⊆ sup N (K ∪ (M ∩ C.σ)c )
⇔ s ∈ K and (∀σ ∈ Σ) s ⊆ sup N (K ∪ (M ∩ C.σ)c ) ∪ (C.σ)c
\
⇔ s ∈ K and s ⊆ {sup N (K ∪ (M ∩ C.σ)c ) ∪ (C.σ)c | σ ∈ Σ}
\

⇔ s ∈ K and s ∈ sup F
{sup N (K ∪ (M ∩ C.σ)c ) ∪ (C.σ)c | σ ∈ Σ}
\

{sup N (K ∪ (M ∩ C.σ)c ) ∪ (C.σ)c | σ ∈ Σ} .
⇔ s ∈ K ∩ sup F


We also need the following lemma.
Lemma 5. Let σ ∈ Σ be fixed. Then the operator Bσ : P wr(Σ∗ ) → P wr(Σ∗ ) given by
Bσ (L) := L.σ = {sσ | s ∈ L}

preserves regularity and is effectively computable.
Proof. Let G = (Q, Σ, δ, q0 , Qm ) be a finite-state automaton with Lm (G) = L. We will construct a
new finite-state automaton H such that Lm (H) = Bσ (L). The construction is in two steps. First, let q ∗
be a new state (i.e. q ∗ ∈
/ Q), and define G′ = (Q′ , Σ, δ′ , q0 , Q′m ) where
Q′ := Q ∪ {q ∗ },

δ′ := δ ∪ {(q, σ, q ∗ )|q ∈ Q},

Q′m := {q ∗ }.

Thus G′ is a finite-state automaton with Lm (G′ ) = Bσ (L). However, G′ is nondeterministic, inasmuch
as δ′ (q, σ) = {q ′ , q ∗ } whenever δ(q, σ) is defined and δ(q, σ) = q ′ . The second step is hence to apply the
standard subset construction to convert the nondeterministic G′ to a deterministic finite-state automaton
H with Lm (H) = Lm (G′ ) = Bσ (L). This completes the proof.

Finally we present the proof of Theorem 2.

16



Proof of Theorem 2. By Proposition 5 and the definition of Ω : P wr(Σ∗ ) → P wr(Σ∗ ) in (9), for each
K ⊆ Σ∗ we derive


\

{sup N (K ∪ (M ∩ C.σ)c ) ∪ (C.σ)c | σ ∈ Σ} .
Ω(K) = sup N K ∩ sup F
Since the language closure, complement, union, intersection, sup N , sup F and C.σ (by Lemma 5)
all preserve regularity and are effectively computable, the same conclusion for the operator Ω follows


immediately.

In the proof, we see that the operator Ω in (9) is decomposed into a sequence of standard or well-known
language operations. This allows straightforward implementation of Ω using off-the-shelf algorithms.
IV.

R ELATIVE O BSERVABILITY

AND

C ONTROLLABILITY

For the purpose of supervisory control under partial observation, we combine relative observability
with controllability and provide a fixpoint characterization of the supremal relatively observable and
controllable sublanguage.
Let the alphabet Σ be partitioned into Σc , the subset of controllable events, and Σu , the subset of
uncontrollable events. For the given M and C , we say that C is controllable with respect to M if
CΣu ∩ M ⊆ C.

Whether or not C is controllable, write C(C) for the family of all controllable sublanguages of C . Then
the supremal element sup C(C) exists and is effectively computable [10].
Now write CO(C) for the family of controllable and C -observable sublanguages of C . Note that the
family CO(C) is nonempty inasmuch as the empty language is a member. Thanks to the closed-underunion property of both controllability and C -observability, the supremal controllable and C -observable
sublanguage sup CO(C) therefore exists and is given by
sup CO(C) :=

[
{K | K ∈ CO(C)}.

(17)

Define the operator Γ : P wr(Σ∗ ) → P wr(Σ∗ ) by
Γ(K) := sup O(sup C(K)).

(18)

The proposition below characterizes sup CO(C) as the largest fixpoint of Γ.
Proposition 6. sup CO(C) = Γ(sup CO(C)), and sup CO(C) ⊇ K for every K such that K = Γ(K).

17

Proof. Since sup CO(C) ∈ CO(C), i.e. both controllable and C -observable,
Γ(sup CO(C)) = sup O(sup C(sup CO(C)))
= sup O(sup CO(C))
= sup CO(C).

Next let K be such that K = Γ(K). To show that K ⊆ sup CO(C), it suffices to show that K ∈ CO(C).
Let H := sup C(K); thus H ⊆ K . On the other hand, from K = Γ(K) = sup O(H) we have K ⊆ H .
Hence K = H . It follows that K = sup C(K) and K = sup O(K), which means that K is both
controllable and C -observable. Therefore we conclude that K ∈ CO(C).



In view of Proposition 6, we compute sup CO(C) by iteration of Γ as follows:
(∀j ≥ 1) Kj = Γ(Kj−1 ),

K0 = C.

(19)

It is readily verified that Γ(K) ⊆ K , and thus
K0 ⊇ K1 ⊇ K2 ⊇ · · ·

Namely the sequence {Kj } (j ≥ 1) is a monotone (descending) sequence of languages. Recalling the
notation from Section III-A, we have the following key result.
Proposition 7. Consider the sequence {Kj } generated by (19) and let ρ = µ ∧ η ∧ ℘(µ ∧ η). Then for
each j ≥ 1, Kj is ρ-supported on Kj−1 .
Proof. Write Hj := sup C(Kj−1 ) and ψj := {Hj , Σ∗ − Hj } for j ≥ 1. Then by [10, p. 642] there
holds
Ner(Hj ) ≥ ψj ∧ µ ∧ Ner(Kj−1 ).
We claim that for j ≥ 1,
Ner(Kj ) ≥ κj ∧ µ ∧ η ∧ ℘(µ ∧ η).
We prove this claim by induction. For the base case (j = 1),
Ner(H1 ) ≥ ψ1 ∧ µ ∧ Ner(K0 )
= ψ1 ∧ µ ∧ η

Since K1 = sup O(H1 ), we set up the following sequence to compute K1 :
(∀i ≥ 1) Ti = Ω(Ti−1 ),

18

T0 = H1 .

Following the derivations in the proof of Proposition 4, it is readily shown that each Ti is ρ-supported
on H1 ; in particular,
Ner(K1 ) ≥ κ1 ∧ ρ ∧ Ner(H1 )
≥ κ1 ∧ ψ1 ∧ µ ∧ η ∧ ℘(µ ∧ η)
= κ1 ∧ µ ∧ η ∧ ℘(µ ∧ η).

This confirms the base case.
For the induction step, suppose that for j ≥ 2, there holds
Ner(Kj−1 ) ≥ κj−1 ∧ µ ∧ η ∧ ℘(µ ∧ η).
Thus
Ner(Hj ) ≥ ψj ∧ µ ∧ Ner(Kj−1 )
≥ ψj ∧ κj−1 ∧ µ ∧ η ∧ ℘(µ ∧ η)
= ψj ∧ µ ∧ η ∧ ℘(µ ∧ η).

Again set up a sequence to compute Kj as follows:
(∀i ≥ 1) Ti = Ω(Ti−1 ),

T0 = Hj .

We derive by similar calculations as in Proposition 4 that each Ti is ρ-supported on Hj ; in particular,
Ner(Kj ) ≥ κj ∧ ρ ∧ Ner(Hj )
≥ κj ∧ ψj ∧ µ ∧ η ∧ ℘(µ ∧ η)
= κj ∧ µ ∧ η ∧ ℘(µ ∧ η).

Therefore the induction step is completed, and the above claim is established. Then it follows immediately
Ner(Kj ) ≥ κj ∧ µ ∧ η ∧ ℘(µ ∧ η) ∧ Ner(Kj−1 )
= κj ∧ ρ ∧ Ner(Kj−1 ).

Namely, Kj is ρ-supported on Kj−1 , as required.



The following theorem is the main result of this section, which follows directly from Proposition 7
and Lemma 2.

19

q1
α,

q6

Σo = {α, γ, σ}

γ
β1

q0

σ

β2

q2
q3

α
α

q7

γ

β3 q4

Σuo = {β1 , β2 , β3 , β4 , β5 }
β5

q9

σ

q11

P : (Σo ∪ Σuo )∗ → Σ∗o

β4
q5

q8
α, γ

β5

initial state

q10

marker state

G
Fig. 1.

Example: computation of the supremal C-observable sublanguage sup O(C) by iteration of the operator Ω in (9)

Theorem 3. Consider the sequence {Kj } in (19), and suppose that the given languages M and C
are regular. Then the sequence {Kj } is finitely convergent to sup CO(C), and sup CO(C) is a regular
language with
|| sup CO(C)|| ≤ ||M || · ||C|| · 2||M ||·||C|| + 1.

Finally, sup CO(C) is effectively computable, inasmuch as the operators sup C(·) and sup O(·) are
(see [10] and Theorem 2, respectively). In particular, the operator Γ in (18) is effectively computable.
V.

E XAMPLES

In this section, we first give an example to illustrate the computation of the supremal C -observable
sublanguage sup O(C) (by iteration of the operator Ω). Then we present an empirical study on the
computation of the supremal controllable and C -observable sublanguage sup CO(C) (by iteration of the
operator Γ, which has been implemented by a computer program).
A. An Example of Computing sup O(C)
Consider the example displayed in Fig. 1. The observable event set is Σo = {α, γ, σ} and unobservable
Σuo = {β1 , β2 , β3 , β4 , β5 }; thus the natural projection is P : (Σo ∪ Σuo )∗ → Σ∗o . Let
M := Lm (G) = {ǫ, α, γ, ασ, γσ, β1 ασ, β2 α, β2 αβ5 σ, β3 γ,
β3 γβ5 σ, β4 , β4 α, β4 γ, β4 αβ5 , β4 γβ5 }

20

and the specification language
C := M − {β4 αβ5 , β4 γβ5 }.

Both M and C are regular languages.
Now apply the operator Ω in (9). Initialize K0 = C . The first iteration j = 1 starts with
F (K0 ) = {s ∈ K0 | D(s) ∩ M ⊆ K0 }
= {ǫ, α, γ, ασ, γσ, β1 , β1 α, β1 ασ, β2 , β2 α, β3 , β3 γ, β4 , β4 α, β4 γ}
= K0 − {β2 αβ5 , β2 αβ5 σ, β3 γβ5 , β3 γβ5 σ}.

Note that since β2 αβ5 σ ∈ K0 , strings β2 αβ5 , β2 αβ5 σ ∈ K0 . But β2 αβ5 , β2 αβ5 σ ∈
/ F (K0 ); this is
because the string β4 αβ5 belongs to D(β2 αβ5 ) ∩ M and D(β2 αβ5 σ) ∩ M , but β4 αβ5 does not belong
to K0 . For the same reason, β3 γβ5 , β3 γβ5 σ ∈ K0 but β3 γβ5 , β3 γβ5 σ ∈
/ F (K0 ). Next calculate
F (K0 ) ∩ K0 = {ǫ, α, γ, ασ, γσ, β1 ασ, β2 α, β3 γ, β4 , β4 α, β4 γ}
= K0 − {β2 αβ5 σ, β3 γβ5 σ}.

Removing strings β2 αβ5 σ, β3 γβ5 σ from K0 makes F (K0 ) ∩ K0 not normal with respect to C ∩ M .
Indeed, ασ, β1 ασ ∈ [β2 αβ5 σ] ∩ C ∩ M and γσ ∈ [β3 γβ5 σ] ∩ C ∩ M violate the normality condition and
therefore must also be removed. Hence,
K1 = sup N (F (K0 ) ∩ K0 , C ∩ Lm (G))
= {ǫ, α, γ, β2 α, β3 γ, β4 , β4 α, β4 γ}
= (F (K0 ) ∩ K0 ) − {ασ, β1 ασ, γσ}.

This completes the first iteration j = 1.
Since K1 $ K0 , we proceed to j = 2,
F (K1 ) = {s ∈ K1 | D(s) ∩ M ⊆ K1 }
= {ǫ, γ, β2 , β3 , β3 γ, β4 , β4 γ}
= K1 − {α, β2 α, β4 α}.

We see that α, β2 α, β4 α ∈ K1 but α, β2 α, β4 α ∈
/ F (K1 ). This is because the string β1 α ∈ D(α) ∩ M ,
/ K1 . Note that β1 α was in K0 since β1 ασ ∈ K0 , but β1 ασ
D(β2 α) ∩ M , and D(β4 α) ∩ M , but β1 α ∈

21

was removed so as to ensure normality of K1 ; this in turn removed β1 α, which now causes removal of
strings α, β2 α, β4 α altogether. Continuing,
F (K1 ) ∩ K1 = {ǫ, γ, β3 γ, β4 , β4 γ}
= K1 − {α, β2 α, β4 α}.

Removing strings α, β2 α, β4 α does not destroy normality of K1 . Indeed F (K1 ) ∩ K1 is normal with
respect to C ∩ M and we have
K2 = sup N (F (K1 ) ∩ K1 , C ∩ M )
= {ǫ, γ, β3 γ, β4 , β4 γ}
= F (K1 ) ∩ K1 .

This completes the second iteration j = 2.
Since K2 $ K1 , we proceed to j = 3 as follows:
F (K2 ) = {s ∈ K2 | D(s) ∩ M ⊆ K2 }
= {ǫ, γ, β3 , β3 γ, β4 , β4 γ} = K2 ;
F (K2 ) ∩ K2 = K2 ∩ K2 = K2 ;
K3 = sup N (F (K2 ) ∩ K2 , C ∩ M )
= sup N (K2 , C ∩ M ) = K2 .

Since K3 = K2 , the limit of the sequence in (10) is reached. Therefore
K3 = {ǫ, γ, β3 γ, β4 , β4 γ}

is the supremal C -observable sublanguage of C .
B. A Case Study of Computing sup CO(C)
Consider the same case study as in [3, Section V-B], namely a manufacturing workcell served by five
automated guided vehicles (AGV). Adopting the same settings, we apply the implemented Γ operator to
compute the supremal relatively observable and controllable sublanguage sup CO(C), as represented by
a finite-state automaton, say SUPO. That is,
Lm (SUPO) = sup CO(C).

For this case study, the full-observation supervisor (representing the supremal controllable sublanguage) has 4406 states and 11338 transitions. Selecting different subsets of unobservable events, the
22

TABLE I.

SUPO COMPUTED FOR DIFFERENT SUBSETS OF UNOBSERVABLE EVENTS IN THE AGV CASE STUDY
Σuo = Σ − Σo

State #, transition # of SUPO

{13}

(4406,11338)

{21}

(4348,10810)

{31}

(4302,11040)

{43}

(4319,10923)

{51}

(4400,11296)

{12,31}

(1736,4440)

{24,41}

(4122,10311)

{31,43}

(4215,10639)

{32,51}

(2692,6596)

{41,51}

(3795,9355)

{11,31,41}

(163,314)

{12,33,51}

(94,140)

{12,24,33,44,53}

(72,112)

{12,21,32,43,51}

(166,314)

{13,23,31,33,
(563,1244)
41,43,51,53}

computational results for the supremal relatively observable and controllable sublanguages, or SUPO,
are listed in Table I. We see in all cases but the first (Σuo = {13}) that the state and transition numbers of
SUPO are fewer than those of the full-observation supervisor. When Σuo = {13}, in fact, the supremal
controllable sublanguage is already observable, and is therefore itself the supremal relatively observable
and controllable sublanguage.
Moreover, we have confirmed that the computation results agree with those by the algorithm in [3].
Thus the new computation scheme provides a useful alternative to ensure presumed correctness based on
consistency.
VI.

C ONCLUSIONS

We have presented a new characterization of relative observability, and an operator on languages whose
largest fixpoint is the supremal relatively observable sublanguage. In the case of regular languages and
based on the support relation, we have proved that the sequence of languages generated by the operator
converges finitely to the supremal relatively observable sublanguage, and the operator is effectively
23

computable.
Moreover, for the purpose of supervisory control under partial observation, we have presented a second
operator that in the regular case effectively computes the supremal relatively observable and controllable
sublanguage. Finally we have presented an example and a case study to illustrate the effectiveness of the
proposed computation schemes.
R EFERENCES
[1]

R. D. Brandt, V. Garg, R. Kumar, F. Lin, S. I. Marcus, and W. M. Wonham. Formulas for calculating supremal controllable
and normal sublanguages. Systems & Control Letters, 15(2):111–117, 1990.

[2]

K. Cai and W. M. Wonham. A new algorithm for computing the supremal relatively observable sublanguage. In Proc.
Workshop on Discrete-Event Systems, pages 8–13, Xi’an, China, 2016.

[3]

K. Cai, R. Zhang, and W. M. Wonham. Relative observability of discrete-event systems and its supremal sublanguages.
IEEE Trans. Autom. Control, 60(3):659–670, 2015.

[4]

H. Cho and S. I. Marcus. On supremal languages of classes of sublanguages that arise in supervisor synthesis problems
with partial observation. Math. of Control, Signals, and Systems, 2(1):47–69, 1989.

[5]

R. Cieslak, C. Desclaux, A. S. Fawaz, and P. Varaiya. Supervisory control of discrete-event processes with partial
observations. IEEE Trans. Autom. Control, 33(3):249–260, 1988.

[6]

S. Eilenberg. Automata, Languages and Machines. Volume A, Academic Press, 1974.

[7]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

[8]

F. Lin and W. M. Wonham. On observability of discrete-event systems. Inform. Sci., 44(3):173–198, 1988.

[9]

W. M. Wonham. Supervisory Control of Discrete-Event Systems. Systems Control Group, Dept. of Electrical and Computer
Engineering, University of Toronto, updated annually 1998-2016. Available online at http://www.control.toronto.edu/DES,
2016.

[10]

W. M. Wonham and P. J. Ramadge. On the supremal controllable sublanguage of a given language. SIAM J. Control and
Optimization, 25(3):637–659, 1987.

24

