ENGINEERING RESEARCH INSTITUTE UNIVERSITY OF MICHIGAN ANN ARBOR 1828-8-P Informal Memorandum 5 GENERALIZED NET 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. Project 1828 BURROUGHS CORPORATION RESEARCH CENTER PAOLI, PENNSYLVANIA October 15, 1954

I - ENGINEERING RESEARCH INSTITUTE ~ UNIVERSITY OF MICHIGAN TABLE OF CONTENTS Page 1. Introduction 1 2. Points, Lines, Functions 2 3. Net Behavior 4 4. Some Mathematical Concepts Applicable to the Study of Nets 5 5. Speculations 7 6. Conclusions 9 BIBLIOGRAPHY 10 L i ii

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN GENERALIZED NET THEORY 1. Introduction. The nets of the reports in the series, Language Conversion for Digital Computers li] and [2], and those in the reports, Theory of Logical Nets [13], Complete Decoding Nets: General Theory and Minimality [4], and The Folded Tree [5], are all composed of directed line segments, enclosures which represent some logical function, and points of intersection called junctions. If the functional nature of the enclosure is disregarded, the configuration may be considered a directed linear graph in the mathematical sense [6]. Furthermore, such net characteristics as the load distribution of a tree, minimality, and the property of being well-formed can be described in purely graph-theoretic terms by dividing the points of the graph into classes. Is net theory then just a branch of graph theory? What has graph theory to say about logical nets? The body of knowledge which is developed in a mathematical discipline such as graph theory depends to a great extent upon the subjects to which it is applied and for which it has been developed. In the case of graph theory this includes the study of circuits in electrical wiring diagrams, the study of double bonds in chemical compounds, the construction of all graphs having certain common properties, counting the number of such graphs, and the like. More recently, it has been applied to the study of problems in group dynamics, etc. All these applications of graph theory are significantly different from our application of it to nets and so we should not expect the results of graph theory to be immediately applicable to our problems. Graph-like diagrams called flow charts have been used in system studies, in the analysis and synthesis of business procedures, in organization charting, in manufacturing process studies, and in the solution of problems on digital and analogue computers. They have occurred in various forms, as heuristic tools in finite differences, the theory of games, information theory, and engineering. In many of these cases a function or operation may be associated with certain of the points. In a business procedures study, for example, a vertex may represent an accounting function such as preparing invoices. Here the input might consist of sales slips and the output might be the customers invoices. The output is merely the sales slip data regrouped according to customer, the slips are totaled, etc. 1

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN It is a distinct possibility that the description of such nets could be formalized and that these abstract formalized nets could be studied mathematically. They bear a close resemblance to logical nets. Some problems which might be considered are: (1) the description of the operation of a given net (to see if it does what it is supposed to do) and methods of constructing nets with specified "behavior", (2) the study of the formation of equivalent nets (equivalent from the behavioral point of view, not from a graph-theoretic or structural point of view), and (3) various "minimality" problems. In the case of a business procedure, one would want to minimize some function of time and cost. In the case of the digital computer program one would want to minimize a function of time and storage requirements. Finally, in order to insure accuracy in the use of analogue equipment, a mathematical study of different methods of computation leading to the minimization of division, for example, would be worthwhile. These problems are generalizations of the ones considered in the study of logical nets. The methods employed in logical net theory appear to me to have much wider applicability than their use there would indicate. If this is true, the theory of logical nets might be reformulated in broader terms and extended greatly. Just how far a "theory of nets" could be developed and what application for it could be found only research can show. My ideas on this subject have not as yet been worked out and I offer only a miscellaneous assortment for consideration here. 2. Points, Lines, Functions. In the theory of logical nets the enclosures have associated with them a logical function. Information on the inputs of an enclosure is transformed by this associated function into information on its outputs. This information is referred to as the "state of a wire." However, the wire and its states is only one specific case of a channel of communication and the information that it is carrying. Such information could be represented by an array of some sort which might be called an edge vector (or EV). The function associated with the vertices would then map the set of input EV's onto the set of output EV's. The function associated with a point may be a function of other variables than those on the inputs. In a complicated system different subnets often play different roles. In many cases it is desirable to study the operation of these subnets separately. For example, a relay contact net may be studied independently of the net activating the magnets. In business a department represented by a point with an associated function may have zero outputs except at certain times during the year when its output EV's will be a function of the input EV's for the preceding period (e.g., when statements are prepared). In this case the associated function is a function of time, as well as of the i 2

- ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN input EV's. In many cases, if not all, this sort of thing can be handled by adding inputs but this may not always be desirable. A cantilever bridge may be considered a net. The intersecting points transfer forces on the "input" into forces on the "outputs". In this case no electrical "state" is involved. In business flow diagrams, there are no physical wires, the directed line segments representing the flow of information, which may, for example, be in the shape of forms distributed by messengers, telephone conversations, written communications, etc. In a manufacturing process the lines would represent the route along which supplies and products move. Clearly the lines represent paths along which "data" are transferred. By "data" are meant information, forces, physical material, electrical states, or the like. Under these restrictions the operation of the net must be such that proper domain elements are produced for each function at all times. The flow diagram for a digital computer seems to be somewhat different, for there the directed line segments denote temporal sequence. If we consider the underlying net (i.e., the conjunction circuit), the flow diagram is a description of a certain behavior or set of behaviors. Is it a net in the sense used here? If it is each vertex must have inputs and outputs which do not explicitly appear. The edges or lines actually appearing in the net can be considered as carrying the control signal. In logical net theory it was assumed for the sake of simplicity that the transfer of data along the wires was instantaneous. Time was introduced through special vertices called unit delays. A more realistic reflection of time considerations may be achieved through the association of functions of time with each directed line segment. Functions of other parameters may also be useful. In logical nets the data was discrete. This restriction does not appear necessary. The possibility of introducing continuous data should be studied. Points, like lines, are abstract elements and may represent, for example, a circuit of tubes and resisters, a lathe and its operation, an accounting section in a business firm, a series of calculations in a digital computer, or an analogue computer such as a wind tunnel where the function is not explicitly 3

- ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN known in mathematical terms).* The associated functions are even more varied. Many are identical or similar to familiar mathematical functions. However, because of the nature of nets and their application, many unusual and unfamiliar functions should be expected. For example, the memory function realized by a cycle which contains a delay is, from the point of view of conventional mathematics, a very peculiar "function". Its construction in terms of a delay illustrates the common mathematical device of defining new or more complicated functions in terms of known ones. In certain cases it is more natural to associate such a memory function with a point rather than forming it by means of a small net with a delay. 3. Net Behavior. In the theory of logical nets the behavior of a net is described by an infinite set of matrices, one matrix corresponding to each sequence of net input states. In the switches of the Language Conversion series the behavior was described by a function which mapped the elements of the domain 1-1 onto the elements of the range. These two approaches can be brought together through the idea of a basis. Let a column vector be constructed as follows: number the edges (or junctions in the formulation of [3]) of the given net from 1 to M, let this mth edge correspond to the mth row of the column vector, and let the mth coefficient of the vector denote the state of edge m. Then, if two column vectors are identical, if and only if the coefficients of the corresponding input edges are identical, then it is possible to construct any of the matrices describing the net's behavior by juxtaposing vectors. Furthermore any matrix so constructed is one of the set. The set of vectors having this property may be called a behavioral basis. It is conjectured that the concept of a behavioral basis can be Extended to all deterministic nets by using matrices instead of vectors and by a process * In mathematics there should be perfect freedom to define and use functions in their most advantageous form and I do not see why this implies that the function be defined numerically (although this may be useful from a theoretical point of view). This, I believe, holds especially when one is dealing with systems of functions, such as might arise in certain nets. The sort of thing I have in mind is already occurring in mathematics, for example, in the theory of linear transformations. As another aspect of this same idea, I would not be surprised to see systems of functions represented by some sort of analogue system which would be studied, for example, by means of digital computers. That is, we would study and work practically with systems of functions which we could not define in conventional arithmetical terms. This, of course, does not mean that numbers may not be associated with the system of functions and with their "behavior". They are, for example, the monthly totals in a business. 1

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN of "shingling", i.e., of matching the k right-hand column of the behavioral matrix to the k left-hand columns of the basis element to be added. If they agree, this basis matrix may be adjoined by identifying the corresponding right and left columns. The number of columns of the behavioral matrix is increased by one, i.e., by the rightmost column of the basis matrix. For example, if A is the behavioral matrix, B is a basis matrix, and k = 2, then A and B can be combined to form C. /1100.110\ 101\ 10.10101 01.1 AV lllllO B k 1111100 / 000 o0lo.l.l 1.10 A 10101011 ' 11i111000 \O101.lO / B This method can probably be generalized to apply to some of the wider classes of nets suggested above. One of the questions that might be explored is the determination of necessary and sufficient conditions for a net behavior to have a basis. One of the important advantages of having a basis is that it reduces the study of behavior from a consideration of an infinite number of matrices to a finite number. The flow diagram for a digital computation is another way of describing the behavior of the computer net. It is, however, very abstract and reveals none of the details of behavior. The last method to be mentioned here is one which I would expect to be of importance. It is derived by the application to a net of the familiar variable concept and illustrated in the case of logical nets by the syntactic approach [2]. 4. Some Mathematical Concepts Applicable to the Study of Nets. The way a problem is analyzed is important to its solution. Each area in mathematics has its own methods, but there are some techniques which appear in different guises in several areas of mathematics. We briefly consider some of them here. One of the most interesting techniques for studying functions is by means of related functions, for example, the study of a function by means of its derivatives. A wide variety of related nets are available for nets. The linear graph defining the underlying structure of this net is called the graph of the net and may usefully be considered a net. Related nets may be formed 5

- ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN - by replacing a subgraph of the net by a "black box" (i.e., a point) with appropriate inputs and outputs and; associating the appropriate function with the new point. This was done in the study of multiplicative switch nets where each multiplicative switch of the net is represented by a box. Another related net was obtained by replacing sets of inputs and outputs by single inputs and outputs. This was done to produce the multiplicative switch net diagram. Related nets may also be obtained by the inverse process, that is, by replacing a point by a net whose associated functions are more "primitive." There are, of course, other related nets derived by other means, for example, by abstraction. Such nets would include those used to describe a net's behavior (e.g., a flow diagram for a problem to be solved on a digital computer). Nets may also be studied by means of subnets. The analogue of this is, of course, a common practice in geometry and topology. Subnets may be of at least two types. If A is a net and B is a subnet of A such that the graph of B is a subgraph of the graph of A, then let us say that the subnet is of Type I- Otherwise, it will be of Type II. The subnets of the Theory of Logical Nets may be of Type II, because the separating of wires from junctions may add additional points to the graph of the net. For example, if (A) is the given net, then (B) is a Type II subnet of (A). (A) (B) 4> 1 Numbers may be associated with a net in many ways. Among such numbers are structural indices. Many of them are described in terms of element counts of various kinds. The element input count and the serial and parallel loading coefficients are examples. In these cases the indices can be defined through the use of subnets. In a tree, the enclosures labeled Pi constitute a subnet. The number of elements in this subnet is the parallel loading coefficient of Pi. It is a structural index. Interchange is a process for altering this index. An enclosure, together with its outputs, is a subnet. The number of outputs is its output order, another index. The dimension of a space, the rank of a matrix, the order of a polynomial are examples of indices which are common, significant devices in mathematics. "Indices" are common elsewhere also. The purpose of many games (e.g., baseball) is defined in terms of indices and the effectiveness of players expressed in terms of other indices. The indices of effectiveness are usually not closely related to the indices in terms of which victory is defined and the result is anomalous. Players can improve their individual effectiveness indices and as a result become poorer players. This illustrates the need for a proper understanding and use of indices. 6

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN One of the most important ideas in mathematics is that of equivalence. Graph theory gives a structural equivalence which in general is ill-suited to the requirements of net theory. In net theory one of the most important types of equivalence is equivalence of behavior. For example, a tree and a balanced multiplicative switch net are equivalent from a behavioral point of view (if only net inputs and outputs are considered), but not otherwise. They are in general quite different from a structural point of view. One of the behavioral complications in the concept of equivalence can be illustrated by two general purpose digital computers. Let one be a single address machine and the other a three address machine. In actual operation those two machines would be quite different and yet they are in a sense equivalent from a behavioral point of view, for any problem which can be solved on one can be solved on the other. 5. Speculations. I have come to think of net theory as a conceptual tool of potentially great power and wide applicability which can be developed into a relatively self-contained body of principles, such as algebra or function theory. If we assume that a business may be represented by a net, then to describe its behavior we must in some sense define the external activities to which the business is sensitive. This additional problem I assume to be part of net theory. It may be done, for example, by considering the business net as a subnet of a larger one. The problem would be to study the action of the subnet relative to the larger net in which it is imbedded. In ordinary systems and production analysis, it is essentially the minute by minute behavior of the net which is considered. However, from the point of view of management, it is the cumulative results of the business behavior which matters. To measure this, accounting records have been devised. From these records, numbers (i.e., the various totals, ratios, etc., employed) are calculated. These numbers are essentially behavioral indices. In some such way as this it may be possible to embody accounting into mathematics and to investigate it rigorously. Net-like configurations exist or can be used in the study of many subjects in which the normal state is one of change (of the net) or growth. Examples could be taken from biology. Business also is subject to constant change, and in a sense so are computers since they are being constantly modified. The nets which we have been considering here take no account of change. They may be called static nets. Nets in which change is considered may be called dynamic nets. The representation of a net by a function N(t) (or set of functions) may be more apt for dynamic nets. ~N can be defined more precisely by con sidering a function FN whose domain in addition to time is a set of points, 7

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN for example, a finite set of points or the points of a plane. FN might be defined as follows: FN(ta,b) = ' if a and b are not connected by a line of the graph of the net at time t; FN(t,ab) (ab) i= (ab) is a line of the graph at time t; FN(tab) = i if a b is a line of the graph at time t; FN(ta,a) = 1 if a is a point of the graph at time t and O if it is not. Or it could be represented numerically by having FN(t,ab) = N if a_ b is a line of the graph occurring N times at time t, 1 if it is a point of the graph, and otherwise 0. Both a and b range over all possible points of the graph. Now we may define f N(t) = {FN(tab) | ab are elements of the given point se. At any moment t the graph can be represented by a matrix. The function t can then be thought of as a sequence of matrices, one for each value of t. Representation of a graph by a matrix may be done in different ways depending upon the nature of the graph and the conventions employed. A matrix representation of *N(t) at time to for the graph shown below would have the following form if both rows and columns represented points, and if a4 was not to be considered a point of the graph at to. al a2 a3 a, al/ 1 2 0 0 al a2 a2 1 1 0 0 a 3 a 1 0 1 0 a4 0 0 0 0 a3 a4 A second function PA could be used to specify the functions associated with the net and determining its behavior. Net-like configurations may be used as approximations to some actual situation. Such approximations may be improved by increasing the number of -! - 8

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN points, the number of inputs and outputs to each point, and the like. This could lead to an infinite sequence of nets and is the limit under proper conditions to an "oo net." This is an analogue of the process of derivation in topology [7]. It would be of considerable interest to see how this extension to net theory could be made and to discuss its consequences. I would be especially interested in the relationship of net theory so extended to the present body of mathematics. 6. Conclusions. In the course of my development of tree theory [8], the ideas briefly discussed above occurred to me. I was interested in them not only for themselves but also because I felt that the framing of my theory should be done with as broad a context in mind as possible. I have not had time to study and discard or in the event of usefulness to reformulate and bring to maturity the ideas discussed in these pages. There may be then much that is poor and naive. I hope there are also some concepts that are of value. 9

ENGINEERING RESEARCH INSTITUTE * UNIVERSITY OF MICHIGAN BIBLIOGRAPHY 1. Burks, Arthur W., Carl H. Pollmar, Don W. Warren, and Jesse B. Wright, "The Logical Realization of Transliterative Functions," Language Conversion for Digital Computers, General Introduction and Vol. I, ERI 1828, Ann Arbor, 1 June 1952 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). 2. Burks, Arthur W., Carl H. Pollmar, Don W. Warren, and Jesse B. Wright, "Minimal Switch Theory and the Folded Tree," Language Conversion for Digital Computers, Vol. III, ERI 1828, Ann Arbor, 1 March 1953 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). 5. Burks, Arthur W., and Jesse B. Wright, Theory of Logical Nets, ERI 1828, Ann Arbor, December, 1952 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). Also published in the Proceedings of the I.R.E., Vol. 41, No. 10, October, 1953, PP. 1357-1365. 4. Burks, Arthur W., Robert McNaughton, Carl H. Pollmar, Don W. Warren,, and Jesse B. Wright, Complete Decoding Nets: General Theory and Minimality, ERI 1828, Ann Arbor,.15 July.1954 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). To be published. 5. Burks, Arthur W.,. Robert McNaughton, Carl H. Pollmar, Don W. Warren, and Jesse B. Wright, The Folded Tree, ERI 1828, Ann Arbor, 30 September 1954 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). To be published. 6. Konig, Denes, Theorie der Endlichen und Unendlichen Graphen, Chelsea Publishing Company, New York, 1950. 7. Lefschetz, Solomon, Introduction to Topology, Princeton University Press, 1949. 8. Pollmar, Carl H., A Generalization of Folded Tree Theory, Informal Memorandum No. 2, ERI 1828, Ann Arbor, 30 August 1954 (Burroughs Corporation, Research Center, Paoli, Pennsylvania). j L - 10

UNIVERSITY OF MICHIGAN 3 9015 03022 7451