The Cascade Decomposition of Sequential Machines

Abstract

This paper studies composite sequential machines obtained from smaller component machines by their connection in cascade, that is, the outputs from one component are the inputs to the next. Given the specification of a deterministic, completely specified, synchronous, sequential machine (Mealy model), a criterion is derived for such a specification to be decomposable into specifications of smaller machines, the cascading of which will lead to a realization of the original machine required. A simple technique, based on homomorphisms between directed graphs, is arrived at for the actual breaking up of a decomposable specification. A number of additional problems related to sequential machine decompositions are pointed out as concluding remarks.