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
Distribution Statement : APPROVED FOR PUBLIC RELEASE