Optimum and heuristic algorithms for finite state machine decomposition and partitioning

The authors formulate the problem of optimum two-way finite-sole-machine (FSM) decomposition as one of symbolic-output partitioning and show that this is an easier problem than optimum state assignment. They describe a procedure of constrained prime-implicant generation and covering that represents an optimum FSM decomposition algorithm under the specified cost function. Exact procedures are not viable for large problem instances. The authors give a novel iterative optimization strategy of symbolic-implicant expansion and reduction, modified from two-level Boolean minimizers, that represents a heuristic algorithm based on their exact procedure. Reduction and expansion are performed on functions with symbolic, rather than binary-valued, outputs. Preliminary experimental results that illustrate both the efficacy of the proposed algorithms and the validity of the selected cost function.<>