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
Distribution Statement : APPROVED FOR PUBLIC RELEASE