HEURISTIC STATE REDUCTION METHODS OF INCOMPLETELY SPECIFIED MACHINES PRECEDING TO SATISFY COVERING CONDITION

This paper presents two kinds of simplification methods for incomplete ly specified sequential machines. The strategy of the methods is that as many states in original machines are covered in the simplification processes as possible. The purpose of the methods is to derive a simpl ified machine having either the largest maximal compatible set or its subset. With the methods, one of the minimal machines can not be alway s derived, but a near-minimal machine can be obtained more quickly wit h less memory, since they need not derive all the compatible sets. In this paper, the effectiveness of the methods is checked by applying th em to simplification problems of incompletely specified machines gener ated by using random numbers, and of the MCNC benchmark machines. The experimental results show that our methods can derive a simplified mac hine quickly, especially for machines having a great number of states or don't care rate.