The programs for state minimization can be divided into two categories:
for completely specified machines and for incompletely specified
machines.
The first problem is relatively easy. The compatibility
relation on states of the machine [114] is in such a case
an equivalence relation and therefore efficient
algorithms have been found [97, 114].
The problem to minimize an incompletely specifed machine is much more
difficult, and the solution is not unique to an isomorphism
(as it is for the completely specified machines).
Very little information on programmed state minimization algorithms
can be found in literature available in the U.S.
All papers attempt to find a minimum solution
and use a variant of covering/closure algorithm for
groups of compatible states (so called compatibles ).
The point is to select such a subset of
compatibles, that is full and closed, which means that all state
numbers of the initial machine are included in some groups, and that
each group implied by some selected group is also selected.
Improved variants of the classical
algorithms were created but not programmed. The only published
references to fast approximate
programs for large machines are [11, 12] and [141].
Both these algorithms are based on the branch-and-bound
principle to find a closed and complete subset of groups of compatibles
The program described in [141]
minimizes 7-8 state machines (20-30 compatibles) in 6-10 second
of Cyber. Generation of solutions for 10-state machines
required 60-100 seconds.
These programs cannot yet be used for interactive design of FSMs with more
than 30 - 40 states on Vax-class machines.
A lot of basic research and especially programming effort is necessary to design practical state minimization algorithms for machines with hundreds of states, inputs and outputs, that occur in current circuits, like for instance control units of microprocessors.