Use of Decomposition Theory in the Solution of the State Assignment Problem of Sequential Machines
H. Allen Curtis · Journal of the ACM · 1963
An important phase of the design of finite state sequential macilines is the assignmen~ of binary variables to represent their internal states.J. Hartmanis, in a number of papers [1-5], has solved the problem of making such assigmnents economically for seqaential machines which can be decomposed into two or nmre simpler sequential machines or which have reduced dependency relations among their internal state variables.The present, author [61 refined some of the methods and theories of Hartmanis in making assignments for sequential machines with multiply-reduced state variable dependency.In the present paper the methods and theories of the aforementioned papers are extended with the aid of the principles of decomposition theory as developed by Ashenhurst [71 and by this author in [8, 91.The extensions are applicable to sequential machines whose internat state vari~bles can be expressed as composite functions with certain decompositional structures; such maehines encompass those with reduced state variable dependency and hence those which are decomposable into a set of simpler sequential machines.How the results of this paper can be further generalized to provide economical solutions to the state assignment problem for all finite state sequential machines is discussed.