Accession Number:

AD0712596

Title:

ON PERIODICITY OF SEQUENTIAL MACHINES.

Descriptive Note:

Technical rept.,

Corporate Author:

TEXAS UNIV AUSTIN ELECTRONICS RESEARCH CENTER

Personal Author(s):

Report Date:

1970-08-06

Pagination or Media Count:

38.0

Abstract:

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

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE