A Linear Decomposition for Sequential Machines

This paper considers the loop-free decomposition of nonautonomous, synchronous, deterministic, nonlinear sequential machines into linear and nonlinear component machines. Two methods are derived which generate the desired decomposition and determine the state code assignment consistent with the linear realization of a component machine. Both processes are well suited for implementation by a digital computer. One of the procedures for decomposition and code assignment is analytic (in that trial and error processes are not required) and it discovers the largest possible linear component machine. In this decomposition the linear component machine is the predecessor of the nonlinear component machine. The other method, which may require iteration in some cases, yields a decomposition in which the nonlinear machine is the predecessor of the linear machine.