Symbolic two-dimensional minimization of strongly unspecified finite statemachines

A generalization of the classical state minimization problem for finite sta te machine (FSM) is proposed and discussed. In contrast to classical state minimization algorithms that minimize in one dimension (states), our algori thm 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 i nput decomposition of the FSM. A modified formulation of the state minimiza tion problem is also introduced, and an efficient branch-and-bound program, FMINI, is presented. FMINI produces an exact minimum result for each compo nent minimization process and a globally quasi-minimum solution to the enti re two-dimensional (2D) FSM minimization problem. For some benchmarks, espe cially 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 th ose produced by the state minimization alone. (C) 2001 Elsevier Science B.V . All rights reserved.