Minimization of number of states of FSMs is a classical topic of most undergraduate textbooks [114, 127, 125, 186] on logic design and sequential machines. It consists of merging groups of compatible states of a machine into single states of the new machine, in order to achieve an equivalent machine with reduced (and possibly minimal) number of states. It is assumed, that a machine with less states yields better realization. Compatible are the states that exhibit identical input/output behavior. Problem is difficult in the general case since the groups of compatible states are not disjoint and compatibility of some group of states can imply compatibilities of other groups of states. A number of mathematically interesting papers have been published [185, 134, 145, 184, 71, 3, 14, 16, 63, 64, 165, 152, 153, 107, 169, 84, 85, 86, 124]. However, it seems that no system is used in American industry, which would apply this advantageous option. This is to the contrary of practise in Europe and Soviet Union, where the present author has had an opportunity to observe several systems of this type in industrial applications. In USA responsible managers do not see a need for this kind of systems. Why is it so? In my opinion there are two reasons for it. First of them is that in the States the high level (architectural) design is often separated from logic minimization/layout design and is done by separate groups of engineers. When the "logic minimization people" receive the specification of the circuit from the "architecture people" they do not see many possibilities for improvement, for instance those that can result from introducing don't cares or minimizing the machine. The machines are small, because the initial decomposition is done intuitively by architecture designer. The other reason is that there never was a large market for industrial control systems realized as FSMs, since the programmable controllers and microprocessors took it early. In Eastern Europe for instance, these types of sequential circuits, which are usually very large, were realized as finite state machines with PLAs, so a need for software for state minimization and state assignment for machines of hundreds states existed.
It is expected that a need for state minimization will be more evident when the new high level tools for FSM description (like for regular expressions, Petri Nets , parallel program schemata) will be incorporated into CAD systems and conversions to state tables will be done automatically. For instance, minimization of a completely specified machine is a part of procedures for: conversion of regular expression to FSM state table, convertion of parallel automaton, nondeterministic automaton or Petri Net to state table, equivalence verification of two FSMs [172] and many others. Various new algorithms lead to state tables that are strongly incomplete (have many don't cares) and therefore can be substantially minimized (for instance, when the invariants of the flow-graph are used to create don't cares in the state table).