On periodicity of sequential machines

摘要

It was shown by Gill and Flexer [3] that the necessary and sufficient condition for the existence of nontrivial periodic decomposition of a sequential machine corresponds to the existence of a nontrivial cyclic partition. We have, in this paper, characterized the existence or nonexistence of cyclic partitions of machines under various connectedness conditions. Also, their theory is generalized here utilizing the concept of cyclic covers. As a consequence of this generalization, the open problem posed by Gill and Flexer [3] is solved. Upper bounds of periodicity of sequential machines are obtained using Sperner's theorem [4].