HSM2: A New Heuristic State Minimization Algorithm for Finite State Machine

This paper proposes a heuristic state minimization algorithm (HSM2) for finite state machines (FSM). HSM2 focuses on the generation and adjustment of the closed cover. First an initial closed cover is generated by heuristically selecting proper maximal compatibles to satisfy all the covering and closure conditions, and then it is adjusted to be a minimal or near minimal closed cover by heuristically removing repeated states. Experimental results show that the algorithm is faster and obtains better or the same solutions compared with conventional methods.