THEORY AND ALGORITHMS FOR STATE MINIMIZATION OF NONDETERMINISTIC FSMS

This paper addresses state minimization problems of different classes of nondeterministic finite-state machines (NDFSM's), We describe a ful ly implicit algorithm for state minimization of pseudo nondeterministi c FSM's (PNDFSM's), The results of our implementation are reported and shown to be superior to a previous explicit formulation. We could sol ve exactly all but one problem of a published benchmark, while an expl icit program could complete approximately one half of the examples, an d in those cases, with longer run times. Then we present a theoretical solution to the problem of exact state minimization of general NDFSM' s, based on the proposal of generalized compatibles. This gives an alg orithmic framework to explore behaviors contained in a general NDFSM.