PROOF OF A CONJECTURE BY A. W. BURKS AND H. WANG: SOME RELATIONS BETWEEN NET CYCLES AND STATES CYCLES.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1970
- Accession Number
- AD0707955
Entities
People
- Bernard P. Zeigler
Organizations
- University of Michigan