Accession Number : AD0712596

Title :   ON PERIODICITY OF SEQUENTIAL MACHINES.

Descriptive Note : Technical rept.,

Corporate Author : TEXAS UNIV AUSTIN ELECTRONICS RESEARCH CENTER

Personal Author(s) : Guha,Ratan K. ; Yeh,Raymond T.

Report Date : 06 AUG 1970

Pagination or Media Count : 38

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 Sperner's theorem. The bound is exact for transient-free machines. (Author)

Descriptors :   (*DIGITAL COMPUTERS, DESIGN), (*MATHEMATICAL LOGIC, AUTOMATA), COMBINATORIAL ANALYSIS, GRAPHICS, SET THEORY, THEOREMS

Subject Categories : Theoretical Mathematics
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE