ON PERIODICITY OF SEQUENTIAL MACHINES.

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)

Document Details

Document Type
Technical Report
Publication Date
Aug 06, 1970
Accession Number
AD0712596

Entities

People

  • Ratan K. Guha
  • Raymond T. Yeh

Organizations

  • University of Texas at Austin

Tags

DTIC Thesaurus Topics

  • Chemical Reactions
  • Decomposition
  • Periodic Variations

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.
  • Linear Algebra