THE UN IV ER S I TY OF M I C H I GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report PROOF OF A CONJECTURE BY A. W. BURKS AND H. WANG: SOME RELATIONS BETWEEN NET CYCLES AND STATES CYCLES Bernard P. Zeigler with assistance from: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-12236 Bethesda, Maryland and Department of the Navy Office of Naval Research Contract No. N00014-67-A-0181-0011 Washington, D C'. and U. S. Army Research Office (Durham) Grant No. DA-31-124-ARO-D-483 Durham, North Carolina and National Science Foundation Grant No. GJ-519 Washington, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR May 1970

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 logical net formed a hierarchy for net behavior. A strengthened version of this conjecture is proved by establishing that any logical 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. Iii

I. Introduction In this paper I establish a conjecture made by Burks and Wang (1957) concerning the strong components of digraphs representing logical nets. These strong components were called cycles and the degree of a cycle was defined as the number of points (hence delays) contained in it. A net was said to be of degree d if it had at least one cycle of degree d and no cycles of higher degree. Burks and Wang made the conjecture: For any degree d, there is some transformation not realized by any net of degree d. In our current terminology "transformation" means transition function and the realization in question is isomorphic state behavior realization (e.g., Hartmanis and Stearns, 1968). The conjecture is true and moreover turns out to hold even when the word "realized" is replaced by "simulated" in its statement. In other words, I shall show that there is no upper bound on the highest degree needed so that all nets of this or lower degree can simulate any finite transition function. That this is the case is indeed surprising since arbitrary memory expansion and slowing of computation rate is allowed by the simulation concept. It is also notable that this "invariance" under memory and time scale expansion is not characteristic of other interesting measures of feedback complexity (Zeigler, 1969). The proof consists, in the first place, in establishing a correspondence between the strong components of a net and the component machines of a

series parallel (cascade) composition. Once this is done, one alternative is to invoke certain little stressed results of the decomposition theorems of Krohn and Rhodes (1965) to complete the proof. In this alternative, one relies essentially on the irreducibility of simple groups. Instead, I shall present a direct proof of the main result which uses entirely machine (rather than semigroup) concepts. In this respect, there is a similarity with the proof of irreducibility given by Ginzburg (1968). However, even though his proof is machine oriented, it still makes heavy use of basic group theory ideas. The present proof is of additional interest because of the attention given to the properties of state cycles in the transition diagram and their behavior under simulation and composition operations. Studies of the relation between net structure and the cyclic properties of net behavior have been initiated in connection with neural and genetic network models (e.g., Kaufman, 1969; Walker and Ashby, 1966). From the semigroup point of view, I shall be concerned in effect with the cyclic (singly generated) subgroups of the machine semigroup and the irreducibility of the cyclic groups of prime order. The restriction to this subclass may explain the ability to carry through fully machine oriented proofs. II. Basic Concepts A machine (automaton, transducer) is a quintuple A = <S,Q,O,M,N> where S(input symbols), Q(states), O(output symbols) are finite sets, M: Q x S ~ Q is the transition function and N: Q ~ O is the output function. Given a transition function M we are interested in machines which can

simulate M via their input-output relations. To do this we need only consider the semiautomaton A = <SA,QA,MA>. A = <SA,QA,MA> simulates M: Q x S + Q if there exists Q' A QA and maps g: S -+ S (the free semigroup generated by SA), h: Q' +-Q (onto) such that Q' is closed under g(S) and for all q e Q', s c S. h(MA(q,g(s)) = M(h(q),s);(MA: QA x SA -+Q is the usual extension to S* of MA) A A Here g represents the input encoding and h the output map of the simulation. When g: S + SA we say that A homomorphically realizes M, and further when h is one-one A isomorphically realizes M. Definition 1 A composition over a finite set of machines {AA = <Sa,Qa,Ma >IaD} is specified by a set S, a family of subsets {I C DlacD} and a family of maps {Za IaD} where Za: QI x S as This structural description uniquely defines a machine A = <S,Q,M> where Q = X Q, and for all qeQ, s~S, acD proj aM(qs)) = M (proja (q),Z (projI (q),s)). a Here projD, (q) is the projection of q on the co-ordinate subset D' C D. Interpretively, Ia is the set of machines directly influencing Aa and Z is the connecting map specifying the next input to A in terms of the next external input S and the present states of the machines indexed by I. In particular, a logical net (digital network, sequential machine realization) is a composition over a set of 2-state delay elements (c.f., Hartmanis and Stearns, 1966). The digraph (directed graph) D(A) representing a composition A has as points the set D, and there is a line from point a to point a just in

case OeI. (The graph theory terminology and concepts used here are taken from Harary, Norman and Cartwright, 1966). A composition over {M aasD} is said to be series-parallel if there exists a linear order on D al,a2,a3,... such that I = ' and for each integer n, Ia C {al'a2' ''a n-1. n one dimensional form in which any line directed to an must come from some point am, m<n, for n>land a1 has no incident lines. For any point asD(A), let Ca denote the strong component containing a i.e., Ca = {BI these is a path (of possibly 0 length) from a to B and back in D(A)}. It is well-known that the set of strong components {CalasD) is a partition of the points of D(A). The condensation of D(A) is the digraph D(A) with points {C aacD} and there is a line from Ca to C8 iff (if and only if) this is the case for some points a'cC,B'ECB (and Ca f C). A digraph D has an (ascending) level assignment if to each a E D there is an integer na (called its level) such that for each line (a,B) in D n < n. Theorem 10.2 of Harary et al states in effect, that the following is a level assignment for an acyclic graph D: Let U be the set of transmitters of D and assign the integer 0 to each point in U. To every point a not in U assign na where na is the length of the longest path to a from any point in U. We call this the longest path length assignment. III. Logical Nets and Series-Parallel Compositions The proof of the Burks-Wang conjecture begins by showing how a logical net A can be considered to be a series parallel composition of component nets associated with the strong components of D(A).

Let A be any logical net and D(A) its representing digraph. It is well known that the condensation of D(A) is acyclic and therefore has an ascending level assignment, which we take to be the longest path length level assignment. For any digraph D with level assignment let L by the subset of points m of D having level m. Clearly, {LmID $ m < m} (where m is the highest level) is a partition of D. We shall employ the following Lemma 1 Let D be an acyclic digraph with level assigned according the longest path length assignment. For any level m _ O, a) there are no lines joining any two points in Lm, b) no point in Lm has any incoming lines from points in Lmi m >m + 1, and c) every point in Lm+l has at least one incoming line from some point in Lm Proof: a) and b) follow directly from the definition of level assignment. To prove c) let L be the longest path from the transmitters to a point P in L We show that point Q immediately preceding P in L has m+l level m. Since Q is in L there is a path of length at least m from the transmitters to Q. The level of Q is then at least m. Suppose it exceeds m. Then there is a path from the transmitters to P (running through Q) with length exceeding m + 1. This contradicts the fact that the level of P is m+l and thus Q has exactly level m. Q.E.D. Corollary 1 Every finite acyclic digraph can be put in the form of a digraph of

a series parallel composition. Proof: For each of the sets Lm of lemma 1, let P(m l)P(m 2),P P (ml) (m,2)(m,3)' '" (m,nm) be an enumeration of its points (where nm is the cardinality of Lm). The digraph represents a series parallel composition for according to the lemma, the ordering of the points P(1,1)'P(1, 2)' P(,nl)'P(2,1)'P(2,2)' '"P(mTi,n ) is such that if there is a line from (i,j) to (k,e) and k 2 1, then i < k, in fact i = k-l, and by definition of L0 no lines are incident on any point with k We need to show that a logical net can be interpreted as a composition over logical nets associated with its strong components. This demonstration, while conceptually straightforward involves a degree of notational difficulty. It consists of 1) defining the logical net A(C ) associated with a strong component Ca of D(A), 2) defining a composition A* over the {A(Ca) IaED(A)} whose digraph is D*(A), and 3) verifying that A and A* are isomorphic. 1) A(C ) will be a composition over the 2-state delay elements in C. The external input to an element a in Ca will consist of the external input to A together with all delay wires incident on Ca not originating within it. a In other words, let I* = {C there is a line from C toCa in D*(A)}and let (I* ) denote the union of the sets CB in I. Then the external input, SC = (I )Q S. a Ca The set of elements within Ca directly influencing a is I' = Ia 1 Ca The new connecting map Z' is the old connecting map Z reinterpreted aZ (proj I (q), proj (Iq)a )) (q),s)

This defines a machine A(Ca) = <Sc,QC PMC > where QC = ECQa and MC determined according to Definition 1. a 2) The composition A* over {A(C.)} will have external input S. The set component machines influencing A(C ) is given by I*. The connecting map a Z ~: 6 CI* QC x S - SC is just the identity mapping. Note that the digraph D(A*) is isomorphic with the condensation D*(A) since it is generated by the sets I. 3) It is now routine to verify that the transition function defined by the composition A* is isomorphic with that of A. In sum, we have shown that a logical net A can be interpreted as a composition over the nets associated with the strong components. The digraph of this composition of D(A) is just the condensation of the original digraph and so is acyclic. Corollary 1 then allows us to conclude that this composition is a series parallel composition. Thus, we have proved Theorem 1 A logical net A is (isomorphic to) a series parallel composition over the set of logical nets associated with the strong components of D(A). IV. State Cycles and Series Parallel Compositions Let M: Q x S -*Q be any transition function and M: Q x S* -+Q its extension to S*. M contains a cycle if there is a q e Q such that k k q = qx (=(q,x)...1) for some x e S* and positive integer k. Let k be the least positive integer for which (1) is true. Let the sequence Z1' Z2' Z3' '" ZkL(x) be the sequence of initial substrings of xk, where Z1 is the first symbol 7

k of xk and Zk,(x) = x. (Here 9(x) denotes the length of x). The sequence of states qZl1 qZ2' qZ3' A' qZk, (x) is called the cycle of x and consists of the states encountered in journey from q back to q in the order of encounter. The number of states in the sequence is its period, T. Clearly, T = kL(x). The x-period, T is the number of states in the subsequence x 1 2 3 k qx, qx, qx,.., qx We note that each of these states must be distinct (since k was the least integer for which (1) held), so that Tx - k...2) and hence T = TxZ(x)...3) (Z(x) may be referred to as the input period). We remark that the cycle of x need not form a cycle in the state diagram of M in the graph theoretic sense i.e., not all qZi need by distinct (although all qx are distinct). We say that M contains a string cycle of string period, p if it contains a cycle of x for some x e S* which has x-period, Tx = p. The following theorem is proved in (Zeigler, 1968). Theorem 2 Let Mi: Qi x Si + Qi be finite transition functions such that M1 simulates M2, with maps h: Q{ +Q2, and g: S2 S. If for some xS q{' sq' '"' qmZ(g(x)) q = Qq is a 2(x)-cycle of Mi with g(x)-period m, then h(ql), h(q'),..., haq') ~~ ~~~~~yl 2~~fi

is an x-cycle of M2 with x-period k dividing m. (Here j: Si + S1 is the unique extension of g to a homomorphism.) Conversely, if ql' q2' *''' qkZ(x) = q is an x-cycle of M2 with x-period k then there exists a g(x)-cycle in h- (ql)J h- (q2)... h (q) in M with g(x)-period m a positive multiple of k. Since homomorphism is a special case of simulation we can state: Cotollary 2 For finite transition functions, M1, M2, if M2 is a homomorphic image of M1 then the string period of any string cycle in M1 is a nonzero multiple of the string period of its homomorphic image. Every string cycle in M2 is the homomorphic image of a string cycle in M1. We shall be considering a series parallel composition A, of arbitrary finite machines A, Al. Let M: Qa QB x S + Q x QB be the transition function of A and Ma: Qa x S -+ Q M: QB x (Qa x S) QB its components. Except for possibly a relabelling of the input alphabet these are the transition functions of A and AS respectively and we need not make any distinction between them. Theorem 3 Let A be a series parallel composition of finite machines A,AB. Let M contain a cycle of x C S* with x-period m. Let the homomorphic projection of the cycle of x on M have x-period k. Then there is a string cycle in MB with string period m/k.

Proof: We must first justify the assumptions made in the statement of the theorem. It is well known that the projection proj:Q - Qa is a homomorphism from M to M. Moreover, the corresponding partition H on Q has S.P. (substitution property) i.e., for all q,q' C Q, s C S, qllq' implies M(q,s)T M(q',s). Thus there is indeed a homomorphic image of the cycle of x lying in M which by assumption has x-period k. By Corollary 2, there is a positive integer n such that m = nk. Let the sequence Z, Z2,..., ZmQ(x) be the initial substrings of xm where Z1 is the initial symbol of xm and Zm=(x) = x Let the cycle of x in M be qZl, qZ2, *.., qZmx) = q. The homomorphic image in Ma is then q'Z1, q'Z2., * 'Z(Zkx =where q' is the image of q under the homomorphism and Z xk kk (x) Every state q C Q has the form q = ([q]~, [q]8) where [q]a is the block of IT containing q. Since II has SP and since qx knq we have qZinaqZjkg(x)+i for all 0 < j < n and 0 < i < kQ(x). We denote k =[qZ Also since the Z. are initial substrings of x we have Zjk2(x)+i - i for all 0 < j < n, 0 < i < kL(x). The sequence 7qZl qZ2,..., q kQx)-1' qZktx), qZkL(x)+l. 10

then becomes ([1], [qZl]B) ([2], [q 2]B)... ([k )(x)-l] [qZk( x)_ )([O] [qxk]), ([1], qxkZl)... ai~~~ B' " ''' kR, O x (, s Let Z. = a a2... ai, 0 < i < k(x). Using the notation ql (qs)q2 1 1I V for M8(ql, (q,s)) = q2 we obtain the following transition sequence in MB starting at [q]B ([ ]a, a2) [q] [qz1] a -... [qz2] a s --.. [Z ([k(x)) x], (ak'(x)) [qxk] ([0, [qxkZ [qzk~ (x) -11 ] ~.......... -k ] B [qZ -.... - a- [qx Z I This sequence is a cycle in MB of the string y e (QI Ia x S)* where y ([o]a, al) ([ a2... ([kk(x)-ll,a akC(x)) Now qxjk, 0 < j < n are all distinct states and recalling that qxjk = ([0~] [qxjk] (i.e., these states all have the same a component) it must be that [qxjk]BO < j < n are all distinct. Thus the existence of the subsequence of the y-cycle [qxk], [qx2k]='., [qxnk] = [qxm] = [q] 11

having n distinct states proves that there is a y-cycle of y-period n = m/k in Mg. Note that R(y) = k1(x) and T = n implies T = nkt(x) = y mQ.(x) which agrees with the period of the x-cycle in M. The basic theorem enabling us to prove the Burks-Wang extended conjecture can be stated: Theorem 4 Let M': Q' x S' - Q' contain a cycle of x e S* with x-period p, a prime number. Assume that M' can be simulated by a series parallel composition of A,A. Then at least one of Ma,M contains a string cycle of string period a non-zero multiple of p. Proof: Let M be the transition function of the composition. Since M' can be simulated by M and given the x-cycle in M', we know by Theorem 2 that there is a string cycle in M of string period m a multiple of p, m = np, n > O.. By Theorem 3, Ma has a projection of this cycle with string period k v 1 and Ma has a string cycle with string period m/k. But since p is a prime either k divides n, in which case MS has a string cycle of period a non-zero multiple of p, or k is a non-zero multiple of p, in which case Ma has a string cycle a non-zero multiple of p. Corollary 3 Let M': Q' x S' - Q' contain a cycle of x e S* x-period p a prime number. Assume that M' can be simulated by a series parallel composition, A of A. A -.., A with transition functions al OL2 "'~an M a: x% X ]..jj xS *Q. ji i x 1i 12

Then at least one of Ma has a string cycle with string period a non-zero multiple of p. Proof: The proof proceeds by induction. The series parallel composition A may be regarded as a series parallel composition of A and a1 a series parallel composition of the A., i>l. Applying Theorem 3 to this situation, the induction may now proceed. Q.E.D. For series parallel composition A of A. A,..., A we define X a2 n size (A) to be the number of states in the largest component machine i.e., size (A) = maxlQ= I ai i where Qa is the state set of A. i 1 Theorem 5 For any integer n, there is a finite transition function which cannot be simulated by a series-parallel composition A, with size (A) < n. Proof: Consider the set of primes which as is known has no greatest member. For any prime p, there is a mod p-counter, namely a machine which counts modulo p occurrences of a symbol e.g., "a" in an input string. The? transition function of this machine has an a-cycle of a-period p. By Gorollary 3 any series parallel composition which can simulate this transition function 13

must have at least one component Aa whose transition function has a string cycle of string period a non-zero multiple of p. But this means that IQaI 2 p since there are at least p distinct states in such a cycle. Thus size (A) > p for any series parallel composition which can simulate a mod p counter. For any integer n, we can choose a prime p > n and so for each n there is -a finite transition function which cannot be simulated by a series parallel composition A with size (A) < n. We note that in particular, for each integer n, there is a finite transition function which cannot be isomorphically realized by any series parallel composition A with size (A) < s. (Thus true because any isomorphic realization is in particular a simulation.) We have seen (Theorem 1) that a logical net A is a series parallel composition of the logical nets associated with the.strong components of D(A). The degree of a logical net is the number of delays in the largest component i.e., degree (A) = maxlCal. A net of degree d has at d csD d+i least one component having 2d states and no strong component having 2 states.where i > 0. Thus size (A) < 2degree (A) The strengthened version of the Burks-Wang conjecture follows: Theorem 6 For every integer d, there is a transition function which cannot be simulated by any logical net of degree d.

CONCLUSION A strengthened version of the Burks-Wang conjecture was shown to be true. The proof relied heavily on the properties of state transition cycles exhibited in Theorems 2,3 and 4. These theorems can be readily interpreted as constituting a proof of the irreducibility of prime cyclic groups which uses only machine (rather than semigroup) ideas.

REFERENCES Burks, A. W. and Hao Wang (1957) "The Logic of Automata - Parts I & II." Journal for the Association for Computing Machinery, 4, 2, April. Ginsberg, A. (1968) "Algebraic Theory of Automata." Academic Press, New York. Harary, F., R. Z. Norman, and D. Cartwright (1965) "Structural Models." Wiley and Sons, Inc., New York. Hartmanis, J., and R. E. Stearns (1966) "Algebraic Structure Theory of Sequential Machines." Prentice-Hall, Inc., Englewood Cliffs, N.J. Kauffman, S. A. (1969) "Metabolic Stability and Epigenesis in Randomly Constructed Genetic Nets." J. Theoretical Biology, 22, pp. 437-467. Krohn, K., and J. Rhodes (1965) "Algebraic Theory of Machines I. Prime Decomposition Theorem for Finite Semigroups and Machines." Transactions of the American Mathematical Society, 116, 4, pp. 450-464. Walker, C. C. and W. R. Ashby (1966) "On Temporal Characteristics of Behavior in Certain Complex Systems." Kyberrntik, 3, 2, pp. 100-108. Zeigler, B. P. (1968) On The Feedback Complexity of Automata, University of Michigan doctoral dissertat:i.:;~.) Zeigler, B. P. (1969) "On the Feedback Complexity of Automata." Proc. Third Annual Princeton Conference on Systems and Infor. Sciences, Princeton, N.J.

UNCLASSIFIED DOCUMEIT CONTRtOL DATA. R & D (.qeerlfirty rlea.'llsraion ot'tl'I, hede bod of ha'rtrl 'nd ti" nd annofiln. timn l he efntered when the overall report i clnaseilfled). Q1RIGINATING ACTIVIT. (Coiporaeri ethiaot) 25. REPORT SECURITY CLASSIlICATION Logic of Computers Group Unclassified The University of Michigan 2b. GROUP Ann Arbor, Michigan t3. REIPORT TITLt PROOF OF A CONJECTURE BY A.W. BURKS AND H. WANG: SOME RELATIONS BETWEEN NET CYCLES AND STATES CYCLES 4. OEsCRIP t-IVE' o.ttS (Type ofl tport and Inctlulve datee) Technical Report:. AU THnO91) s (Fiet name, mddle, at name) Zeigler, Bernard P. '. RcEPORT OAT 7a. TOTAL NO. OF PAGES 7b. NO. OF REFS May 1970 17 9 6-. cflNTR1ACT O4 GRANTa NO. 9s. ORIGINATOR'S REPORT NUMBERISI DA- 31- 124- ARO- D- 483 03296-2-T b. PROJECt NO. C. fib. OTHER REPORT NO(S) (Any other numbers thai may be aessigned this report) d. 10. OISTRISUTION STATEMENT Distribution of this document is unlimited. II. SUPPLMEWT TARV~ NO TE 1. SPONSORING MILITARY ACTIVITY U. S. Army Office (Durham) Durham, North Carolina s. ABSTRAC T 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 logical net formed a hierarchy for net behavior. A strengthened version of this conjecture is proved by establishing that any logical 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. I NOVS ID Hv*173UNCLASSIFIED - Security Classifcatlion

UNCLASSIFIED - 'securiy Clasification 4,. LINK A LINK I I7nK C KEY WORD - - ROLE WT ROLEr WT - 0.', E-p Wo UNCLASSIFIED ~iscurIty C1Mtuvficulto

UNIVERSITY OF MICHIGAN 9 1111111111l1111-1111 I III8ll69iIIIill 3 9015 03527 5869