A Method for Minimizing Incompletely Specified Sequential Machines

After Paull and Unger introduced the problem of state minimization in incompletely specified sequential machines (ISSM´s), its increasing importance and complexity induced many people to continue research related to this field. Here we shall present a method for obtaining a minimum form of a given ISSM by application of a directed tree graph. In order to save counting effort for a minimum form, we extend the concept of erasure from a relation between compatibles to one between subsets of compatibles. The use of the extended erasure rules can prune the directed tree graph effectively to find a minimum form of a given ISSM. Furthermore, by utilizing the concept of maximal incompatible (MI) we can determine a lower bound for the state number of the minimum form of a given ISSM, and also effectively control the initial steps in generating the directed tree graph.