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.
Paper
On some properties of the semigroup of a machine which are preserved under state minimization
Abstract
Some results on special types of semigroups of transformations of a set (including permutation groups) are developed and combined with the fundamental results of Paull and Unger on state minimization of incompletely specified sequential machines to obtain some properties of the transformation semigroup of such a machine which are preserved in all minimum state machines (strong preservation), or in at least one (weak preservation) minimum state machine. The principal results are that for permutation machines (those whose states are permuted by every input) there is strong preservation and for simple machines (those whose semigroups have no proper ideals) there is weak preservation. A number of further properties of permutation machines in the satisfaction and minimum state relations are developed. © 1967 Academic Press Inc.