Symbolic two-dimensional minimization of strongly unspecified finite state machines

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 algorithm minimizes the FSM in two dimensions: the numbers of both input symbols and internal state symbols are minimized in an iterative sequence of input minimization and state minimization procedures. This approach leads to an input decomposition of the FSM. A modified formulation of the state minimization problem is also introduced, and an efficient 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 (2D) FSM minimization problem. For some benchmarks, especially those with a high percentage of donʹt cares, as those that occur in machine learning (ML), this approach produces a more optimum result than those produced by the state minimization alone.