Accession Number:

AD0707955

Title:

PROOF OF A CONJECTURE BY A. W. BURKS AND H. WANG: SOME RELATIONS BETWEEN NET CYCLES AND STATES CYCLES.

Descriptive Note:

Technical rept.,

Corporate Author:

MICHIGAN UNIV ANN ARBOR DEPT OF COMPUTER AND COMMUNICATION SCIENCES

Personal Author(s):

Report Date:

1970-05-01

Pagination or Media Count:

21.0

Abstract:

In a foundational paper on the theory of automata A. W. Burks and H. Wang 1957 conjectured that a certain complexity measure involving the size of the strong components of a logic net formed a hierarchy for net behavoir. A strengthened version of the conjecture is proved by establishing that any logic net can be interpreted as a series parallel composition of nets associated with its strong components. Some properties of the periodic behavior of machines, shown to be preserved under simulation and composition operations, are used to complete the proof. The relationship of this approach to algebraic proofs of series parallel irreducibility is discussed. Author

Subject Categories:

  • Computer Hardware
  • Bionics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE