Symbolic Two-Dimensional Minimization of Strongly Unspecied Finite State Machines.

Abstract | A generalization of the classical state minimization problem for Finite State Machine (FSM) is proposed and discussed. In contrast to classical state minimization algorithms that minimize in one dimension (states), our algo-rithmminimizes the FSM in two dimensions: the numbers of both input symbols and internal state symbols are minimized in an iterative sequence of input min-imization and state minimization procedures. This approach leads to an input decomposition of the FSM. A modied formulation of the state minimization problem is also introduced, and an eÆcient branch-and-bound program, FMINI, is presented. FMINI produces an exact minimum result for each component minimization process and a globally quasi-minimum solution to the entire two-dimensional FSM minimization problem. For some benchmarks, especially those with a high percentage of don't cares, as those that occur in Machine Learning, this approach produces a more optimum results than those produced by the state minimization alone.