About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SWCT 1962
Conference paper
Some theorems for incompletely specified sequential machines with applications to state minimization
Abstract
Let M be an incompletely specified aequential machine and Q be the set of internal states of M. We derive certain properties for classes of subsets of Q with particular emphasis on certain classes of compatible sets of states, subsequently called C-classes for M We then briefly describe state minimization algorithms using these properties. The following types of theorems are proved: From an arbitrary incomplete machine M a machine M ∗ is constructed which is transition complete, i. e., has a transition defined for every state and every input. Given a special type of partition of Q we construct from M a machine M ' whose states correspond to the members of the partition. Relations between the C-classes of M and M ' are given, anc in particular. sufficient conditions are given for which the state minimization problems for M and A' are equivalent. Through the use of a class of sets of states "generated" by a given set of states of M and a restricted type of compatibility relation between sets of states, certain sets of compatible states are shown not to be elements of any minimum C -class for M. Conditions are given on compatible sets S and S' of Q, where 5' ⊂ S. such that if S is an element of a C-class Σ for M, then (Σ - {S}) {S'} is a C-clus for M. Using these results, which restrict the family of C -classes one needs to consider, algorithms are described for two state -minimization problems.