A new method for the state reduction of incompletely specified finite sequential machines

A new method for the state reduction of incompletely specified finite sequential machines is proposed. Fundamental theorem of minimization theory states that, given an incomplete state table, another state table specifying the same external behavior corresponds to each closed set of compatibility classes which covers all internal states of the given table. The new heuristic algorithm builds up a closed cover for a given state table selecting maximal compatibles (MCs) one by one until both covering and closure requirements are satisfied. Near-minimal solutions are also incrementally generated. The process is dynamic as the consequences of adding a particular MC are precisely determined. The new algorithm is designed for speed and has proven to be extremely valuable in situations where fast but good optimization is required. The algorithm has been programmed and results on a wide set of machines shown