ON PERIODICITY OF SEQUENTIAL MACHINES.
TEXAS UNIV AUSTIN ELECTRONICS RESEARCH CENTER
Pagination or Media Count:
It was shown by Gill and Flexer that the necessary and sufficient condition for the existence of non-trivial periodic decomposition of a sequential machine corresponds to the existence of a non-trivial cyclic partition. The authors have, in this report, characterized the existence or nonexistence of cyclic partitions of machines under various connectedness conditions. Their theory is generalized here using the concept of cyclic covers. As a consequence of this generalization, the open problem posed by Gill and Flexer is solved. Upper bounds of periodicity of sequential machines are obtained using Sperners theorem. The bound is exact for transient-free machines. Author
- Theoretical Mathematics
- Computer Hardware