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) : Zeigler,Bernard P.

Report Date : MAY 1970

Pagination or Media Count : 21

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)

Descriptors :   (*DIGITAL COMPUTERS, THEORY), (*MATHEMATICAL LOGIC, THEOREMS), COMPUTER LOGIC, MAPPING(TRANSFORMATIONS), AUTOMATA

Subject Categories : Computer Hardware
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE