Decomposition of Asynchronous Sequential Switching Circuits

The problem of decomposing an asynchronous sequential circuit into the serial connection of two asynchronous sequential circuits is considered. Six types of serial connections are defined, and necessary and sufficient conditions are derived for making five of the six types of serial decomposition, while sufficient conditions are derived for the sixth. Systematic and constructive procedures are presented for making each of the decompositions. These results are an extension of the work of Hartmanis and Stearns [1] who used partitions for making decompositions of synchronous circuits. The procedures derived can also be used for making arbitrary loop-free decompositions of asynchronous circuits [7].