Computation of Flexibility in Sequential Networks - The Unknown Component Problem: Theory and Applications - page 173

and so there are no don't care transitions from state b 2 ,since DC a 0 \DC a 1 Df u 3 g\
f u 1 gD; . In other words, all missing transitions are added as don't care transitions,
i.e., they are directed to the DNC state. The obtained incompletely specified FSM
M B is shown in Fig. 10.10 d.
Each reduction of M B can replace the component FSM M B , e.g., we can replace
M B by the reduction FSM M B R with a single state that is portrayed in Fig. 10.10 e.
This procedure has the advantage that it works directly on machine M B (or M A )and
can obtain a result that is no worse than the original machine.
An FSM that is a reduction of the ISFSM obtained by the Yevtushenko-
Zharikova's procedure is a reduction of the ISFSM obtained by the Wang-Brayton's
procedure, but the vice versa does not always hold. Indeed, the Wang-Brayton's
procedure allows more flexibility.

Problems

10.1. Refer to the example with FSMs MA.aut and MB.aut computed in
Sect. 10.1 . It is claimed there that the largest solution xfsm min.aut contains
the solution MBifsm.aut obtained by the K&N script . Show that it is the case.
10.2. Comparisons of procedures to compute flexibility
Consider the example shown in Fig. 10.10 .

(a) Compute the flexibility for FSM M B according to the procedure of Wang-

Brayton/Kim-Newborn.
(b) Compute the maximum flexibility for FSM M B solving the FSM equation M A
M X D M A M B .
(c) Compare

these results with the flexibility computed by Yevtushenko-

Zharikova's procedure.