STAMINA

A method for minimizing Moore finite-state machines by merging two states. The problem of minimization of Moore Finite-State Machines (FSMs) is considered. This problem often arises in designing digital devices based on programmable logic devices. The proposed approach uses the operation of merging of two states of an FSM and the representation of the FSM as a list of transitions. Conditions guaranteeing the identical operation and deterministic behavior of the transformed FSM obtained by merging two states are given. The cases when wait states can emerge are also discussed. Algorithms for minimizing the number of internal states, transition paths, and the number input variables of Moore FSMs are described. Experimental results have shown that the proposed approach reduces the number of internal states by 6% on the average and sometimes by a factor of 1.86; the number of transitions is reduced by 20% on the average and sometimes by a factor of 2.83. The use of the proposed method in combination with the STAMINA computer program reduces the number of internal states by 16% on the average and sometimes by a factor of 2.17; the number of transitions is reduced by 41% on the average and sometimes by a factor of 7.97. In conclusion, important directions of research concerning the minimization of FSMs are discussed.