Exploitation of Flexibility in Sequential Networks - The Unknown Component Problem: Theory and Applications - page 219

Definition 14.2.1. A set of states is a compatible if and only if there exists an FSM
whose initial state is a reduction of each state in the set.
The intuition is that a set of states is a compatible if they can be merged into a single
state in such a way to obtain an FSM that is a reduction of the original FSM. The
following theorem serves as an equivalent, constructive definition of compatibles.
Theorem 14.1. Aset c of states is a compatible if and only if for each input i ,
there exists an output o such that
1. Each state in c has a transition under input i and output o
2. From the set c of states, the set c 0 of next states under i and o is also a compatible
Definition 14.2.2. A set of compatibles covers the reset state(s) if at least one
selected compatible contains a reset state.
Definition 14.2.3. AsetC of compatibles is closed if for each compatible c 2 C ,
for each input i , there exists an output o such that:
1. Each state in c has a transition under input i and output o
2. From the set c of states, the set d of next states under i and o is contained in a
compatible in C
Here we restate a main theorem for state minimization of PNDFSMs.
Theorem 14.2. The state minimization problem of a PNDFSM reduces to the
problem of finding a minimum set of compatibles that covers the reset state(s) and
is closed.
As in the case of ISFSMs, it is sufficient to consider a subset of compatibles, called
prime compatibles, for PNDFSM minimization.
Definition 14.2.4. A compatible c 0 prime dominates a compatible c if for each
minimum closed cover containing c, the selection with c replaced by c 0 also
corresponds to a minimum closed cover.
Definition 14.2.5. A compatible c is a prime compatible if there does not exist
another compatible c 0 such that c 0 prime dominates c.
Theorem 14.3. There exists a minimum closed cover made up entirely of prime
compatibles.
The above theorem justifies that prime compatibles are sufficient to find a minimum
solution, although there may exist other minimum solutions.
State minimization of incompletely specified FSMs (a special case of observable
FSMs) has been shown to be an NP-hard problem [115]. Therefore even for
problems represented with two-level descriptions involving a hundred states, an
exact algorithm may be computationally infeasible. Methods for recasting the
computations as operations on BDDs have been proposed and implemented in
the program ISM [65, 67, 135], for which interesting experimental results were
reported. Still the fundamental limitation remains that ISM works on a state-based