Supervisory Control - The Unknown Component Problem: Theory and Applications - page 237

P \ C D S ,itis ˛ˇ 2 C ; moreover, ˛ 2 C , because C is prefix-closed. Thus,

˛ 2 P \ C and P \ C ¤ S . So we contradict that C is a controller, completing

our reduction ad absurdum . t

If S is prefix-closed, S P is also a sufficient condition for solvability.

Corollary 15.5. If is prefix-closed then a solution of the supervisory control

problem exists if and only if

S

S P .

Proof. If S is prefix-closed then S D Pref .S / ,so P \ Pref .S / D S if and only if

P \ S D S if and only if S P . t

15.2.2.2 Equation Solving Approach

Casting the problem as solving equations over languages, we must solve the
language equation P \ X D S , restricting X to be a prefix-closed language.

According to Proposition 15.3 (when S and P are prefix-closed languag es) , if

P \ X D S S L P [ S

is a solution. In the following we extend the solvability and characterization results
to the case when

is solvable then each prefix-closed language L such that

are not prefix-closed.
From the theory of equations over languages, we obtain the following solvability
condition based on the largest solution, whereas in Theorem 15.4 solvability was
obtained according to the existence of the smallest solution.

S and P

Corollary 15.6. A so lution of the supervisory control problem P \ X D S exists

Pref

if and only if P \ .P [ S/ D S .

Pref

This is a consequence of Theorem 2.12 or Theorem 2.1 6, wher e .P [ S/ is the

largest prefix-closed sublanguage of the largest solution P \ S D .P [ S/ .

Since Pref .S / is the smallest prefix-closed language that contains S ,and .P [

S/

Pref

is the largest prefix-closed sublanguage contained in the largest solution P [ S

of the equation P \ X D S , the following statement holds.

Theorem 15.7. A prefix-closed language L is a solu tio n of the supervisory control

problem P \ X D S , if and only if Pref .S / L .P [ S/

Pref .

Pref

Proof. If If L is a prefix-closed language s uc h that Pref .S / L .P [ S/

Pref

then S D P \ Pref .S / P \ L P \ .P [ S/ D S ,so P \ L D S is a

solution of P \ X D S .

P \ X

D S

P \ L D S L S

Only If If L is a solution of , i.e., ,then . Given that

L is prefix-closed, and the fact that Pref .S / is the smallest prefix-closed language

L Pref containing S , it follows that .S / .

\ X D S [ S

L P

[ S

The largest solution of P is P , therefore it must be .

Pref

.P [ S/

Given that L is prefix-c los ed, and the fact that is the largest prefix-closed

Pref , it follows th at Pref .

[ S/

L .P

[ S/

language contained in .P

Pref

Pref

.S / L .P

[ S/ P [ S t

Finally, S .