Informal Memoranidum 2 A GENiERALlZATION OF FOLDED TREE THEORY Carl H. Pollmar Note: This material is issued as an informal memorandum because it is tentative, it has not been completely checked, and the exposition is unpolished. Administrative circumstances prevent further work on the material. Consequently, it is necessary to present the results so far achieved in this form rather than in a complete regular report. Burroughs Corporation Research Center Paoli, Pennsylvania Project 1828 University of Michigan Ann Arbor 30 August 1954

ii. Table of Contents Section page 1. Introduction,,.**.****...*..........*****... 2. Fundamental Graph Theory.................11 3. Graph-Theoretic Trees,........ *.........18 3.1. Concepts Fundamental to GraphTheoretic Trrees.......................o1 3.2. The Property of Semi-admissibility....28 33.3 The Property of Admissibility.........44 4. The Practical Problems of M-furcation and Vertex Assignment..........................64 4.1. The Technique of M-furcation..........64 4.1.1. General Description of the iethod of M-furcation.....................65 4.1.2. Determination of the Fundamental Sequenc s........................ 72 4.1.3. Construction of F(S)..............74 4.1.4. Construction of D(S)................80 4,1.5. Examples of Mi-furcation............84 4.2. Vezrtex Assignments.......... 93 Appendix I te *~..e o 103 Appendix 1.....................................10 Appendix IIo.....,.......... *........104 B3ibliography. * O........... *................109

. -I — I -), "';, I ii 1.1 1: LI " LO T""EZI Th.E'ORY . U!, ii i , I kil: llol 0 il D;,'. in t roduc tionL. ilany properties of electrical networks depend not upon the nature of the elements used, that is, the relays, tubes, and other devices which are connected together to form the network, but rather upon the way in which these devices are hooked togethero In considering properties of this kind, it is natural to avoid all unnecessary detail and to represent the elements by small circles or vertices and the wires connecting two elements by a line joining the corresponding vertices. This figure of vertices and lines is called a linear graph. There is a large body of mathematical literature devoted to this subject (Refs. 1, 2, 3, and 4). Fig. 1(A) shows a relay contact tree, The circles inclose the transfer contacts and the associated P. designate the relay coils which operate the J contacts. A coil is limited in the number of transfer contacts that it can reliably operate. As a consequence, a problem arises in the assignment of transfer contacts to relay coils. The assignment must be such that (1) it does not essentially alter the operation of the tree, and (2) it keeps the number

P3 2 _ "4- p 1,.P \P~j c ', P2 to T n Ph o rntact Tree Linear Graph of (A) (A) (I) Relay Co Fig. 1

3. of transfer contacts assigned to each relay coil within proper limits. The second condition may be N considered in terms of a sum ZL CiPi where Ci i-l is the number of transfer contacts operated by Pi. It is called the "load distribution" (LD) of the tree. The tree of Fig. 1 has the LD, 1Dl+- 4D2 4D3 -6D4. Since the LD is independent of the nature of the elements inclosed by the circles, their interior may be ignored, and the tree of Fig. 1(A) reduced to the linear graph of Fig. 1(B). The tree in Fig. 2(A) may be thought of as being constructed from pulse control unitso Each square represents a coincidence detector and the Pi represent the flipflops to which the coincidence detectors are connected. Again it is unnecessary to consider the interior of the circles, and Fig. 2(A) reduces to the linear graph of Fig. 2(B). As linear graphs, the network of pulse control units and the network of relay transfer contacts are identical. Considered abstractly, the labels of the vertices which denote the relay coils or input sets operating the elements,a pair of which is represented by the vertex concerned, divide the vertices into disjoint classes. This division must be done in a

I, P 4 Pulse Control Unit Tree Linear Graph of (A) (A), (B) Fi g. 2

5 o manner which (1) preserves the essential operating characteristics of the tree, and (2) keeps the number of elements in each class below some bound (which depends upon the nature of the physical equipment to be employed). These conditions are met by studying the variety of LD's possible in trees which "operate properly", This, as will be shown in Section 3, can be done in graph-theoretic terms. The trees of Figs. l(A) and 2(A) both have LD, 1Dl+ 4D2 4D3- 6D4. Other assignments yield the LD's, lD1+2D2 + 4D3 w 8D4 and 1Dl- 4D2- 5D3- 5D4o The first is the "worst" LD (in the sense that D4 operates the maximum possible number of transfer contacts), and the second is the best. Still other LD's are possible. Three questions arise naturally in these considerations. (1) Given an expression of the form LCiPi, how is it possible to determine if there exists a tree having this as its LD? (2) How can the set of possible LDts be generated? (3) Given a sum ZCiPi which can be realized in a tree, how can a tree having this sum for its LD be determined?

6. Shannon (Ref. 5) defined a set of LD's which he showed could be realized in a tree of the form shown in Figs. 1 and 2, and he gave a method of testing whether a given sum LCiPi belonged to this set. Thus, he partially answered the first two questions. He did not show that the LD of every tree would belong to this set and he did not answer Question 3. The answers to all three questions for this simple type of tree is given in Vols. I and III of the Language Conversion series (Ref. 6). An important limitation of the class of trees considered there is that each vertex has exactly two outputso From the point of view of linear graph theory, this seems an unnecessary restriction. It should be possible to consider trees whose vertices have M outputs, M an integer and M S- 2. This has its counterpart in terms of physical equipment. The transfer contact is essentially a two-terminal switch. The selector switch may be considered as its generalization to M terminals (Ref. 7). Trees of selector switches, the analogues of relay trees, may be considered and their LD problems handled in terms of the theory presented in this report.

70 Another extension in equipment terms is illustrated in Fig. 3(A). There the generalization is effected by increasing the nurmber of coincidence detectors (logical "ands") within each circle. The input sets, instead of consisting of pairs alone, contain two, three, and four wires. This tree will operate as a decoding network for any code which associates exactly a single 1 with the wires of each Di, io.e, for codes whose elements are of the form 01, 010, 0001 D1 D2 D3 Such a requirement is a natural extension of the concept of "Polar Pair" employed in the Language Conversion series. Fig. 3(B) is this tree in linear. graph form, and Fig, 3(C) is the linear graph of a tree equivalent to that of Fig. 3(A) in the sense that it will decode the same class of codes, but differing from it, for example, in the number of vertices it contains. In the body of this report only linear graph trees are considered. No consideration will be given to the "interior of vertices." Section 2 defines linear graphs and introduces the basic definitions and concepts used in the theoryo Restrictions are

D2 (B) D 3 D2 (C) Fig. 3

imposed successively on the class of graph-theoretic trees until the more restricted class of trees is derived for the type of electrical network considered hereo Useful properties are stated and proved at each stageo In Subsection 3.2 the graph-theoretic characterization corresponding to the proper labeling of the vertices is introduced and problems associated with the LD's of these trees are considered. The trees of this subsection are called "semi-admissible." Their vertices may be of different orders (i.e., the vertices need not all have the same number of outputs) than those of the trees of Fig. 3. Subsection 3o3 considers "admissible" trees. These are semi-admissible trees all of whose vertices have the same number of outputso (See the tree in Fig 4(A)o) For this class of trees the first two fundamental questions regarding LD"s are answeredo A method is given for testing any sum CiDi to see if there is a tree having this as its LD, and a method is presented for "generating" the set of all such LD's. Section 4 answers the third question by giving a method for constructing a tree having a given '2CiD as its LDot tThis was the original intention but lack of time precludes the complete realization of this goal.

10. — >~5 S (4, ) -1-2 3,3)=3,iD J/ 8 (4,6) =1D2 D4 7 fT/ 6(3,2)=3^J^ —S4s(4)='lD2,; S- 2 (4, 5)1D2./ S(4.11)=lD3 / 3 - / S (4,12) =1D3 D2 X / 8(2,2) 3Iw+9 4(, 5(4,13)-lD3 __,., (4 5 _t- — S 4,1 ) =D1D3 D S (1,1\RT-i+13 -13D3+J- I (4,14) =1D3 9-2 b(l, ll+ll3 6 l( S(4,16)lD3 iD *JC\zE S (4,17) -1iD 3.ID)-D3 2' D \ S(3,7)=1.(4,19)1D4,Hq \,)S(4,21)-1D4 ---- s (4,23)=1D4 -i^ o8 -(4,24) =1D 0'. ''S)S(4(,251)-1lD 6- =1.S (4, 26)-=1D3 3- -— Qs ( 4, 27) -D4 (A) Fig. 4

11. 2. Fundamental -Graph noThe Def'.: A directed linear graph.(here simply a graph iis a system composed of: ()a set P(GI) of Points A1,A2,,***YnY*9e and (2) a set EIi() of ordered pairs of points (Ai,Aj), i j, where each pair (A.,Aj) may have multiplicity, mij and i's such that eve.-1ry element of P(14) is an element of at least one member of 0) if the number of points and pairs is finite, the graph is called finite. Remark: if i~ anid N\* are two graphs such that B CN G~i~*, then -W Proof:9 This follows f romn the consideration that the set of edges, iLe., pairs defined and assigned sets of points, A Ai is an end point of some E. an element of It is convenient to represent the pairs. by line sel-gments (i.e.,. Ai )eAi) called edges, if E (AiAj) is an edge, then: Ai and Ai are its end -points, Ai being the orgi and A~ the terminus.

12. In net theory the points will be represented either by end points or by inclosures such as those representing a conjunction, a stroke element or a delay elemento For example, in the net diagramed below the points are Al, A2, and A3, A2 A1 l A3 Al and A3 are end points in the usual sense while A2 is an inclosure and is considered the end point of the two edges, (A1,A2)1 and (A1,A2)2. (Subscripts are used to distinguish among edges having the same origin ald terminus,) The inputs of a point A are the edges having A as terminus (i.e., those which are directed toward it). The outputs of a point A are similarly the edges having A as origino Consider again the set P(O) consisting of all points of the graph No P(N) may be divided into two disjoint sets V and J, the elements of which are called vertices and junctions, respectively0 A division of the points into two disjoint subsets may be done generally in many wayso We only require that it

13 satisfy the following: i 1f. A E1 V, then A has aat least one input anfd at least one output; P2 AG~ ~V(~O P AN), (note that J Gi) V~i~ ~/satisfies this condition); i 1f E (A,A)6 Q) then either Ai orA (but not both) is an element of VO'). Def.: A graph with a division satisfying the above conditions is called a partiioned grh If N is a partitioned graph,, then V(.N) is the set of vertices of N, arid J(.N) is the set of junctions of N. If A & J(N) and A is not the terminus of any element of ~E(N)', then A is an inpto jfunction of N. Similaarly, if A E, J(N4) and A is not the origin of any element of E() then A is an ~gtp j unction of N. Finally, if A 6 J(N) and A has two or more. inputs., then A is ca-lled a mutil jfuction of N~. Graphs for the most part will be studied here by meanis of subgrapso Def0 If N is a graph and N~ is a graph such that P(ii) CPGii) and ~(N ' C!(i4), then N' is a subg~raphn of N.

14~ If N is a partitioned graph and N t is a subgraph with the induced division of points and this division satisfies P1, then N1 is called a subpartitioned graph. (Clearly, a partitioned graph can have subgraphs which are not subpartitioned graphs.) Def.: A ath is a subgraph whose edges can be labeled Eli.o.En in such a way that EmEn 1 have an end point in common which is the end point of no other edge in the sequence. Defo: A subgraph C is connected if and only if for every pair of points P1 and P2 of C there corresponds at least one path E1..EM such that P1 is an end point of E1 and P2 is an end point of EjVoI Def.: An oriented path is a path in which the terminus of Em is the origin of Em+ 1 for M = l1oooM-lo Def.: If C is a path such that E1 and EM have a point in common, then C is a cycle. If C is an oriented path, then C is an oriented cycleo

15 Def.: If R = E1E2, oooE is a path, then the end point of E1 which is not an end point of E2 and the end point of EM which is not an end point of EM_1 are end points of R. Def.: If R = El,...,EjM is an oriented path, then E1 is called the inilut of Rt and EM is called the output of R. Alternatively, R is sometimes said to oriinate in E1 or in al if E1 = (a1,a2) and to terminate in EM or in aj if EM - (ai,aj). Remark: Any point of a cycle is an end point of the cycleo Defo: The length of a path is the number of edges it containso Defo: The vertex rank (or, briefly, rank) of a graph (or subgraph) is the number of vertices that it containso Insight into some of the significant structural characteristics of a graph can be gained by forming equivalence classes of various kinds. Using the idea that two oriented paths, a and b, are equivalent if and only if a and b terminate in the

16 same edge, we have the following definitiono Def: If E is an edge of M, then the set of all oriented paths terminating in E form a class 6p(E) called the path class of Eo E is the class outputo The inputs of N belonging to the paths of ep(E) are called class inpss their number is the input order of the class. The maximum of the ranks of the paths of;p(E) is the class rank. Def.: A tree, in the graph-theoretic sense, is a finite connected graph without cycles. If the trees of Vols, I ard III of the Language Conversion series are considered as graphs, they constitute a special subset of the set of graphtheoretic treeso A few additional definitions are nowintroducedo Defo If E, 0 oEK is an oriented path and EK is a net output, then El. 0,EK is an oriented output patho Def.: If E is an output of T, then Up(E) is called an oriented output class of T.

17. The outut order of a vertex V (or, briefly, order of a vertex) is the number of outputs of V. If all the vertices of a class have order "a", then the order of the class is "at" If all the vertices of a tree have order "a", then the tree is of order "a"To

18 U0 Graph Theoretic Trees. 2l — Concepts Fundamental to Graph-Theoretic Trees. in this report we are concerned with a very special class of trees, a class even more restricted than the following definition of tree with which we begin. Defo: The term, tree, is restricted here to a partitioned graph-theoretic tree in which each vertex has exactly one input and at least two outputs and each junction has at most one input and one outputo If T is a tree in which each oriented output class has the same rank, then the tree is said to be complete. If each oriented output class does not have the same rank, the tree is said to be partial. The vertices of a tree may be divided into equivalence classes called bays Let a and b be two vertices and consider the oriented path class terminating in the input of each, If the ranks of these two classes are the same, say, m, then a and b lie in the same bayo It is often convenient to label the bayso All vertices in the m'th bay have

19 associated oriented path classes of rank m. This characteristic of a tree may be described by a sequence of numbers al,a2,...,a,...,aN where an is the number of vertices in the nrth bay. In addition to the oriented path class used above in the definition of bay, a vertex V of a tree determines another oriented path class as follows: (oriented path a) (oriented path b) with respect to V if and only if a and b have as their initial edge the input of Vo Given a V, the union of all paths of T equivalent with respect to V form a network called a minor tree and denoted T(V) Defo; Two if they do minor trees are said to be disjoint not have a vertex in common~ Theorem 1: Two disjoint minor trees T1 and T2 of a given tree T have no edges and no junctions in common. Proof: (I) The proof is contrapositive. Suppose they have an edge in common, then, since each minor tree is the union of a set of paths and hence of subgraphs, the end points of the edge are points of both minor treeso Since the given tree is a partitioned graph,

20 one of the end points is a vertex. This is a contradiction (II) Suppose they have a junction J in common; then this junc'tion lies in one or more of the oriented paths defining T1 and similarly for T2. If J has an input Ij but no output, then IJ is common to T1 and T2. If J has an output Oj, then Oj is common to T1 and T2, but this is impossible by (I) of this proof. (ote that all junctions have at most one input and one output.) Hence, T1 and T2 have no vertices, edges, or junctions in common. QoE.Do Theorem 2: A minor tree of a tree T is a tree. Proof: (I) A minor tree T(V) of T is a finite set of vertices and directed edges containing no cycles since T does not. It is connected since the input of V is common to all the determining pathso (II) If it contains a vertex, it will contain the input and all outputs of that vertex, and, if it contains a junction, it will contain the output and/or input of that junctiono Finally, it is a subgraph satisfying P1 and hence is a subpartitioned graph (i.e., a partitioned graph). QoE.Do

21. Lenmma [' If T is a tree and a and b are two oriented paths of T, each of maximum length, having a point p in common, then a and b have a common initial suboriented path containing po Proof: If p is a vertex, then, since the paths are of maximum length, the input of p (there is only one) will be an element of a and bo If p is a junction, then, as above, a and b will contain the input of p (there is at most one) if such exists. If none exists, then the output of' p is a tree inputo A point p, then, determines a unique oriented path originating with a tree input and terminating in po If this were not unique, then at some point it must be possible to choose among alternatives. But this is impossible since each point has at most one input and the orientation of the path prevents the choosing of an outputo QoEoDo Theorem A: A minor tree of a complete tree is a complete treeo Proof: It is a tree by Theorem 2. Let T(V) be the minor tree and consider the set

22. of oriented paths of maximum length through V. All such paths will have one of the paths defining T(V) as the terminal segment, and they will have a coammon initial segment terminating in p where (p,V) is the input of Vo Let R(T) be the common rank (since T is complete) of all output classes of T. Let r(t) be the rank of the common initial segmento Then, (rank of an output class of T(V)) = (T) - r(t)o Q.o ED Lemma 5: In a tree there is exactly one vertex whose input is not connected to the output of any other vertexo Proof: A tree. has at least one such vertex. If it does not, one can start at an output of the tree and form a path which has no other end merely by adding the input of a vertex if its output is part of the path (allowing possible repetitions)o Since there are only a finite number of edges, there must be repetition, ioeo, there is a cycle, but this is impossible in a treeo If there is more than one vertex whose input is connected to no other vertex, consider the minor trees

23 originating with each of these inputs. These minor trees are disjoint as can be shown by appealing to the preceding lemma. This, by implying that T is disconnected, leads to a contradiction. The tree, however, is connected. Hence, there exists a path (which in this case cannot be oriented or it would be part of one of the minor trees) connecting two of the minor trees, say, T(V1) and T(V2) Consider it as originating in T(V1) and going to T(V2 ), There will be a point p along this path where the orientation of two successive edges is different (ioeo, the point in common is the terminus of both). All points, including this one, and the edges of the path so far considered are in T(V1). The next is outside T(V1). Clearly, p will have two inputs, but this is impossible by the definition of tree. Hence, the tree is not connected. But this is impossible. Q.EoDo The vertex whose input is not associated with any other vertex is called the center (in Vols. I and III of the Language Conversion series, the "Key") of the tree,

240 Theorem 6: If (1) a tree T is of order "a" and (2) for each vertex V all oriented output paths of T(V) have the same rank, then (a) the n'th bay of T contains an1- vertices, (b) the inputs of the (n — l)st bay and the outputs of the n'th correspond in 1-1 fashion, and (c) the tree is complete. Proof: The proof is inductive. T has a single vertex V whose input is associated with no other vertexo By definition it will be in the first bay. Each of its outputs will be connected to the input of a vertex whose output has a class rank of 2. Hence, they will be in the second bay and there will be lxa - a2-1 of them. Suppose this has been done until n bays have been defined (the j th containing an-1 vertices) and consider the formation of the (n+-l)st bay. Suppose the outputs of vertex nVr are tree outputs but that an output of another vertex nVs is connected to the input of a vertex n+-lV. If this is the case, there is an output path originating in the input of lVl which has greater rank than the output path containing an output of nVro This is a contradiction of the hypothesis on ranko

25 Hence, since each vertex of a tree has one input and each junction at most one, there corresponds one vertex in the (n-1l)st bay to each output of the n'th (ioeo, correspondence is 1-1)o Hence, there will be an-l x l a n a(nl)- vertices in the n'th bay. Completeness follows immediately from the definition. Q.E.D. Theorem 7: In a tree T every oriented output path M of maximal rank determines an oriented output path class (composed of the oriented suboutput paths of M) and every oriented output class defines a path M of maximal rank in To Proof: The suboutput paths ofthe maximal path M are all contained in the same output path class by definition of output path classo Are there any other output paths in this class? Suppose there is one of maximum length, call it Xo Then X and M have at least the terminal edge and hence its terminus in common. Hence, by Lemma 3, they are identical. oSo D

26o Corollary 8: if T is complete, every output path of maximal rank will be of rank N whiere N is the maximal rank among the set of output paths, Proof: Consider the output path of T having maximal rank oN Call this output path Mo M determines an output path class which has rank No Every output path class has the same rank which must be N since T is completec Consider any output path MI of maximal ranko It determines an output path class whose rank must be m and consequently the rank of M't must be N. Corollar 2: If T is a tree, T(V1) and T(V2) two minor trees of T, V1 in bay m1, V2 in bay m2, and m1 < m2, then, if T(V1) and T(V2) are not disjoint, T(V1) T(V2) Proof: Since they are not disjoint, there is a common vertex Vo Consider an output path originating with the input of VQ This output path must be common to T(V1) and T(V2), ioeo, they have a tree output E in common0 All elements of 6p(E) are subpaths of a single maximal output path of T by Theorem 7. This implies that V1 anrd V2 lie in the same output

27. path, i.e,, that V2 lies in a path through V1 and hence that T(Vi) C T(V2) by definition of minor tree. Q.EoD. Theorem 10: If T is a complete a-order tree of N bays, then T has aN distinct outputs and each oriented output path class is of rank N. Proof: Each maximal oriented output path determines an oriented output path class, and, since T is complete, each output path class has the same rank. If there are N bays, the rank of the oriented maximal output paths will be N (see the definition of bay). In order to apply Theorem 6, we must consider a vertex V and the maximal output paths containing an output of V. These are all of rank i. Consider that part of lay maximal output path terminating with the input of V. This part is common to all the maximal output paths containing anl output of V (Lemma 3). Let its rank be m. Then the rank of every output path originating with the input of V is N-m -lo Applying Theorem 6, there are aN- vertices in the N th bay and hence aN-1 x a = aN outputs since T is of order a. QoEDo

28. 3. 2. Te Property of emi-admissibil.Y. Before proceeding to the derivation of additional interesting tree properties, it is necessary to present the following definitions. Defo: If T is a tree of N bays, then a partitioning of V(T) into N disjoint, nonempty classes Dn which satisfy the conditions: (1) all vertices of Dn have the same order mn, called the class order (see Section 2); (2) if a and b are vertices of the same class, then T(a) ald T(b) are disjoint; is called a proper tree partition. The classes of vertices are called proper vertex classes (or, briefly, vertex classes). i ot all trees can be partitioned properly. Def.: A semi-admissible tree is a complete tree with a proper tree partition. Defo: A semi-admissible tree all of whose vertices are of the same order m is called an admissible tree of order mo

29. It is convenient to divide trees into equivalence classes on the basis of proper tree partitioning, Defo: If T1 and T2 are two N bay semiadmissible trees with mn(T1)} and {rn(T2)}, the set of vertex class orders of T1 and T2, respectively, then T1 is equivalent to T2 if there exists a map 1-I Z: {mn(T1) on to, mn (T2) such that if t (mn(T)) - mn(T2) then mn (Tl) Inn (T2)Remark: This equivalence relation is transitive. Theorem 110 If T is a semi-admissible tree and M is an output path of maximal rank in T, then no two vertices of M belong to the same classo Proof: If two vertices of M did belong to the same class, Condition (2) of-a proper tree partition would be violated~ This is impossible by definition of semi-admis sibilityo QoEoDo

30 Theorem 12: If T is a complete N bay tree whose vertices are divided into N classes satisfying the conditions: (1) each vertex is assigned to one and only one class and no two vertices of an arbitrary maximal output path M belong to the same class; (2) for an arbitrary class all vertices belonging to that class have the same order; then T is semi-admissible Proof: Clearly the' N classes will be disjoint and nonempty. The two conditions of a proper tree partition are satisfied: the first by Condition (2) of the hypothesis; the second by Condition (1). The latter follows contrapositively. Suppose that in T V1 and V2 are elements of the same class and that T(V1) and T(V2) are not disjointo Then by Corollary 9 T(V1) 3 T(V2) (or conversely), and there exists a maximal output path of T containing both V1 and V2. This implies a contradiction of Condition (2) of the hypothesis and hence is impossibleo QoEoDo

31. Theorem 1: If Dn is an arbitrary vertex class of a semi-admissible tree T and M is an arbitrary oriented output path of maximal rank, then M contains a vertex assigned to Dno Proof: Let T have N bays. Then by definition there are N vertex classeso M belongs to an oriented output path class K. By Theorem 10 K is of rank N and hence by definition of the rank of an output class and by Theorem 7 the rank of M is N' By Theorem 11 no two vertices of M belong to the same class and hence one must be assigned to Dn. Theorem 14_ A semi-admissible tree of N bays contains vertices of at most N different orderso Proof: This follows directly from the fact that in a semi-admissible N bay tree there are exactly N classeso The orders of these N classes are independento Hence there can be N different orders but this is the maximum. QoEoDo

32. Theorem 1: A minor tree of a semi-admissible tree is semi-admissible. Proof: A minor tree of a complete tree is a complete tree. A proper tree partition of T(V) is induced by the proper tree partition of T for if either of the two conditions fail in T(V) they will fail in T, but this is impossible. A similar argument holds for the requirement of disjointnesso To show that there are the proper number of classes proceed as follows. All maximal output paths through V have rank N. If V is in the i'th bay, then all the output paths of maximal rank have their first (i-l) vertices assigned to (i-l) distinct vertex classes and hence each has its vertices which appear in T(V) assigned to the same (N-i+l) distinct vertex classes. QoE.D, Theorem 16: If T is a semi-admissible tree and Dk is assigned to iV1, then the cardinality of Dk is and for all Di (i f k) it is greater than 1. Proof: Consider any oriented output path of maximal rank. It will contain vertex 1V1 which is assigned to Dko If another vertex were assigned to Dk,

33, consider any oriented output path containing this vertex (there would be one); then this maximal oriented path would have two vertices assigned to the same class and this is impossible. If Di is not assigned to 1V1, consider any two maximal oriented output paths having only the center as a common vertex. Such exist. Both contain vertices assigned to Di since T is semi-admissible. However, since Di is not assigned to the center, there must be at least two of them. o.E.D. The definition of a semi-admissible tree tells us how to recognize such a tree, but it gives little insight into the "variety" of semi-admissible trees equivalent to a given oneo Nor does it suggest any way of constructing themo Given a set of N classes ~Di3 each with its associated class order mi, it is possible to construct a simple tree which will be semi-admissible and which may be used as a basis for deriving allother equivalent semi-admissible treesO

34. Def.: A complete tree T which has a partition with the properties: (1) if Bi is an arbitrary bay of -T, then all the vertices of Bi are of the same order mi and are assigned to the same class Di; (2) Di = Dj if and only if i = j; is called a standard treeo Such a tree is easy to construct. N bays are provided. Provide a single vertex with mi outputs for the first bay. Assume that n bays of the tree have been constructed, then form the (n+l)st by providing a vertex of order mnr+l together with its input and outputs for each output of the n'th bay connecting the outputs of the n-bay vertices 1-1 to the inputs of the (n+-l)st bay vertices and proceed until all N bays have been constructed, Theorem 17.: A standard tree of N bays is semi-admissible. Proof: Clearly it has N disjoint nonempty vertex classeso By definition it must satisfy Conditions (1) and (2) QoEoDo

35 Defo- If T is a tree with a proper tree partition and Bi and Bi l are adjacent bays of T such that the vertices of Bi are all assigned to Dm, whose vertices are of order a, and the vertices of Bi-i- are all assigned to D,, whose vertices are of order b, then an iintercharc e operation on T is accomplished as follows: (1) replace each vertex of Bi by a vertex of order b assigned to DP forming Bi; (2) conniect to each output of Bi the input of a single vertex of order a assigned to DI to form Bi* 1; (3) connect the inputs of the vertices of B. 2 to the outputs of the vertices of -tBi -1 in 1-1 fashion~o The following example illustrates the interchange operation and suggests the variety that is possibleo It also indicates variation in the number of vertices that takes place,

'- \ IJ '\ / /\ /~, /,.' ^.../ -.. - /-/ ' a'c2 "/ / ' h H. I I ` \ / C) Co \/ H H 9 ^'"

37 Theorem 18: If T is a tree which is semiadmissible, then T, a tree formed from T by an interchag e operation in a minor tree of T, is semi-admissible anld equivalent to T, Proof: The proof is based on Theorem 12. Let T(V) be the minor tree. Consider an arbitrary oriented output path M of maximal rank through V. Paths not intersecting T(V) will be unaffected. Let Bi and Bid l be the two bays of T(V) to be interchanged, and let their vertices be assigned to Di and Dil1, respectivelyo There will be the same number of vertices in Bi as in Bi; the vertices of Bi, however, are assigned to Di o Bi 1 may have a different number of vertices from Bi 1, However, it will have the same number of outputs as Bi4 1, namely, (number of outputs of Bi_l) mi x mi 1o M is the path identical with M except for the points and edges involved in the interchange. There is a unique path, however, joining the output of Bil1 belonging to i to the input of Bi 2 belonging to Nio This path is the altered portion of M. Clearly there is a 1-1 correspondence between the set of M's of T and the M s of T

38. preserving rank. Hence, since T is a complete tree with iN bays, so is T. Since the vertices of T are divided into 1 classes, those of T are also. Furthermore, the fact that, for an arbitrary class, all vertices belonging to that class have the same order is unaffected by interchange. Finally, all the vertices of M are assigned to different classes since this is true for M in To Hence T is semi-admissible. T and T are equivalent for both are still N bay trees and the vertices of both are clearly assigned to sets of classes with the same set of vertex orders. Q.EoD, Theorem 19: If T is a standard tree, any tree derived from T by a sequence of interchange operations is semi-admissible and equival ent to T. Proof: (I) T is semi-admissible. (II) If the sequence of trees is T, T2o,,, Tk, then, if Ti is semi-admissible, Ti+ 1 is semiadmissibleo Hence by induction all are semi-admissible. Equivalence follows from the previous relations and the transitivity property of equivalence.

39~ Theorem 20: If T is a semi-admissible tree, it may be derived from the standard tree with same set of vertex class orders by a sequence of interchanges. Proof: The proof is by induction. (I) V1 carl be assigned to any Di by a sequence of interchanges in a standard tree Ts each interchange moving the bay assigned to Di to the lefto (II) Consider that all the vertices in the first i bays have been assigned as in To Then the (i+ 1)st bay will contain the same number of vertices as are in T since this depends on the first i bayso Consider an arbitrary vertex V of the (i +l)st bayo (a) T(V) is a standard tree since we started with a standard tree and all interchanges were with respect to minor trees containing T(V) properly, and hence they would have merely changed entire bays at a time. (b) Either V is assigned to the proper DC- or some bay of T(V) is so assigned (i.eo, all vertices of' this bay are assigned to Dy)o Suppose no bay of T(V) is so assigned; then a maximal output path containing V would have a vertex in, say, the j th bay, j < il, assigned to DC since this tree

40. is semi-admissibleo This implies that T has two vertices (V and one in the j th bay) in the same maximal output path assigned to D~ o This is impossible since T is semi-admissible. Since V must be assigned to the proper Dx or some bay in T(V) is assigned to D, it is clear that by a sequence of interchanges V may be assigned as desired. QoEoD, Theorem 21: If T1 and T2 are two equivalent semi-admissible trees, then both have the same number of output paths of maximal rank, ioe., the same number of tree outputsO Proof: By Theorem 20 both T1 and T2 can be derived from the same standard tree by a sequence of interchangeso Hence there exists a sequence of interchanges taking T1 into T2o If the number of maximal output paths is to be increased, interchange must increase the number of outputs of the final bay. Any change which does not affect this leaves the number of maximal output paths unchangedo Interchange does not affect the number of paths of maximal rank in a treeo The proof is inductiveo It is true for trees of two bays; assume it holds for

41. trees of (n-l) bays. We will show it holds for an arbitrary tree T of n bays. If the interchange is in a proper minor tree of T or involves two consecutive bays from the first (n-l), then the theorem holdso If the interchange is between the (n-l)st and n'th, we proceed as followsQ Let hMn2 be the number of outputs of the (n-2)nd bay and let an-1 and mn be the orders of the vertices in the (n-l)st and nrth bays, respectivelyo Then, before the interchange, the number of outputs of the tree is Mn1-_2 x m l x mild, after the interchange, it is Mn_2 x mnl x mn, i.e., the number of outputs of the n'th bay is unchanged, and the number of maximal output paths is unchangedo QoE.D. Theorem 22: For a given set of vertex class orders the set of trees semi-admissibie with respect to this set is identical to the set derived by interchange from the corresponding standard tree, Proof: (I) (Set of semi-admissible trees) C (Set derived by interchange)o See Theorem 20O (II) (Set of semi-admissible trees) 0 (Set derived by interchange). See Theorem 19o

For a tree T which is semi-admissible, two numerical characteristics of importance will be considered here: (1) the total number of vertices, and (2) the sequence of numbers, one for each vertex class indicating the number of vertices belonging to that class0 Defo, If T is a semi-admissible tree with a proper tree partition D1 o,., DN, then the following sum, C1Dl1+ o0 +CDN where Cn is the number of vertices of T in class Dn (n 1,..o, N), is called the load distribution (LD) of T. The remainder of this subsection considers the first of the characteristics given above. The second is studied for a special case in the next subsectiorn From the example and from the definition of interchange, it is clear that in the set of semi-admissible N bay trees, all having a given set of orders, the number of vertices per tree may vary widelyo Some idea of the limits on the range of variation is given by the following conjecture0

43o Conjecture 2: If T is a semi-admissible tree withl vertex classes so labeled that the order of D1 is equal to or less than that of Di+ 1 then (1) T will have a minimum number of vertices if it is the staiidard tree with Di assigned to the vertices of' t.he i th bay, and (2) T wi~l have a manximum number of vertices if it is the standard tree w-ith Di assignied to the (I -i+l) st bay, where N is the number of bays in T.

44. l.io The Property of Admissibility. The concept of interchange will not be used in this subsection. However, it is interesting to note that all admissible trees of order m can be deriv;ed from the stanldard tree by an alternative form of interchange. Def.: If T is a folded tree, T(k,q) a minor tree of T (it may be T itself), Hi the set of vertices in T(k,q) assigned to Di, and Hj the set of vertices in T(k,q) assigned to Di (i(Hi),1(Hj) * 0) then the operation which reassigrLs all elements of Hi to Di and all elements of Hj to Di is an interchange relative to T(k,q) of Di and DJ An important property of a semi-admissible tree is represented by its LD. It would be of interest to determine the set of all possible "admissible" LD's for a given set D1,.., D T This, however, seems quite a difficult problem if the Dn are allowed to be of different orders. A more limited problem is considered here. It is required that the order of all the Dn1 be the same for a given tree. 'The order may, however, be any positive integer ' 2. N(X) is defined to be the number of elements in Xo

45 Def.: An m-order load distribution ZCiDi of an m-order tree is called admissible if and only if the following four conditions are satisfied. N N (1) The total sum condition: Ci L mi- 1 i=l i=l k k (2) The partial sum condition: Z Ci Z _ mi-1 i-=l i-l (tihe prime indicates the coefficients in nondecreasing order), k r 1,2,..., N. (3) The unit condition: there is exactly one i such that Ci - 1. (4) The difference condition: Cj-Ci = k(m-l) for all j and i where k is an integer. The definition of admissible LD, like that of a semi-admissible tree, gives only a little insight into the nature of admissible LD's and suggests no simple method for constructing themo Here the idea of "flow" is introduced as an analogue of interchange. In considering flow it is convenient to eliminate the idea of LD entirely and to consider merely sequences of integers (positive). If S is a sequence

46. of integers and there is an rn > 1 with respect to which S satisfies the four conditions for admissibility, then S is called an m-order admissible seguenceo Def.: A sequence S2 is derived from a sequence S1 by flow if S1 can be transformed into S2 by a succession of the operations: (1) an interchange of terms; (2) an (m-l) flow from a larger number to a smaller one (i.e., subtract (m-l) from the larger, and add (m-l) to the smaller), no flow being allowed to the unit term (1). Theorem 2b: A sequence derived from l,m,m2,..., mN-l by flow is admissible and an admissible sequence may be derived from l,m,m2O..., mN-1 by flow, Proof: (I) (a) Conditions 1 and 3 of admissbility are obviously satisfied. (b) Condition 4 is satisfied because Cj - m + hl(m-l) and Ci = mk2 + h2(m-l) Cj-Ci = mkl-mk2 + (hl- h2) (m-l). This part ((hl- h2) (m-l)) has the desired property.

47. Consider m rkm 2 ald for convenience assume kl k2, then rki-mi 2 - i2 (mki-k2_ m 2(m) (kl-k-l.. ~ 1). Hence Condition 4 is satisfied (c) Now consider Condition 2. (1) It is clearly true for any sequence of flows consisting of a single flow. (2) Assume it is true for any sequence of flows consisting of i flows so as to show it true for any sequence of flows consisting of i+-1 flows, (3) Let the sequence of coefficients after i flows be 1,C1,C2,..., Cn_l in nondecreasing order. This satisfies the partial sum condition. After the single additional flow we will have 1,C1,...,Cj (m-l), Cj+1 **. Cri, Cr (m-lj)... Clearly, in the derived order, the partial sum condition is satisfied. Reordering, so long as Cr - (m-1) remains to tne right of Cj + (m-l), would preserve the partial sum conditiono The only way these terms could trade places would be for Cr to equal Cj +(m-l) in which case they could simply be switched and the partial sum condition would be unaffected,

48. (II) (a) Let the admissible sequence be (in nondecreasing order) (1) 1,CC2,.. Ci-l0 (2) 1,m,m2,. mN-1 (b) The two first terms agree. Since the partial sum condition holds, C1 - m. If equaiity holds, compare C2 and m2o If Ci > m, then flow in (2) onto m from terms as close to m as possible unltil this term is equal to C1o (c) This is possible because of the followingO (1) By Condition 4 of admissibility, Cl-l k(m-l) = m-l+ (k-l)(m-l) or C1 - m(k-l) (m-l), k 2. (2) To show that there are enough (m-l) s available, assume C1 larger than the largest possible. Let this be C1 Then kCl+ (N-l-k)C2 minm2+ ooo +m 1 - Sm where C2 - 1 -(m-l) and k is the number of occurrences of the value of C1 in the "most even" distribution. Substituting, we have kC1 + (N-l-k) C1 (M-l-k)(m-1) - Sm. Solving for C1, we have _ -1 (m-l)+ k(m-1) If C C1 -. If Ci C1l, ~1....

49. then C1 C 4- (m-l) Furthermore, C1 +C2tQ - + C N-1 C (N-1) because of the nondecreasing order. Combining these results, we get Ci > Sm and this is impossible since fCi] is admissible. The general step using the same idea as above is showni as follows. kUi+ (N-i-k) i+4-(m-1) ] mi - l ZC; i- i=l j=l (1) 4 -l i-1 ' m1- Z- 2 Cj - (I-i) (m-i) + k(mn-l) C i - -- _ --. -, k >- 1. (2) Assume as before that Ci C- i(m-l). N-1 i-1 (3) Furthermore, Z Cj E Cj- Ci(N-i). j-= j=l Substituting (2) in (1) and substituting the result for the rightmost Ci in (3) yields N-1 ri J-l j= z N-1 i-1 + - mi _ C - (N-i)(m-l)+k(m-l), i.eo, i=l j-1 N-1 N-1 C j C Z mi+ k(m-l). j =1 i=l This is impossible by the total sum condition. Q.E.D.

500 An admi ssibl u-cjuenc e of(iN 4- 1') terms may always be vvritten in the, form AlA,,A~ hr 1~~A cr~~nd the standrd forma will always be assumerld Lunless otherwise indiccated0 Remark: if An is a coefficient of' an admissible sequence of order MV, then An = + Kn(Mu-l1) where Kn is a- positive integer or zero. Proof: This follows directly from the unit condition. Q.E,D, Anl important class of admissible sequences is characterized by having A1,., 1 as nearly equal in value as possible.-, (or, equivaltent'ly, ha-ving AN a minimum) InL terms of equipment this would Idean, for example,, that the ma-iximaum number of relay transf er contacts operated by- Ca single co'iil would be a mainimum. -A useful generalization of this "'miinimum" concept follows. Def: I f l,1,00 A is and admissible sequence and no is the smallest integer., 0 1-5 n 0 14 -such that A no* lp ooo,~ An0~ -f(N-n0) differ from eaG,,Lc hother by at most (-) then -LVl,A19**p AN is a minimum segu ence with re t o 00I no=0, then we speak- of a minimum seune

510 To &r arbitrary admissible sequence 8 1,IJ~ A1,..,AN there corresponds an nI(. Its val-ue may be determiired by: (I) counting all. terms diffe111ring by at most (M —1) from AN'~i including ~ ' 1N it s elf; (2) if L denotes the number of such terms, no0 N-L. If 8 =J1,13,13,13,, then L = 3, N 3, and n=3-3 0. On the ot-her hand, if, S 1,3,15,21, thene L 1 and no 3-1 2. Note that in general', 'if L = 1, i~e., no N-l, the minimum sequence with respect to this n0 is the sequence, itself. Te-orem 25: if 1 lA.,0,0 An(. An ~19*yAN is a minimum sequence with respect to no, then n0j (1 j (N-n0)) may be defined Cals follows: Ano 4_j= l+K (M-l) for j 1,2,..,., N-no-e 1 + (K +l) (M-l) for j N-no ---,.,Nn Ni - t -(N-n10) (iq-n0)K(M-l) e ~ M-l Proof: It is easy to check that the unit and difference conditions hold. e is the number of coefficients of +WhereiX1 means the largest integer contained in X.

52. the form 1 (K+ 1)(M-1) and an integer as may be shown as follows. (1) ~-l. 1M _ +l 2t 1 ' M (2) nA - no + K' (1-l) n1=l (3) (N-no) (1 + K(M-l)) - (N-no) + K" (Mi-l). Subtracting (2) and (3) from (1) and dividing by (m-l) yields (4) e (1-1U( I-1 + (N-) - K'(M-l) - K"(M-) (M-l) which is clearly an integer. To show that e < (N-nO) consider that ~M'(M1) _A - (N-n) ) K > ------ - I o0 Substituting [ (N-no) (1M-l) in the expression for e in the statement of the theorem, replacing - by <, and simplifying yields e < (N-no) To show that the total sum condition holds, consider N-no (5) 1 Ano j r N-nO t-e(Mi-l) + (Ni-no0K(i-1) Substi1=1 tuting in (5) for e and simplifying yields N-noMN 411 no -n0 MNl - 1 S ~ An thus establishing j t1 nd n the total sum condition,

53. The partial sum condition may be established contrapositively. Let An0 be the first term for which it fails. Then nr-1 no -l (1) 1+n Aj -, and j=l j=(no n*r -i i (2) 1 A < A M-l. These imply j-l j-l (3) An0 < M ~ If it fails for successive terms until Am0 (m0 _ n0 - 1), we have m0 mO + 1 (4) Al- A- 1 (2) and (4) yield, upon j-Il j=l simplification, B A. > O j-l M, 01 ~ (m0-n0), which implies that n0-1 no Am0 - An0 > Mn0f Mn0 _ M0(IM-l) which is impossible since nO '. 1 and any two Aj can differ by at most (M-1)n nEo D. The minimum sequence may be obtained by the application of this theorem, letting no0 - O, and 0 defining Z A. = 0. Consider the following examples. n-1 (1) What is the minimum sequence for N 9, M 2,

54. nO - 0? K - - 9i 112, e - 5, and the sequence is 1, 113, 113, 11i, 113, 114, 141, 114, 114. (2) What is the minimum sequence for N = 4, M 4, and no = O? 4(44-1) O - 4 K = L.3 —J 28, e - 0, and the terms are all 1-f28(3) 85, and the sequence is 1, 85, 85, 85, 85. For any M, if I - M, all terms of the minimum sequence are the same and have the value Mj-1 j —1 (3) What is the minimum sequence with respect to nO 2, where M - 3, N - 6, and A1 5, A2 17? f-!- - 22 - (6-2) 1 2 (6-2)-2 - 3), e 1. Hence the sequence is 1, 5, 17, 267, 267, 267, 269. This concludes the preliminary discussion of admissible sequences and LD's and itis now appropriate to turn to a consideration of admissible trees, their LD s and the relation between the LD's of admissible trees and admissible LD s

5 5, To facilitate discussion of complete rn-order trees, each vertex is Clabeled iVj, The i denotes the bay in which thle vertex aippea-rs and the jits position number in the bay.j is defined recursively as follows0 (1) The vertex in theD first bay is labeled iVi, (2) Suppose thle first i bays have been labeled. Then determine the labels of" those in thle (+it lSt bay as follows: la,,:Lbel the m. vertices whose inputs are connected to the outputs of iVj i -~-lVmj -(M-l), i-IlVmj-(m-2),,,.,0, i4-lVmj (the order within this se~t is immaterial but is usually ta-ken in order from top to bottom as in the following diagram). i 4- lVmj The minor tree with iVj as its center 'is denoted T(i,j~) and its LD is denoted by S(ij) U(8(i,j)) denotes the.~ term of the LD) wi th coefficient 1. Example* if 85(iij) =4D1 +1D2+ 8D3 +.0., then U(S(i.,j)) lI)2

56 Note: The single-valuedness of U is demonstrated in the proof of the following remark, Remark: In any admissible tree S(i,j)-U(S(i,j))' _5S(u, v) where u and v u,v range over minor trees of S(i,j) which are of dimension 1 less than S(i,j). Proof: (1) A minor tree of a semi-admissible tree is a semi-admissible tree anid so there is exactly a single unit coefficient of b(i,j) and this is assigned to the centero (II) All other vertices belong to the minor trees which are 1 dimension less, i.e., S(ij)-U(S(i,j)) -- S(CuV)o QoE.D. uv Theorem 26: For a given m (order) and N, the set of admissible LDts contains the set of LD's of admissible trees. Proof: (I) The total sum condition is satisfied for the sum of the Cn = number of vertices 1 m -m2 + o.. mN-l in the tree. (II) The unit condition follows from Theorem 16. (Ill) The difference condition and the partial sum condition can be shown by induction. Assume the

57, theorem true for trees of (n-i) and f ewer bays. The,31 difference condition can now be shown as follows. J i. J 1 J 1 -kl (m-12)-o a a+ km (m-1) =(kl 4 o 9o +km) (M-1) where 0h is the number of vertices in class r r and in minor tree T(2Vh) which is a,-n (n-i) bay admissibl-e, tree. (by Theorem 15 it is semi-admissible., arid, since the order of all vertices is My it is admissible). Hence for i anidj such that the center belongs to neither Di or DJ, the difference condition holds. if Di contains the center then Ci 1 arid Cj-Ci= C 1 0j01) (Cj - 1)* mJ - 1 - (kl o..+kn) (ml1) 4mJ-(kl4- o4-km +1) (n1) o (UV) The proof of the partial sum condition can be carried through exactly as in the corresponding theorem of Vol. III (Ref0 6). QaEoDo This theorem shows that the LD of an admissible tree is admissible arid we now turn our attention to establishing the converse, i.e., that every admissible LD is the LD of an cadmissible tree.

58. For the special case of m i 2, several methods exist. The first is an existence proof developed by Shannon (Ref. 5, t the second is the constructive proof developed by this author and presented in Vols, I and III (Refo 6). The constructive proof is here generalized to cover admissible trees of any order. Let T be an N bay admissible tree of order mo Form T* identical with T except that T* does not have a vertex partition. With iVj of T* associate S(i,j) of To T* with associated S(ij)'s is called the derived LD pattern for To Consider a complete m-order N bay tree T. Associate with each vertex iVj an admissible LD of i-i -l 1 terms in such a way that the following condition is satisfied: m 5(i,j)-U(5(i,j)) - ~ S(i-l,mj - (m-L)) L-1 for all i and j o The resulting pattern is called an admissible LD _patterln Fig. 4(A) shows an admisible 3-order 4-bay tree. The classes to which each vertex belongs are indicated by the Di above the vertex, Fig. 4(B) is the derived LD pattern for this tree, Considered by itself without reference to the tree in Fig. 4(A), Fig. 4(B) is an admissible LD pattern,

59~ Theorem 27: The set of m-order derived LD patterns is identical with the set of admissible m-order LD patternso Proof: (I) Derived pattern C admissible pattern. Let T* be the pattern derived for T and consider the bays from left to righto Since T is admissible, S(1,1) is admissible0 Since each minor tree of T is admissible, its LD will be admissible and by the preceding remark they satisfy the condition of the definition of admissible LD patterns. (II) Derived pattern Z admissible patterno Here we construct a tree having as its derived pattern the given admissible patterno Assign each iVj vertex of the pattern to the class with unit coefficient in S(i j)o This will give a proper vertex partition for the treeo If V and VV are two distinct vertices of T assigned by this procedure to the same class D, and if T(V) and T(V') are not disjoint, then by Corollary 9 T(V) D T(Vv) (or the converse) and hence the coefficient of D is:. 2 in T(V)o This is a contradictiono The fact that the derived pattern of T is the given admissible LD pattern may be shown inductively by proceeding from right to left. O0oEoDo

60 This -theorem guarantees that an admissible tree may be constructed with LD S provided 6 is an admissible LD for which an acdmissible LD pattern may be formed0 Hence the first step is to determine the class of admissible LDVs which can generate patterns, Thlis turns out to be tt3 entire class of admissible LD so, First, it must be shown that an admissible LD can be "m-furcated" (i,,e, divided into m admissible LDvs) so as to satisfy the additive condition of the pattern definitiori. Def.: If SS1,ooO, S are admissible LDVs of n, (n-1)..., (n-1) terms, respectively, m and are such that S-U (b) - 2. ^, then j J S1i., m is said to be the m-furcation of 6 (or S m-furcates into b1e,, m) For example, if S - 1D+ lD13D2 13D3 +13D S1 - 9D2 + 1D3 + 3D4 S2 - 3D2 - 9D3 -1-iD4 S3 1D2 + 3D3 + 9D4, then Sl1 S 2 and S3 are an m-furcation of S since each is the proper length and each is admissibleo

61; We intended to proven that any aZidmisible LD may be rn-furcated. However, Since the%0 proof is not yet complete, we ofler the following conjecture which is assumed to be va'lid for subseqjuent theorems. Coictr 28: I f S i s an rn- or dezr adm-iissible LD of N t erms, then S may be m-furcated, i.e., there exist m a-dmissible L-D's each of N-i terms and such that m Theorem 2J: An a —dmissible rn-order LD pattern may be constructed for any rn-order LD. Proof: Let S be thecl given rn-order tD a,-nd let the.. number of its terms be da-ioted by h~. Construct ain i~~ ba,,,y complete rn-order tree a,;Lnd assign S to lVl, A-~sume that the vertices of' the first n-l bays have been assigned admissiblelI LD's. The aassig~nients of the vertices of the ntth bay may be dete-rmixned by considering each (n-I) VJ-, m-furcating its assigned b S(n -l.9L) and -assigning the so de.,termined to the nViaL - (In-j) (j 1,Mrm The result of this procedure is anr admissible" LD pattern as acheck of the definition will show,

62. Theorem _Q: The set of admissible m-order LDts is identica-l with the set of LD's of m-order admissible trees. Proof: (I) The inclusion (set of admissible LD's)C (set of LlD's of admissible trees) holds because an admissible LD pattern ca be constructed for any admissible 4iD S and then lani admissible tree can be constructed having S as its derived 1D pattern. (II) Inclusion the other way (set of LD's of admissible trees) C (set of admissible LD's) follows from Theorem 26. QE.oD

63 The Practical Problems of M-furcation and Vertex Assignment. In the first major subsection of this section we turn from the consideration of graph theory to the probl.em of M-furcating admissible LDts. This is essentially a number-theoretic problem and is discussed in these terms. The second major subsection presents, by means of an example, a "practical" method for determining the class membership of each vertex of a tree having a given admissible LD,.4 _1. The Technique of M-furcation., This subsection is devoted to presenting a procedure which is a useful aid in M-furcating LDls. A method for M-furcating any given admissible LD and proving the validity of such a method could be achieved, but to date only the following results have been obtained. (1) For M - 2 a complete and fully established method is given in Vols. I and 111 of the Language Conversion series. (2) For M - 3 this section, together with Appendix I seems to give a complete solution (Appendix I is a table giving M-furcations for all cases when M - 3

640 and N = 3). The procedure has not been proved, however, and it may require modification. (3) For M > 3 a method is provided which is believed to hold for all sequences where N > M and which may funcition as an aid in ~-furcating sequences where N A. M. It should be emphasized that the validity of the method has not been established for any M > 2 and it is presented here as a tool to aid in the process of M-furcation. 4A1.1. General Description of the Method of M-furcation. Instead of considering LD's, it is convenient here to present the method in terms of admissible sequences. Def,: If S,S,S ^ 2., SM are admissible sequences of order M consisting of N +1, N,o.., N terms, respectively, and such that M S-U(S) -- ZSj, then S1,..., SM is called an J j-1 M-furcation of S (or S M-furcates into SL.., - -).

65. As an example, consider the minimum sequence for M - 7 and N - 5. S = 1, 697, 697, 703, 703 S1 - 1, 169, 133, 97 S2 = 1, 175, 127, 97 S3 = 1, 175, 127, 97 4 - 1, 175, 121, 103 S5 = 229, 1, 67, 103 S6 = 229, 1, 67, 103 S7 - 235, 1, 67, 103 Here S M-furcates into S1,..., S7. The M-furcation technique defines a function or operator which maps a given admissible sequence onto a set of i admissible sequences of length one less. These M sequences will be called the image sequences, the given sequence the domain sequence. If the domain sequence is denoted l,A1,A2,,oo, AN, then the sequence A1,A2,.oo, AN is called the reduced (domain) sque nce. The mtth image sequence is denoted {x4. The superscript indicates the image sequence under consideration, and the subscript the term of the sequence. The M-furcation operation may be expressed in the form of an (M+l) x N matrix called the M-furcation

66. matrix CIand denoted M(io). If the first row is design:ated by 0, then ao., = A, the nrth term of the reduced domain sequence. The nIth termi of the mtth image sequence m 1,2,...,M is xm -= am,. The domain sequence l,A1,.., AN will be assumed always to be in monotonic nondecreasing order. Any technique for M-furcation must provide a method which, given a sequence S (in monotonic nondecreasing order), will yield a set of sequences S1,, S such that M (1) m_ xi x An for n = 1,.*., N, and m=l (2) every image sequence x1,..., x4 (m 1,.o.,1) satisfies the four conditions of admissibility, i.e., the difference condition, the unit condition, the total sum condition, and the partial sum condition. These conditions are, of course, all interrelated, The difference condition is met by so constructing the xn that they are of the form l1 k(M-l). The unit condition is more difficult. In the example for M " 7 and Ni 5 it was possible to confine the units to the first two columns. This, as might be expected, is not always possible if the other conditions are to be met. For example, consider the M-furcation of the

67. minimum sequence for M -- 3, N 3, given by S = 1, 13, 13, 13 S1 = 1, 5, 7 S2 - 7, 1, 5 S3 = 5, 7, 1. Any M-furcation of this S-sequence will require exactly one unit in each column. If M is fixed, the class of M-order admissible sequences may be divided into two subclasses. Class I: The set of all M-order admissible sequences for which N ~ M. Class II: The set of all M-order admissible sequences for which N > Mi The method considered here is a technique for Class II sequences. It will be assumed in the technique that the M-furcations of Class I sequences are known. For example, this is the case for M - 2 where there are three possible Class I sequences: S 1, 2 S = 1, 2, 4 S- 1, 3, 3 S1 - 1 Sl - l, 2 Sl 1 l, 2 S1 2 1, 2 S2 2, 1. Appendix I gives this data for all Class I sequences for M - 3. This assumption is not unreasonable for, given an M, there are but a finite number of Class I

68. seiuences and these, in most cases, may be Mi-furcated by trial and error aided by a judicious appiication of the General method. (If time perraitted, an attempt would be made to determine a general method for Class 1 se uences ) We will assume^ then, that the M-furcations of Class I sequences are knovln. Consider now the Mi-furcation of Class II sequences~ Def.: If' 8 -,A1,.., AjN, N Mii, is an admissible sequence of order M (in monotonic nondecreasing order), thlel its funidamental secju.enlce Sp denote d i,a,.e., ai is that Class I sequence (in monotonic nondecreasilg order) which sati sfi es (1) am A4 (mn 1,2,=.,, M ), and (2) its n0 is as small as possible (see Subsectioln 3o3, page 50) For example, suppose - i, 11i, 15, 35, 59, then the Class I sequence 1, 3, 9, 27 satisfies Condition (1)o It does not satisfy Condition (2) however, for its n0 o 2, and, for 1, 11, 13, 15, n 1. Hence the latter seqtuence is the fundamental sequence of S. If S - 1, 71, 73, 73, 73, 73, then SF 13, 13, 130

69. Def.:O1* The (M t l) x N dimensional ma,-,trix in which elements are detercmined as follows is the fundamental matrix of 8, denoted F($): ao,n an for n 1,.,,, M. and ao, n 0 for n IVIf- ly,, N. The a~ for m 1,.e0.., MA and n 1,...,7 M a re th e values given by the iV-furcation of 8F. if n = M +l,,., N, then am n= 0 no matter what the value of' m. The distribution of units is given by the fundamental seune Essentially, it is the distribution provided by the M-furcatioln of' 6p which has the "broadest possible distribution of" units."1 These concepts are made precise in the sta-itemne.nt o f th e technique given in S3ubsection 4.1,3. The quantity A a,,- a1 kII (Ni L, =1,. N is called the n'th overflow. an for n > Ni is defined to be 0. This overflow must be distributed Camong the non-unit n'th coefficients of the image sequences. This procedure may also conveniently be represented in matrix form.

70. Def.: The (M-1+1) x iN dimensionalMi matrix iwhoe t;erms Care defined as fo.llows is the distribultion matrix of S and is denoted D(6): aO,n An an (ni. N) am n - 0 ifthe corresponding coefficient of i(S) is 1, otherwise it is that calculated by the technmique given below. T1ie'coimpl ted M-furcation is then obtained by adding F(S) and D(S). Rema~Lk: M() f F('S) + D() Given an M-order Class 11 sequpence wA1,... AN, M-furcation may be carried out in four steps. btep I1 Determination of ' the fundaImen'tali sequence of 5. Step ii: Construction of F(j). Step i1:1 Construction of D(). (A) 'The first ijot col.mns of D(S) (B) The gener'al co lumn for n > M. Step IVL Determination of M(b;) by adding F(i) and D(S). The remainder of Subsection,4.1 will give a detailed discussion of these steps together with several exampni es.

71.0 A*1l2* Determination of the Fnamental Se~uxice. 6F may be determined most easily by comparing the given sequence with Class I seq"uences and pick~ing out the one satisfying the covering condition and having the smallest n0. It may also be determined mechanically. This is done by computing the terms of 5Fsuccessively. Let lA1,A2,..., AN be the given sequence. Define the first term of SF to be 1. The second may then be determined by computing the minimum sequence $ l,,.., whosen length 'is M+l and comparing second coefficients. If Al 4 1 th-eEIn al A1 if A1 -: 6 th en a1 - To determine the third coefficia'it fined the minimum se-qu en ce huvin g lA.31 as its first two coefficients (where A is the second coefficient of L4F) and repeat the process. More formally, consider the coefficients of S =1. Aj.,.~A N' the given sequence, one by one arid in order from n= 1 to M0~ (1) If An 1 l- kn (M-l) then an l+ kn(~M1 for n nn+l,,,,, M-e~. and an = -~ (kn )M-) for n M- en +-l ~ m

72. r M n-l MJ - - (M-nt 1) k^. r - _____ n (M-n +-1) (Mv-1) M n-l &t1J. - Aji - (M-n f-1)(l kn(M-l)) and en jl __ (iV- 1) (2) If Ai < lkM-l), then define an An and consider Aril Consider the following examples. I: Let S, 13, 13 13, Here N - Mi - 3 and k l - 53 l = 6. Al 1 6- 6(2) - 13, and el = 0. Hence al - a2 - a3 - 13 and SF - S. II; Let S- =, 11, 15, 15, 79. Here N -4 and M 3. As in Example I, kl 6, 11 A1 < 13, and, consequently, a1 - 11 Consider next A2. k2 112 A2 15 - 1+ 6(2) -13, and e2^ 1-2 1. As a consequence, a2 - 1+6(2) 13; a3 lt 7(2) 15; and SF =, 11, 13, 15. n-1 tlf nl - 1 then define z Aj - 0. jil 7Where IX] means the largest integer contained in X.

73 4.- 1. j (coLstctruction of 10~1. F(S) is an (iVl X1) x i\ matrix. The first row is labeled 0 and, for n. NI, a0 n is tile n'th coefficient of the reduced fundamental sequence. For n > MI, ao n 0.0 All coefficients in columnls beyond the Mlth are 0. The coefficients of the first M columns are determined by the M-furcation of the fundamental sequence. The fundamental sequence is a Class I sequence and so we assume that its M-furcations are known. Usually a sequence may be MI-furcated in more than one way. In order to avoid possible difficulties and in order to make the procedure precise, we require that the distribution of units be the "broadest possible." This subsection is devoted to defining this concept and to providing a method for determining the "broadest distribution" for a given- sequence~ Theorems which are needed here will be stated without proofs and, in fact, may not as yet be fully provedo The distribution of units in an M-furcation may be represented by an Mi x N matrix formed from the Mfurcation matrix by deleting the 0'th row and replacing every coefficient am 1 by 0 If A is a Ynl'

74. distribution, let A, called a non-increasing distribution, be a distribution formed from A by a permutation of columns and having the property that if coltr;umn m contains x units and column (m - l) has y Ulits, then x -> y. The relation > (read t is a broader distribution than") may now be defined. Def.: Let A and B be two distributions, Consider A and B and let m be the first column for which (number of units in column m of A) f (number of units in column m of B). Then A > B if and only if (nunber of units in column m of A) < (nurmber of units in column m of ) The distributions used in our technique of Mfurcation are required to be non-increasing distributiotls. We limit our discussion to tlhe case When iN M for, since we require our distribution to be nonincreasing, this will cover all the interesting cases. If M = 4, there are five possible distributions:

7 5. (1 ~ D~( D4 K r i). D DZ D D Clearl, D5 D~3 2~ 1 In order to dete~Luine, the broadest distribution for a given S. it 'is necessary to relate the concept to that of admissible sequences. A partial ordering useful in this connection may be defined in the set OV(MN) of all mnonotonic nondecreasing sequences of order M and length N-f-i. Def.: if S,, S2 6-d ~(M,N), then S, ~tS2i and only ifS cana be derived from S2 by flow. (The "Iz ero flow" being considered a flow.) 1 -2 may bDe rezaid, "16j can be obtained by flow f romt 82" Remark,: The Jrelation betwee.:~n elements of 1/(Mi defines a- partiaw orderin (i.e., is reflexive, ainti-sylmmetric, and transitive).

760 then f;,. If - 1 9 1.5 15 and S2 1., 7, 9, 23, S1 - S2o However, if S1 1. 5, 17, 17, and 1, 7, i3, 19, tlhe'l 81.. anld S2 SgL. Dfl: if D is a distribu tion ad i e / (M, M) having D as as distributio and if S is suchf that there does not exist an S with distribution D such that S 8. S, then S(D) is called a m inimal s^e.queniTce for D. Remark: S(D) is a liqi:ue sequence. We may consequently speak of a smallest seiejieie with distribution Do S(D) - 1, C1C2, ~ooo ~ M may easily be obtained by the following procedureo (1) Form the distribution matrix D, (2) In the positions not containing Luits insert,M 2o e M M-I in that order. (3) Total the columhns. The total of the m th column i S = Let M..3 anid D - 1 Then the calcu 13atio 19 ota 7 13 19 totals0

77 If - 4 arnd the Di ar, defined as above, then S (D1) 1,, 16 64, 256 S(D2) - 1, 7, 13, 64, 256 S(D3) 110, 10, 64, 256 S(D4) o1,10, 25, 49, 256 ((Dj) = 1 3, 37, 97, 193. These concepts together with the- following theorem make it possible to determine the broadest distribution for a given S. Theorem J: If S S (D) and D- is the broadest distribution 6 may have, then D* _ D~ T heorem I2 If S? S (D), then S cannot have distribution D* where De Do We illustrate their use in three exampleso Exar2-le iLo Determine the broadest distribution for S-1, 9, 9, 21 (M l 3). Clearly, D1 D2 ) and D3 ( 1 (D1) 1, 3, 9, 27; S(D)- 1, 5, 7, 27; S(J ) 1, 7, 13, 19. Obviously, S - 8(Di1; S S(D2); S. $(D.-) Hence D2 is the broadest distribution

78. possible for S. It Ls interesting to note that 1. 7, 15, 17 and all other sequences of the form 1,, 9, -, - and 1 I 1a 13, 13 have D. for broadest distribution (see Appendix I)o Examna:l1e 2= Determine the broadest distribution for S 1 10, 229 52, 256 (iM 4D) Using) the Di and S(Di) already calculated for this M, it is clear that S 2- j(D1); S S S(D); S?(D3); S ) Since S * S(D4), no broader distribution is possible and D3 is the broadest distribution for the given S. Exampie 1: Determine F(S) for S 1, i11 15, 15, 79 ( - 3). (1) SF - 1 11, 1.3, 15 as may be determined by the method of the preced.ing subsectiono (2) Determine the broadest distribution for SF using the data from Example 1. We see that:F Q(DI) j S- 5;(D); i S s (D3), antd hence that Do is the broadest distributionr (3) Constr-uct F(S) o Applying the definition of.'(s) given in the beginning of this subsection and using an M —furcation with distribution D3 (one is provided in the appendix) we see that \5 0> iF(S) 91 0 \, 7 1, 55 0/

79..L-..k o Costructio). of i)j (j), the distribution matrix of S, is an (M +1) x N whlose 0Ith row has coefficients aO n -a for n ^and in for n M amr n 0 if the corresponding coefficient of F(S) is 1o These will be referred to as the derived zeros of D(S) The remaining coefficients are calculated column by column proceeding from left to right. Procedure I (n r M) (1) Let un be the number of derived zeros in the ntth column and let (An -n aLn) b.e ai, Form Z Xj for all m such that a n 0 The xa- are j — 1~ the coefficients appearing in D(S) They will not form an admissible sequence. In gen1eral bars will indicate coefficients and quantities calculated with respect to D(S) although they may be omitted when no confusion will result. (2) At the ntth stage consider the image sequences in the following order Let the sequence with am = 0 occupy the last un rows and arrange the others in descending order with respect t-o the mi.agnitudes of LxJ. *xm will refer to the sequences in this ordero j-l

n -.l, For 1 2,,, MI-ul form n — " i(3) We de fi:ne k an d e s follows (a) I f Ai - a:1 > i _ t l. ---~J`1 i... -.. - 'U-n- 1. - A) ( ) ( -l. (I i'Ml-i) 11 -I (b) If -. < aiK, ki - e% 0. (4) The coefficients not defined as zero by the iMlfurcation of SF will be: kr ( —1)+A. an d (n- 1) (M.i-l).fA. where MglM - n M a — 1^nO1.1 l ql. 2-A = O, anld - abI means the smallelr of a qal and b. The above expressions are not as formidable as they appe:ar If A 11 -'^ I n, then ^n ^n If A - an < An then it merely formalizes the idea that AL n - an be applied to the 'A m in decreasing order of magnitudeo Thus, it is to take care of the largest first, then the next largest and so on as far a.s possible, Note that is of.e form i (M-1.) o

The coefficients arre assigned in the obvious manerl. If A: - an an A, 0, 1then th e first en rows have coefficients of the form (ir + 1) (-l1)+1 n. As an example, consider the following case -where IM 4. S - 1, 10, 25, 163, 163,. SF - 1, 10, 25, 1.51, 154 10 I 4 4 25 4 4 1 16 151 49 49 52 154 31 31 28 0 0 0 0 O f ' O I * fC u ~ * iD()./ ',' i.. 0 0 0 I 0 0 0 0 f). 1 64 o.2 9 o 6 0 3 0 3 3 0 6 i t I The calculations yielding these results are summarized in the following tables. ik - TablJe k1 -= k = el = e2 O- 0 12-0 1. k3 -F i.1J k = 4- 0 (here /,_ - Table e, ), * - e n -a Ln);. - An- an< L n); e4 = O. / 1 -- 4 4. 3 m L4 - { 9- (6, -3+ 0); o - 0. Q[9-(6-.3).; 3 o o0. {9 - (6); 3- }_3. Qj9-0; 6 6.

Procedure II (n > Mv): This procedure is very similar to Procedure I if Un is taken as zero. 2.xj is determined as j =1 beforeo The seyuences are ordered with respect to it* n rand n are then calculated ao n in this case will be An which is of tle form 1 -k-(M-l) 1. The coefficient of the image sequences will be of the form 1 +-kn (i-) r An or 1 + (x-n tdl) (i-1) - t where rAn M 1 -M - k(-l) kn L MMl J atrd 4 n & —. —" — __ where en is the number of coefficients of form I, (k+ll) (~-1)+ An, As before the first el rows have coefficients of this form. Once the matrices F(SJ and D(S) have been calculated, the M-furcation of S is determined for M (S) F(S) +- ) (S)

alE__ ~xapl_.es of LM-u~lL.c tioll. Example 1: Determine and iVM-furcate the minirmum sequence for M 5 3 and N = 5. It is worthwhile to construct the following table before beginning the M-furcation. Powers of M: 1, 3, 9, 27, 81, 243, 729 Partial Sums: 4,13, 40,121, 364 Applying Theorem 25 yields (- (3- 5 7 k M '3) -" 35 e( (5-0)-I1kI) 4. Thus, S - 1, 1 +-35(2), 136(2), 1-36(2), 1 636(2), 1 i- 36(2) - 1, 71, 7, 73, 73, 73. SF -1, 13 13,. 13. 413 1 13 0 0 1 9 3 0 0 3 1 900 \9 3 1 0 0 /58 60 60 73 73\ 0 44 22 19 23 3 - 8 0 38 17 25 ~ [30 16 0 37 25/ /71 73 73 73 73 \ \39 19 1 37 25

84. The image sequernces may be compared with 1,, 9, 27, 81, 243 Partial Sums: 4,13, 40,121, 364 to determine if tLhe partial sum condition holds. The admissibility condition holds for all these and hence we have an M-furcatioln. Th important calculations for this M-furcation are given in Table I. TABLE I k i F5 14; el (58 _.QI_ ~/j- 1. k1 -_2J 3-1. 2 72; e2 ( 3-1 1 = 73 --- - 8; e 1) 1. k5 - 73- =; e5 0 Eximpe 2* If now we M-furcate the image sequences of Example 1, we will have avCaiable with the table in tihe appendix all the data needed for assigning all the v. ertices of ithe tree. Thiis example consists iri ca;iculatinig tlhese M —ifurcatio ins Aill the image se~-quences in this exrample appear in Table I of the appendix and hence are admissible.

85 02 "1 1 17, 0"' 5 1 14 S, -.,19,25,7,39 9) 'l, 3I 18I = 1,13,1313 S2F - 1.) 19 ) I f13 F Si) / 1 9 /6 D(Si) = ~ 2 4 /19 MI(S )"a 5 13 13 13 9 3 1 9 3 1 10 12 6 4 0 8 4 o 23 25 15 7 1 17 7 1 0 F(2) 0 53\ 17 17 D(S2) 19 53 1i7 (S2) 19 /13 13 1 9 3 1 9 3 /4 12 0 6 2 0 2 6 13 3 9 1 18 8 10 0 31 11 19 1 0\ 0O O i 3F -= 1,1 3,1.3,13 / 13 13 13 - ) - 1 9 3 3 1 9 i 9 3 1 47\ 13 1 15 D(83) 19 6 0 2 J4 (17 1 5 11 12 8 0 4 25 17 1 7 24 10 14 0 37 13 23 1 0 0 0/ 39 9 11 19/ 39\ I9 11 19 25 15 1 9 47 /19 131 1 15 vi(S3) 5 19/ 13 The important calculations for these M-furcations are given in Table Io1 For S1: For S ' 2 TABLE II 6- - k 1 1 el 1 2 k2 L 2; e3 k4- -4 8; e4 - 0 k jj -- 3-2 kl.A 1; el o 0 k2 - 2.;-j.. 2 L2k j - 2; e2 - 2 —222 - 2 3 2 2 3 2 k 747-3-8 6; e4 0 4 3.2; 4

For S6: 3 l =. 1;0-6 (l6-2K1 ) 1. 2 1... ~. k,3 2; e3 1.. - ~ k 4e4.; 3l 3 i,,, ~. j 4; - '0 I-2 - 2. e - 4 - 3.2 - 2~~~1 t, Examle 3: Construct the minimum sequence with respect to n0 - 2, M - 5, and Al - A2 749, and then M-furca.te it. It is useful to construct Table A before beginning the calculations. TABLE A m 1 2 3 4 5 6 7 8 N 1 Powers of M: 1,5;25;125;625;3125;15,625;78,125;390,625; Partial uSums: 6;31;156;781;3906;19,531;97,656. This table, besides giving values nleeded in later calculations, gives some interestinlg facts about the tree. It tells, for example, that the tree contains 97,656 vertices and has 390,625 outputs. The minimum sequence may be determined by applying Theorem 25 This yields 79 1 62x- (749 + 749) ( (7-2) 6152 e (,612-(7-S2A,87,x Al) - 3 4

Thus vwe have three terms of the form 1 +- (K+l)(5-1) 1-4,808(4) 9 19'233 aiid two terms of the form ilt 4807(4) 19229. However, our minimum secquence is S 1, 749, 749, 19229, 19229, 19233, 19233, 19233. The first step in M-furcation is to obtatin the fundamental sequencle. To do this, we follow the procedure previously outlined cand calculate 1 1 o - 195,:nd A1 749, l 195 (4 781 Hen ce ai 749, aid we ccnsider A2. 2 l2+ ii] 197, and A2 2 r 5-2 4~ IJ /) - a}c A 749, 1+197(4) - 789. Hence a2 - 749 and we consider A3. 749.7.2+, -#. 1 200 and 3 i 1,5-3 ) (4) e -- 2AQ-4 20) i, 19229 - A3, 1-200(4) - 801 34 Hence a3 " 801 and a4... 801 and a5 805, i e,, S - 1, 749, 749, 801, 801, 805. The tecnulique presented in this report assumes that ani M —furcation of the fundamental. sequCece is known.o Tlhis is, of course, not in. eneral the caset The difficulty in the formula tioi ofi a complete technique lies in the distribution of the units. Here we assume as nearly equal a distribution between the first two columns as possible and construct the

88. M-furcation matrix. The coefficients of the O'th row are the an of SF. The calculations are made according to a variation of Procedure II of the distribution matrix construction technique, thus: Fa _ \. n - 7 an e - Arl-i'-(M-u,,) (1+ k1l(M O )) k u T) arld e where un is the number of units in the n'th column and a n is calculated only with respect to the set of rows n-ot contaiinilg units in column in. The coefficients are of the form 1/ k1(Mli) and 1 + (k4+ 1) (1-l). Applying this to the case under consideration yields /749 749 801 801 805 1 1 249 209 161 161 _ _ 2 1 249 209 161 161 (JF) - 1 249 209 i61 161 4 373 1 85 161 161 5 \ 373 1 89 157 161 The four conditions of admissibility check for these five image sequences~ Hence this is an iM-furcation. The table of calculation is: T3iBLE FOR COIST'RUCTlNG M (SSF) 1(1_4-f-#_L_ 7 3 kl = 93; el 5 0 k2 -7 79y9-0- i = 62; e2 = ). L~-2) l(-5, — _J) (5 ' k3 - 80Q1S72 3 1 21; e3 42 1 k4 51-4 39; e4 C L 45 ] 4; e4 5 0. L_ - 81 j =-*' -~

89. It should be noted that the procedure used above violates the given tecuhnique because it does not employ the broadest possible distribution of units. Nevertheless, it goes through, illustrating that the "broadest possible distribution" condition is not always necessaryO Slight modification of the general technique employed above is not always successful. For example, if S " 1, 7, 13, 19 and the diagonal distribution of units is employed, then the application of the general technique (because it does not anticipate the unit in the third column) will yield /7 13 19 M7(S) 7 3 5 1/ This is not an M-furcation since the image sequences are not admissible. However, if modified by subtracting 4 from aj,2 and 2 from a2,3 and adding 4 to a352 and 2 to al3 it is an M-furcation Returning now to the original problem, we have 749 749 801 801 805 0 0 1 249 209 161 161. 0 0 1 249 209 161 161 0 0 - 1 249 209 161 161 0 0 373 1 85 161 161 0 0 373 1 89 157 161 0 0

90. It is now necessary to calculate o /O 1 0 _ 2 0 D( D j " 4 0 5 0 wvlich yields 0 /749 i 1 3 i 4 373 5 373 o 18428 o 3684 0 3684 0 3684 0 3688 0 3688 18428 3684 3688 3688 3684 3684 18428 3688 3684 3684 3684 3688 19233 3845 3845.j845 19233 3849 3849 3845 3845 3845 749 249 249 249 1 1 19229 3893 3893 3893 3773 3777 19229 3845 3849 3849 3845 384.1 19233 3849 3845 3845 3845 3849 19233 3845 3845 3849 3849 3845 19233 3849 3849 3845 3845 3845 Totals 749 749 19229 1.9229 19239233 233 19233. CAL CULATION T ABLE iFOR D18TRlb'UT1014 hiid~1TlX k [428 921; k4 [ 4 - 920 e3- (182 921lA-521 2. e4 ( 4, k - L8 4 921 60; e6 - -) 5 *45> 4 / k6 - ~[1C2X _ 960; e6 -93- 6?6 A) 3. 7 5 - 4 7 k7 - I - 961; e7 - 0. Check of the 1M- furcation: (i) The totals for the last five rows in each column of iil(6) equals the coefficient in the first. (2) The admissibility conditions,, (a) The unit condition holds obviouslyo (b) The total sum and partial sum conditions may be checked togethero Note that the first three rows are essentially the same and the

91. last two are likewise almost identical, Consequently, it is only ncecessary to check the third and fourth rows: Row 3: 1, 249, 3845, 3845, 3849, 3849, 3893 Partial Sums: 250, 4095, 7940, 11789, 15638, 19531 How 4: 1, 373, 3845, 3845, 3845, 3849, 3773 Partial Sums: 374, 4219, 8064, 11909, 15758, 19531. These results check with Table A and hence these conditions are satisfied. (c) The difference condition may be checked by subtracting one from each coefficient to see if the result is divisible by 4. It is and so the difference condition holds.

92 a...VertexAssigrnmenits. The M-furcation techniq~ues discussed have been presented in terms of sequ~ence,,-,s instead of LIDIS. it is now necessary to rela —te the re-sults obtained to tree theory, specifically to determine the class mn emibersvhip of' ec~a-ch vertex in the tree. One way of doing this 'is to construct the admnisslible LD pattern arid thenr deduc4e, the vertex assigninent from it. A sy s tema(:7,tic method equivailient to this is illustra,~"ted in the folliowing examiple. Exagjl e i: Construct anl admissible,.I 6 bay tree T of order 3 having ij.D(T) i~ Di+- 711)2 p-7313 -~ 7~ 731)5+-73D1)6 The M-furca-tions needed have been carried out in Example.~s i anid 2 of" thre -Last subsection or are available in the appendix. Thi s information is s~ummarized in Table 1110.~ t Ie,1 Construct a comaplete 6 bay tree of order 3. It will,L,. of course., be a partitioned tree but its vertices will not be divided into proper classes0 That is the function of Step II, 1te II (1) The --- classes are denoted Dl,,,,,' 1)Nl (h-ere Nl +- 6). -As sign lVl. to Dlo (2) List aill the M-furciation mnatrices., allowing room at the top Cand right for la'-bels as in Table 111.

93. (3) Label the columns of the (M1-) x N matrix D2.'*. DN +i The colulin label designates the class to which all the numbers in that columnl "belongo" This induces a labeling of the (i4-l) x (n-l) matrices, for the columns of each of these matrices are labeled so as to preserve th-e class membership of the numbers in the top rowo (4) At the same time the M+ 1 rows of the matrices may be labeled by iVj so These will indicate the vertex whose assignment is given by the 1 in the row so labeled. Label the top row of the (m +1) x N matrix 1Vl and the remaining rows 2V1,..., 2Vm. This labeling vill induce a labeling of the rows of the (mf-l) x (n-l) matrices as follows. Label the top row of each of these matrices with the label assigned it in the (M +-l) x N matrix and assign labels to the image sequences in accordance with the rule that if iVj is the label of the top row then the M remaining rows are labeled i - VMj- (M-); i+-lVij-(I-2);ooo; i- iVMj- (ML~M) o These are the vertices whose inputs are connected to the output of iVjo

94. (5) The repeated application of the procedure described above produces a labeling of columns and rows for all matrices listed. If a matrix which has already been labeled is to be used again, the columns may be labeled by adding a row above the existing rows of column labels and the rows may be labeled by adding a column to the right of the existing columns. See, in particular, matrices (A), (B), and (C) in Table IIIo (6) To determine the class to which a vertex, say, pVq belongs, first find its occurrence as a label of row j, j not the O'th row, Suppose that it is in the r'th column of row labels (numbering them from left to right), then determine the matrix column containing coefficient 1 and assign pVq to Ds where Ds is the label for this columnn in the r'th row of column labels (numbering the rows from bottom to top). For example, 4V27 appears in the second column of row labels in matrix (i) of Table 111; the unit of its sequence is in column 3 of the matrix; the label of this column in row 2 of the column labels is D20 Hence 4V27 is an element of class D2o The classes to which the vertices in the N'th

9 5, anid (N +_l) St+ bays of a tree belong can both be determined. for thEe M-furcation matrices of two columns. Those of the Af'th are read off in th-e]. usual miariner, Th os e o f th e (O ~- 1) s t a.re,., determined as follows. Let il Vj be avertex in the 10th bay. its outputs~ are connected to the 'inputs of1 -i+KV1ij - (M-l),..., * 14 ilVivij -(M —M) and the-_.-n are assigned to thel class to which the non-unit term belongs. For example, consider 5V62. lt is connected to 6V184,y 6V185, and 6V186. T h ese are all assigned to D5 for in Table 1II matrix (B) 5V62 appears in column S., hence class assignments are given in row 8 Cand the non-unit column is labeled DI). The classes for all (N4-1-)st bay vertices rmay be quickly determined by going through the NVj's in order. If an GN4l)st column vertex i's given, then its class can easily be determined by the -use of the following remark. tThegie sequence is of the form l.~,A-1,2,.,.. i1lj and thus contains (i++l) terms. This means that there are (N - 1), bays in a tree heaving tD 1 Di+ ri

96. Remark: If nVk is a given vertex of a tree of order M, then the vertex of the (n-l)st bay to which the input of nVk is connected is n-lVh ivwhere h LjLJ1l Proof: The outputs of n-lVh are connrected to the inputs of n-lVMh- (M-l1),., n-lVM'h- (I-M). Thus, k Mh-ii where 0 _ R L M-l and (h-l) (l- r ), i.e., h-1. J.EoD, Exa.mlel 2: 2 Determine the assiginment of 6V200 in the tree of Examples 1 and 2 of' the last subsection, Applying the remark yields 2 0 1 = 67, i e, the output of 5V67 is connected to the input of 6V200. 5V67 appears in column 10 (see Table III, matrix (B)), and hence the assignments are given in row 10o The non-unit coludm is labeled D5; hence 6V200 is in class D5. The aim of the M-furcation tech.iqLue is, of course, to divide thle vertices' of a tree into proper vertex classes This sequence of examples,- then, ought to end with the diagram of an admissible tree of order iMv - 3 ancd U.D - iDi 71D2 + 731D3 73i 73D)+ 73D6 with each vertex labeled to show the class to which it

97. belongs. Since this tree has 729 outputs, 364 vertices, 243 of which appear in the final bay, it is impossible to give the entire tree diagram in a page figure. Its first four bays, however, are shown in Fig. 5.

98. F, -... I.il-IbL6 111 D2 D D4 5 6 71 1 31 39 D5 19 1 5 13 17 1 5 11 D3 19 7 1 3 3 D5 5 1 3 73 53 1 19 7 D6 25 15 1 9 25 15 1 9 '73 7) 73 25 19 23 47 17 25 1 37 25 2 D6I D3 - 2 1 D6 D /1 3 3 1 3 9 2V1 2V2 2V3 DI i. MAIIdX (A) 19 V3 3V9 9 4 V7 4V25 9 4V8 4V26 1 / 4V9 4V27 1 2 D6 D4 25 7 17 1 D2 31 11 19 1 D3 53 17 17 19/ D4 47 13 15 19 D2 39 9 11 19 2V1 3V1 3V2 3V3 2V2 3V4 3V5 3V6 2V3 3V7 3V8 3V9 t)f D5 1 1 3 D6 D2!9 1 3 D4 13 3 9 1 D4 15 7 7 1 D5 11 3 1 7 D5 13 5 1 7 15 9 1 5 D2 19 5 5 9 D4 19 9 1 D6 7 9 1/ 3V4 4V10 4V11 4V12 3V5 4V13 4V14 4V15 3V6 4V16 4 V14 4V17 4V17 4v1 8 3V7 4V19 4V20 4V21 D6 D 25 37 17 13 1 23 7 1 D6 3 15 17 5 7 1 9 9 1 ) 3VI 4V1 4V2 4V3 D4 D3 17 17 9 3 7 5 1 9 3V2 4V4 4V5 4V6 D3 5 1 3 D2 11 5 5 1 D5 23 7 7 9 3V8 4V22 4V23 4V24

99. T BLE,111 (comt.) 10 D2 D5 9 D2 D5 8 D2 D5 7 D5 D6 6 D6 D5 5 D2 D4 4 D 1 D4 3 D6 D2 2 D3 D 1 D6 D3 5 7 \ 4V1 4V5 4V12 4V13 4V14 4V18 4V19 4V21 4V22 4V23 1 3 \ V1 5V13 5V34 5V37 5V40 5V52 5V55 5V61 5V64 5V67 1 3 5V2 5V14 5V35 5V38 5V41 5V53 5V56 5V62 5V65 5V68 3 1 5V3 5V15 5V36 5V39 5V42 5V54 5V57 5V63 5V66 5V69 1 2 3 4 5 6 7 8 9 10 MA1.HTRIX (B)

17 D6 16 D6 15 D3 14 D3 13 D2 12 D6 11 D5 10 D5 9 D2 8 D4 7 D6 6 D6 5 D3 4 D5 3 D3 2 D4 1 D4!3 1 1 V D3 D2 D2 D5 D6 D4 D4 D D2 D4 D6 D5 D3 D2 D3 D4 D6 D3 3 3 3 3 100. TABLE 111 (cont.) 4V2 4V3 4V4 4V6 4V7 4V8 4V9 4V10 4V11 4V15 4V16 4V17 420 424 4T25 426 4T27 5V4 5V7 5V10 5V16 5V19 5V22 5V25 5V28 5V315V43 5/46549 5V49 58 170 5V73 5176 5V79 5V5 5V8 5V11 5V17 5V20 5V23 526 5V29 5V32 5V44 5V47 5V50 5V59 571 5V74 5V77 5V80 5V6 5V9 5V12 5V18 5V21 5V24 5V27 5V30 5V33 5V45 5V48 5V51 5V60 5V72 5V75 5V78 5V81 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 MATRIX (C)

101. D/ -4 D D/ 5 5 Di Fig. 5

102. APPENDIX I. The M-furcation of Class I beqluences 1. Table for - = 2: 1, 2; 1, 2, 4; 1, 3, 3 1 1, 2 1, 2 1 1, 2 2, 1 II. Table for I = 3: (1) N = 3. (A) 1,3,17,19 1 5 7 1 5 7 17 5 (B) 1,5,17,17 1 9 3 1 7 3 1 9 (C) 1,7,15,17 1 5 7 3 1 9 3 9 1 391 1,3,15,21 1,3,13,23 1 5 7 1 3 9 1 5 7 1 5 7 1 5 7 1 5 7 1,5,15,19 1,5,13,21 1 7 5 1 9 3 17 5 1 3 9 319 3 1 9 1,7,13,19 1,7,11,21 1 3 9 1 57 3 1 9 1 5 7 391 51 7 1,3,11,25 1 3 9 1 3 9 5 7 1,5,11,23 1 5 7 1 5 7 3 1 9 1,7, 9,23 1 5 7 1 3 9 5 1 7 1,3,9,27 13 9 13 9 13 9 1,5,9,25 1,5,7,27 13 9 13 9 15 7 13 9 31 9 31 9 1,7,7,25 13 9 1 3 9 51 7 (D) 1,9,15,15 1 7 5 3 1 9 5 7 1 1,9,13,17 1,9,11,19 15 7 1 3 9 3 1 9 3 1 9 5 7 1 5 7 1 1,9, 9,21 1 5 7 1 3 9 7 1 5 (E) 1,11,13,15 1 3 9 3 9 1 7391 715 1,11,11,17 1 5 7 3 1 9 7 5 1 751 (F) 1,13,13,13 1 7 5 5 1 7 7 51 (2) N 2. 1, 3, 9 1 3 1 3 1 3 1, 5, 7 1 3 1 3 3 1 (3) N 1. 1, 3 1 1 1

103 itPPflidDIX II. Notes on the Validity of the M-furcation Technique Although no proof has been established, steps have been taken in this direction. The pilan that was contemplated is analogous to the proof for M 2. M First, the fact that f xj - Aj (j = 1, 2,..., JN) m=1 was to be established, and, second, the admissibility of each sequence was to be demonstrated. Admissibility was to be proved by showing directly that the total sum condition, the unit condition, and the difference condition hold, and then attempting the more difficult partial sum condition. It was hoped that it could be shown that the partial sum condition holds in the image sequences in derived order and then that it holds in monotonic order. To facilitate the latter, the concept of a quasi-monotonic sequence is generalized to that of a sequence of degree L. It is the properties of such sequences that are now considered. A: Sequences of degree L. Def.: 'x is a seluence of degree j if and only if xj - xj+k - L for k > 0. The force of this definition is that a given term can be at most L larger than the smallest of the

104.0 succeeding terms. For example, if. L 6., then 1, 5, 10, 4,j 7, 4,j 5, 12 is a sequence of degree 6. Def.: If xj,xj+,,, are a pair of" successive t erm s of a s e quenc e such tha t 0 Z., Xj - X then the pair is called a- do i sic it is such terms that introduce degrees~ 0 in a 'sE:q5c&uce).11 L emm a 1: sequence of degree L of' integers x1.,.., xil can be mad-e of degree 0 (i.e.., monotonic non-decreaising) 'by pearmuting degree pairs. Proof: Consider the set {x,XiK N-x This will contain a- finite number of pairs. Clearly, for all el-eiments of the set 0 < Xj - xj L Ptermuting an L-pair will produce a new sequence X1100 it associated set fx x! Ii < N I4-tx! ->x' Xl''0 x.1 X will be a seque-nc-e- of delgre e L for Conisider XI XjI f or all Po ss ibie i anid k( o). There will be a correspondence between the pa-irs of xli anid X. except that for the degree -pair X x we will consider_-~i x~ix. (i.e., x!;xj~) adsin ce x+-lIj4llJ., t will be..~ a sequence of degree L. Furthermiore,, the

1.05 0 cardina~lity of' {Xpx XI )0 will be reduced by exactly 1 since the only difference between the pairs of the two sequences lies in the degree pair. Repeat thi-s process until thie resulting sequence 8*contains no degree pairs. Since the cardinality o f is reduced each time, this ccan be done in a finite number of' steps. The sequeS.nce 8* will be of degree 01, for suppose that there e!.,xists an i and k such that o < xi - x 1-+k= LU() and let k be the sma-llest such. k, ~ 1 scethere are ~io degre,..e pairs. i'1ow consider xi 4/-k-l" Cas e i. 6uppo se xij-~k-. x i k+2~ where0 If L = 0., then xixi k-I satisfies (1) which contradicts the assumption on the rainiwm-~-lity of k. if > 0, then 0 xi k-l- xi4~k S_ L. Righthand inequality is true since the sequen ce i s of d e g r e:e Li or less. Case II, Now suppose xik*2 8ince 0 -" xi xi+ k we have 0 < Xi-,(xi, k-1i ) x. x. k- But since the seque-1n~ce is of' degree L., xi-x~kl~,i.e., 0 4&xi - ik L, and again the=re is a contradiction on the minimcality of k., KE. D t

106. Theorem; If xl,...,x is a sequence of integers of the form (i+k(m-1)), i.e., numbers congruent to 1 mod(m-l), k 0O, which k k satisfies. xji ^ mJ k l..,i and j=1 j — if a q such that Xq.,...xN is a seiuence of degree (m-l), then k k L \ xJ z' k 1,.., N where the x! are j-=i j=l J the terms of ixj.\ with xq,.., xN arranged in monotonic non-decreasing order. Proof: xq,..., xN, can be monotonized through permutation of degree pairs by the preceding lemma. Such permutation of degree pairs will not destroy the partial sum property as can be shown inductively. The lemma can be used to define an ordered set of sequenices, the i'th derived from the (i-) st by the permutation of a degree pair. Suppose that the sum condition holds for the first h of thlese- and fails at the (h-1) st. These differ by the permutation of a degree pair, say, xixi, i qc Clearly, the sum condition holds for k - loo(i-l), (i+l), oo* N. The value at k = i (after permutation) must be considered.

107. In the h'th sequence (since the sun condition holds) either (A) xj >mj-l or (B)xj ix mji if (A) holds, then, since (as is shown below) the right-hand sequence must be greater by a multiple of (m-1i) permutation of the degree pair will not destroy the sum property - at worst equality will result. Consider the terms of Ymj-l. mi - 1l (mi-l) 1+ (mi-I + mi-2... +l) (m-l) and thus is of the form l+ k(m-l), k? 0. The sum of i such terms is of the form i+k(m-l). Both sides of (A) are of this form and so differ by a multiple of (m-l). If (B) holds, then since in the h'th sequence the sum property holds xi +1 > mi but i i - i Xi > i > xi +1 - mX i mj-l xj xi i-i i-1 j (since 'X j 21 mj-l 0) showing that (B) j —l j l cannot hold. E oD. B: Other Steps in the Proof. Some other preliminary steps which seem to indicate the feasibility of the plan of proof outlined above have been taken. However, because of their rough unchecked form, they are of little use and so are not included here.

Biblio graphy 1.Kdnig, De~nes, Theorie der JEndlichen und Linendlichen Gra hen Chelsea Pulishing Co., 1950. 2. Lefschetz, S,, introduction to Toogz Princeton University Press, 1949 3. Veblen, 0.. als~ils Situs, Vol. V, Part 1I, (Second Ed.), Colloquium Publicationi Ame-:rican-L Mathematical Society, 1931. 4. S-Elifert., H., and W. TheflLehrbtich der Topologite3,. Chelsea Publishing Co.,. 1947. 5. Shannon, C. i., "~The Synthesis of Two-Terminal Switching Circui ts," Bel.~em Technical Journali, Vol. 28, 1No. 1, ipp. 59-98, Janua,-ry, 1949. 6. Burks., A. W.,, Carl H. Pollma-r, D. W1. Warren, and J. B. Wright, Lang~uage Conversion for Digital Computers: Vol. I, "tThe Logical Realization of Transliterative Functions," Project MV812-8 (Burroughs Research Center, Paoli., Pennisylvania), Ann Arbor., 1 J-une 1952; Vol. HIl "Minimal Switch Theory and The Folded Tree,." Project!A82-8 (Burroughs Research Center, Paoli, Pennsylvania), Ann Arbor, 1 Ma,,1rch 1953. 7. Gilbert, E. N., "INVterminal Switching Circuits.," Bell atemn Technical Journal., Vol. 30, Pp. 668 -688, July19'51, 8. -Shannon., C, E., "A Synthetic Analysis of Reluay and Switching Circuits, Trans. Al Vol. 57, pp. 713 -7f23, 19380

UNIVER15 03 5 ICHIGAN 3 9 36 i9 36