THE UN I V E R S I T Y OF MI CHI GAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report A LEAST UPPER BOUND ON THE FEEDBACK INDEGREE FOR HOMOMORPHIC REALIZATION OF SEQUENTIAL MACHINES 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 administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR October 1969 Distribution of This Document is Unlimited

ABSTRACT It is known that for every integer d, there are transition functions not isomorphically realizable by any net having feedback indegree (the largest number of wires that any delay receives from other delays in its feedback loop) less than d. Here we show that, in contrast to the isomorphic case, every transition function can be homomorphically realized by nets of feedback indegree not exceeding 2. This is a least upper bound, since simple nets (i.e., those having feedback indegrees not exceeding 1) are shown not to be universal in this sense.

A conjecture concerning feedback complexity of logical nets (sequential machine realizations employing delay elements) was made by Holland [2] as follows: for any logical net define the feedback indegree as the largest number of input wires that any delay receives from other delays in its feedback loop; for each integer d, there is a transition function which cannot be isomorphically realized by any net of indegree less than d. This conjecture was shown to be valid by Zeigler [4,5] and the question then arose as to whether it held as well for homomorphic realization (i.e., allowing state splitting memory expansion). In this paper we show that a complexity hierarchy does not hold in this case. Specifically we show that every transition function can be homomorphically realized by nets of feedback indegree not exceeding 2 and this is the least upper bound in the sense that there are transition functions which cannot be homomorphically realized by nets of feedback indegree 1. Logical nets and their representing digraphs were formally defined in [4], Essentially the digraph D(A) of a logical net A considers the delay elements as points and there is a (directed) line from point a to point a just in case delay 8 receives an input from the output of delay a. See for example Figure 1. For any point a of D(A) let S denote the strong component containing a, a (S = {BI there is a path from a to B and back in D(A)}. I denotes the set of points preceeding a in D(A) i.e., the set of delays feeding delay a in the logical net and FI = I f S is the set of wires coming into a from points in its strong component. As usual, IIal is the indegree of a and we call jFI aithe feedback indegree of a.

Based on a result of Arden [1],Weiner and Hopcraft [3] show that a finite set of modules can homomorphically realize any transition function if, and only if, the set is complete (i.e., can be used to realize with some delay all finite memory span functions). As they note that there are complete modules having just two binary input wires (for example Figure 2) we can conclude that every transition function can be homomorphically realized by logical nets in which no point has indegree greater than 2. Also in order to satisfy the completeness requirement at least some points must have indegree 2, so that 2 is the least upper bound on the indegrees of the'nets which are universal in this sense. It does not follow however that this is the case for feedback indegree. Since for each point a, iFI I<! I we can conclude that 2 is an upper bound on the feedback indegree required for universality. But 2 is not necessarily the least upper bound since it is possible that every point in a net has feedback indegree 1 but also some have indegree greater than 1. (Figure 1 is an example.) Thus it is still possible that simple nets, as defined below, are universal in the sense that every transition function can be homomorphically realised by some simple net. Definition A logical net A is simple if for every pointaaD(A), FIal I<l. Thus simple nets consist of cycles (in the graph theoretic sense) connected together in series-parallel fashion by feedback free circuits (Fig. 1). We now proceed to demonstrate the limitations on such nets. First we establish a general theorem which relates the cycle cnaracLeristlcs of transition functions one of which can simulate the other.

Definition For transition functions Mi:Qi x Si + Qi' i=1,2, we say that M2 divides (is simulated by) M1 if there exists Q' C Q1 and maps G:S2 + S* (the free semigroup generated by S1), h:Q' + Q2 (onto), such that Q' is closed under g(S2) and for all qeQ', szS2 h(M1(q,g(s)) = M2(h(q),s) (Mi:Q1 x S1 + Q1 is the usual extension to S* of M1, we write qx = M(q,x).) M2 is homomorphically realizable by M1 if g maps S2 into S1 in the above definition. Definition: M: Q x S + Q contains a cycle if there is a q ~ Q such that m q = qx = qx x...x...1) m times for some x E S* and positive integer m. Let k be the least positive integer for which (1) is true. Let the sequence Z1, Z2, Z3,... ZkQ(x) be the sebe the sequence of initial substrings of x k, where Z1 is the first symbol of k k x and Z(x) = x. The sequence of states qZ1, qZ2, qZ3,., qZkZ(x) is called the cycle of x and clearly consists of the states encountered in journey from q back to q in the order of encounter. The x-period of this cycle is the number of states in the subsequence qx, qx2, qx3,.., qxk We remark that the cycle of x need not form a cycle in the state digram of M in the graph theoretic sense i.e., not all qZi need be distinct (although all qxi 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 p. Theorem: Let Mi: Qi x Si + Qi, i = 1,2 be finite transition functions such such that M2 divides M1 with maps h: Q1 + Q2' and g: S2 -+ S. If for some x E S* 2'

ql' q2' "' qm(g(x)) = 1 is a g(x)-cycle of M1 of g(x)-period m, then h(ql), h(q2),..., h(q') is an x-cycle of M2 with x-period k dividing m. Conversely, if ql' q2,'.., qk9(x) = q is a x-cycle of M2 with x-period k then there exists a g(x)-cycle in h (ql) h (q)... h (q) in M1 with g(x)-period m > 0 a multiple of k. Proof: + Consider the subsequence of the given g(x)-cycle of M1: q'g(x), q'[g(x)]2,, q[(x)] q' Let H(q') = q. Noting that h(M,(q',[g(x))]i h(Ml(q', g(xi)) = M2(h(q'),x') M2 (q,xi) We see that the given subsequence maps under h to a sequence 1 2 m qx, qx,..., qx = q in M2. Not all states in this sequence need be distinct. Let k the least integer for which qx = q. Then we readily establish that qxm = q iff m=kQ, for some integer Q > 0. The reverse direction is immediate. In the forward direction, we can always write m = kQ + n where Z, n are integers, m kl+n n Q > 0, O < n < k. Then q = qx = qx = qx, but k is the smallest integer with the property qx = q, n = 0, and hence m = kQ.

Thus 2 k qx, qx,...., qx q is a subsequence of an x-cycle which thus has x-period k dividing m. Consider the subsequence of the x-cycle of M2: qx, qx,.., qx = q. Then the blocks h (qx), h-1 (qx2),...,h- (q) of fh are all distinct 2 k (since qx, qx,..., qx are all distinct). ( rr is the partition induced by h.) Let Z = g(x). We note first that for all i > 0, q' e h-l(qxi) + q'Z e h-l(qxi+l). This is so since q' s h-l(qxi) implies h(q') = qxi implies h(M (q',g(x)) = M2(qx,x) implies q'g(x) hl (qxi+l ). Now let q0 be a fixed state in h (q). From the preceding facts we can construct a sequence 2 i q0Z, q0Z,.., q0 in M1, such that for all j > O q0zjk+l1 E h 1(qx), qOZjk+2 h-l (qx2), q0zjk h-l (qxk = q). Sinceh (q) is finite, not all qZjk can denote distinct states. Let n1 > 0 be the least integer such that nlk 1qoZ = qxk q0Z = q0Z

for some integer x > nl. Let n2 be the least such integer x, i.e., nlk n2k q0Z = q0Z Then n1k n1k+l n2k nlk+l n2k q0Z, q0..., q0Z q0Z is a subsequence of a g(x) = Z-cycle in M1 having g(x)-period (n2-n1)k, a non-zero multiple of k. To show that all states in this sequence are distinct (hence establishing the claim) note that q0zqk+i' qoZjk+i qoZj for any i Z i', 0 < i, i' < k, as these elements belong to distinct blocks of Trh i.e., qjk+i i q0Z) c h (qxi) and qoZj k+i h -1 qxi') q0zjk+ ' e h ). Thus set i i' and n1! j ~ j' < n2. If qzk+i 'k+i qoz = q0Z then n21 (j '-j+n )k qoZ = qoZ and hence that nlk [n2-(j-j' ) ] k qoZ qoZ

But n2 is the least integer for which this is true so j-j' = 0 and j = j', a contradiction. Since homomorphism is a special case of division we can state: Corollary 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 apply this result to simple nets by extending a result of Holland [2]. Theorem 3 (Holland) Let M: Q x S - Q be isomorphically realized by a logical net A whose representing digraph D(A) is simple. For every x C S the period of any cycle of x in M divides 2a l.c.m. (9(x),b) where a, b are integers characteristic of A. Equivalently, the x-period of any x-cycle must divide l.c.m(Q(x),b) b a a (x) 2 g.c.d(Q(x),b) (L.c.m = least common multiple, g.c.d = greatest common divisor.) Using Corollary 2 we extend this result to homomorphic realization: Theorem 4: Let M: Q x S -+ Q be homomorphically realized by a logical net A whose representing digraph is simple. For every x e S the x-period of any x-cycle in M must divide 2a b

Proof: Since A is finite, by Corollary 2, given an x-cycle in M there is an x-cycle in the transition function MA of A. Also the x-period of the x-cycle in M divides the x-period of the x-cycle in MA which in a b turn divides 2a by Theorem 3. g.c.d. (lcx),b) Corolary 5 Let M:Q x S + Q, JISJ2, be such that there exists qcQ and seS such that for all xeS M(q,x) = q, if, and only if, the number of occurances of s in x is a non-zero multiple of j, a positive integer, (M is a modulo j counter). If M is homomorphically realizable by a logical net whose representing digraph is simple, j is a power of 2. Proof: Pick x = sy where yeS* contains no occurances of s and L(x) is a non-zero multiple of b (in Theorem 3 ). Then there is an x-cycle in M with x-period j. But by Theorem 3 this x-period must divide a b a 2 g.c.d(pa(x),b) 2 2 = 2 hence j divides 2a. Corollary6: There are transition functions, M which cannot be homomorphically realized by any logical net whose representing digraph is simple. Proof: The modulo three counter is an example of such a finite transition function. In sum, we have shown that the least upper bound on the feedback indegree is 2 for nets which can homomorphically realize any transition function. This involved showing that simple nets are not universal in this sense. The question of whether simple nets are universal in the sense that they can simulate (allowing rate slow dow) every transition function is still open (unfortunately, Theorem 1 cannot be applied in this case).

REFERENCES 1. Arden, D.N., "Delayed-Logic and Finite State Machines", Proceedings AIEE Symposium on Switching Theory and Logical Design, pp. 131-151, September, 1961. 2. Holland, John H., "Cycles in Logical Nets", Journal of the Franklin Institute, 270, 3, pp. 202-226, 1956. 3. Weiner, P. and J.E. Hopcroft, "Modular Decomposition of Synchronous Sequential Machines", IEEE Symposium on Switching and Automata Theory, pp. 223-239, October, 1967. 4. Zeigler, Bernard P., "On the Feedback Complexity of Automata", Technical Report 0822-6-T, The University of Michigan, January 1969. S. J, Summary of Above in 3rd Annual Princeton Symposium on Systems and Information Sciences, 1969.

n J I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I -— I Fig. 1. A Simple Logical Net and Its Representing Digraph. a b Fig. 2. A Complete Module.

UNCLASSIFIED Security Classification DOCUMENT CONTROL DATA R&D (Security claaeification of title, body of abstract and Indexing annotation must be entered when the overall report 1s clasitlied) 1. ORIGINATIN G ACTIVITY (Corporate author) 2o. REPORT SECURITY C LASSIFICATION LOGIC OF COMPUTERS GROUP Unclassified The University of Michigan 2b. GROUP Ann Arbor, Michigan 3. REPORT TITLE A LEAST UPPER BOUND ON THE FEEDBACK INDEGREE FOR HOMOMORPHIC REALIZATION OF SEQUENTIAL MACHINES 4. DESCRIPTIVE NOTES (Typ of report and Incfuesve datee) Technical Report S- AUTHOR(S) (Laet name. ftret name, initial) Bernard Phillip Zeigler 6. REPORT DATE is. TOTAL NO. OF PAGES.b. NO. OF mirs October 1969 14 5 8a. CONTRACT OR GRANT NO. 9a. ORIGINATOR'S REPORT NUMBER(S) DA-31-124-ARO-D-483 b. PROJLECT NO. c. | b. OTMjR REPORT NO(S) (Any other numbere that may be aeisied this report) d. 10. A V A IL ABILITY/LIMITAtION NOTICES Distribution of This Document is Unlimited. 1 1. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY U. S. Army Research Office (Durham) Durham, North Carolina 13. ABSTRACT It is known that for every integer d, there are transition functions not isomorphically realizable by any net having feedback indegree (the largest number of wires that any delay receives from other delays in its feedback loop) less than d. Here we show that, in contrast to the isomorphic case, every transition function can be homomorphically realized by nets of feedback indegree not exceeding 2. This is a least upper bound, since simple nets (i.e., those having feedback indegrees not exceeding 1) are shown not to be universal in this sense. DD IJAN 4 1473 UNCLASSIFIED Security Classification

_ UNCLASSIFIED Security Classification 14. LINK A LINK 8 LINK C KEY WORDS, ROLE WT ROLE WT ROLE WT INSTRUCTIONS 1. ORIGINATING ACTIVITY: Enter the name and address imposed by security classification, using standard statements of the contractor, subcontractor, grantee, Department of De- such as: fense activity or other organization (corporate author) issuing (1) "Qualified requesters may obtain copies of this the report. report from DDC." 2a. REPORT SECURITY CLASSIFICATION: Enter the over- (2) "Foreign announcement and dissemination of this all security classification of the report. Indicate whether "Restricted Data" is included. Marking is to be in accordance with appropriate security regulations. (3) "U. S. Government agencies may obtain copies of this report directly from DDC, Other qualified DDC 2b. GROUP: Automatic downgrading is specified in DoD Di- users shall request through rective 5200. 10 and Armed Forces "ndustrial Manual. Enter the group number. Also, when applicable, show that optional,, markings have been used for Group 3 and Group 4 as author- (4) "U. S. military agencies may obtain copies of this ized. report directly from DDC Other qualified users 3. REPORT TITLE: Enter the complete report title in all shall request through capital letters, Titles in all cases should be unclassified.,, If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis (5) "All distribution of this report is controlled Qualimmediately following the title. ified DDC users shall request through 4. DESCRIPTIVE NOTES: If appropriate, enter the type of.__.. report, e.g., interim, progress, summary, annual, or final. If the report has been furnished to the Office of Technical Give the inclusive dates when a specific reporting period is Services, Department of Commerce, for sale to the public, indicovered. cate this fact and enter the price, if known. 5. AUTHOR(S): Enter the name(s) of author(s) as shown on 11. SUPPLEMENTARY NOTES: Use for additional explanaor in the report. Enter tast name, first name, middle initial, tory notes. If military, show rank arind branch of service. The name of the principal..uthor is an absolute minimum requirement. 12. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (pay6. REPORT DATE:. Enter the date of the report as day, ing for) the research and development. Include address. month, year; or month, year. If more than one date appears on the report, use date of publication. 13. ABSTRACT: Enter an abstract giving a brief and factual summary of the document indicative of the report, even though 7a. TOTAL NUMBEER OF PAGES: The total page count it may also appear elsewhere in the body of the technical reshould follow normal pagination procedures, i.e., enter the port. If additional space is required, a continuation sheet shall number of pages containing information. be attached. 7b. NUMBER OF REFERENCES: Enter the total number of It is highly desirable that the abstract of classified reports references cited in the report. be unclassified. Each paragraph of the abstract shall end with 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter an indication of the military security classification of the inthe applicable number of the contract or grant under which formation in the paragraph, represented as (TS). (S), (C), or (U). the report was written. There is no limitation on the length of the abstract. How8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate ever, the suggested length is from 150 to 225 words. military department identification, such as project number, subproject number, system numbers, task number, etc. 14. KEY WORDS: Key words are technically meaningful terms or short phrases that characterize a report and may be used as 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the offi- index entries for cataloging the report. Key words must be cial report number by which the document will be identified selected so that no security classification is required. Identiand controlled by the originating activity. This number must fiers, such as equipment model designation, trade name, military be unique to this report. project code name, geographic location, may be used as key 9b. OTHER REPORT NUMBER(S): If the report has been words but will be followed by an indication of technical conassigned any other repcrt rnumbers (either by the orizinator text. The assignment of links, rules, and weights is optional. or by the sponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any limitations on further dissemination of the report. other than those UNCLAS S IF I ED Security Classification