PROOF OF A CONJECTURE BY A. W. BURKS AND H. WANG: SOME RELATIONS BETWEEN NET CYCLES AND STATES CYCLES.
MICHIGAN UNIV ANN ARBOR DEPT OF COMPUTER AND COMMUNICATION SCIENCES
Pagination or Media Count:
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
- Computer Hardware