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

every reduction of the largest solution is a solution of the equation. In particular,
when the context FSM M Context and the specification FSM M spec are complete and

deterministic FSMs, the following properties hold:

1. If M Context is a Moore FSM, then each complete reduction of the largest solution

of the equation M Context M X Š M spec is a solution of the equation.

2. Each complete deterministic reduction of the largest solution that is a Moore
FSM is a solution of the equation.

These sufficient conditions may be used to select a reduction of the largest solution,
forcing the rule that a Moore component FSM can be replaced only by a reduction
of the largest solution that is a Moore FSM. As discussed in Sect. 3.1.2, the
largest Moore solution is a submachine of the largest solution that is computed by
Procedure 3.1.5. If the component FSM used for replacement is not a Moore FSM
and the context is a Moore FSM, then any complete deterministic reduction of the
largest solution can be selected as a replacement.
In Chap. 14 we will discuss the issue of extracting an optimal solution from
the pool of all solutions contained in the largest solution. Useful cost functions
to measure a solution are the number of states or the number of connection
lines. Suppose that for a realistic cost function it is feasible to extract a behavior
minimizing the chosen cost, the problem arises of how to resynthesize a given
network of FSMs replacing legally the individual components. We propose a scheme
of iterative FSM equation solving, which requires the solution of an appropriate
sequence of FSM equations.
To illustrate the idea, suppose that we start with the component FSM M A 1 and

assume that all other component FSMs are optimal. Then we collapse all other
component FSMs into a single context FSM M Context Š M A 2 M A n and solve

the equation M Spec Š M A 1 M A n ,inorderto

capture all FSMs which can replace the component FSM

M X M Context Š M Spec ,where

M A 1 without changing the
external behavior of the overall circuit. The largest solution of the equation contains
each possible behavior; we select a reduction of the largest solution of minimum
cost that is a solution of the equation. Then we iterate on each component FSM
M A 2 ; :::;M A n in order to replace it with a corresponding component of minimum
cost in the composed system. Finally we return to FSM M A 1 and repeat the process

until none of the component FSMs can be reduced.
Summarizing, we resynthesize iteratively each component FSM assuming that
all other components are already optimal. The component FSM is modified while
checking for improvement and conformance. The former is measured by the
optimization cost function, whereas the latter is verified by solving its related FSM
equation.

Example 12.2. For the network topology shown in Fig. 12.1 , consider the FSMs
instances

M A , M B and M C given in Fig. 12.2 a-c. The largest solution of the

equation M X .M A M C / Š M A M B M C shown in Fig. 12.2 e has three states,

M B

and has a reduction with a single state shown in Fig. 12.2 g. By noticing that the

M B transitions of depend essentially only on input I , we can remove input U from