THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report ON THE FEEDBACK COMPLEXITY OF AUTOMATA Bernard Phillip Zeigler ORA Projects 01252, 01487 and 08226 supported by: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-12236-03 Bethesda, Maryland and Office of Naval Research Contract No. N00014-67-A-0181-0011 Washington, D. C. and U. S. Army Research Office (Durham) Grant No. DA-31-124-ARO-D-483 Durham, North Carolina administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR January 1969 Distribution of this document is unlimited.

ACKNOWLEDGEMENTS I wish to thank the members of my doctoral committee for their service on it. I am especially indebted to my Chairman, John Holland and his doctoral committee chairman, Arthur Burks (who is also on my committee) whose conjectures I have seized and pushed to their limits. Special commendation goes to John Meyer, who in our working sessions took nothing for granted and was therefore the source of much clarification which otherwise would not have come into being. Any remaining confusions are of course mine and not ascribable to him. So much for the academic credits. Equally, if not more important is the spiritual sustenance I absorbed through my association with the people of the Logic of Computers Group and Computer and Communication Sciences Department. Not to mention my wife Rebecca and daughter Bianca without whose support and understanding I might have long ago given up this task for easier though less rewarding ventures. My sincere thanks also to colleague Stewart Bainbridge who was always available for consultation when the going got rough. Also my appreciation is extended to Roger Weinberg for his helpful biological comments and most of all for being himself. A special Thank You goes to Miss Linda Beattie for a superb typing and drawing job.

TABLE OF CONTENTS ACKNOWLEDGEMENTS 11 INDEX OF SYMBOLS v INDEX OF TERMS vii INTRODUCTION ix I FOUNDATIONS 1 1.1 Transition Functions and Semigroup Actions 3 1.2 State Behavior Realizations 11 1.3 Homomorphic Realizations 17 1.4 Simulation 21 1.5 Implementation of Input Encoding 23 1.6 Simulation and Semigroup Actions 25 1.7 Cycle Correspondence in the Division Relation 31 1.8 Co-ordinatization and Prediction 39 1.9 A Short Look Ahead 49 1.10 Review of Graph Theory 51 1.11 Feedback Indegree 53 1.12 A Packing Density Problem 61 1.13 Hereditary Properties 67 II REPRESENTING DIGRAPHS FOR LOGICAL NETS 69 III BURKS-WANG CONJECTURE ON STRONG COMPONENT SIZE 81 IV HOLLAND'S CONJECTURE ON FEEDBACK INDEGREE 90 4.1 Proof of Conjecture on Feedback Indegree 90 4.2 Primitivity and Maximum Dependence 94 V FEEDBACK COMPLEXITY FOR HOMOMORPHIC REALIZATIONS 100 5.1 Proof that minmax FI( hom M ) 2 101 5.2 Expansion Limited Realizations 103 5.3 Characterization of Arbitrary Homomorphic Realizations 108 VI INFORMATION PATHS IN LOGICAL NETS 111 6.1 Partition Pairs for the Iterated Transition Function 111 6.2 Characterization of Physical Information Paths 119 111

TABLE OF CONTENTS (Cont.) VII FEEDBACK COMPLEXITY FOR A CLASS OF SIMULATIONS 127 7.1 Feedback Indegree Dependence on Semigroup Structure 130 7.2 Computational Slow-up and Feedback Complexity 135 7.3 Cellular Space Realizations 136 CONCLUSIONS AND OPEN PROBLEMS 138 EPILOGUE 142 REFERENCES 144 Figure 2.1 77 iv

INDEX OF SYMBOLS [In Order of Their First Appearance] R (semigroup), 3 MfAf, 23 S (generator set), 3 1(M), 27 S* (free semigroup), 3 4', 29 (isomorphism), 3 T (x-period), 32 x (equivalence), 4 {Qja C D}, 39 [x], B(x) (classes), 4 D'11D DI9 a, 39 l,p (partitions), 4 PQ, q, U. 40 Th' h (kernel), 4 0 I, PD 41 M: Q x S -+ Q (transition function), 5 M(p) (kernel), 48 <S,Q,O,M,N> (machine), 5 M, 48 0M (semigroup of M), 5 IS, 08, 51 (x) (length), 6 d(a, D') (distance), 52 x (representative), 6 S(a) (strong component), 53 R~ (representative semigroup), 6 D* (condensation), 53 <R,S,Q> (right action), 8 size (D), 53 <RS> (x in terms of S), 8 min I(D), 54 kc p 8 max FI(D), 54 <RS>' gen <R,S>, 9 D(n,m) Fnm)56 maxgen <R>, 10 V (r), 61 A (machine), 11 A(f,r,n), 63 A' (composed machine), 11 D' cell space' 63 Z (connection map), 11!, min 2, 68 n. A. (product), 12 D(A), 70 1 1 MD (delay), 14 detQ, (D2), 70 M' (subtransition function), 18 Q., 71

INDEX OF SYMBOLS (Cont.) D(AIQ'), 71 M (p) (k-prediction kernel), 112 AQ,, 72 1f, 112 ~M' 74 1 2' 112 iso k, 76. + 1 min A(D'), 83 M (D'), Mw(D'), 119 size (A), 86 k k D -D D D -2 D 119 1 D2 D1 w 2' minmax FI ( isO), 90 k F(M c -+ 6, 125 hom P Whom 4 100 ~iso,C.S. 130 <R,S,Q> 130 minmax FI( hom 100 R1 (n',m)" 108 9<R,S,Q>, 5 ' C.S. 131 Mk: Q ~ 5k ~ ~ size <R>, 134 Mkf Q x Sk + Q, 111 vi

INDEX OF TERMS [Including the Page of Their First Appearance] automaton, 4 generator, 3 index, 10 b-slow computation, 24 group, 3 composition, 13 hereditary, 67 product, 12 homomorphism series parallel, 15 semigroup, 3 sub-composition, 83 transition function, 17 unrestrained, 12 computation, 24 identity, 3 b-slow, 24 initial state, 27 slow-up, 135 input selection, 71 congruence, 4 input code, 21 connection map, 11 irreducible, 30 co-ordinatization, 39 isomorphism binary, 39 semigroup, 3 Cartesian, 43 transition function, 19 dependent, 44 determined, 44 length, 6 independent, 44 minimum representative, 6 irredundant, 42 location, 42 projections, 39 logical net, 15 cover, 104 cycle, 32 machine, 4 string cycle 32 composed, 11 string period, 32 feedback, 11 Moore, 11 degree of net, 89 maximum dependence, 91 delay, 14 memory capacity, 19 determining set, 48 monoid, 3 k-, 119 weak k-, 119 orbit, 17 D1 weakly k-determines D2, 119 operative, 74 digraph, 51 output behavior, 18 concepts, 51-61 extended, 22 cellular space, 61 of kind (n,m), 55 partition, 4 minimal, 68 index, 47 reduced, 71 kernel, 4 representing, 69 labelled, 106 division distinguished, 108 minimal, 74 saturated, 108 semigroup, 26 prediction, 47 transition function, 21 kernel, 48 pair, 47 equivalence relation, 4 D1 predicts D2, 48 k-prediction, 111 feedback indegree, 54 k-prediction kernel, 112 maximum, 54 prime cyclic group, 96 primitive, 96 vii

INDEX OF TERMS (Cont.) realization, 17 simulation, 22 expansion limited, 106 simulation*, 25 homomorphic, 17 minimal, 74 isomorphic, 19 mutual I, 27 of kind (n,mm), 108 series parallel, 31 refines, 40 size gkb, tub, 40 digraph, 53 reduced net, 72 A, 88 representing digraph, 69 reduced, 71 <R,S,Q>, 131 right action, 8 R, 134 faithful, 8 substitution property, 18 non-trivial, 39 semigroup, 3 free, 3 transition function, 3 of M, 5 iterated, 109 sub, 1 sub, 16 transitive, 28 k-ply, 89 viii

INTRODUCTION X ow complex does the structure of a system have to be in order that it can display any possible behavior? The question is unanswerable in this form,and we are forced along the following path: First the notion of system has to be explicated and for this purpose we turn to logical nets as appropriate mathematical models of real world systems. Second a means of representing the structure of logical nets is formulated. For this the theory of digraphs is pressed into service. Third we select two measures of interaction —strong component size and feedback indegree —to explicate the notion of complexity, Roughly, the feedback indegree of a delay is the number of delays(in its strong component) from which it receives a direct output. The strong component of a delay is the set of all delays with which it communicates whether directly or through other delays. Finally, we define what "displaying a behavior" means; namely, we consider the general concept of simulation and the more restricted, though broad, classes of homomorphic and isomomorphic realization. Roughly, homomorphic realization allows memory expansion (state splitting) which isomorphic realization does not; and simulation allows computational slow-up and delay which homomorphic realization does not. With these concepts we shall find that our original question can be answered in certain cases and not in others depending on the kind of simulation allowed and the measure of complexity adopted. In the case of strong component size, we shall show as conjectured by Burks and Wang (1957) that for every integer s, there is a finite transition function which cannot be simulated by a logical net with maximum strong component size less than s. Thus according to this measure no set of systems ix

of bounded complexity can simulate every behavior. We shall only be able to establish a like statement in the case of feedback indegree in certain special but important cases —those of isomomorphic realization (as conjectured by Holland (1956)) and expansion limited homomorphic realization. We shall manage however to show, in the case of (arbitrary) homomorphic realization, that logical nets of complexity 1 (so called simple nets) are not powerful enough to realize all possible behaviors. The question then, remains unsolved in the general case of simulation and even in the restricted case of homomorphic realization. It may indeed be the case that by allowing arbitrary (but finite) memory expansion and slow-up every behavior can be realized by simple logical nets! In one sense this is surprising yet in another sense it is not. For it is known that any behavior can be realized by logical nets of maximum feedback indegree O (so called combinatorial machines) over any finite time span. The memory capacity required of such nets however increases linearly with the period of valid realization and thus an infinite number of states is required to realize even some of the most elementary finite state behaviors over an arbitrary time span. Thus it is only when finiteness is introduced that feedback becomes necessary. Is more than feedback complexity 1 required in general? Nobody knows. A step in the right direction, I feel is taken in the second half of this presentation. Here we undertake to compute the feedback indgree required to homomorphically realize a fixed (but arbitrary) transition function. The results give a clue as to the relevant parameters but are not transparent enough to enable substantial inferences to be made. We also show how a lower bound on the maximum feedback indegree for isomorphic realizations of a transition function may be obtained from knowledge of its semigroup.

This leads naturally to consideration of a restricted class of simulations defined as "mutual H-simulations". In such simulations, both memory expansion and computational slow-up are allowed but only within the bounds imposed by preservation of the semigroup of the simuland. This latter result necessitates the development of certain novel mathematical machinery. We are led to consideration of the partition pair structure of the iterated transition function and to the characterization of the physically possible information flow paths in logical nets. We encounter the curious situation where if one restricts one's attention to closed subsets of states of a logical net it is possible that the state of a delay B k-time steps in the future may be predicted by the present state of a delay a even though there are more than k delays in the shortest path from the output of a to the input of 8! The resolution of this supernatural phenomena is, I think interesting in its own right. In our final chapter we shall make small stabs in the direction of certain other current problems in automata theory. We discuss the trade-off relation between computational slow-up and system complexity as it appears in this context. We also make plausible a conjecture concerning the limitations of cellular spaces of the von Neumann variety. This would say that there is a sequence of logical nets each of bounded feedback complexity such that for any a given (but arbitrary) dimension, at least one net in the sequence cannot be mutually H-simulated (in particular isomorphically realized) by any cellular space of that dimension. The reader interested in going directly to certain results without passing through others may find the following theorem dependency tree useful in this endeavor. xi

Major Theorems and Their Dependents 3.7 (Burks-Wang conjecture on degree) 3.6 3.5 3.4 3.3 1.9 1.11 1.10 4.1 (Holland's conjecture on feedback complexity for /J\ isomorphic realizations) 4.3 4.4 1.16 1.23 1.25 2.3 4.2 1.24 2.2 2.1 hom 5.4 (minmax FI(5Mq ) > 2) 5.3 5.2 1.11 5.1 1.10 5.5 (Expansion Limited Realizations) (as in 4.1) 5.6 xii

5.7 (Realizations of kind (n,m)) 1.19 1.23 1.25 5.6 1 1.16 1.17 1.18 7.3 (mutual H-simulations) 7.1 7.2 l.9i 6.3 6.6 1.22 1.25 2.3 6.10 6.2 1.20i 1.24 2.2 1.25 4.6 6.5 1.20 2.1 1.24 6.1 6.4 6.2...

CHAPTER I FOUNDATIONS ehis chapter presents basic concepts and results upon which the discourse of later chapters will be based. The contents are of two kinds: the review of some key ideas of contemporary automata theory, and the establishment of fundamental sub-theorems necessary for the proof of the main theorems of this work. With regard to the former, the presentation is intended not to be comprehensive but to lay a groundwork sufficient for the understanding of the ideas of interest here. The reader who wishes a more complete introduction to the topics introduced may wish to start with the books by Arbib (1968) and Hartmanis and Stearns (1966). On the other hand, the reader already acquainted with current trends in automata theory may wish to begin his reading with Chapter II. He may then return to the relevant parts of this chapter as it becomes necessary or useful to do so. It should be mentioned however that while some of the results in Chapter I are well-known, they have been formulated in novel ways in an attempt to bring out new implications. Thus a scan of Chapter I may prove interesting, even for the cognoscente. In Section 1.1 we develop the correspondence between transition functions and semi-group actions. The treatment is original (as far as I know) in emphasizing the part played by the generators of the semi-group. This role is important in relating what is essentially the time lag allowed in a computation to the feedback complexity required by a machine which will perform it. In Sections 1.2, 1.3, 1.4 some basic kinds of machine realizations are discussed and shown to be subsumed under the most general form —that

-2 -of simulation. We define a notion of composition of machines and its specialization to logical nets and series-parallel decompositions. Section 1.5 concerns the implementation of input encoding for simulations and shows how prior concepts of slow computation can be algebraically formulated in the simulation framework. Section 1.6 relates simulation and semigroup action. We show how a class of machines able to simulate each other by means of product compositions is just the class of all actions of the semi-group of any one of them. The role played by SP (substitution property) partitions is outlined in Section 1.7. We also show how the cycle structure of machines is preserved by the division relation —a result which will prove very useful later on. Section 1.8 discusses the notion of co-ordinatization and the algebra of partitions associated with it. The concepts of prediction, location and determining set will prove to be essential in characterizing graph theoretic properties of logical net realizations. In Section 1.9 we pause to place the concepts already introduced in a context appropriate to our main concerns. Sections 1.10 to 1.13 have to do with the theory of finite directed graphs —this being the medium in which the structure of logical nets are represented. This theory is reviewed in Section 1.10, while Sections 1.11 and 1.12 establish results which will be helpful in the sequel.

-3 -1.1 Transition Functions and Semigroup Actions We begin by briefly reviewing some of the basic concepts of semigroup theory. A semigroup R is a set closed under an associative binary operation (usually written a.b or just ab, for a,baR). A monoid is a semigroup having a unique identity i.e., an element 1 such that for all a L R al = la = a. A group is a monoid in which every a c R has a unique inverse a such -1 -1 that aa =a a = 1. A sub-semigroup is a subset of a semigroup R which is closed under the binary operation of R. Given any subset R' of R, the smallest subsemigroup containing R' exists and is called the sub-semigroup generated by R' and denoted by <R'>. <R'> in fact is just the set of all products x1 x2... xn of elements x.i R'. A semigroup R is generated by R' if <R'> = R. Analogous concepts hold for submonoids and subgroups. The monoid generated by a semigroup S, denoted S is defined by S1 = S if S is a monoid, S = SUlotherwise, where 1 acts as an identity. Given semigroups R1, R2, a map h: R1 + R2 is a homomorphism if h(ab) h(a)h(b) for all a, b a R1. If h is onto, R2 is said to be homomorphic to or a homomorphic image of R1. If h is one-one and onto, it is said to be an isomorphism and R2 isomorphic to R1 written R1 - R2. A semigroup R1 is free on a subset S if for any semigroup R2 any map f: S - R2 can be extended to a unique homomorphism h: R1 - R2 where h(x1 x2... n) = f(xl) f(x2)... f(xn) for every product x1 x2... xn, x. E S. The free semigroup generated by a set S denoted by S* exists and is just the set of all non-empty strings on S —i.e., all finite sequences of elements from S. S* is the free monoid generated by S with A, the empty string playing the role of identity.

-4 -An equivalence relation - on a semigroup R is said to be a congruence if for a, b, x, y s R a - b implies ax - bx and a - b implies xa - xb. is said to be a right congruence in the first case and a left congruence in the second. A function f: A - B induces the kernel equivalence, f on A defined by x - y iff f(x) = f(y) f (iff = if, and only if). For any equivalence _ on A, A/- denotes the partition induced on A by - and [x] or B(x) (possibly with subscripts associating the partition) denote the equivalence classes or blocks of A/=. We set f = A/=, thus Tf is the partition induced by the funcf tion f. A homomorphism of semigroups, h: R1 R2 induces a (two-sided) congruence on R, namely h. Conversely, if = is a congruence on R, there h exists a homomorphism h: R -* R/= given by h(x) = [x] for all x s R. That R/- forms a semigroup follows from the fact that - is a congruence. A machine (automaton, transducer) is a quintuple <S, Q, O, M, N> where S, Q, O are sets and NI: Q x S -+ Q, N: Q x S - O. S is the input alphabet, Q the set of internal states, and 0, the output alphabet. The map M is the transition function, dictating the next state of the machine as a function of its present state and the present input symbol. Transition functions represent state behavior of machines and will be at the focus of attention. Given a transition function M: Q x S - Q we can extend M to strings x E S*. We define the extended function M: Q x S* + Q by

-5 -M(q,s) = M(q,s) for q ~ Q, s s S M(q, xs) = M(M (q,x),s) for q E Q, x ~ S*. To extend M to S* we add M(q,A) = q for all q c Q. We often abbreviate M(q,x) = qx. With each x c S* we can identify the transformation ~x Q + Q defined by (q)~x = M(q,x) for all q ~ Q. The set H = {p xx c S*} forms a semigroup with =x ' py =xy for all x, y c S*. M is called the semigroup of H. (Adding A the identity transformation convertsN1 to a monoid.) If Q is finite not all transformations in ~M can be distinct, in fact |>11 < nn where n = Q, the cardinality of Q. S* can be partitioned into blocks of strings corresponding to the same transformation. Define the equivalence,' by x M Y iff 9x = ~y for all x, y E S*. is in fact a two-sided congruence so that S*/ is a semigroup with operation [x] [y] = [xy] for all x, y c S*. It is easily shown that qM is isomorphic to S*/M. (S* /M and qM U ~A are isomorphic monoids.) Note that each block [x] E S*/M corresponds to the transformation px

-6 -or by extended notation [x]. The length of a string x c S*, k(x),is number of symbols (elements from S) in it. (g(A) = 0). We choose as representative from each class [x] a string with minimum length. More precisely for x E S* we define the map x -+ where z(x) = min z(y). yE [X] We also write [x] = x. The significance of this is as follows: z(x) is the least length of string such that the transformation ~[x] can be realized by iterating the transition function M. Physically interpreted, the length of a string is the number of time steps in the duration of an input signal. Since as is usual we are assuming discrete time operation the empty string can have no physical interpretation since it does not occur during a time step (k(A) = 0). ~M may, of course, possess an identity transformation ~1' but if so z(1) > 1. If one considers the functions mapping present states to their successors t time steps in the future, Z(x) is the shortest time interval for which the transformation ~[x] can be observed. The semigroup ~ can be succinctly represented by (i.e., is isomorphic to) the set of representatives R = {xlx E S*} under the multiplication y= xy. Without loss of generality we assume that no two input symbols induce the same transformation i.e., for all sl, s2 E S [Sl] = [s2] implies sl = s2. Then [s] = s for all s ~ S and R~ is generated by S.

Conversely, suppose that we are given a semigroup R generated by a set S. The homomorphism of semigroups h: S* + R obtained by extending the identity map i: S -+ R is unique (by virtue of the freedom of S*). It is easily seen that S*/- is isomorphic to R. Let be a right congruence on R and set Q = R/. Define the tranR R sition function M: Q x S - Q by Ml([x]R, s) = [xs]R for all [x] ~ Q. The extended transition function M: Q x S* - Q can be verified to be M([x]R,y) = [xh(Y)]R for all y ~ S*. The congruence - can then be seen to be given by M x y iff [zh(x)]R = [zh(x)]R for all x,y,z c S*. Now, x j y implies h(x) = h(y) implies [zh(x)]R = [zh(x)]R implies x M y. Thus there is a homomorphism h' from S*/- to S*/= (given by h'([x]) M h [X]M); hence also homomorphisms from R to DM and from R to R4. It is in fact always possible to find a transition function such that the homomorphism is an isomorphism. One way, but not the only way to do this, is to take Q =R1 Then M: R x S R is given by M(x,y) xh(y). It follows that for all x, y a S* x Y implies zh(x) = zh(Y) for all z R1 implies h(x) = h(y) (using z = 1) implies x h y. It follows that and are identical and R,M, R are all isomorphic. M h are identical an ~M'

-8 -Classically when the generating set S is R itself and when PM is a homomorphic image of R, M: Q x R + Q is said to be a (right) action of R (on Q). Correspondingly, we say that M: Q x S -+ Q is an <R,S,Q> (or just <R,S>) action if 4M is a homomorphic image of R. This action is said to be faithful when (D N1 R. In the semigroup R generated by S C R, each x ~ R has a shortest expression as a product of elements of S and we define Z<R S> (x) to be the number of symbols in this expression. In fact, <RS> (x) min (y) yc[x]h By convention let each x a R always be represented by a shortest expression in terms of S. IWhen the <R,S,Q> action M, is faithful [x]h [X]M for x ~ S*. It follows that for x E R, %<RS> (x) = min (y) yc[x]h = min ~(y) Y6[x]M (x). Equivalently, there are choices of minimum length representatives such that R, = R. To sum up, we have the classical representation theorem with however an emphasis placed on the role of the generators: 1.1 Theorem Given a machine M: Q x S - Q we can represent the semigroup of M as R, the semigroup of shortest length representatives from S*/R.

-9 -Conversely, given a semigroup R generated by a set S C R, we can find a faithful <R,S,Q> action i.e., a machine M: Q x S + Q whose semigroup, ~M is isomorphic to R and in fact RM = R. We define 9 RS>= {x RIZ<R S>(X) I 1 where <R,S>(x) is the shortest length of x in terms of S. We have that RS (x) is the least k such that x Ec tRS> We define the generator index, gen <R,S> = max <R s>(X) x@R k Thus, if gen <R,S> = k, S> = R and k is the least integer for which this is true. Correspondingly, for any faithful <R,S> action, we define <RS> ix ~ S] <R S>(X) < PI where &R S>(X) is the length of the shortest string in [x]. Since x E R <R, we have U [XI <R,S> U [x] XE <RS> and if gen <R,S> = k then ~<R,S>

-10 -Given any <R,S> action M: Q x S + Q and any subset R' C R, we obtain an induced action <<R'>, R'> on Q as follows: Let M be the extension of M to S*, then the induced action MR, is given by MR, (q,x) = M(q,x) for all q E Q, x e R'. We define max gen <R> = max gen <R,S>, where the maximization is taken over all generating sets S C R. If max gen <R> = k then for all generating sets, S <R,S> and this is least integer for which this is true. The index, min gen <R> = min gen <R,S> over all generating sets S C R is a trivial parameter since gen <R,R> = 1. 1.2 Proposition Si gen <R,S> -1 gen <R,S> < R < gen <R, > -.S Isl- 1 or equivalently loglSIIR|' < gen <R,S> < IR| where |R| RI..S -' + 1 IRI + 1 for large IsI ISI Proof: Let k = gen <R,S>, and x*be the longest element in R in terms of S. Then letting x* = s1 s2... sk we have that each of the heads xi = s1 s2... si

-11 -i = 0, 1,..., k are distinct. Suppose to the contrary xi = x ji < j. Adding si+l ''... Sk to the right we have xi sj+l... sk = xj sj+... sk = x*. But then Z(x*) = Z(xi sj+l... Sk) < k, a contradiction. Thus [R[ > k as stated. The upper bound on IRI is obtained by assuming that all words of length less than or equal to k are distinct in R. 1.2 State Behavior Realizations We begin by considering what it means to compose or connect machines together. To do this first consider the result of placing feedback around a machine —i.e., making its input depend on its output. Let A = <S,Q,O,M,N> be a Moore machine i.e., a machine for which the output depends only on the internal state —N: Q - O. A feedback machine or composed machine, A' associated with A is any machine of the form: A' = <S',Q, *,M', *> where S' is an arbitrary set, M': Q x S' + S' is given by M'(q,s') = M(,Z(N(q),s)) for all q, ~ Q, s' ~ S, where Z: 0 x S' -* S is called a connection map and dictates how the new input alphabet, S' is to be coded into the old alphabet S, as a function of the output 0.

-12 -Graphically, going from A to A' may be represented by S 0 S' 0 A' Note that since the output depends only on the state we can consider connection maps to be of the form Z': Q x S' - S where in terms of the original map Z: 0 x S' -+ S Z'(q,s') = Z(N(q),s') for all q C Q, s' c S'. We have considered only Mooremachines, but this is as general as we need be. In fact as the reader may verify, well-formed compositions (Burks, 1953) may always be considered to be composed Moore machines. Now consider any countable set of machines {A.ilA = <Si, Qi 0i' Mi' Ni>}. The product or unrestrained composition over {Ai} is the machine 1i A = < 11 iQi, i0 1iMi'.iNi > 1i i i' i <i ' ' 1

-13 -H. M.: H. Q. x H. S. +. Q. 1 1 1 1 1 1 1 1 is given by niMi(ql' q2' q3. 5, s, s.... = (M1(ql,sl), M2(q2,S2), M3(q3,s3),...) for all (ql, q2, q3'...) E H iQi and ( S2' ) iSi and.iNi is analogously defined. A composition over {A.} is any composed machine, (riAi)' associated with the product over {Ai}. In a composition ( ) = <S Q M'-> the connection map Z: iQi x S' + iSi can be factored into component maps Z..Q. x S' - S. where Z(ql' q2'.'' s) = (Z1(ql' q2' q3'... s'), Z2(ql, q2' q3'... s'),...) for all (ql' q2' ') c HiQi, s' S'. The component map Zi, dictates how the component machine 4i is to be connected to all the components Ai E (Ai). We allow the possibility that Zi does not functionally depend on all Qi i.e., Zi.: Qj x x.x Q x s' + s. where Q. ~ ji E iQi

-14 -Graphically, we can represent this as follows: I iQi J iQi M"': iQi x S' + niQi can then also be factored into components li!: HQi x S' - Qi which can be evaluated as M!( ' qi., S) =Mi(qi Zi (' '' qi' '' S)) for all qi ' '') 5iQi, s' E S'. A delay element is a two state Moore machine <2, 2, 2, M, i> where 2 = {O, 1}, i: 2 + 2 is the identity and MD: 2 x 2 +- 2

-15 -is given by MD(ql q2) = q2 for all ql' q2 c 2. Note that the next state of a delay does not depend on its present state but only on the input symbol. A logical net (Burks, 1957) (also called on abstract network, by HIartmanis and Stearns (1966)) is a composition over a finite set of delay elements. We say that a composition over A1, A2, A3,..., is a series composition if the connection map Z is of the form: Z: S' -+ S Z2 Q1 X S' S2 Z3: Q1 x Q2 x S' S3 etc. A composition over {Ai. is a parallel composition if the connection map Z is of the form Z.: S' -+ S. 1 1 for all i. Note that the product H.iAi is a parallel composition. A composition over {A.} is a series-parallel composition if {Ai}is partitioned into sets al, a2, a3,... such that each (II. Ai)' is a 21

-16 -parallel composition over aj and (HAi)' is a series composition over the parallel compositions (i. Ai)' J A series parallel composition, then consists of blocks of components internally connected in parallel and interconnected, in series. Graphically this is represented by 1a 1 2

-17 -1.3 Homomorphic Realizations Given an abstract transition function M: Q x S -+ Q we want to be able to discuss the properties of machines capable of exhibiting the state behavior associated with M. Such machines are said to realize (or be realizations of) the transition function M. We mention that a machine realizing M and having a suitable output map can also imitate the input-output behavior any machine whose transition function is M. Given transition functions Mi: Qi x S + Qi i = 1, 2, a map h is said to be a homomorphism of M1 to M2 if h: Q1 Q2 (onto) and for all q ~ Q1' s E S h(M (q,s)) = M2(h(q),s). Thus the following square commutes: qlh h q2 w q2s If there is a homomorphism from M1 to M2, M2 is said to be a homomorphic image of M1. Given a transition function M: Q x S -- Q, a non-empty set Q' C Q is said to be an orbit if it is closed under the action of M, i.e., for all s ~ S, q ~ Q', M(q,s) ~ Q'. For any orbit Q', the function M restricted

-18 -to Q' is said to be a subtransition function of M. We write M' C M to denote that M' is a subtransition function of M. A homomorphic realization of M2: Q2 x S - Q2 is a machine A1= <S, Q1' Q2' M1'h> where h (restricted to a suitable orbit) is a homomorphism from a subtransition function M C M1 to M We shall show that the output behavior (to be defined in a moment) of A1 when operating in the orbit corresponding to M' is identical to M A partition H on the state set Q of a transition function M: Q x S - Q is said to have the substitution property (SP) if for all ql, q2 ~ Q, s ~ S q! q2 >M(ql's) M(q2's)' (Here ~ is the equivalence associated with H i.e., Q- = H.) If H has SP on Q, there is a homomorphism h from M to a transition function M[H where MnH:H x S -+ and is given by MlH([q],s) = [M(q,s)]H for all q ~ Q, s ~ Q. That M H is well defined follows from the fact that H has SP. Conversely, if h is a homomorphism from bI1 to M2, Hh = QHh has SP and Ml1 Hh is isomorphic to M2. The output behavior of a machine <S, Q, O, M, N> where N: Q -+ 0 (i.e., a Moore machine) is represented by the map MN: 0 x S + 20 given by for all o a O, S ~ S. MN dictates the possible next output symbols which can follow the

-19 -present output symbol when an input symbol is applied. There will be only one possible next output (and we can take MN: 0 x S - 0) precisely when for all ql, q2 ~ Q. s ~ S ql q2 M(ql's) N M(q2's)' This happens just in case 1N = Q I has SP, and if this is the case, MN MIIN. Thus if h is a homomorphism from a subtransition function M1 C M to M the machine <S, Q Q2 M, h> has output behavior M' _M'H M 2'QV Q2- I N 1 l l h 2 when restricted to the orbit of MI. (In fact since h: Q2 Q1 MN = M2.) This substantiates the assertion that the output behavior of a homomorphic realization of M2 suitably restricted is identical to M2. More than this, we have shown that if the output behavior of a Moore machine is to be considered as the state behavior of some machine it must be deterministic and hence the output map must induce an SP partition on its state set. When a homomorphism from M1 onto M2 is one-one we say that it is an isomorphism. In this case M1 and M2 are isomorphic and we write M1 M2. Correspondingly, an isomorphic realization is a homomorphic realization whose output map is an isomorphism when restricted to the appropriate orbit. Let the memory capacity of a realization be the cardinality of its internal state set. Then the realizations with least memory capacity must be isomorphic realizations. In particular <S, Q, Q, M, i> where i: Q * Q is the identity is a realization of M: Q x S - Q having IQI states, the least memory capacity possible. While for isomorphic realizations of M there must be an orbit having IQI states, the total number of states is unbounded. Clearly, however, any

-20 -subtransition functions not corresponding to M play no role in the realization. On the other hand, the operative subtransition function of a homomorphic realization (the domain of the homomorphism) may have an unbounded number of states. Such realizations arise because it is often convenient to expand the memory required by a realization in order to satisfy other criteria. Since we are here interested in measures of feedback complexity we shall want to know whether this complexity can be reduced by allowing more memory capacity than is minimally required.

-21 -1.4 Simulation We proceed to the most general form of realization to be considered. Given transition functions Mi: Qi x Si + Qi, i = 1, 2 we say that M2 divides M if there exist states QO C Q1 and maps g: S2 - Sl h: Q1 Q where = Q(g(S2))* such that for all ql ~ Q1,s h(M1(ql, g(s)) = M2(h(ql),s). Thus the following square commutes: g(s) q! ~ q 1g(s) h h q2.. 2 The map g is called an input code and dictates how the symbols of S2 are to be represented by strings over S1. We insist that strings over S2 be coded in a memoryless fashion, namely that the map S1 to S* be just the unique extension of g to a homomorphism g: S +- S1 (recall that g(s S2 g(sl) g(s2)... g(sn) for all strings with elements si E S2). Note that when S1 = S2, g is the identity and QO[g(S2)] = Q1 we have that M2 is a homomorphic image of M1; when h is one-one as well, M1 M2. Thus if M2 is a homomorphic image of M1,M2 also divides M1. Let M1: Q1 X S1 + Q1 be a transition function and M1 C_ M1 a

-22 -subtransition function. Assume that M2 divides M1 with maps g: S2 S and h: Q + Q2. A simulation of M2 is a machine A <S1, Q1= P2 Mlh> preceded by an encoder realizing the map g: S* + S*. Accordingly, if M divides M we also say that M can simulate M or that M can homomor2 1 1 2 -1 phically realize M2 allowing input encoding. Again it is the output behavior of a simulation of M2 (or more properly a portion of the extended output behavior) which is to be identified with M2. To show this we first note that ql h q2 implies Ml(ql, g(s)) h M1(q2, g(s)) for all ql', q2 E Q1, s e S1. i.e., that 1h has SP with respect to g(S2). The extended output behavior of a Moore machine <S, Q, O, M, N> is the map MN: x S* + 2~ given for all o ~ 0, x ~ S* by MN(o,x) = {N(M(q,x)) q E N (o)}. Restricted to some subset T C S* MN is deterministic, i.e., can be taken to be a map MNIT: 0 x T + O, just in case q! N q2 implies MN(ql,x) N MN(q2,x) for all ql, q2 z Q, x ~ T. Thus happens just in case HN has SP with respect to T. As before, we can easily establish that MN C M|IN (restricted to T). Applied to the machine A1 of the definition of simulation we have that MlN(q 2g(s)) = M2(q2,s) for all q2 e Q2, s ~ S2. Thus if the output symbol of a simulation of M2 is q2 and a string g(s) is applied the output symbol following this string will be just what the next state of M2 would have been if started in state q2 with

-23 -input symbol s. The concept of simulation can be readily extended to the computation of functions. Given a function f: S* -+ 01, we say that a machine A1 = <S11 Q1' O1' M1, N > simulates f if there exists a homomorphism g: S* + S* and an output o' c 01, such that M1N (0', 9(x)) = f(x) for all x ~ S*. There is a minimal machine associated with the function, f, namely Af = <S, S*, 01' Mf N > f 1' ff where Mf([x]f,s) = [xs]fl and Nf([x]f) = f(x), for all [x]f ES*a, s C S and x f y iff f(xz) = f(yz) for all z E S*. It is readily established that if A, simulates f then Mf divides M'CM1. 1.5 Implementation of Input Encoding Essential to the operation of a simulation is the input encoding.

-24 -There are several ways to implement this encoding. One way is to consider an encoder whose input rate is fixed. Since it must in general put out strings of symbols in response to the input symbols, it must be able to store incoming symbols while it is translating previous input. In fact it is not difficult to show that such a device must have infinite memory capacity! The term "memoryless" applied to it previously is, from this point of view, deceptive. A more productive approach is to allow the encoder to control its input rate. For example, the encoder could proceed by accepting a new input symbol only when it has completed outputing the string corresponding to its previous input symbol. Another possibility is that of off-line pre-processing. Here the input encoding is not considered to be part of the simulation proper. If one regards x ~ S2 as data and f(x) as the results of a computation, then the map g: S* -+ S* may be considered as the appropriate manner to prepare the data for input to the computer (i.e., the simulation of f2). The concept of slow computation (McNaughton, 1962; Holland, 1968) turns out to be an interesting special case of this approach. A machine A1 = <S1' Q1' o1' M1' N1> is said to b-slow compute a function f: S* + 01 if for any input string of the form: b-l b-l b-l Q s 1 s2... sn there is a state q0 ~ Q1 such that b-l b-l b-l MlN(N(qO)s Q1 s2... S s Wc) = ilNO ( N ( S2 Snn c 1 2~~~ nI

-25 -Here S1 D S U Q where Q is intended to represent a no-signal input and as usual Q denotes a string QQ...Q(k times). W is any string of length c c; where both b and c are fixed non-negative integers. What this means is that the function value of a string sl s2... sn whose symbols are fed in at a rate of one symbol every b time steps appears c time steps after the end of the input sequence. To establish the correspondence between b-slow computation and simulation we extend the latter as follows: Given a function f: S* ~ 01 we say that a machine A1 = <S1, Q1' 1 M 'N1> simulates* f if there exists a homomorphism k: S* + S1 o' ~ 0 such that MiN(O', g(x) w ) = f(x) for all x c S*, and all strings wc of length c, a fixed non-negative integer. Clearly, if A1 simulates f then A1 simulates* f. It remains true that if A simulates* f then M divides M1. Now let A1 b-slow compute f: S* + 01. Let g: S + S* be given by g(s) = b S for all s ~ S, let g be its homomorphic extension to S*. Then M1N(N(g), g(x) wc) = f(x) for all x ~ S*. But this means that A1 simulates f and furthermore that Mf divides M1. 1.6 Simulation and Semigroup Actions We now proceed to establish the relation between simulation and semigroup actions.

-26 -We shall say that R2 divides R1 (R1, R2, semigroups) if R2 is a homomorphic image of a subsemigroup of R1. 1.3 Proposition If 2divides M1 (Mi: Qi x Si -+ Qi' i = 1, 2) then M divides M1 Proof: It is readily established that h(M1 (ql,g(x)) = M2(h (ql),x) for all x c S1, ql C Q1. It follows that -(x) - -(y) implies 1; (ql'g(x)) = M1(qlg(y)) implies h(Ml(qlg(x)) = h(M1(ql,'g(y)) implies M2(h(ql),x) = M2(h(ql),y) implies x 2 (since ql a Q1 was arbitrary).

-27 -Letting (S1 ) be the semigroup 1I { [g (X) ]M IX S*} we have that g': -(S* I 1 1 22 is a homomorphism where g ( [(X) ]M)= [x]M for all x ~ S*. We wish to consider a possible converse to this proposition —if R2 divides R1 what can be said about any actions of the form <R2,., <R.,.>? In what follows all semigroups are finite and all <R,.,.> actions are faithful. For any transition function M: QxS-+Q, H(M) denotes the set of all transin n n tion functions of the form H i= Mi: i=l Qi S i=l Qi where the Mi are isomorphic copies of M and Hn=l Mi(q... 'qn'S) = (ql We say that M' divides H(M) if there exists some machine in 1(M) which can simulate M'. Clearly if M' divides M then M' divides H(M). We define the equivalence relation "mutually 1 simulates" on the set of all transition functions by M1 mutually n simulates M2 iff M1 divides H(M2) and M 2 divides 1(M1) for all transition functions M1, M2. For any semigroup R, and action <R, S, Q>, <R, R, R > divides 1(<R,S,Q>).

-28 -Proof: Let M = <R, S, Q>. Take IQI copies of M(i.e., Mi = M, i = 1,2,...,IQI to form the product HiMi. Take g: R -+ S* where g(r) is any string of S* whose product in R equals r. Take h: Q{ + R1 as h(ql,q2,...,qQ) = 1 where (ql1q2,... qlQI) is a fixed state of RiMi, qi all distinct and h(qlr,q2r,...,qIQIr) = r for all r E R. Here Q{ = {(qlr,q2r,..., qlQir)Ir e R}. h is well defined since R is the semigroup of M and thus has a faithful representation as a semigroup of transformations on Q, i.e., we may identify r + M,r (ql' q2' '' qlQI) + (q1r, q2r,... qlQjr) It now is readily verified that <R, R, R1> divides i.M..! 1 We say that M: Q x S + Q is transitive or connected if there is a q0 EQ such that (q0) ~M = Q. q0 is called the starting or initial state of M. 1.5 Proposition <R1, R1, R1> can simulate any transitive <R2, S2' Q2> action in which R2 divides R1.

-29 -Proof: Since R2 divides R1 there is a homomorphism k from R1 C R to 2 - 1 1-1 R2 Take g: S2 +, as g(s) = k (s) where k (s) is any element in the inverse image of s, and h: R1 +2 by h(l) = q and for all r c R, h(r) = M2(q,k(r)) (k(r) expressed as a product of elements of s2) where M2 = <R2, S2' Q2> and qO is the starting state of M2. That M2 divides <R1 R1' R1> may now be verified. 1.6 Proposition For any semigroups R1, R2, if R2 divides R1 then for any transitive <R2, S2' Q2> action and any <R1, S1, Q1> action, <R2, S2, Q2> divides l (<R1, S1, Q >). Proof: From Proposition 1.5, <R2, S2, Q2> divides <R1, R1, R1>. By Proposition 1.4, <R1, R1, R1> divides H(<R1, S1' Q1>) By the transitivity of the division relation, <R2, S2, Q2> divides H (<R1, S1, Q1>). 1.7 Theorem Let c be the set of all transitive (connected) finite transition functions. Two transition functions in e have the same semigroup if, and only if,

-30 -they are in the "mutually H simulates" relation. Thus the equivalence class of all faithful actions <R,S,Q> over a given semigroup R is just the class of all transition functions which can mutually H-simulate any member of that class. Proof: Consider two faithful <R,S1,Q1>, <R, S2,Q2> actions. By Proposition 1.6 <R,S1,Q1> divides H(<R,S2,Q2>) and <R,S2,Q2> divides l(<R,S1,Q1>) so both are in the "mutually H simulates" relation. To show the converse, the reader may readily verify that the semigroup of Hi M where M. M, i = 1,2,...,n is just the semigroup of M. i=l 1 1 i Thus if <Rl,S1,Q1> divides H(<R2,S2,Q2>) then by Proposition 1.3 R1 divides R2. Likewise <R2,S2,Q2> divides H(<R1,S1,Q1>) implies R2 divides R1. But then R1 - R2 as required. We mention that these ideas may be used to characterize the irreducible transition functions for series-parallel decomposition. Let us say that a transition function M is H-irreducible if, whenever M divides a series parallel (finite) composition of machines with (possibly distinct) transition functions Mi, then M divides H(Mi) for some i. As defined in the Krohn-Rhodes theory M is irreducible if whenever M divides a series parallel (finite) composition of machines with transition functions Mi, then DM divides M. for some i. It is readily shown that these definitions define the same 1 set of transition functions. Thus we arrive at a characterization of the irreducible transition functions which can be stated without reference to the underlying semigroups but wholly in terms of series parallel compositions.

-31 -1.7 Cycle Correspondence in the Division Relation We have seen how SP partitions are induced by the output maps of homomorphic realizations. We shall now present the well-known relation between the SP partitions of a transition function, M, and the existence of isomorphic series parallel realizations of M. Let (HiAi)' be a series parallel composition over the set of machines {Ai.}. We say that (HiAi)' is a series parallel (SP) simulation (homomorphic realization, isomorphic realization) of a transition function M if (.iAi)' simulates (homomorphically realizes, isomorphically realizes) M: Q x S + Q. (HiAi)' is a nontrivial SP simulation (realization) if for every component A., with transition function M.: Qi X Si + Qi' 0 < IQil < IQI We sometimes say that M has a nontrivial SP decomposition if there exists a nontrivial SP simulation for M. A partition H, on a set, Q is nontrivial if it is neither the finest nor the coarsest partition on Q. (See Section 1.8.) We quote a slight extension of Theorem 2.4 of Hartmanis and Stearns (1966): 1.8 Theorem A transition function M: Q x S -+ Q has a nontrivial isomorphic series parallel realization if, and only if, there exists a nontrivial SP partition I on Q, the set of states of M. The proof consists in noting that the front components of an isomorphic realization (i.e., the machines Ai whose connection maps Zi depend only on the input) induce nontrivial SP partitions on Q. Conversely, any nontrivial SP partition H on Q has associated with it a machine with transition function M|l which can be used as a front component of a nontrivial

-32 -SP realization. Actually, the proof of Theorem 1.8 allows us to state 1.9 Corollary Let M: Q x S - Q be isomorphically realized by a series parallel composition of machines {Ai} with corresponding transition functions {Mi}. Then there is a homomorphism from M to a subtransition function of M1, where M is the transition function of any front component A1. This follows from the correspondence between SP partitions and homomorphisms alluded to previously. We now wish to study cycles in the state diagram of transition functions and show how these behave under homomorphisms. Let M: Q x S -- Q be any transition function and M: Q x S* - Q its extension to S*. M contains a cycle if there is a q ~ Q such that q = qx...1) for some x ~ S* and positive integer k. Let k be the least positive integer for which (1) is true. Let the sequence Z1, 2' 3'... Zk,(x) be the sequence of initial substrings of x k, where Z1 is the first symbol k k of x and ZkQ(x) = The sequence of states qZ1, qZ2, qZ3,..., qZkQ(x) is called the cycle of x and clearly consists of the states encountered in journey from q back to q in the ordered of encounter. The number of states in the sequence is its period, T. Clearly, T = kZ(x). The x-period, T..... ' ' ~~~~~~~~~~

-33 -is the number of states in the subsequence 1 2 3 k qx, qx, qx,..., qx We note that each of these states must be distinct (since k was the least integer for which (1) held, so that Tx =k...2) and hence T = T(x)...3) (Q(x) may be referred to as the input period). We remark that the cycle of x need not form a cycle in the state diagram of M in the graph theoretic sense i.e., not all qZi need be distinct (although all qx- are distinct). We say that M contains a string cycle of string period, p if it contains a cycle of x for some x e S* which has x-period, Tx = p. We extend the concept of SP partitions to arbitrary maps 0: Q x z - Q. As is to be expected, I has SP for 0 (on Q) if ql n q2 2=0(ql'o) (q 2, oa) for all ql, q2 c Q and a ~ X. We shall require the following 1.9 i Proposition Let S be a generating set for R, a semigroup and 0: Q x S - Q. Then n has SP for 0 iff I has SP for 0: Q x R +- Q where e is the extension of 0 to R if it exists.

-34 -In particular, for any transition function M: Q x S + Q and its extension to S*, M: Q x S* -* Q, H has SP for M iff H has SP for M. Proof: The forward direction of the proposition follows from induction while the reverse direction is immediate. The main theorem of this section linking string periods in the domain and range transition functions of a homomorphism will now be stated. 1.10 Theorem Let Mi: Qi x Si - Qi be finite transition functions such that M2 divides M1 with maps h: Q Q2' and g: S S*. If for some xe S2, q q2, (g(x)) = ' ~ Q is a g(x)-cycle of M! with g(x)-period m, then h(q'), h(q9),..., h(q') is an x-cycle of M2 with x-period k dividing m. Conversely, if ql' q2' '"' qk, (x) = q is a x-cycle of M2 with x-period k then there exists a -(x)-cycle in h-l (ql) U h (q2)...Uhl(q) in M1 with g(x)-period m > 0 a multiple of k. Proof: -- Consider the subsequence of the given g(x)-cycle of M1:

-35 -q '(x), q[g(x)]. q[(x)]m = q Let h(q') = q. Noting that h(M (q',[g(x)]i) = h(Ml(q', k(xi)) = M2(h(q'), x ) = M(q,x ) We see that the given subsequence maps under h to a sequence 1 2 m qx, qx,..., qx = q in M2. Not all states in this sequence need be distinct. Let k the least integer for which qxk = q. Then we readily establish that qxm = q iff m = kk, for some integer Z > 0. The reverse direction is immediate. In the forward direction, we can always write m = kk + n where Z, n are integers, >2 0, m kZ-ln n 0 < n < k. Then q = qx = qx = qx, but k is the smallest integer with the property qx = q, so n = 0, and hence m = kZ. Thus 2 k qx, qx,..., qx = q is a subsequence of an x-cycle which thus has x-period k dividing m. < Consider the subsequence of the x-cycle of M2: 2 k qx, qx,..., qx = q. Then the blocks h l(qx), hl(qx2),..., h-l(q) of 1h are all distinct 2 k (since qx, qx,..., qx are all distinct). Let Z = g(x). We note first that for all i > 0, q' ~ h l(qxi) q'Z c h-l(qxi+l).

-36 -This is so since q' e h-l(qxi) implies h(q') = qxi implies h(M1 (q' (x)) = M2 (qx'x) implies q'g(x) h-l (qx i+l). Now let qO be a fixed state in h (q). From the preceding facts we can construct a sequence 2 i q0Z q0Z,... q0Z... in M1, such that for all j > O qZjk+l ~ h (qx), q0Zk+2 ~ h (qx ),... q0zjk ~ h-l(qxk = q). Since h l(q) is finite, not all q0Zjk can denote distinct states. Let nl > 0 be the least integer such that 10Z - Z xk q0Z q0Z for some integer x > nl. Let n2 be the least such integer x, i.e., nlk n2k q0Z q0Z Then nlk n k+l n2k nlk q0Z ' q0Z.'. q0Z = q0Z is a subsequence of a g(x) = Z-cycle in M1 having g(x)-period (n2-nl)k, a non-zero multiple of k. To show that all states in this sequence are distinct (hence establishing the claim) note that

-37 -q0k+i q k+i' for any i Zi', 0 < i, i' < k, as these elements belong to distinct blocks of Hk i.e., q0Zj Ik+i' h (qx') and q0Zj ~- h (qx). Thus set i = i' and nl < j < j' < n2. If zjk+i q jk+i qOZ = q0Z then n2k (j '-j+n2)k q0Z = q0Z 2 and hence that nlk [n2-(j-j')]k q0Z = qZ But n2 is the least integer for which this is true so j-j' = 0 and j = j', a contradiction. Since homomorphism is a special case of division we can state: 1.11 Corollary For finite transition functions, M1, M2, if M2 is a homomorphic image of M then the string period of any string cycle in M1 is a nonzero multiple of the string period of its homomorphic image. Every string cycle in M2 is the homomorphic image of a string cycle in M1. Remark The reader may wish to check that the more difficult direction for

-38 -1.10 cannot be carried over to (unlabelled) digraphs with the usual definition of homomorphism.

-39 -1.8 Co-ordinatization and Prediction We wish now to develop the correspondence between coordinates and partitions and to develop the algebraic manipulations on partitions upon which we shall rely in establishing our main results. A more extensive review may be found in Roosen-Runge (1967). Let {Q la c D} be a family of non-empty sets, Qa with D = {l1, a2'....} the index set. (lWe also write D = {a, 8, y,...}.) We say that {Q } is a co-ordinatization of a set Q if Q c otQ Q= x Qa x... x Q. x 1 2 i More generally we allow Q to be mapped one-one into H aQ. We shall be dealing mainly with logical nets we shall usually be considering binary co-ordinatizations in which for each a e D, IQa = 2. Each a c D is called a co-ordinate. We define the family of coordinate projections proj H Q + Q by prof (q q,...q...) = q for all (q, q,... qa,...) ~ HaQa' ai ~ D. 1 a2 1 Every subset D' C D induces an equivalence -, on Q, where for q, q' ~ Q q = q' iff proj (q) = proj (q') for all a ~ D'. The corresponding partition I_4 —,. We write

-40 -1 = 11 for any a c D. PQ denotes the set of all partitions, n on Q. PQ is a lattice with underlying partial order <, where for all H11 H2 C PQ 1 < 2 (read 11 refines 12) iff for all q, q' E Q, ql n q2 implies ql 2 q2. 1 2 H22 The least upper bound (k.u.b) and greatest lower bound (g.9.b) operators are denoted U and n respectively. The g.Q.b, q, is defined by q( =- _)q ' iff q - q' and q _ q' and s n Q =H- - The Z.u.b operator, U is defined by iff there exist q = ql' q2' q3' ' qn q such that qi 1 qi+l for all odd i, and qi 2 i+l for all even i; and

-41 -1 U 2 = Qll 2 These definitions satisfy the required conditions namely that 11 < H (i=1,2) implies R < 1 U H2 and Hi < H (i=1,2) implies H1 n 12 < i. O is the finest and I the coarsest partitions of PQ are defined by q =' q iff q = q' q i q' iff q, q' E Q and o = qlQ I = QI= (={Q}). 0 I We write PQ = { I D' C D} We note that Q - o = HD ~Q, and I = E Pq. It is readily established that for all D', D"C D D aD' and D' CD" implies ID" <- DI

-42 -The latter assertion means that D' -* 11D' is an order reversing map D D D between 2 and PQ However PQ is not in general a sublattice of PQ antiisomorphic to 2D This condition does hold when {Q la C DI is an irredundant co-ordinatization (as defined below) of a finite set. We say that D' C D is a location for H E PQ if HDt < n and for all D" C D' if HD" <- n then D" = D. In other words a location DH of H is a least subset of D with property that HD refines H. A co-ordinatization {Qla c D} is irredundant if every partition H $ I ~ PQ has a unique location and no non-empty subset of D is the location of I (i.e., D' C D and IIDI = I implies D' = P). 1.12 Proposition (Similar to Theorem 2.10 of Roosen-Runge, 1967.) Let Q be a finite set and {Q la c D} a co-ordinatization of Q. {Qala ~ D} is irredundant if, and only if, for all D1, D2 C D D D In this case, since already HD = H P is anti-isomorphic to 2 D D om o2 Q 2 2 Proof: We show that if for some D1, D2 C D, HDU HD2 D D2 then {Q Ul ~ D} is not irredundant. Since HD _ D1N D (i=1,2) it is always true that i 1 2 H uH <H11 D1 D2 1N D2 So it must be that rD D <D DD. 1 I2 1 2

-43 -Now for each i, D < -D U nD < ID (D i 1 2 1 2 so each Di contains a location for ID U 1D which is strictly larger 1 2 than D1 DD2 DN <than DL D2 Now be lU ti I (for if HD U H2 = I then D =D2 I 1 2 1 1 2 and HDnD nD U n2 a contradiction) and moreover D n D 2 1 (if D1 ( D2 = D. then D D U ID < 1 1 2 1 a contradiction). Thus both D!, D2 contain non-identical locations for HD UHD (# I) and {Q } is not irredundant. 2 <K Let D_ D be locations for any I c P We show that D = D2 Since H1D. < H (i = 1,2), 1D U ID <H 1 1 2 By assumption 11 Un =11 1 2 1 2 so 1D1 D D < 1 and D1 n D2 cannot be a proper subset of Di(i = 1,2) (which 1 2 is a minimal set for which ID < ) Thus D1 1 2 = D2 Thus the location of any 1 c PD is unique and {Q } is irredundant. A co-ordinatization {Qlia s D of Q is said to be Cartesian if Q = 1 Q. It is readily established that for such a co-ordinatization, 2 1 2 for D1, D2 C D and hence a Cartesian co-ordinatization is irredundant.

-44 -We say that a co-ordinate a c D is dependent whenever HD-a < II a is independent if it is not dependent. Two kinds of dependence may be distinguished. a E D is called a constant if I = I. The appropriateness of the term is that proja(q) constant over q ~ Q. Clearly Ha = I implies D l<. When D-a a h ii < I < I D-a a We say that a is completely determined. In this case Q can take on more than one value (i.e., there exist q, q' E Q for which proja(q) $ proja(q')) but the values it can take on are completely determined by the other coordinate values. For example, let IQI = n and consider the well-known co-ordinatization of Q = {qill < i < n} by {Q |1 < i < n} where for each i, qi = (0, O,..., 1,...0) (only proja. (qi) is non-zero). 1 As we shall presently show, no more than n-l co-ordinates can be independent, so that as the reader may directly verify, any one co-ordinate in this co-ordinatization completely determined by the rest. 1.13 Proposition Let {Q la ~ D} be a co-ordinatization of a set Q. Then a) For any D' C D and a e D ', RD- = 1D' implies ais dependent. Conversely, b) If a is dependent, HD-a = HD = 0 and thus {QI1B e D-a} is a coordinatization of Q (i.e., there is a one-one map from Q into lHQ8). Proof: Since =D = (D'-) U D (D = ~'-c)V)Q =D'-5 5c

-45 -we havell =11 iff D -n =1 D- iff il < r. Now il < H D' D'-a D'-a na D'-a i D-a Now D-a- < D'- a (since D' C D) so Dt = 11D'- implies H < 'n, and a is dependent. Conversely, if HD < H then from the above equivalence HD- = D 0= We say that a co-ordinatization is independent if all of its co-ordinates are independent. We show now that independence is a weaker condition than irredundance. 1.14 Proposition If a co-ordinatization is irredundant it is also independent. The converse is false —it may be independent without being irredundant. Proof: Let {Q la ~ D} be irredundant and not independent. Then there is an a ~ D such that H = I or H a I and D-a < n. In the first case, from aaa - a the definition of irredundance {a} =4, a contradiction. In the second case, D-a contains a location for H distinct from a. As a counter example to the converse we present an independent binary co-ordinization on which is not irredundant. Let D = {a,x,y,6} with Q = {O,1} = and Q= = {a,b} = Q. Let Q C Q x Q x Q x Q6 be Q = {OOaa, Olba, 10ba, 10ab, llba, llab, llbb} Graphically Q is the subset of the (axx) x (yx6) plane: Y6 bb ab ba.. aa = 00 01 10 11 1 a3

-46 -We have: H = {OOaa Olba, 10ba, 10ab, ilba, ilab, llbb Ha~ (= 00aa, Olba, lOba, lOab, ilba, ilab, llbb} = {OOaa, Olba, 10ba, 10ab, ilba, llbb, llab} Since a,3,y ~ 0, 6 is not redundant. (Note that there are two distinct states having the same a,3,y projections with different 6 projections.) By symmetry neither are a,B or Y is redundant. Clearly none of the co-ordinates is constant so independence holds. But even though {a,} f{y,6} = {, H UH 6 = II00aa, Olba, lOba, 10ab, llba, llab, llbb ~ I has as distinct locations{a,8}and {y,6}. So D is not irredundant. Essentially we have shown that the condition -II D= D U tD D1 nD2 D1 D2 can fail to hold even if D is an independent binary co-ordinatization. Our final assertion about co-ordinatizations places bounds on the number of independent co-ordinates. 1.15 Proposition Let {Qala C DI be a co-ordinatization of Q of finite set. Let D' C D be any independent subset of D. Then ID' I | IQI -1. If m = max IQa|, then IDI > logmQI. acD Proof: As the second part of the proposition is well known, we prove only the first. For D" C D, ~ ~ D", D"-a C D" and so it is always the case that

-47 -HD"-a > HD,,. From Proposition 1.13, we have that if a is independent D1 DI "I-nand thus > HD It follows that if D' = {a1 2 aID' I} is an independent set >11 >... > a1 a1'a2 1' a2P".' |D'D| Let |I1 denote the index of 1 (the number of blocks in H). If IQI > 2 then IN > 2 since 1Ha = 1 implies Ha = I. (If IQI = 1 then for every a,Hn = I and so ID'I = 0, as required.) Also < HI' implies II' > IH'I for all II, H' C PQ, so 2 < Ia I < I aa I..I In U1"'la a = I 1 1 2 2 D | and it follows readily that ID'I + 1 < IKHD'| but HD > O so IIID'I < IQI and thus ID' I + 1 < IQI as stated. Let M: Q X S + Q be a map. For any partitions i, p E PQ we say that H predicts p if for all q, q' E Q, s ~ S, q = q' implies M(q,s) M(q',s). AH p A pair of partitions is said to be a non-trivial prediction pair if T

-48 -predicts p and 11s 0, p $ I. The kernel M(p) of p c PQ is defined for all q, q' C Q by q M-p) q' iff M(q,s) p M(q',s) for all s ~ S. That 1 predicts p iff 1 < M(p) now immediately follows. Whence from the definitions of Z.u.b. and g.Z.b it follows that if,H1' predict p then 1 n T' and 1 U i' also predict p. Now let {Q al ~ D} be a co-ordinatization of a set Q. For any a E D consider the function M: Q x S + Q given for all q ~ Q, s ~ S by M (q,s) = proj)(M(q,s)). Similarly for D' C D, MD,: Q x S + c Q is given by MDI(qs)= (Ma (q,s), M (q,s), ''') for a. c D'. We say that D1 predicts D2 if for all q, q' C Q, s c S q D q' implies MD (q s) = MD2(q',s). 1 2 2 Clearly, D1 predicts D2 is equivalent to ED predicts HD2 and hence to 1 2 iD~ M(I ). When RD is a location for M(HD ) we call D1 a determining 1 2 1 2 set for D2. Thus D1 is a determining set for D2 just in case D1 predicts D2 and if D' C D1 predicts D2 then D' = D1. We define the relation "det" on D (meaning "determines") for all a, 5 ~ D by a det 6 iff a belongs to a determining set for B. It is almost immediate that a det S iff there exists D' C D such that a ~ D' and D' predicts 5 but D'-a does not predict S.

-49 -1.9 A Short Look Ahead As conclusion to this portion of review, we place some of the points developed above into a context appropriate to our main concerns. Let {A aa s D} be a set of machines A = (H A )'a composition over it. Let A simulate a transition function M: Q x S + Q with maps g: S - S'* and h: Q' - Q where Q' C Ha Qa is the orbit corresponding to the appropriate subtransition function of A. Clearly {QIaa E D} is a co-ordinatization of Q'. Also, we have identified the connections maps Za: Ha Qa x S' - Q as essential determinants of the next state functions M: HQ x S' + Q In the next chapter the associate the relation a det 8 with the dependence of Z on co-ordinate a hence with the possible existence of wire from a to S. We have seen that in a non-irredundant co-ordinatization there may be multiple locations for a given partition. Thus for any E~ PQ, there Q I may be more than one determining set. To construct an appropriate connection map Z then, there may exist more than one minimal set of component output wires from which to choose. In a word —in a non-irredundant co-ordinization more than one minimal source may be available from which the next state of a component may be computed. By the same token, this is true for higher order successor states and this leads to an axiomatization of the conditions satisfied by physical information flow paths undertaken in a later chapter. (Chapter VI). We note that in addition to the partitions PQ, there is the partition ~h on Q' (sometimes referred to the output partition) induced by the homomorphism h: Q' - Q (which is also the output map of the simulation). In problems concerning non-isomorphic realizations, A of M, the question of how much information about PQ, may be deduced from knowledge of the

-50 -constraints on A's behavior provided by Ih (and M) becomes of paramount importance. The results obtained here, some being strong, others weak, do not provide an unequivocal answer to this question.

-51 -1.10 Review of Graph Theory In representing the interconnections among elements of a net, we shall be employing certain concepts of graph theory. These concepts, together with some pertinent facts which we shall establish, will be presented here. Aside from a slight modification in the definition of a digraph, the terminology and unproved facts alluded to, are those of Harary et al. (1966) which should be referred to for a much fuller presentation. A directed graph (digraph) is a pair (D,L) (usually just denoted, D) where D is a non-empty set and L a binary relation on D i.e., L C D x D. Pictorially, D is a set of points such that there is one, and only one, directed line from a to 8 (indicated by an arrow) just in case aLS. Notice that we allow the possibility aLa which appears as a loop in the pictorial representation. (These loops are disallowed in the treatment by Harary, cited above.) If aLB we say that there is a line leaving a coming in to 8, or that a is an immidiate predecessor of 8 or that B is an immediate successor of a. A pair (D',L') where D' < D and L' C (D' x D') L is a subgraph of a digraph (D,L). Any point (or line) in a subgraph must be a point (or line) of the graph itself. If D' is a subgraph of D then D is a supergraph of D'. IS = {a c DtaLB} is called the inbundle or input set of 3. Similarly, O = { j ~ DIsLB} is the outbundle or output set of a. The indegree of a is the number of

-52 -points in I, i.e., II I, similarly, the outdegree of a is IO I. A point is a transmitter if its indegree is 0, and its outdegree is positive, a receiver, if its indegree is positive and its outdegree is 0 and an isolate if both its indegree and outdegree are zero. A path from a to ~ is a set of distinct points a = l' a2' **' an a together with the lines (al 2) (a2' a3) ''' (an- lan) A path is trivial if it consists of 4 single point. Any path from ai to a. (i < j) in the path from a to 8 is a subpath of this path. A cycle is 3 a nontrivial path together with a line from the terminal to the initial point of the path. A digraph is acyclic if it has no cycles. We remark that a finite acyclic digraph has a point of indegree 0 (hence either a transmitter or an isolate). For suppose to the contrary every point has a predecessor. Starting at any point a E D we can find an unending sequence of predecessors (a = a1, a2, ' such that ai+1Lai) which must include a cycle if D is finite. The length of a path or cycle is the number of lines in it. The distance from a to 8 (a,B 6 D), d(a,3) is the length of the shortest path from a to S. The distance from a to a subset D' C D, d(a,D') = min d(a,B) 8ED' The distance satisfies d(a,6) < d(a,y) + d(Y,f)

-53 -for a, f, Y c D. a is reachable (accessible) from 8 if there is a path of finite length from a to S. A digraph is strong (or strongly connected) if every two points are mutually reachable. A strong component of a digraph is a maximal strong digraph subgraph i.e., two points are inthe same strong component, iff, there are mutually reachable. The strong components of a digraph are blocks of a partition, S(a) denotes the unique block containing a. The condensation D* of a digraph, D is the digraph without loops {S(a) a c D} with a line from S(a) to S(3) just in case there are points a' E S(a), 8' ~ S(B) such that there is a line from a' to 3' in D. The fact that there are no loops in the condensation means that some of the internal structure of strong components has been neglected but such a loss is not important for the uses we have in mind. We assert that a condensation D* is acyclic. A digraph D has an (ascending) level assignment if to each a c D there an integer n (called its level) such that for each line (a,B) in D n < n Harary's Theorem 10.2 states in effect, that the following is a level assignment for an acyclic graph D: Let U be the set of transmitters of D and assign the integer 0 to each point in U. To every other point assign the length of the longest path to it from any point in U. We call this the longest path length assignment. We define size (D), the size of digraph D to be the number of points in the largest strong component of D. Thus size (D) = maxlS(a)l c~ED

-54 -1.11 Feedback Indegree We now proceed to establish some properties and facts about digraphs which are relevant to our primary concern —the discussion of feedback in logical net realizations. We define the feedback indegree of a point a C D as the number of lines coming into a from points in the strong component of a. Thus the feedback indegree of a is IIa n S(a)I. Clearly the feedback indegree of a point never exceeds its indegree. In fact it may be 0 when the latter is non-zero. We can however establish bounds on the feedback indegree, given certain information concerning the indegree and the number of points in the graph. If N(a) is any numerical property of a point a e D, the minimum N of D is the smallest N(a) over all a E D. Likewise is the maximum N defined. Let min I(D) be the minimum indegree of D and max FI(D) be the maximum feedback indegree of D. The next proposition relates these two indices. 1.16 Proposition For any finite digraph D, max FI(D) > min I(D) Unpacked this means that if every point in D has indegree at least r(= min I(D)) then some point in D has feedback indegree at least r. Proof: The condensation D* of D is acyclic and therefore has a point having indegree 0. The corresponding strong component of D is such that the lines coming into any point in this component must originate from points belonging to this component. But any point in this component has indegree at least r(= min I(D)) and therefore must have feedback indegree at least r.

-55 -The next question we shall presently require an answer to is: Given that the sum of all the indegrees of the points of a digraph is known, what can be said about its maximum feedback indegree? We say that a digraph is of kind (n,m) if it has n points and the sum over the indegrees of its points is m (the outdegree sum must therefore also be m. Let Pi be the number of points with indegree i, i = 0, 1, 2,.*, n. Then for a graph of kind (n,m) n E Pi = n... 1) i=O n E i Pi = m...2) i=0 First note that not all pairs (n,m) correspond to possible digraphs: 1.17 Lemma For any digraph of kind (n,m), m < n Proof: Under the constraint of (1) the largest sum of E i Pi occurs when Pi = n =n In this case Ei Pi = n2. Next given the total indegree we can find a lower bound for the minimum indegree.

-56 -1.18 Lemma For a digraph D (n,m) min I(D(n,m)) > (n,m) where P(m,n) is the least integer k > 0, satisfying (n) (n-l) + k > m. Proof: If the minimum indegree is k > 0 then Pi = 0 for all i < k and pk >1. Subject to the constraint of (1) the largest sum E i Pi occurs when Pi = i < k-l k = 1 pi = 0 k+l < i < n-l P = n-l n In this case Ei Pi = (n) (n-l) + k. It follows readily that if min I (D (nm)) < k then (n) (n-l) + k > m. Contrapositively, if (n) (n-l) + k < m, then min I (D(n,m)) > k, from which the statement of the Lemma follows. We define F(n,m) is the minimum of maximum feedback indegrees for digraphs of kind (n,m), i.e., F(n,m) = min max FI(D n m))' all D (nm) (n,m)

-57 -Thus every digraph of kind (n,m) has at least one point receiving at least F(n,m) lines from points in its strong component. Our aim is to present a recursion relation for F(n,m) so that a lower bound on F(n,m) may be calculated for every possible (n,m). The formula obtained is not very transparent but establishes the fact that lower bounds can be obtained without examining all possible cases. While we do not pursue the direction here, it may be possible to strengthen the formula and to establish some properties of digraphs from it. We note that F(n,n 2) = n (from Lemma 1.8) hence that F(n,m) has unbounded range. Also, we should expect that as m decreases from n, F(n,m) decreases from n in a monotonic manner. 1.19 Theorem F(n,m) > min max r, min F(n-p,m-rp-q)} n - >r > (n,m) (p,q)cAr where Ar is the set of all pairs of integers (p,q) satisfying a) p = Pr in some solution of (1), (2) with Pi = 0 for i < r, which corresponds to some graph of kind (n,m), b) q < (n-p)p, c) (n-p)2 > m-rp-q. To start the recursion we have F(n,O) = 0 for all n, and F(l,1) = 1. Proof: First F(n,O) = 0 since any graph all of whose points have indegree 0 must also have maximum feedback indegree 0. F(1,1) = 1 since there is only digraph of kind (l,l) —a point with a loop —whose feedback indegree is 1. To establish the given formula we examine the subgraphs of a given graph each have a minimumi indegree r, where r is an integer whose lower limit is Jin m). Thus defining

-58 -F(n,m,r) = min max FI(D all D(n,m,r) where D(n,m,r) is any graph of kind (n,m) having minimum indegree r, it is clear that F(n,m) = min F(n,m,r) n > r (nm) Furthermore, by Proposition 1.16 max FI(D(nmr ) >r, so F(n,m,r) = max{r, Exp.} So F(n,m) = m max {r, Exp.} n >r > '(n,m) where Exp. is an expression yet to be established. >r With each graph D(n m r) we associate the digraph D(n m r) which is the full subgraph generated by the points in D(nmr) having indegree >r strictly greater than r. In other words D(rmr) = {a ~ D(nm r) I |I I,> r and for all a,c E~ D(nmr) there is a line (a, in D r) just in case there is a corresponding line (a,3) in D (nmr). Define F min max FI(D ) (n,m,r) all D>r (n,m,r) all Dnr (n,m,r) We now show that F(n,m,r) > F (n,m,r)

-59 -Proof: Since D(nmr) is a subgraph of D(n mr) any strong component of D(nmr) is in a strong component of D(n mr) and moreover the feedback indegree of a >r considered as a point in D(nr) is at least as great as that considered (n,m,r) as a point in D(nmr). (These properties are hereditary, in the terminology soon to be introduced.) Thus max FI(D ) > max FI(D >r (n,m,r) - (nmr) Now let D(nm,r) be any digraph of kind (n,m,r) having max FI(D(n r ) = F(n,m,r) (n,m,r) Then F(n,m,r) = max FI(D(n,m,r)) > max FI(D(nm, r) > max FI(D ) _ (n,m,r) >r min max FI(D ) (n,m,r) (n,m,r) This inequality enables as to assert that Exp. = F>r (n,m,r) in F(n,m) > m minax r, Exp -n _r (n,m)

-60 -The final step is to establish >r F(nmr) min F(n-p,m-rp-q). (n~m,r) ( p, q) EA r >r Let D(nmr) have exactly p points of indegree r. Then D(nmr) has >r n-Pr points. What is the total indegree of D(nmr)? >r If each of the points in nr received a line from each of the n,m,r) Pr removed points there will have been (n-pr)pr removed from the total indegree of D(nmr). In general, if this deficit is q, then q < (n-Pr)pr. Furthermore, the removal of pr points having indegree r must reduce the total of rp. Thus every D(n mr) is of kind (n-p, m-rp-q) where q < (n-p) and p = pr in a solution of (1), (2) which corresponds to a graph with minimum indegree r. By Lemma 1.17, (n-p) > m-rp-q for a graph of kind (n-p, m-rp-q). Thus F=r min max FI(D>r (n,m,r) >r (n,m,r >r all D mr) = min min max FI(D(np,m-rp-q ) (p,q)cAr (n-p,m-rp-q) = min F(n-p,m-rp-q) (p,q)cAr Here we have used the fact that any digraph of kind (n-p,m') can be a graph D(nmr) which is readily verified. This completes the final step and hence the proof of the theorem.

-61 -1.12 A Packing Density Problem In the later portions of this thesis we shall wish to infer a lower bound on the feedback indegree of digraph given knowledge about how "close" the points are together. For any point a of a digraph D, the innumber of a is the largest distance d(^,a) over all B E D. The inradius of D is the smallest finite innumber. Thus if D has in radius rin. then there is a point in D which can be accessed (from any point which can access it) by a path of length at most r in. We define the involume, V (r) of a point a to be V (r) = r Bd(B,) < rj In other words, the involume is the number of points which can access a by a path of length no greater than r. (The set of such points may be thought of as forming an "insphere" of inradius r centered at a). Clearly, the innumber of a is the least r for which V o(r) = iDl. Given the maximum indegree of a digraph we can readily determine an upper bound for the involume. There is an interesting subclass of digraphs for which this bound can be strengthened. We shall say that a digraph is a cellular space digraph if its points are the intersections of a discrete (integer) Cartesian k-dimensional grid, k > 0, and every point in this grid receives a line from itself and each of the immediately adjacent grid points but from no other points. As implied by the designation, cellular space digraphs are closely associated with the structure of cellular spaces (von Neumann, 1966; Holland, 1968). It is clear that all points in such a graph have the same indegree, namely 2k + 1 where k is the dimension of the grid.

-62 -1.20 Proposition Let D be a digraph with maximum indegree, max I(D) = I. Then for any a s D, V (r) < (I)(r-l) If D is a cellular space digraph then Vk (r ) k k r where k = Proof: There at most I points within distance 1 of a since max I(D) = I. There are at most I points at distance 2 from each of these points, hence at most I2 points at distance 2 from a. By induction, there are at most I points at distance k from a. Thus the total number of points within r of a Va(r) = I l) k=l If D is a cellular space digraph it has dimension, k = 2. Notice that an upper bound on the number of points within radius r of a is the volume of a cube with diameter 2r —namely V (r) < (2r). Because of the vagaries of k-dimensional space where sufficiently large k the volume of a sphere vanishes in relation to least enclosing cube, this bound is much too lax to serve our purposes.

-63 -Instead we proceed as follows: We enclose each point 8 for which d(,,a) < r in a unit cube centered at 3. The least sphere containing all these cubes has radius r + 7-/k i.e., the distance from a to the most extreme corner of a cube centered about a point B for which d(^,a) = r. It is known that the volume of a k dimensional sphere with radius, a is k 2 k 211 a kP (k) where F(x) is the well known Gamma function (Somerville, 1929). Substituting a = r + -/ and noting that the volume of a sphere is the number of unit cubes contained in it yields the given bound on V (r). Let f(I,r) be any function of integers, I,r. We have in mind in particular, fD(I,r) (I)(I-1) and 2I2 ~r +,.,Fk f (I,r) 22 )k cell space where k = - (I-1). Define X(f,r,n) = the least integer I for which f(I,r) > n, if it exists. Otherwise X(f,r,n) is undefined. 1.20i Lemma If a digraph D contains a point a such that for some radius r, the involume V (r) > n then max I(D) > X(fD,r,n). If D is a cellular space digraph then max I(D) > X(fcell space' n). -cell space' r')

-64 -Proof: By Proposition 1.20 for any graph D with max I(D) = I fD(I,r) > Vjr) > n and for a cellular space digraph fcell space (Ir) > V (r) > n. But X(fD,r,n) and X(fcell space' r, n) are the least integers, I for which these inequalities can hold and thus max I(D) > A(fD' r, n) and max (D) X(f space' r, n) in the two cases. Essentially, we have here a formulation of the "packing density" problem. If we wish to pack a certain number of points, n sufficiently close together such that a certain distance bound, r is not exceeded then it follows that there must be a lower bound on the number of points immediately adjacent to a given point. For a given function f describing the manner in which points may be connected together this bound is given by X(f,r,n). Because of the uniformity constraints imposed in the construction of a cellular space graph, V (r) for this graph will be smaller than Va(r) for an unconstrained graph having the same indegree at each of its points. (In fact an infinite tree attains maximum V (r) for every r.) Thus if f is a tight enough bound it should be that cell space X(fcell spaces r, n) > X(fD, r, n) for every r, n. In fact we can establish 1.21 Proposition Let n,r go to infinity in such a way that logr n = c (a constant). Then

-65 -rim X(fD,r,n) n,r -+ o 2c+1 cell space Proof: Let k = -(I-1) be large and r2 >> k. Sterling's approximation then yields k 41er2)2 cell space (I,r) = k4 2 k Now (4lker ) increases from its value at k = 1 to a maximum when k 2 k = 411r Thus when k << r we are assured that if k 411 er) 2 n = \k / then X(fcell space' r, n) = 2k+l. Also approximating fD(I,r) > Ir so k X(fD, r, n) _< n = 411 2r (fD' r= n) < n But then 1 im n,r + x (fD' r, n) < 1 and

-66 -X (f! r, n) 1 im. < r 2k+l r -oX (f1cell space' r, n) But since r2 >> k we can obtain that log n = k log r, hence that k = c as claimed. 1.22 Proposition Let D be a finite digraph for which there are integers r,n such that for all a E D, Va(r) > n. Then max FI(D) > A(fD,r,n). If D is a cellular space graph then max FI(D) > X(fcell space' rn). Proof: As in the proof of Proposition 1.16, consider a strong component of D which corresponds to a point of indegree 0 in the condensation D*. Let D' be this component and note that for every point in D', the indegree and the feedback indegree are identical. Also for any point a 6 D', V (r) > n so by Lemma 1.20i,max I(D') > X(fD,r,n). Noting that max FI(D') = max I(D') we have the first part of the proposition. Substituting f for cell space fD yields the second part. In Chapter VII will be concerned with obtaining the integers r,n required in Proposition 1.22 in order to infer lower bounds on the feedback indegree of digraphs representing automata realizations.

-67 -1.13 Hereditary Properties We introduce at this point the concept of hereditary properties of graphs. If a property is hereditary with respect to a class of graphs we shall show that only a subclass of graphs from this class need by examined to establish the property for the whole class. The concept takes on utility since, as we shall show, the properties of interest to us here are hereditary. Let! be a collection of digraphs. We say that a property P is hereditary over gif whenever it holds for a digraph D ~,it holds for any supergraph of D in Y. That is, for all D e s and D' ~ such that D is a subgraph of D' then P(D) implies P(D'). 1.23 Proposition The following properties of a digraphs are hereditary over any set of digraphs: 1) P(D) iff there are points a, 6B D and a line (a,3) in D. 2) P(D) iff there are points a, 8 a D and a path from a to 3 in D. 3) P(D) iff D contains points a,S which are in the same strong component of D. 4) P(D) iff D contains a point a with indegree II > I. 5) P(D) iff D contains a point with feedback indegree PFI I > I. 6) P(D) iff max I(D) >_ I. 7) P(D) iff max FI(D) > I. 8) P(D) iff D contains a strong component S(a) for which jS(a) > S. 9) P(D) iff size (D) > S. Proof: 1) follows directly from the definition of the supergraph of a digraph. 2) though 9) follows from 1).

-68 -A minimal digraph of!!is adigraph DE! for which no subgraph of D other than D itself belongs to i.e., D E! and if D' is a subgraph of D and D' c!then D = D'. Let min! denote the set of all minimal digraphs of a set of digraphs Lemma 1.24 Let q be a set of finite digraphs. Then every D E! is a supergraph of a minimal digraph. Proof: Either D is itself minimal or if not there is a proper subgraph of D having fewer points and/or lines. By induction on the total number of points and lines in D (which is a finite integer) we arrive at a minimal digraph which is a subgraph of D. 1.25 Theorem (Principle of Induction for Hereditary Properties) Let q be a set of finite digraphs and P a property which is hereditary over A. Then P(D) for all D E ~ if, and only if P(D) for D C min2. Proof: In the nontrivial direction, we note that by Lemma 1.24 every D ~ is a supergraph of some D' E mina. Since P is hereditary over A2, P(D') implies P(D). By assumption, P(D') for all D' e min!2 and so P(D) for all D eZ!.

CHAPTER II REPRESENTING DIGRAPHS FOR LOGICAL NETS ehis chapter develops the notion of the representing digraph for a logical net. We show that a certain set of reduced digraphs includes the minimal digraphs of the class, M of all digraphs representing logical net simulations of a given transition function M. Recall that a logical net is a composition over a finite set of delay elements. (See Section 1.2.) While it would not be much more effort to obtain representing digraphs for compositions over arbitrary components there are two good reasons for restricting our attention to delay elements. One is that delay elements are generally considered to be the ultimate components in finite automata or sequential machine realizations. The second is that the delay element (whose next state is independent of its present state) allows one to implement all the component interdependencies in logical netsby explicit switching functions. In fact given a composition over arbitrary components we can represent each of the components by a delay (having the same number of states) with appropriate switching accounting for the internal state dependence of the component and thus obtain an equivalent composition over delays. Let {A la E D} be a finite set of (two state) delay elements and aaD a composition over {A }, (i.e., a logical net). A is the quintuple <S,Q,,M,.> where Q = i Q and M: Q x S -- Q. We have seen (Section 1.2) aED that each of the components of M, M: Q x S - Qn is of the form M (q1 q2..., qlDis) = MD (q Zo(q1 q2..., qlD s)) -69 -

-70 -With MD the transition function of a delay we have M (q,s) = Z (q,s) for all q ~ Q, s E S. Given the logical net, A, we obtain the digraph representing A, D(A) as follows: D(A) has as points, D, the index set of {A la e D}; there is one and only one, line from a to B in D(A) just in case Qa appears as an argument in Z,, i.e., Z a.. D' E Qi s where a c D' C D. At this point and throughout the next few pages the reader may wish to follow the example in Figure 2.1. D(a) may be thought of as having for points the delays in the net A and having a line from a to 8 precisely when there is a wire running from the output of delay a to the input switch Z of delay B. Note that the external input wires are not represented in D(A). Let Q' C Q = a1 Q be an orbit of M with M': Q' x S + Q' the corresponding subtransition function. Note M' may equal M. Note that {Q cla E D} is a co-ordinatization of Q' and so it is possible to define the relation "is a determining set for" on the subsets of D. (See Section 1.8.) Let det, (D ) be any determining set for D2 where the subscript Q' emphasizes that this is with respect to the orbit Q' (we shall omit Q' when no confusion can arise in doing so). In other words, detQ, (D2) is a minimal set D1 such that for all ql, q2 ~ Q' s ~ S, q1 D q2 implies MD (ql,s) = MD2(q2,s). 1 ~~~22

-71 -Taking D = {2 } and noting that M8 = Zg we have that detQ, (8) is a minimal set D1 such that for all ql, q2 6 Q', s, S, ql,1 q2 implies Z (ql,s) = Z (q2,s). An input selection of D w.r.t, is a collection of IDI subsets D D,..., D where each D is a determining set det, (a) C I al 2 aDI ai in D(A). Thus >Qj. is the result of assigning to each a c D a determining set detQ, (a) which is a subset of the input set of a in D(A). Each input selection 6D, specifies a digraph E as follows: E has as points, D and there is one and only one line from a to 8 in E just in case a E detQ,CB) z IQ, Clearly, E is a subgraph of D(A). Now note that any constant co-ordinate a z D is an isolate in any digraph E specified by an input selection. For if a = I (w.r.t. Q') then detQ,(a) = { so that the indegree of a is 0. Also if for any D' containing a, HD' predicts HB then = (D- = = D D'-a Do- a DI-a inU ta D also predicts H8. So for no B E D is a in detQ,(B) and so the outdegree of a is 0 and a is an isolate. We say that D(AIQ') is a reduced digraph representing A restricted to Q' if D(AIQ') is the full subgraph of a digraph E consisting of the set {all # I}. We restate the definition as follows: Let Q be an input Q, selection (of D wrt to Q') in the logical net A = (II A ) aeD a Q,.specifies a digraph D(AIQ') with points {alI $ I} in which

-72 -there is one and only one line from a to 8 in D(AIQ') just in case a ( detQ,(8) C, D Recall that D(AIQ') is a subgraph of D(A). We see that there are as many reduced digraphs, D(AIQ') as there are input selections Q When the co-ordinatization {Q Ia ~ D} of Q' is irredundant, however, only one such input selection exists (every determining set, detQ,(8), being a location of M(Hn), is unique). Since {Q la ~ D} is a Cartesian co-ordinatization of Q = a DQav it is irredundant and thus only one reduced digraph D(AIQ) exists. We proceed to show that there is a logical net which corresponds to D(AIQ') in a natural manner which has M' as a subtransition function and in which the switch Z preceeding any delay a has an input wire from a delay B precisely when line (a,3) is in D(AIQ'). 2.1 Lemma Let A = (H DA )' be a logical net with transition function M: Q x S + Q and subtransition function M':Q' x S + Q' where Q' C Q is an orbit. Given any reduced digraph D(A]Q') there is a logical net AQ' = ( D A )' where D C D with the following properties: 1) AQ, has a transition function M: Q x S - Q which has a subtransition function isomorphic to M': Q' x S + Q', 2) D(AQ,) = D(AQ,IQ') = D(AIQ') C D(A), where as defined D(AQ,) is the digraph representing AQ,. We call AQ, a reduced logical net of A restricted to Q'. QI -

-73 -Proof: Let D be the point set of D(AIQ') and let A = (H A )' be speciQ' acD' a fied by the switches Z' as follows: For each a E D, Z'. Q x S +- Q OK aC cx. ca 1 cx 1 where D = detQ,(a) ~ IDQ,, the input selection set specifying D(AIQ'); for all q e Q', s s S, Z' is defined by Z' (projD (q),s) = M (q,s), and for all q Q-Q', z'(projD (q),s) is arbitrary, say Z' is a constant qO ~ Q for these values. (In practice these "don't care" conditions should be expeditiously chosen to minimize switch complexity.) Because AQ, is a logical net, M = Z'. We claim that h = proj'. is an isomorphism of M' and MQ' restricted to projU (Q'). It is sufficient to show a) that for each a E D proj (h(M'(q,s))) = proj (MQ (h(q),s)) and for q ~ Q', s E S and b) h is one-one. To prove a) we note that it reduces to proj (M' (q,s)) = Z'(proj- (q) s). But noting that for q ~ Q', s C S, M'(q,s) = M(q,s) the left hand side is just M (q,s). Since by construction Z' depends only on {QBIB ~ D } we have the right hand side equal to Z'(proj, (q),s). By construction the two sides are equal. To show b), suppose to the contrary

-74 -that there are ql,q2 in Q' such that ql $ q2 and projT (ql) = projD (q2). Then there must exist some a E D - D such that proj (ql) # proj (q2). But this is impossible because a is constant. 2) D(AQ,) has the point set of D(A|Q') by construction. There is a line from a to 8 in D(AQ,) iff Q% is an argument for Z8 iff acx D = detQ,(@) J Q, iff there is a line from a to B in D(A[Q'). Thus D(AQ,) = D(AIQ'). Now D(AQ, IQ') has point set {ajla J I} which is the point set of D(A[Q'). Since each detQ,(8) E Q, is a location for M(ll) and thus no proper subset of detQ,(@) can be a location for M(ll). Thus there is only one input selection possible for D, and that is consists of all Q the non-emptysetsin >DQ. Thus, there is a line from a to 8 in D(AQIIQ') Q iff a C detQ,(B) E D Q, iff there is a line from a to 8 in D(AIQ'). Recalling that D(AIQ') is a subgraph of D(A) completes the proof. Let ~'M be the class of all digraphs representing logical net simulations of a transition function, M: Q x S - Q. Thus M = {D(A) IA is a logical net simulation of M}. The minimal digraphs of! M are included in a certain set of reduced digraphs as we now show. We say that M2 minimally divides M1 if M2 divides M1 and for any 1, if2 d i v1 2 1 subtransition function M' C M if Mdivides M1 then M' = M 1 1' 2 1 1 V, A simulation A1 of M2 has operative orbit Q' if M2 divides the subtransition function M1 < M associated with orbit Q'. If furthermore M2 aminimally dividesf M1 minimally divides M we say that A is a minimal simulation w.r.t. Q'

-75 -2.2 Theorem min GM C {D(AQ,) A is a logical net simulation of M which is minimal w.r.t. Q'} C {D(AQ,) A is a logical net simulation of M having operative orbit Q'}. Proof: We prove the weaker inclusion first. Let D be a minimal digraph of ~M. Then D represents a logical net A which can simulate M, i.e., M D = D(A). There must then exist an operative orbit Q' in the state set of A such that M divides the associated subtransition function M'. Suppose that D(AIQ') is a proper subgraph of D(A). By Lemma 2.1 there is a logical net AQ,, for which D(AQ,) = D(AIQ') which has a transition function isomorphic to MI. AQt can therefore simulate M and thus D(AQI) E M. But D(AQ,) = D(AIQ') is a proper subgraph of D(A) = D and so D is not minimal contrary to supposition. Thus D = D(A) = D(AIQ') = D(AQ,). Now proceeding to the stronger inclusion: we now know that if D E min M then D = D(AQ,) for some logical net A which simulates M with operative orbit Q'. Suppose that A is not minimal w.r.t. Q'. Then M divides a proper subtransition function M1 C M. Thus there is an orbit Q" C Q'. Suppose that D(AQ, IQ") is a proper subgraph of D(AQ,). Then there is a logical net simulation AQIQ of M such that D(AQQ,,) = D(AQ, IQt). But then D(AQQ,,) is a proper subgraph of D and since D(AQQ,,) E M' D is not minimal contrary to assumption. Thus M1 = M1 and M minimally

divides MN, so AQ, is a logical net simulation of M which is minimal w.r.t. Q'. For any transition function M: Q x S -+ Q let be the set of representing digraphs of logical net isomorphic realizations of M, i.e., M so= {D(A)IA is an isomorphic logical net realization of M.}2.3 Corollary Let M: Q x S -+ Q min 9Ms C{D(AQ)IA is an isomorphic logical net realization of M having operative orbit Q}. Proof: In the case of isomorphic realization A of M: Q x S - Q, the subtransition function of A,M' corresponding to the operative orbit Q' is isomorphic to M. Thus we may identify M' with M and Q' with Q. (Note too that in this case M minimally divides M' so the two sets of reduced digraphs in Theorem 2.2 coincide.) The corollary now follows by restricting the statement of Theorem 2.2 to 15M '

-77 -FIGURE 2.1 The logical net A with delay set D = $c,3,yt is specified by the switches Z, ZS, Z given by Y S Z c a S Z S| Z O0 0 -0-0 0 — 0 0 0 0 1 1 1 -0 1 1- 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 01 1 0 O 1 1 1 0 1 1 1 0 0 0 1 1 1 0 0 1 01 1 1 1 0 1 1 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 O 1 1 11 0 1 0 1 0 where a blank indicates all possible values are to be substituted in this position. This is the logical net (without outputs) irZ y y

-78 -The graph D(A) representing A is then Y Note that D(A) does not contain any input lines. The state graph representing the transition function M of A is 1 1 0~i 0 1y01 O1 1 0 0 0 1 0 oY o B ~ 0 1o

-79 -The set of states Q' = {100, 101, 110, 111} forms an orbit in the state graph. Restricting M to Q' there is only one determining set for each co-ordinate: detQ, () = X, detQ, () = 8 detQ, () = {8,y} These determining sets can be found directly from the given maps Za, ZV, Z. When in Q', a is constant at 1. With a restricted to 1, Z8 is seen to depend on, and only on, itself and Z on {8,Y}. There is only one input selection —>D = {, {}, {,y}}. The reduced digraph representing A, D(AIQ') is then where since a is constant it does not appear. The reduced logical net of A restricted to Q', A, is then specified by the switches Z' which agree with the switches Z when restricted to 1 1 Q' namely, 8 S Z y S Z 0 0 0 000 0 0 1 1 0 0 1 O 1 0 1 0 1 0 O 1 1 0 0 1 1 1 1 00 0 1 0 1 O 1 1 0 1 1 1 1 O In this case there are no "don't care" conditions to be satisfied.

-80 -AQ, is the logical net: Finally, A, has a subtransition function (the transition function itself in this case) isomorphic to MjQ', namely 1 1 O 1 Y and D(AQ,) = D(AQQ') a subgraph of D(A).

CHAPTER III BURKS-WANG CONJECTURE ON STRONG COMPONENT SIZE Jn this chapter attention is turned to the strong components of the digraphs representing logical nets. These strong components were called cycles by Burks and Wang (1957). The degree of a cycle was defined as the number of points (hence delays) contained in it. A net was said to be of degree d if it had at least one cycle of degree d and no cycles of higher degree. Burks and Wang made the conjecture: For any degree d, there is some transformation not realized by any net of degree d. In our current terminology "transformation" means transition function and the realization in question is isomorphic realization. The conjecture is true and moreover turns out to hold even when the word "realized" is replaced by "simulated" in its statement. Thus, as we shall show, there is no upper bound on the highest degree needed so that all nets of this or lower degree can simulate any finite transition function. That this is the case despite the fact of arbitrary memory expansion and slowing of computation rate is indeed surprising; all the more so in view of the difficulty of establishing like results for other measures of feedback complexity. The result follows quite directly from the decomposition theorems of Krohn and Rhodes (1965). I feel however that its importance justifies a direct proof. Such a proof has two motivations: 1) to focus attention of just those elements relevant to conjecture, by-passing thereby the apparatus necessary to establish the decomposition theorems, and 2) to demonstrate the applicability of algebraic methods to problems -81 -

-82 -posed in logical net form. We begin by showing how a logical net A can be considered to be a series-parallel composition of component nets represented by the strong components of D(A). (See Section 1.2 for the definitionof series parallel composition.) Let A be any logical net and D(A) its representing digraph. The condensation of D(A) is acyclic and therefore has an ascending level assignment, which we take to be the longest path length level assignment. (See Section 1.10.) For any digraph D with level assignment let L be the subset of points of D having level m. Clearly, {LmID < m < m} (where m is the highest level) is a partition of D. We shall employ the following 3.1 Lemma Let D be an acyclic digraph with level assigned according the longest path length assignment. For any level m > O0 a) there are no lines joining any two points in Lm, b) no point in Lm has any incoming lines from points in Lm,, m' > m + 1, and c) every point in Lm+l has at least one incoming line from some point in L. m Proof: a) and b) follow directly from the definition of level assignment. To prove c) let L be the longest path from the transmitters to a point P in L We show that point Q immediately preceding P in L has level m. Since Q is in L there is a path of length at least m from the

-83 -transmitters to Q. The level of Q is then at least m. Suppose it exceeds m. Then there is a path from the transmitters to P (running through Q) with length exceeding m + 1. This contradicts the fact that the level of P is m+l and thus Q has exactly level m. Returning to the logical net A and its digraph D(A) let D' be any subset of D(A). The subcomposition associated with D' is the logical net having as input, the input of A together with the wires associated with lines in D(A)coming into D' from points not in D'; aside from this relabelling of its input the operation of the subcomposition is unchanged. More formally, A(D') the logical net associated with D' is a composition (a D' A )' where the switch Z' preceeding delay a E D' is defined by Z': HeD' D Q x (H FD-D Q x S) + Q where Z'(qD,, (qD_D, S)) Z (q q Z DI'(q D- s)) = Za, DI- D-Dq )'s) for all q = (qD" qD-D') EaD a Now let S1, S2,..., Sn be the strong components of D(A) and A(S1), A(S2),..., A(Sn) the associated logical nets. Let Lm be the strong components having level m in the condensation of D(A). Lemma 3.1 tells us that for each m, A = (II A(S ))' m S.zL i 1 m is a parallel composition of the A(Si), Si e Lm and A is a series composition of the A. Thus we have proved the m 3.2 Theorem A logical net A is a series parallel composition over the set of logical

-84 -nets associated with the strong components of D(A). This fact justifies the consideration of arbitrary series parallel compositions. We begin by considering a series parallel composition A, of arbitrary finite machines A, Ad. Let M: Q~ x Q X S + Qa x Q8 be the transition function of A and Ma: a X S - Qa, M: Q x (Q x S) - Qs its components. (We note that when A,A are in parallel M a: Q x S + Q~a) Except for possibly a relabelling of the input alphabet these are the transition functions of Aa and AS respectively. More generally, we need not make any distinction between the transition function of A and the 1 projection M of M the transition function of A,a series parallel comai position over a set {ai}. 3.3 Theorem Let A be a series parallel composition of finite machines A,A8 with transition functions M: Q x Q X S + Qa x QX, M: Qa x S + QS, Ms: QB x (Q x S) - QB respectively. Let M contain a cycle of x E S* with x-period m. Let the homomorphic projection of the cycle of x on Ma have x-period k. Then there is a string cycle in MS with string period m/k. Proof: We first justify the assumptions made in the statement of the theorems. Corollary 1.9 tells us that there is a homomorphism from M to a subtransition function of M (in this case M itself since M is the full a a transition function of A). Thus there is indeed a homomorphic image of the cycle of x lying in M. By Corollary 1.11 the x-period of this homomorphic image, k divides m. Say m = nk. Let the sequence Z1, Z2,..., Zm(x) be the initial substrings of x

-85 -where Z1 is the initial symbol of xm and Z = x.m 1 m m~(x) Let the cycle of x in M be qZ1, qZ2,..., qZm(x) = q. The homomorphic image in M2 is then q'Z1, q'Z2,'... q'Zkk(x): q, where q' is the image of q under the homomorphism and Z x. kk(x) We have seen in Section 1.2 that a homomorphism h: Q - Q1 may be identified with a partition 11h on Q. In fact since here h is the projection of Q1 x Q2 on Q1,h = H. Since Q = Q1 x Q2 we must have lla n l = O and every state q ~ Q has the form q = ([[q], [q]3) Since qx - k we have qZi _ j Since qx q we have qZ.i qZjk(x)+i for all 0 < j < n and 0 < i < kQ(x). We denote [i] = [qZi]. Also since the Zi are initial substrings of i k x we have = xjkz Zjkk(x)+i i for all 0 < j < n, 0 < i < kZ(x). The sequence Z2' bq km(x)-l' k(x) x+l' then becomes ([1], [qZ11]), ([2]cz, [qZ2]1 )... ([kZ(x)-l], [Z _l])([O], [qxk] ), ([1], qxkz 1),...

-86 -Let Z. = a a a a2 0 < i < kQ(x). Using the notation ql (q q 1 1 2 q for M2(ql, (q,s)) = q2 we obtain the following transition sequence in M2 starting at [q]a [qZk (x) - ([k(x) l],a k,(X)) [qxk] ([]a a kz This sequence is a cycle in M2 of the string y = ([0], al) ([1], a2)... ([kQ(x)-l], ak(x)) in (q2 x S2) (or better (Q| x S) * Now qx jk 0 < j n are all distinct states and recalling that qxjk ([x ] [qxjk] ) (i.e., these states all have the same a component) it must be that [qxjk] 0 < j ~ n are all distinct. Thus the existence of the subsequence of the y-cycle [qxk] [qxZk,, [qx) -1 = [qxm] [q having n distinct states proves that there is a y-cycle of y-period n =m/k in M2. Note that Z(y) = k[(x) and T = n implies T = nkk(x) mi(x) which agrees with the period of the x-cycle in M. Also note that if AtA are in parallel then y reduces to Y = al a2 a k( anT = x

-87 -The basic theorem enabling us to prove the Burks-Wang extended conjecture can be stated: 3.4 Theorem Let M': Q' x S' -+ Q' contain a cycle of x s S* with x-period p, a prime number. Assume that M' can be simulated by a series parallel composition of Aa,A with transition functions M: Q x S - Q, Mu: QB X (Qa x S) -+ QB, respectively. Then at least one of M,M contains a string cycle of string period a non-zero multiple of p. Proof: Let M: Q x Q x S Qa Q Q be the transition function of A the series parallel composition of A,A Since M' can be simulated by A it must be that M' divides a subtransition function of M. Given the x-cycle in M' we have, by Theorem 1.10 that there is a string cycle in this subtransition function and hence in M itself of string period m a multiple of p, m = np, n > 0. By Theorem 3.3, MI has a projection of this cycle with string period k > 1 and My has a string cycle with string period m/k. But since p is a prime either k divides n, in which case M has a string cycle of period a non-zero multiple of p, or k is a non-zero multiple of p, in which case M has a string cycle a non-zero multiple of p. 3.5 Corollary Let M': Q' x S' - Q' contain a cycle of x C S* x-period p a prime number. Assume that M' can be simulated by a series parallel composition, A of A, A,..., A with transition functions 1 2 an M: Q x.i Q x S + Q ax. a. j<1 a. Q c.' 1 1 3 1

-88 -Then at least one of M. has a string cycle with string period a non-zero 1 multiple of p. Proof: The proof proceeds by induction. The series parallel composition A may be regarded as a series parallel composition of A and (Hil A ) — 1 a series parallel composition of the Aa, i>l. Applying Theorem 3.4 to this situation, the induction may now proceed. For series parallel composition A of A, A,..., A we define i 2 n size (A) to be the number of states in the largest component machine i.e., size (A) = maxlQ |. where Q is the state set of A. 1 1 3.6 Corollary For any integer s, there is a finite transition function which cannot be simulated by a series-parallel composition A, with size (A) < s. Proof: Consider the set of primes which as is known has no greatest member. For any prime p, there is a mod p-counter, namely a machine which counts occurances of a symbol a, say, in an input string modulo p. The transition function of this machine has an a-cycle of a-period p. By Corollary 3.5 any series parallel composition which can simulate this transition function must have at least one component A whose transition function has a string cycle of string period a non-zero multiple of p. But this means that IQ | > p since there are at least p distinct states in such a cycle. Thus size (A) _ p for any series parallel composition which can simulate a

-89 -mod p counter. For any integer s, we can choose a prime p > s and so for each s there is a finite transition function which cannot be simulated by a series parallel composition A with size (A) < s. We note that in particular, for each integer s, there is a finite transition function which cannot be isomorphically realized by any series parallel composition A with size (A) < s. (Thus true because any isomorphic realization is in particular a simulation.) We have seen in Section 3.2 that a logical net A is a series parallel composition of the logical nets associated with the strong components of D(A). The degree of a logical net is the number of delays in the largest component i.e., degree (A) = size D(A). A net of degree d has at least one component having 2d states and no strong component having 2 states where i > 0. Thus size (A) < 2degree (A). The strengthened version of the BurksWang conjecture follows: 3.7 Corollary For every integer d, there is a transition function which cannot be simulated by any logical net of degree d.

CHAPTER IV HOLLAND'S CONJECTURE ON FEEDBACK INDEGREE 4.1. Proof of Conjecture on Feedback Indegree XYaving developed the necessary apparatus in Chapters I and II we are in a position to establish the conjecture of Holland (1956): For every integer r, there is a transition function which cannot be isomorphically realized by any logical net whose representing digraph has maximum feedback indegree r. Let us first rephrase this statement in the terminology previously introduced. For any transition function M: Q x S + Q recall that iso GM = {D(A) A is an isomorphic logical net realization of M}. Since isomorphic realization is a special case of simulation, iso C I M cRecalling that max FI(D) is the maximum feedback indegree of a digraph D define minmax FI(W M ) = min max FI(D). D iso Thus if minmax FI( 5Mq ) = r then in every digraph D(A) representing an isomorphic logical net realization, A of M, there is a point having feedback indegree r. The conjecture on unbounded feedback indegree for isomorphic realizatio -90 -

-91 -can now be stated: 4.1 Theorem For every integer r, there is a transition function, M such that minmax FI( 'AM ) > r. In order to prove this theorem we shall first establish some helping lemmas. 4.2 Lemma Let A be a logical net and M: Q x S - Q a subtransition function of A's transition function. Suppose there is an a c D(A) such that every partition predicting H (w.r.t. Q) has at least k blocks. Then the indegree of a, lI >log2 k. Proof: Assume to the contrary that I C D(A) (the input set of a) has cardinality k < log2 k. Then Z the switch preceeding delay a in the net A has as its arguments {Q ala I }. Since M - Z (Chapter II) we see that for all q, q' E Q, s ~ S q - q' implies M (q,s) = M (q',s) I a hence that RI predicts H (w.r.t. Q). (See Section 1.8.) Since a 8'I it has at most 22 blocks. But 2 < log2 k implies 22 < k, a contradiction. We conclude that [I > log2 k. We say that a transition function, M:Q x S + Q is k-ply-transitive

-92 -if for every pair of ordered k-tuples on Q, (ql, q2. qk) (ql, q, v, qk) there is an s ~ S such that M(ql, s) = ql, M(q2, s) = q(q ) 2s 2k' S) k qk If M is k-ply transitive it is clearly k'-ply transitive for k' < k. Recall that a non-trivial prediction pair is a pair of partitions (H,pj such that I predicts p and H A 0, p A I. A transition function M: Q x S - Q is said to have maximum dependence if it has no non-trivial prediction pairs. 4.3 Lemma If M: Q x S - Q is doubly transitive it has maximum dependence. Proof: Consider a partition pair (H,p) on Q such that I A 0, P $ I. There are at least two blocks in p, hence two states ql, q2, say which are in different blocks of p. Consider any block in I having at least two states and pick any pair of states ql,q2 in it. By double transitivity there is an s z S mapping ql to q andq2 to ql. Thus ql q2 but M(ql,s) I M(q2,s) so that H does not predict p. Since (H,p) was arbitrary other than the condition H A 0, p A I, there can be no non-trivial prediction pair and so M has maximum dependence. 4.4 Theorem If M:Q x S +- Q has maximum dependence, then minmax FI( I ) > g2 QI M 2 log2 IQI

-93 -Proof: By proposition 1.23, the property P(D) iff max FI(D) > log2 IQI /? iSO is hereditary overg~iM By Theorem 1.25, the induction principle for hereditary properties it is sufficient to establish that max FI(D) > log2 [Q] for all D ~ min a M in order to establish max FI(D) > log2 IQI iso for all D ~ q Ms. By Corollary 2.3 min i C {D(AQ)]A is an isomorphic logical net realization of M having operative orbit Q} and thus we need only establish that max FI(D) > log2 IQI for all D in the latter set to prove the theorem. Let AQ be any reduced logical net restricted to Q which has subtransition function M:Q x S -+ Q (and hence can isomorphically realize M). Now since D(AQ) is reduced every a C D(AQ) is such that I $ I. Since M has maximum dependence any partition predicting IH must have at least IQI blocks (i.e. if p predicts na then p = 0 w.r.t. Q). By Lemma 4.2, II log2 IQI and thus min I(D(AQ ) > log2 QI. By proposition 1.16 max FI(D(AQ)) > min I(D(AQ)) > log2 IQI

-94 -and thus the Theorem is proved. We can now provide the proof of Theorem 4.1. Proof: Consider the symmetric group Sn acting on n letters. It is doubly transitive (in fact it is n-l ply transitive). Consider the action <S, Sn, Qn>' that is the transition function M Qn x S +n n n where [Qn] = n. Since Mn is doubly transitive it has maximum dependence by Lemma 4.3. By Theorem 4.4., minmax FI( 5M ) > log2 I Qn = log2 n Thus for every integer r, there a transition function M such that 2 +1 2r+1 4.2 Primitivity and Maximum Dependence The proof of Theorem 4.1 made use of the property of maximum dependence for transition functions. Double transitivity ensures maximum dependence but as we shall show, it is not a necessary condition. In fact for actions <G, G, Q> (i.e., classical G-actions) primitivity is a necessary and sufficient condition for maximum dependence. This extends a result of Hartmanis and Stearns (1966) who showed that for a group accumulator, i.e., a <G, G, G> action, and the existence of non-trivial SP partitions is equivalent to the existence of non-trivial (l,p) prediction

-95 -pairs. We provide a proof of the primitivity —maximum dependence equivalence in this section which makes explicit use of group theoretic properties. In Chapter VI an extended version is proved but the proof relies on machinery not yet developed up to this point in the presentation. Though double transitivity is not necessary in the isomorphic realization context, it apparently is required in extending these results to nonisomorphic realization. Before proceeding, the following fact may be of interest. 4.5 Proposition Let M: Q x S -+ Q have maximum dependence. Then for every pair ql' q2 s Q it is not the case that for every s s S, {q1,q2} is mapped either into itself or completely outside itself. Proof: If this is the case then n = {[ql,q2], [q3]'.., [qn]} and P = {[ql,q2], [Q - {qlq2} ]} form a non-trivial prediction pair. We may also observe that 4.6 Proposition For any M: Q x S -+ Q if S contains an identity map 1 (i.e., M(q,l) = q for all q s Q) then for a prediction pair (l,p), I < p. Proof: ql q2 implies M (ql,) M(q2,l) implies ql - q2 for all ql,q2 C Q. p

-96 -In this section we consider <G, G, Q> action i.e., a transition function M: Q x G - Q whose semigroup is G is where G is a group. This is a classical G action on Q. We denote by Gi, the stabilizer subgroup of qi ~ Q, i.e., Gi. = {gjg C G and qig = qi}. G acts primitively on Q if <G, G, Q> has no non-trivial SP partitions. Primitive action divides into two cases according to the following proposition (Wielandt, Proposition 8.7, Page 17): 4.6 Lemma If G is primitive on Q and ql,q2 are different points of Q then G = <G1,G2> or G is regular of prime degree. (Here G is semiregular it Gi = 1 for all qi C Q and regular if it is semiregular and transitive. The degree refers to the cardinality of Q.) We note that for a regular group the order and degree are equal (Proposition 4.2, Page 9, Welandt). Thus a regular group of prime degree has prime order, but this implies that it must be a prime cyclic group (for if it were generated by more than one element it would have a subgroup whose order would divide its order). We thus have Case 1. G is a prime cyclic group. 4.7.Lemma Consider any pair ql,oi C Q. If there is an a E G such that q2 = qla then for any prediction pair (l,Q' if ql - q2 then the cycle ql a q2 + q3... + ql is in a block of p [where qi + qj means qia = qj].

-97 -Proof: Since the identity exists in G we have ql E q2 by Proposition 4.6. a a a If q2 ql', we are done. Otherwise q2 + q3 ~ ql and since ql + q2 we must have q2 q3. Now if q3 + ql then we are done, otherwise a 2 G and q2 9 q4 a _ 9q a q3 so q 43 E Continuing in this way, find that ql E q2 E 3 3 p 4P P P as claimed. 4.8 Proposition Let G be a prime cyclic group acting transitively on Q. Then <G, G, Q> has maximum dependence. Proof: Let G be generated by a E G, and (H,p) a prediction pair. For any am m pair ql, q2 6 Q we have ql + q2 for some a. If q q2 then by Lemma 4.7 m m a m the cycle ql a q2 a q3... + ql is in a block of p. But since G is prime, am generates G and by transitivity this cycle is all of Q. So p = I. Thus if H Z 0 then p = I and M has maximum dependence. Case 2. G is generated by Gi, G. for qi, qj s Q. 4.9 Proposition Let G be primitive but not a regular group of prime degree. Then <G, G, Q> has maximum dependence. Proof: For any (H,p) prediction pair let ql - q2. Since G = <G1, G2> every element is of the form 1 2 1 2 g = gl g2 g3 g4 ' where gi s.. We can thus assign an integer 9(g) which the smallest length J

-98 -of g expressed in terms of the generators, where the identity 1, has Q(1) = 0. Let SQ = {gjQ(g) = 9} and q St = {M(q,g) lg a Sk}. We claim for every Z, that both ql SV, q2 S are included in the block of p containing ql,q2. 0o If this is so then all of Q is in this block of p since G = Uz=0 S9 and 00 acts transitively on Q, i.e., Q = UO=0 ql SR. (So (H,p) must be trivial and the proposition is proved.) Certainly this is true for Z= 0. Since then SO = 1 and {q1, q2} = qlSOUq2S0 which must be in a block of p. Now by induction assume that for 9 < k, both ql SV, q2 Sk are in this same block of p. Consider any element g C Sk+l. It is of the form either a) g = gl g or b) g= g2 g where gi Gi, i = 1,2 and g, g ~ Sk In case (a), ql g1 g = ql g recalling that gl fixed ql. But ql g e ql Sk which by hypothesis is included in the required p block. Also ql - q2 implies ql g E q2 g so P that q2 g is also in the required p block. A similar argument applies in case (b). We have thus that both ql Sk+l and q2 Sk+l are included in the required p block. Combining these results we have

-99 -4.10 Theorem Let M = <G, G, Q> where G is a group. Then G acts primitively if and only if M has maximum dependence. Proof: The only if part follows from Lemma 4.6, Proposition 4.8 and Proposition 4.9. The converse holds because if G does not act primitively it has a non-trivial SP partition H and M certainly has a non-trivial prediction pair (11,1).

CHAPTER V FEEDBACK COMPLEXITY FOR HOMOMORPHIC REALIZATIONS go far we have shown that no limit can be placed on the complexity, as measured by feedback indegree, that logical nets must have in order to isomorphically realize all transition functions. A similar result, this time for complexity measured by strong component size, was shown to hold even when memory expansion and input encoding are allowed. A natural question to ask is whether the feedback indegree results carry over into the non-isomorphic context as well. The remaining chapters are devoted to various aspects of this question. The present chapter seeks to extend the results of Chapter IV to the case of homomorphic realization while Chapter VII deals with a restricted case of input encoding. Let om be the set of digraphs representing logical nets which homomorphically realize a given transition function M, i.e., hom = {D(A) [A is a logical net homomorphically realizing M}. Clearly iso c ghom C a. M - M M Let minmax FI( 7hom) min max FI(D(A)) M D(A)s Eom The reader may have already guessed that we have not been able to establish that for every integer k, there is a transition function M such that minmax FI(G hom) > k. -100 -

-101 -We shall show however that (1) this statement holds for a restricted class of homomorphic realizations (strictly larger than the isomorphic realizations), (2) there are transition functions, M such that minmax FI( hom) > 2. 5.1 Proof that minmax FI( h m ) > 2. We begin with the consideration of (2). For any digraph D a strong component, M of D is simple if every point in S has feedback indegree 1. A digraph is simple if all its strong components are simple. Thus a simple digraph consists of cycles (in the graph theoretic sense) connected together in a "series parallel" fashion. We shall essentially be extending a result of Holland (1956): 5.1 Theorem (Holland) Let M: Q x S -+ Q be isomorphically realized by a logical net A whose representing digraph D(A) is simple. For every x ~ S* the period of any cycle of x in M divides 2 l.c.m(t(x),b) where a,b are parameters characteristic of A. Equivalently, the x-period of any x-cycle must divide 2a l.c.m(Q(x),b) 2a b (x) g.c.d(,(x),b) (k.c.m = least common multiple, g.c.d = greatest common divisor.) Using Corollary 1.11 we extend this result to homomorphic realization: 5.2 Theorem Let M:Q x S + Q be homomorphically realized by a logical net A whose representing digraph D(A) is simple. For every x E S* the x-period of any x-cycle in M must divide 2a b g. c.d(k (xj,b)'

-102 -Proof: Since A is finite, by Corollary 1.11, given an x-cycle in M there is an x-cycle in the transition function M', of A. Also the x-period of the x-cycle in M divides the x-period of the x-cycle in M' which in turn divides 2 g.c.d ((x),b) by Theorem 5.1. g.c.d (ktx),b) We employ the same trick used by Holland to show that modulo 3 counters for example can not be isomorphically realized by logical nets whose representing digraphs are simple. 5.3 Corollary Let M: Q x S + Q, ISI 22, be such that there exists q C Q and s 6 S such that for all x E S*,M(q,x) = q -if, and only if, the number of occurrences of s in x is a non-zero multiple of j, a positive integer, (M is a modulo j counter). If M is homomorphically realizable by a logical net whose representing digraph is simple, j is a power of 2. Proof: 1 Pick x = sy where y 6 S* contains no occurences of s and Z(x) is a non-zero multiple of b (in Theorem 5.2). Then there is an x-cycle in M with x-period j. But by Theorem 5.2 this x-period must divide 2a -.b = 2a g.c.d (9(x),b) hence j divides 2a 5.4 Corollary There are transition functions, M which cannot be homomorphically realized by any logical net whose representing digraph is simple, i.e., minmax FI ( hom) > 2 M)>2

-103 -Proof: The modulo three counter is an example of such a finite transition function. Let us now show that this method of proof breaks down when input encoding is allowed. Let A be a logical net with transition function M': Q' x S' + Q' which simulates M: Q x S + Q. Let g: S + S'* be the input encoding. According to Theorem 1.10, M' contains a cycle of j(x) with g(x)-period a non-zero multiple of the x-period of a cycle of x in M. Let x = sy where y contains no occurrences of s. Then g(x) = g(y)g(s) where g(y) contains no occurrences of g(s); similarly xj contains j occurrences of s so that g(xj) = [g(x)]j contains j occurrences of g(s). If M has a cycle of x with x-period j then M' has a cycle of g(x) with g(x)-period j for some k > 0. Now if D(A) is simple j divides 2a k.c.m(b,P(g(x))) (g(x)) as in Theorem 5.1. In order to carry out the proof of Corollary 5.3, we must be able to find an x ~ S* such that j(g(x)) = pb for some positive integer p. This however is not always possible. Let S = {s,t}. Then k(g(x)) = Z(g(s)) + qZ(g(t)) where q is the number of occurrences of t in x. We require that Q(g(s)) + qQ(g(t)) = pb, hence that there exist integers p,q such that pb - qQ(g(t)) = Q(g(s)) But from number theory this equation has an integer solution in p,q just 1That is, there exists g for which this is true.

-104 -in case g.c.d (b,Q(g(t)))divides Q(g(s)). To prove a theorem extending Theorem 5.2, we would have to assure that for every integer b which characterizes a logical net A with D(A) simple, there is an encoding g, such that a condition similar to the requirement g.c.d (b,k(g(t)))divides ~(g(s)) is satisfied, an unlikely event. In fact as we shall presently show, the modulo 3 counter —the test automaton here —can be simulated by a logical net whose representing graph is simple. 5.2 Expansion Limited Realizations In this section we shall present a subclass of!2hom for which a IM bound on the feedback indegree required to realize all transition functions is shown not to exist. Let A = a(CD Aa)' be a logical net with transition function M1: Q1 x S ~ Q1' Let A homomorphically realize a transition function M: Q x S + Q. Let Q' C Q1 be the operative orbit and MI the associated subtransition function. Thus there is a homomorphism h: Q' + Q from MI onto M. According to the discussion of Section 1.8, 11h e PQ' is a partition on Q' having SP and furthermore MllNh is isomorphic to M. In order to say anything about the feedback requirements on A in realizing M we shall have to be able to relate 1h and PQ,, the set of partitions on Q' associated with subsets of the co-ordinate set, D. Allowing arbitrary memory expansion, i.e., allowing M1 and PQ, to be arbitrary (other than the requirement that MIh M and {QIla E DI is a co-ordinatization of Q') there does not seem to be much that can be said about the nh' PQ relation. There is however an interesting special case with which we can begin —the so called expansion limited case. A collection of sets {SilSi C Q} is said to be a cover (or set system) of a non-empty set Q if

-105 -1) US. = Q 2) S C S. implies S. = S. for all S.,S. 1i - j 1 J 1 J Covers were introduced by Hartmanis and Stearns (1966) and employed by Zeiger to obtain series parallel decompositions which agree with the Krohn Rhodes decomposition theory results (Arbib, 1968). 1 2 n Let p E PQ, be any partition on Q' with blocks B B, B,..., B Under what conditions do the sets h(B ), h(B ),..., h(B ) form a cover of Q? Clearly n U B Q i=l p since h is onto Q. Let us identify Q with Hh and take h to map Q' onto nh' i.e., h(q) = Bh(q). Then i k kki h(Bi) { k B B $ B } p = Bh k i j where Bh are the blocks of Hh' Condition (2) then reads, for Bi Bj h(B ) ~ h(Bj) P P and h(Bj) h (Bi ) p p k k iff there are blocks Bh I Bh in Ih such that (Bh n Bi $ ~ and Bhl n Bj = P P and (k2 Bj h B nB and B nB. D h p

-106 -Now if p is a non-trivial binary partition on Q' the last statement k 1 k2 2 1 2 is equivalent to Bh C B and Bh C B where p = {B1 B2} ~~~~~i k Let us say then that a block Bi of p is labelled by a block B of P h k i 1h(P, 11h E PQJ) if Bh C B A binary partition p is labelled by a partih - _.. p................. tion Ih if each block of p is labelled by some block of hI In the 1 k following figure, Bis labelled by B but is not labelled by any Bh. P h Ph P 01 Define asusu )L* 1 2 B B P P Thus a binary partition p is labelled by a partition llh(p, 11h ~ PQ') just in case {h(B ), h(B )} is a cover for Q where h: Q' - Q (onto). P P Going back to the logical net A = ( D A )'(which homomorphically realizes M with operative orbit Q') we say that A is expansion limited if every IIE P~P (a c D) is labelled by 1h' Define, as usual gim {D(A) A is a logical net which is an expansion limited realization of M}. Thus iso c Zlim _ hom M M _ M_. (That! isoC lim follows from the fact that h = 0 in isomorphic realizations and 0 labels every partition.) We can now state

-107 -5.5 Theorem For every integer k, there exists a transition function M such that minmax FI(i ex im) s k. That is, for every integer k, there exists M such that M cannot be realized by any expansion limited realization whose maximum feedback indegree is less than k. Proof: We require the following Lemma 5.6. Having established Lemma 5.6, the proof of Theorem 5.5 proceeds in almost word for word manner with that of Theorem 4.1 and will thus be omitted. 5.6 Lemma Let M: Q x S + Q be doubly transitive and h: Q' + Q (onto) a homomorpism of M' onto M. Let p be a binary partition ~ I on Q' labelled by 1h. Then any partition which can predict p (w.r.t. MI) must have at least IQI blocks. Proof: Suppose that n predicts p. Let q1, q2 ~ Q' be two states in the same block of i. Suppose ql,q2 are in different blocks of Rh say ql F Bh(ql)' q2 c Bh(q2) (Bh(ql) $ Bh(q2)). Noting that M'ITTh M is doubly transitive on Nh we can find an s E S to map Bh(ql) into a block of Rh labelling B1 and Bh(q2) into a different 2 block of 1h labelling B. Thus qlq2 get mapped under s into distinct blocks of p and so I does not predict p —a contradiction. Thus whenever any two states q1,q2 are in the same block of n they must be in the same block

-108 -of h.' Thus n < nh and the number of blocks in II >_ Inhl = |QI. 5.3 Characterization of Arbitrary Homomorphic Realizations Can anything be said along these lines when the realization is not necessarily expansion limited? We have seen that the index of any partition which predicts a partition labelled by Nh can be bounded from below. When the partitions H do not suffer this labelling we must seek the least combinations of the H for which the lower bounding can be accomplished. A measure of these least combinations will serve to parameterize arbitrary homomorphic realizations enabling a lower bound on feedback indegree to be attributed to them. For any partitions p, ~h ~ PQ' we say that ~h distinguishes p if 1) there are two distinct blocks Bi Bj of p which are labelled by p p blocks of Hh, or 2) there is a block B of Nh which is saturated by p, i.e., for every block B of p either B C Bh or B n Bk p p- p = ' Clearly, every H is distinguished by Hh in an expansion limited realization. Also if p refines nh then every block of Hh is saturated by p and thus Hh distinguishes p. Now returning to our realization A of the transition function M. We characterize the realization as follows: Let D' = {ajll I}, the set of nonconstant co-ordinates w.r.t. to operative orbit Q'. Let A = {D1, D2,... } D } be a partition of D'. We say that m is distinguished by Hh if for each block Di of A', HD. is distinguished by Hh. A realization of M will be said to be of kind (n,m) if n = ID' I and m = max I|I over all partitions ' on D' distinguished by Hh. Thus n is the number of nonconstant co-ordinates and m is the largest

-109 -integer k such that a partition of index k on D' is distinguished by h' Note that m always exists since if no non-trivial partition on D' is distinguished by 1h then the trivial partition {D'} is so distinguished since HII = 0 refines nh. In this case of course m = 1. At the-other extreme, for an expansion limited realization m = n since every I, a ~ D' is distinguished by Nh. As usual define _Nom) = O{D(A) IA is a logical net homomorphic realization of M of kind (n,m)} We now have for any (n,m) iso lim C g(n,m) ghom C M - M - M - M - Note that ghom U g (n,m) all (n,m) 5.7 Theorem Let M: Q x S + Q be doubly transitive. Then for any (n,m) minmax FI( (ln'm )) > F(n, m log2|Q). Recall that F(n,m) = minmax FI(D) over all digraphs D having n points and total indegree n. (See Section 1.11.) Proof: Let A as above be a homomorphic realization of M and let. be a partition on D' distinguished by 1h for which Iyl = m. For each 1D. Di a block ofu

-110 -either (1) or (2) of the definition of "distinguishes" holds. We show in either case that Hn| > IQI for any H predicting HD.' Case (1) proceeds precisely as in Lemma 5.6. In case (2) let block Bh of Hh be saturated by HD.' Let ql,q2 be distinct in a block of H. If ql,q2 are in distinct ~~1 ~k k k blocks of nh we can map Bh(ql) into Bh and Bh(q2) into some block Bh Z Bh of Hh with some s E S. Then ql,q2 are mapped into distinct blocks of D. and thus H cannot predict DH — a contradiction. Thus ql,q2 are in the same block of Nh so H refines Hh and iHt1 ~ I|hl = I Q. Proceeding to the reduced digraph D(AQ,) we will find that arriving at each Di ~ A are at least log21QIlines, i.e., the sum of the indegrees of the points in Di is log2 QI. The total indegree is therefore at least |/1 log2 IQI. Thus D(AQ,) is a digraph of kind (n,m log2 |QI). (See Section 1.11.) According to the principle of induction for hereditary proper ties)minmax FI( M(nl'm)) bounded below by minimizing max FI(D(AQ')) over all D(AQ') C But this bound is just F(n,m log2 IQI).

CHAPTER VI INFORMATION PATHS IN LOGICAL NETS an Chapter VII we shall be establishing lower bounds on feedback indegree for a class of simulations. To arrive at these results we shall first have to develop some more apparatus in this chapter. The tools developed are to include means for discussing the effect on the partition pairs of the iterated transition function and the characterization of physical information paths in the representing digraphs of logical nets. As with Chapter I, the reader may wish to turn first to Chapter VII to find motivation for the topics discussed here. 6.1 Partition Pairs for the Iterated Transition Function Given the transition function M: Q x S - Q we define k-th power function Mk: Q x S + Q as follows: M (q,s) = M(q,s) M (q,xs) = M(M (q,x),s) k-l for all q Q, x ~ S, s ~ S. We have then that Mk+ (q,xy) = Mk(M(q,x),y) ~alk co k for all x E S and y ~ S The union U M forms the extended trank=l sition function M: Q x S* + Q. For any partitions lI,p c PQ we say that 11 k-predicts p if for all q,q' ~ Q, x ~ S q q' implies M (q,x) Mk (q',x). -111 -

-112 -The k-prediction kernel, M (p) of p E PQ is defined for all q, q' e Q, x Sk by q = q' iff Mk(qx) - Mk(q',x). Mk (p) P Recall that H 1-predicts p iff H predicts p, and M (p) = M(p) the kernel of p. That H k-predicts p iff H < M k(p) now follows. Whence if,nH' k-predict p then H n f', H UH' also k-predict p. With respect to a set t of partitions on Q( 4 c PQ) we say that H minimally k-predicts p if no partition in? strictly coarser than H can k-predict p, i.e., for all H' E 4 if H' k-predicts p and H' > H then H' = H. If H1,H2 E PQ and H1 i H2 let H1:H2 be the partition on the blocks of H1 such that for all Bn (ql), BH (q2) in H1 1 1 BH (ql) BH (q2) iff ql q2 H1:H2 2 Thus the partition on Q obtained by uniting all equivalent blocks in H1:H2 is just H2. We say that H:H2 k-predicts H3:H if for all B (ql), B (q2) in H1, -.1-2. 31 ' H 1-2 x Sk k k Bn (ql) B l(q2) implies M (B (ql),x) - M (B(q2),x) 1 H 'H2 1 H H3H4 Clearly, H1:H2 k-predicts H3:H4just in case H1 k-predicts H4. We write H1:H1 = H1 in a slight abuse of notation (since Hi'H1 ={{B1 }, {B2 },...} 1r 1 H1 H1 where H1 = {B B, }) Thus is justified since H1:H1 k-predicts H1 H1

-113 -H3:H3 just in case HI k-predicts H3. We shall now present a number of facts concerning k-prediction partitions. We use the notation k ni (min) j to mean that H1i (minimally) k-predicts H.. 6.1 Theorem For M: Q x S + Q and Hi E PQ i = 1, 2, 3, k k+2. i) Hl H2 + 3 implies H1 H n3 k Z k ii) I 1 12 + H3 implies H1 +k 1H min min k M2'12 iii) 1 M (n+ H implies Hi1 M3(H ( 3 3 3 k+Q iv) H2 3 implies I1 2 M (H3) v) n - 2:M (3) implies H 11 min min vi) HI + Mi() + H3 implies Hk+ H min min min

-114 -viii) k MPI3 viii) H1 MV (3) H3 implies H1 M(H) H min min Proof: i) follows directly from the fact that M (q,xy) = M (M (qx) y) for all x ~ S, y e S ii) If ' > 1 E 1 is such that k H2 then by (i) H k+ H3, a contradiction. iii) Suppose RH does not k-predict M (H3). Then there must exist k k k ql' q2 E Q and x e Sk such that ql, q2 and Mk(ql,x) k M (q2,x)' k k 3 1 But M (ql,x).1 M (ql'x) implies that there exists y ~ S such that M (H3) M (Mk(ql,x)Y) M(M(q2,x),y).(Mk q2x H3 Thus there exists xy E Sk+ such that q qand M k+ (qlxy) M M (q2,xy) 3 and H1 does not k+. predict H3 —a contradiction. Thus H1 k-predicts M((Hg). iv) This is a corollary of (iii), noting that H2 CM (Hn3) and 1 k H2 M ( ) iff H1 k M (H3) v) If ' > H1 c ~ is such that H' k+k 13 then by (iv) ' + H2: M (n3) a contradiction. vi) This is a corollary of (v).

-115 -vii) If II' > E11 is such that 11' k 2:M (113) then by (v) 11' k+ 113 a contradiction. viii) This is a corollary of (vii). The result (vii) will be especially useful. The reader may wish to convince himself that nothing stronger can be inferred; that is to say, 1 2 3 min does not in general imply that 1 II2' min For example in the logical net: Bb — 1 y,6 min 1 1 but it is not the case that 11,S 1 for in fact 11 H,6' y,6 Let M = <R,S,Q> be a faithful action. Recall now from Section 1.1 that '<,s> ={x ~ Rg<R S (x) < z} <RS> ~<R,S> -

-116 -where (<R s>(X) is the shortest length of x expressed as a product of elements from the generator set S of R; gen <R,S> = max Z<R s>(x) x~R and <R gen<R,S> R. <RS> Recall too that any subset R' C R induces an action MR, = <<R'>, R',Q> where MR,: Q x R' - Q is given by MR, (q,x) = M(q,x) = qx for all x s RI q ~ Q. We say that a pair of partitions (I,p) (l,p e PQ) is a k-prediction pair for M if for all q, q' ~ Q, X E U St q _ q' implies M(q,x) - M(q',x). II P Thus (H,p) is a k-prediction pair iff H g-predicts p for all 1 < g < k. If (H,p) is 1-prediction pair then Ii predicts p. 6.2 Proposition Let M = <R,S,Q> be a faithful action. If (H,p) is a k-prediction pair for M then (H,p) is a 1-prediction pair for any action MR, = <<R'>,R',Q> where R' C <RS> 6.3 Corollary If (l,p) is a gen <R,S>-prediction pair for M then (L,p) is a 1-prediction pair for MR = <R,R,Q>.

-117 -6.4 Corollary Let R be a monoid. For MR = <R,R,Q> if I k-predicts p for some k > 1 then H predicts p. Conversely if I predicts p then I k-predicts p for any k > 1. Proof: For all q, q' ~ Q q q' implies for all x~ Ulg<k M(q,x) - M(q',x) <<k'MM P k implies for all x E < S> qx - q'x <R, ' p implies for all x ~ R', qx _ q'x p So n predicts p for MR', Corollary 6.3 follows by noting that (gmaxgen R. e<R,S> In Corollary 6.4, we need only show that for a monoid R, H k-predicts p implies (Hl,p) is a k-prediction pair and then apply Proposition 6.2. But this follows directly from the fact that for a monoid R, R=Rk U Rg k<g<k (since 1 c R) and that R C _ for any k > 1. <R,R> We now present as promised a proof of Theorem 4.10 extended to monoid actions. 6.5 Theorem Let R be a monoid. If I predicts p for MR = <R,R,Q> (H,p e PQ) then there is a i' ~ PQ such that n < ', T' has SP and ' predicts p.

-118 -Proof: We establish first that for every p c PQ, M(M(p)) = M(p). From this it follows that M(p) predicts M(p) so M(p) has SP. Consider the diagram 1 1 1 + ~ M(p) + p. min From Theorem 6.1 (vi) we may infer 2 min and from Corollary 6.4, + p. min Now H1 = M(M(p)) implies H1 minimally predicts M(p) over S= PQ so 1 minimally predicts p over PQ i.e., 11 = M(p). Thus M(M(p)) = M(p) and M(p) has SP. Now finally if H predicts p then HI ' M(p) a partition which has SP and predicts p. 6.6 Corollary (c.f. Theorem 4.10) Let R be a monoid. MR = <R,R,Q> has no non-trivial SP partitions iff MR has maximum dependence. Proof: Let IH predict p A I. Then by Theorem 6.5, I ' I< ', where I' predicts p. Since i' has SP, i' = I or H' = 0. If I' = I then I predicts p. But since 1 ~ R by Proposition 4.6, I < p a contradiction. Thus H' = 0 and so i = O and MR has no non-trivial prediction pairs.

-119 -6.2 Characterization of Physical Information Paths Let A = (H As) be a logical net with transition function M:Q x S + Q and subtransition function M': Q' x S -* Q' where Q' C Q is an orbit. Recall (from Lemma 2.1) that from A we can form a reduced logical net AQ, whose points are the nonconstant co-ordinates of the co-ordinatization Q' C 1 D Qa and which has as subtransition function an isomorphic copy of M'. Given the hereditary nature of the feedback indegree we shall be able to restrict our attention to such reduced logical nets. This mainly a matter of convenience, is not really essential to the development. Thus in this section A = (H A ) is a logical net which is reduced with respect to an orbit, Q of its transition function. Thus D(A) = D(AIQ) and every a E D is such that H ~ I (H E PD). We write D = D(A). We now transfer the concepts of k-prediction established for partitions to like concepts of subsets of D. In the following,all partition and prediction relations are defined with respect to a given orbit Q (for which A is reduced). Given a nonempty subset D' C D, a k-determining set for D', M (D') is a subset of D which is a location for M (HD,). This happens just in case H k minimally ~D')~~~~ ~M (D') k-predicts HD' with respect to the set I= {HD,,ID" C Mk(D')}. A weak kkD'~ k M kk determining set for D', M (D') is a location for M (n), where H is any partition in PQ such that I > H >_ HD. This happens just in case HMk(D,) minimally w k-predicts D':H w.r.t d as before. Clearly, a k-determining set is a weak k-determining set but not necessarily conversely. We note that unless {Qjla C D} is an irredundant co-ordinatization of Q, (weak) k-determining sets being locations, need not be unique. For D2 P, D1 C D we say that Dl(weakly)k-determines D if D1 C M( w)(D2) for some (weak) k-determining set Mrw) (D2). D1 (weakly) k-determines D2 is

-120 -denoted by D1 k D2. D1 (weakly) determines D2 if D1 (weakly) k-deter(w) mines D2 for some finite k 2 1. We especially are interested in these relations restricted to points a E D (and we write a for {a} in, for example, k D1 + ). k k Note that if D1 + x then D1 + c. Since I~ll = 2 the only coarser partition is I, so that if Mk (a) is a location for H, I < E < T then = w a a and Mk(a) is a location for. w k We should like to have it the case that a + B implies d(a,B) < k k in the digraph D = D(A). This should be so since a + B means that the present state of delay a takes part in determining the state of delay B k-time steps hence. Physically it is impossible for this to happen if there are more than k delays in the shortest path from a to 6 in the logical net A. We shall see that this is the case if the prediction is with respect to the full transition function of the logical net (i.e., Q = I Q ). From this we can infer the appropriate conditions when Q is redundantly co-ordinatized by {Q } i.e., Q c H Q. We require the following 6.7 Lemma Let a ~ D, D' C D be such that a weakly k-determines D'. Then for every r, 1 < r < k there exists weak r determining set Mr(D') such that a weakly (k-r)-determines Mr(D'). Graphically, there exists Mr(D') such w W that Mr(D') D' implies a k-r Mr(D') w w

-121 -Proof: k k Since ca + D' there is a M (D') containing a for which ~w k Mk H M (D') min where I > H > nHD Choose an Mr(D') for which HMr r. Thus n k k-r D M (n) WM (D') min D) r awa(e ini seH IT Mk(D') M(D) m k mi implies k-r rr Mi.e., (D' ) is a location for M (I) I. But D') =Dacnrdtosiea~ Ww a weak (k-r)-determinin set for M r(D') and thus Mr (D') as asserted. 9 w w w But suppose Mr(H) = I. Then Mr(D') w so II k k-r M(D') w min i.e., Mk(D') is a location for Mk-r=(I) I But H = I and Mk(D) so W ' -- W

-122 -6.8 Theorem For the logical net A and any orbit Q, if the co-ordinatization k Q Cg nHD Qa is irredundant then a + 8 (w.r.t Q) implies d(a,8) < k for all a, 8 E D. Proof: We establish the following statement for all k > 1 by induction: S(k) iff (a + D' implies d(a,D') < k w for all a c D, D' C D). First S(1) states that + D' implies d(a,D')< 1. To show this ~~1 w assume a C D'. Note that every B c D' has a unique determining set, w detQ(8). By the construction of the reduced representing digraph d(y,8) = 1 for every y c detQ(8). Let D" = U detQ(8). Then 11D, predicts nD'* (This follows from the fact that if H1 < M(pl) and H2 < M(P2) then n1 n 2, M(pl) n M(p) < (pP2 ) ) m(p n Now for I > In ' nRD" ED" predicts H (as is readily verified). Since locations are unique the location of M(H) must be within D". Taking H to be the partition for which a belonged to the location of M(H) (as implied in 1 a + D') we see that a ~ D". But then d(a,8) = 1 for some B s D' (namely, w any B for which a s detQ(B)). Thus d(a,D') = min d(a,B) < 1 83D' and S(1) is established. k+l Now assume S(k). Suppose a + D'. By Lemma 6.7 there exists a 1 k Mr weak 1-determining set M (D') (in this case unique) such that a + M(D'). W w w

-123 -~~~~~~~~~1 1 By S(k), d(a,M (D')) < k. This means that there exists a y E M (D') such W W that d(ac,y) < k. Also since y + D', d(y,D') < 1 by S(1). Now d(a,D') < d(a,y) + d(y,D') < k+l. In this way S(k+l) is established and so S(k) holds for all k > 1{. Replacing D' by ~ and noting that O k implies k gives w k a 8 B implies d(a,8) < k. Now for the transition function M of A with state set Q = lHQ~, {aQ} is a Cartesian co-ordinatization of Q and hence is irredundant. (See Section 1.8.) We thus have the following 6.9 Corollary Given the logical net A with state set Q = HaED Qa if c + (w.r.t Q) then d(a,8) < k for all a, 3 ~ D. For any orbit Q C HaQa which is not irredundantly co-ordinatized, Theorem 6.8 need not hold. The following logical net provides an example: Here consider the orbit in which delays,yr are in the same states i.e., Q = {qlprojB(q) = projy(q)}

-124 -Since both 3,y receive the same input from a, Q is indeed an orbit. With respect to Q, = Hy and so Q is redundantly co-ordinatized by {Q }. Now 1 1 1 y + 6 and also 6 (since 1 (11) + 16); d(y,6) = 1 but d(S,6) $ 1, min in fact d(3,6) = o since there is no directed path from 8 to 6. k 1 Thus a + 8 need not imply d(a,3) < k when locations are not unique. We can however show that the following statement is true which will be sufficient for our purposes. 6.10 Theorem Given the logical net A with orbit Q. For every k > 1 and B c D there exists a k-determining set for 3,(w.r.t Q) M (g) such that for all a S Mk(B), d(a,B) < k. Proof: Given B ~ D and k > 1 there exists a k-determining set for B w.r.t Qa (the full state set of A) which we denote by Mn (s). Since H Q is Cartesian, M> Q (8) is unique and since for every a c (8a) k,, by Corollary 6.9, d(a,B) < k. Now let M:11aQ x S + HaQ be the transition function of A and M:Q x S -+ Q be the subtransition function with orbit Q C aQa. For all s c S,if for all q, q' H Qa q q' implies Mn Q (q,s) Mn Q(q',s) at M Qa 1The pairs (a,B) for which a k B and d(a,B) < k may be said to represent physically possible information paths. Only half in jest might we k refer to the pairs (a,B) for which a + B but d(a,B) > k as psi pairs, where psi refers to the phenomena associated with ESP (extra sensory perception). If the world were redundantly co-ordinatized it would be possible for one event to predict another with no apparent causal connection

-125 -then for all q, q' e Q q q' implies M(q,s) _ M(q',s) (since M = Y restricted to Q). Thus k (8) contains a k-determining set for 8 w.r.t Q, say M(). k k As we have shown that for all a E MQ(8), d(a,8) < k, the Theorem is proved. Let a ~ 3 mean that a + S and d(a,B) < k (a can physically kp determine 5). We present the following as an aside. k P k+p It is not in general true that if a + and y then a y. P P P This follows from the remark associated with Theorem 6.1 (vii). If this condition does hold we can say more about the relation between k-prediction and paths in D: 6.11 Proposition In the logical net A with orbit Q, assume that for all k, ~ > 1, a,, y ~ D k Q k+Q o + -+ Y implies a + y. P P P Then k a) a + S implies that there is a path from a to S in D of length Z < k, k b) If there is a path of length k from a to S in D then a +, c) d(a,S) = >_ 1 iff k is the least integer such that a + 5. p Proof: (a) follows from the fact that d(a,B) ~ k. (b) If there is a path of length 1 from a to S then a E detQ (8) by the construction of A and so a + 5. Now assume (b) is true for all paths of p length k. Consider any path of length k+l from a to 5. There is a subpath

-126 -k of length k from a to some point 6 and a line from 6 to S. Thus a k 6 1 k+l and 6 l B so a + B and (b) is established by induction. P p P (c) (<=) Let Q > 1 be the least integer such that a + B. Then d(c,S) < ~. Suppo k d(a,S) = k < Z. Then by (b) a + S. But ~ is the least integer for which p this is true so k > Q, a contradiction. (=>) Assume d(a,S) = Q. If k k + for k < 9 then d(a,S) < k < Z, a contradiction. So a + S for k > Q. P Z P But d(a,S) = Z implies that a + B, so k is the least integer for which 9, P ca -+.

CHAPTER VII FEEDBACK COMPLEXITY FOR A CLASS OF SIMULATIONS Jn this chapter we shall show how the feedback requirements of isomorphic realizations of a transition function M, depend on its semigroup, M. This will lead naturally to the establishment of a lower bound on maximum feedback indegree given a class of machines having the same semigroup. Recalling that such equivalence classes are just those induced by the "mutually 1 simulates" relation (Section 1.6),we shall be able to establish lower bounds on the feedback requirements of an appropriately restricted class of logical net simulations. To see the implications of these results consider for example any faithful <Zp, Zp, Z > action where Zp is the cyclic group of order p, a prime number. Because this action is primitive we know from Theorems 4.10 and 4.4 that any isomorphic realization of MZ = <Z, Zp, Z > by a logical p net must have at least one delay whose feedback comes from at least log2 p delays. As soon as we allow input encoding however this feedback requirement no longer holds. To see this, note that the transition function <Zp, {1}, Zp> (where p p 1 is the generator of Z ) has semigroup Z and therefore <Z, {1}, Z > mutually H-simulates MZ. In fact, in this case, one copy of <Zp, {1}, Z p> p is sufficient to simulate MZ. This may seem surprising since <Zp, {1}, Zp> P is autonomous having in effect no input dependence (<Zp, {1}, Z > has state graph: 1

-128 -where p = 3, for example). Nevertheless, the input encoding g: Z + {l}* given by g(l) = 1 g(2) = 11 g(p-l) = 11...1 (p-1 times) g(O) = 11...1 (p times) together with the identity map h: Z + Z can be used to show that Mz p p P does indeed divide <Zp, {1}, Zp>. (The reader may wish to convince himself that such a simulation can be implemented. (See Section 1.5.)) In contrast to the maximum dependence of MZ, <Zp, {1}, Z > has p very small feedback requirements. In fact <Zp, {1}, Zp > can be isomorphically realized by a logical net with maximum feedback indegree, 1. The case p = 3, for example uses the net: with the orbit {(1,0,0, (0,1,0), (0,0,1)} representing the required 3-cycle. This structure is seen to correspond to the set of prediction pairs {(lii+l )} where II = {{i}, Z -{i}} for i E {0,l,...,p} = Z. It is interesting to note that the set {Hiii C Zp} forms a redundant co-ordinatization

-129 -of Z (Section 1.8). This shows that redundancy in state assignment may be employed to reduce feedback since, as the reader may verify, any other binary co-ordinatization will result in a net with greater feedback requirements. Along the same vein, consider the modulo-p counter <Z, {0,1}, Z >. P p In Chapter 5 we found that such transition functions can be homomorphically realized only by logical nets characterized by a feedback indegree of at least 2 (Corollaries 5.3, 5.4). That this lower bound can be achieved is shown in the example p = 3: 1 0 11 (The same set {Iii C Zp} is used to co-ordinatize Z but now{(Hi n i+lni+) )} are the relevant prediction pairs. Note that the presence of 0, the identity in the input set requires that Ei+1 refine any partition predicting it (Proposition 4.6).) Since the modulo p-counter has semigroup Z it too can be simulated by <Zp, {1}, Zp>. This agrees with the observations made at the end of Section 5.1 concerning the possibility that logical nets with simple representing graphs may be sufficient to simulate all transition functions. We shall return to this possibility in the Conclusion, but in the meantime, let us see what can be said about the situation just outlined.

-130 -7.1 Feedback Indegree Dependent on Semigroup Structure Let M = <R, S, Q> be a faithful action of a finite monoid R. Recall that iso <R S Q.= {D(A) iA is an isomorphic logical net realization of <R,S,Q>}, and that minmax FIRS ) min max FI(D). iso We shall show how a lower bound on minmax FI k<R,S, Q>) can be obtained from knowledge about the monoid R and its generating set S. In fact, we can do more than this. We can also consider cellular space realizations with the two-state delay element as primitive. These may be defined as logical nets with representing graphs which are cellular space digraphs. (See Section 1.13.) Let iso,C.S. I<RSQ> = {D(A) A is an isomorphic cellular space realization of <R,S,Q>}. Clearly, iso,C.S. iso <R,S,Q> - <R,S,Q> The lower bound on feedback indegree for cellular space realizations is greater than that for the general case as we shall see. We define the radius, rad <R,S,Q> as the least integer k, such that whenever I, p s PQ and (l,p) is a non-trivial k-prediction pair of <R,S,Q> then I < H' for some SP partition II' where H' E PQ and H' $ I.

-131 -rad <R,S,Q> always exists as is shown by 7.1 Proposition 1 < rad <R,S,Q> < gen<R,S> Proof: By Corollary 6.3 if (H,p) is a non-trivial gen <R,S>-prediction pair for <R,S,Q> then (H,p) is a non-trivial 1-prediction pair for MR = <R,R,Q>. By Theorem 6.5, there is a H' E PQ such that H < I', H' has SP w.r.t. <R,R,Q> and H' predicts p w.r.t. <R,R,Q>. As in Corollary 6.6, p Z I implies H' $ I. Also by Proposition 1.9i,if I' is an SP partition for <R,R,Q> then H' an SP partition for <R,S,Q>. Thus gen <R,S> is an integer satisfying the condition in the definition of rad <R,S,Q> beginning with "such that...". Since rad <R,S,Q> is the least such integer, the proposition is proved. Note that from Theorem 6.5, rad <R,R,Q> = 1. Define the size, size <R,S,Q> as the index of the coarsest partition H E PQ, H $ I, which has SP w.r.t. <R,S,Q>. We can now provide lower bounds for the feedback indegree in both the general and cellular space cases. The reader may wish to review Section 1.13 at this point. 7.2 Theorem a) minmax FIJ <RSQ) X D (f rad <R,S,Q>, log2 size <R,S,Q>) b) minmax FI(S <RSYQ>)> (fcell space, rad<R,SQ>, log2 size <R,S,Q>). Proof: As in the proof of Theorem 4.4 it suffices to consider a lower bound for max FI(D(AQ)) over all logical nets which are reduced w.r.t. an orbit, Q

-132 -with associated subtransition function <R,S,Q>. Since D(AQ) is reduced, every B c D(AQ) is such that l l # I. For each k, 1 < k < rad <R,S,Q>, Theorem 6.10 assures us that there exists a k-determining set for g, Mk(3) such that for all a E Mk (), d(a,1) < k. For each k, let Mk(@) be such a set and denote the union of these sets by ra1 rad k rad Mrad (i e Mrad U., M (8) Then clearly for all E M Mr., M~ l<k<rad<R, S,Q> d(a,f6) < rad <R,S,Q>. But also it is easy to see that (I rad, 1) is a rad <R,S,Q>-prediction M pair and hence by definition 1 rad ' 11' (where H' $ I has SP). Thus i1 radl > size <R,S,Q> and since nad = it must be that Mrad Mad Mrad a rad IM ad 2log2 size <R,S,Q>. Since for all ~ Ma, d(a,B) < rad <R,S,Q> rad Vp(rad <R,S,Q>) > > log2 size <R,S,Q>. Thus D(AQ) is a finite digraph for which there are integers r = rad <R,S,Q>, n = log2 size <R,S,Q> such that for all S E D(AQ), V (r) 2 n. By Proposition 1.22 we may infer that max FI(D(AQ)) > Xl(fD, rad <R,S,Q>, log2 size R,S,Q ). Since this holds for any reduced digraph AQ we have proved part (a) of the Theorem. Part (b), likewise follows.

-133 -Let us try to picture the situation in Theorem 7.2. Let A be any logical net having <R,S,Q> as a subtransition function. In the representing digraph D(A) pick any point 8 in an initial strong component S(8) (as in Proposition 1.16). Consider the sets M1(W), M2(8),..., which k-determine 8, k = 1, 2,.... Proposition 7.1 assures us that there will exist an integer r = rad <R,S,Q> such that the partition associated with r ad Mk M M() l<k<r has SP. Since S(B) is initial, can get input only from points in S(s) and thus Ma C S(s). In fact for the reduced net AQ it is not difficult to trad S(8) (note that Hs(~) also has SP by Theorem 7.2) show that M = S@B), (note that.I also has SP by Theorem 7.2). Theorem 6.10 then tells that all the points in S(s) are within distance r of 8. Finally, Proposition 1.22 indicates that if n > log21S()I >_ log2 size <R,S,Q> points are packed into a volume with radius r = rad <R,S,Q>, then the indegree of points in S(3) must be at least X(fD,r,n). A (a logical net) mutually H simulates M (a transition function) if A has a subtransition function M' such that M' mutually H simulates M. Recall that if A mutually I-simulates M then the logical net HA consisting of a number of copies of A in parallel can simulate M. Note that the feedback parameters of A and HA are identical. Now let ~R be the union of the sets! over all faithful <R,S,Q> transitive actions <R,S,Q> of a finite monoid R. (Actually our results can be carried over to R, a semigroup, by noting that every finite semigroup contains an idempotent and hence a maximal non-empty submonoid.) Then gIR = {D(A)IA is a logical net having a subtransition function with semigroup (isomorphic to) R}. For any faithful transitive action M = <R,S,Q> define

-134 -R <RS,> S,= {D(A) IA is a logical net which mutually 11-simulates <R,S,Q>}. Clearly, iso R <R,S,Q> - <R,S,Q> - <R,S,Q> Further Theorem 1.7 allows us to state that R R <R,S,Q> Finally let CR be the subset of R consisting of cellular space digraphs. We can now state 7.3 Theorem a) minmax FI( R) > X(fD, maxgen <R>, log2 size <R>) b) minmax FI( R S! ' (fcel space maxgen <R>, log2 size <R>). Where size <R> is the index of the coarsestnon-trivial right congruence on R (and as already defined maxgen <R> = max gen<R,S> over all generating sets S of R). We remark that if R is a group G, then size <G> = IGI/IHI, where H is the largest subgroup C G. This follows from the fact that there is a oneone identification between the right congruences and the subgroups of G. Also from the Krohn-Rhodes Theorem (1965) if G is simple, size (A) > size <G> for any simulation A of a faithful <G,S,Q> action. (See Chapter III.) Proof: iso Noting that R is the union of the sets <RS, Q> and Theorem 7.2, we wish to find non-trivial upper and lower bounds for rad <R,S,Q> and size <R,S,Q> respectively. By Proposition 7.1, rad <R,S,Q> < gen <R,S>. And thus for every <R,S,Q> action, rad <R,S,Q> < maxgen <R>. Also every

-135 -transitive <R,S,Q> action is isomorphic to an action <R,S,R/-> where = is a right congruence on R. Furthermore any partition H on R/E with SP induces a right congruence on R with the same number of blocks. Thus for all <R,S,Q> actions size <R,S,Q> > size <R>. Noting that if n < n' r > r' X(f,r,n) < k(f,r',n') the theorem now follows from Theorem 7.2. 7.2 Computational Slow-up and Feedback Complexity In this section we wish to suggest an approach to a trade-off relation between computational slow-up and feedback complexity. Let us first consider possible measures of computational slow-up. The reader may wish to refer to Section 1.5 at this point.) When M2 is simulated by M (Mi: Qi x S. + Qi' i = 1, 2) with input encoding map g: S2 + S* we can consider the measures: min slow-up (g) = min ~(g(s)) seS2 avg slow-up (g) = Z E (g(s)) max slow-up (g) = max ~(g(s)) seS2 Here min slow-up (g) < avg slow-up (g) < max slow-up (g). Any one of these measure seems reasonable. Now consider M1 = <R,S1,Q>, M2 =<R,S2,Q where S 1 C S2 M mutually I1-simulates M2; let gl2 S1 + S 2S be the 1 2' g12: ~~~l ~~ S~, g21: S2 t S1

-136 -associated input encodings. Since S1 C S2, it is possible to take g12 as the identity map gl2: S1 S2' Then all three measures of gl2 slow-up have the value 1, and thus on any measure, gl2 involves less slow-up than g21 (s e S2 - S1', (g(s)) > 2). On the other hand it is readily shown that rad <R,S2,Q> < rad <R,S1,Q> (and that size <R,S2,Q> = size <R,S1,Q>) hence X2 >_ Xi, where for i = 1, 2 X. = X(fD, rad <R,Si,Q>, log2 size <R,Si,Q>). Supposing that these bounds are attainable we have the expected trade off where increasing computational slow-up is associated with decreasing feedback complexity. 7.3 Cellular Space Realizations Recall that the dimension of a cellular space digraph is directly related to the indegreesof its points. Proposition 1.21 showed that there is a sequence of integer pairs (nl,rl), n2,r2),..., such that X(fcell space' rk, nk) becomes arbitrarily large compared with X(fD, rk, nk) as k becomes large. In fact it was shown that while X(fD, rk, nk) remains bounded above by 1, X(fcell space'rk' nk) increases linearly with k. This suggests the conjecture that there is a sequence of logical nets A1, A2,..., each having maximum feedback indegree bounded above by some constant integer, whose state behavior cannot be mutually H-simulated (in particular isomorphically realized) by any cellular space of fixed dimension i.e., for every dimension, d, there exists an integer i, such that the transition function M. of A. cannot be mutually 1-simulated by any 1 1 cellular space of dimension d. Holland (1968) has shown that von Neumann's cellular spaces are "computation universal" but not "composition universal" (i.e., can simulate

-137 -the behavior of any logical net but only in a manner in which the structure of the net is lost). If our conjecture is true it would lead to the stronger assertion that even if one allows the structure to be lost, these spaces are still not computation unversal if the allowed simulation is limited to mutual I simulation.

CONCLUSIONS AND OPEN PROBLEMS We have considered the simulation classes: isomorphic, expansion limited and homomorphic realization, and mutual H-simulation. For given transitive faithful action <R,S,Q> the sets of representing digraphs associated with these classes can be ordered by inclusion as follows: <R, S,Q> hom <RS3,Q> XR (n,m) <RSQ> <R,S,Q> 1 im <R,S,Q> iso <R,S,Q> Each of these classes can be restricted to the special class of cellular space digraphs. We have shown 1) That for every integer d, there is transition function which cannot be simulated by any logical net of degree d (Corollary 3.7). Equivalently for every d, there exists M such that min size (D) > d Ds.M -138 -

-139 -This also shows that minmax FI( M) > 1. 2) That for every integer k, there exists a transition function M such that minmax FI(g lim) > k M (Theorem 5.5). This entails Theorem 4.1, viz., for every integer k, there exists M such that minmax FI( is) > k. M~ 3) That minmax FI( hom) > 2 M (Theorem 5.4). 4) That minmax FI( ('n, )) > F(n,m log2jQj) M (Theorem 5.7) where M: Q x S + Q is doubly transitive. 5) That minmax FI( is ) > (fD' rad<R,S,Q>, log2 size<R,S,Q>) <R,S,Q> (Theorem 7.2) and 6) That minmax FI(~ R ) > X(fp, maxgen<R>, log2 size <R>) <R,S,Q> (Theorem 7.3).

-140 -The outstanding problem yet remains of deciding whether or not it is the case that for every integer k, there exists a transition function M such that minmax FI( ) > k or even minmax FI( ) > k. M A step toward the solution of this problem was taken in the results of (4) and especially (5) and (6) above. Further progress hinges on obtaining much more knowledge about the relation of semigroups and their generators than we have at present. As we have indicated, size <G> for groups, G is a well-known parameter in group theory. Just the opposite seems to be the case for maxgen <G>. There seems to be no currently available means of characterizing this parameter given any arbitrary group, or even for special but important, classes like the alternating groups. Since size <G> is known for this class, if maxgen <G> were also known the case of mutual H-simulation might be decided, viz., is it the case that for every integer k there exists a semigroup R such that minmax FI(q R) > k. To go from this result to the case of arbitrary simulation would require a study of what happens to the two parameters size <R>, maxgen <R>, when a semigroup R is embedded as a homomorphic image in a larger semigroup. It is known that size <R> cannot decrease but again nothing seems to be known about maxgen <R>. One possible source of information is that every semigroup can be embedded in a semigroup generated by only two elements.

-141 -Closely related to this problem is the trade-off relation between feedback complexity and computational slow-up referred to in Section 7.2. It may be that the approach begun there may be fruitful in elucidating the general time-complexity trade-off problem which is just now coming to be tackled in automata theory. Also within range is the conjecture made in Section 7.3 concerning cellular space realizations.

-142 -EPILOGUE I wish to mention some implications of the results obtained here for wider areas of knowledge. When one examines the structures of living systems, whether at the lowest or highest levels, one is continually impressed by the complexity they display. It has often been remarked that such systems are so interactive as to be indecomposable. Is this interactive complexity necessarily a property of such systems or will the proper methods of examination lay bare a transparent plan of organization? We have established that in the case of strong component size, no set of systems of bounded complexity can simulate every behavior. (Weaker but similar results have been established for feedback indegree.) In other words, it is possible that organisms have become as complex as they are because the behavioral demands of their environments have been such that no simpler structures could possibly have been able to realize the reguired behavior. Structural complexity, we have shown, is a necessary concomitant of certain behavioral requirements (as specified in the properties transition function). Are such behavioral demands made on living systems by their environments? If so, and this is a question open to empirical investigation, then structural complexity is not only not illusory, but inherent in the very process of evolution. One has here the beginnings of a direction in evolution that non-believers in opportunistic evolution have been proposing. Such biologists have always claimed that organisms evolve from simple to complex and that this trend is not merely the result of chance, but an inevitable consequence of fundamental laws, as yet unknown. The catch has been that no measure of complexity

-143 -could be consistently held to fit the known course of evolution and at the same time be independently justified. The rejection of this belief has led to the opposite extreme view in which it is maintained that there is no discernible complexity measure upon which it can be said that evolution goes from simple to complex. I suggest that a resolution of this difficulty might lie in the use of interactive complexity measures as discussed here. These, as we have shown, have both the virtue of entailing the possibility of systems of arbitrary complexity as well as being correlatable to the behavioral demands made of organisms by their environments. Knowing the environment facing an organism at a given time might then enable one to determine the minimum level of complexity required to cope with it and hence predict the subsequent course of evolution. In an entirely different vein, I mentioned in a footnote the striking similarity between the phenomena of extra sensory perception and the existence of non-physical information paths arising from redundantly co-ordinatized orbits. Several questions are raised if this is taken seriously. One being, for example, the question of whether the universe considered as a transition system is redundantly co-ordinatized by our senses and measuring instruments. If so, the existence of psi phenomena may be a naturally concomitant consequence of this fact.

REFERENCES Arbib, M. A. (1968). "Algebraic Theory of Machines, Languages, and Semigroups'.' Academic Press, New York. Burks, A. W., and J. B. Wright (1953). "Theory of Logical Nets". Proceedings of the Instititue for Radio Engineers, 41, 1357-1365. Burks, A. W., and Hao Wang (1957). "The Logic of Automata - Parts I & II". Journal for the Association for Computing Machinery 4, 2, April 1957. Harary, F., R. Z. Norman, & D. Cartwright (1965). "Structural Models". Wiley and Sons, Inc., New York. Hartmanis, J., & R. E. Stearns (1966). "Algebraic Structure Theory of Sequential Machines". Prentice-Hall, Inc., Englewood Cliffs, N. J. Holland, J. H. (1956). "Cycles in Logical Nets". Journal of the Franklin Institute, 270, 3, 202-226. Holland, J. H. (1968). "Hierarchical Descriptions, Universal Spaces and Adaptive Systems". University of. Michigan Technical Report, 08226-4-T. Krohn, K., and J. Rhodes (1965). "Algebraic Theory of Machines I. Prime Decomposition Theorem for Finite Semigroups and Machines". Transactions of the American Mathematical Society, 116, 4, 450-464. McNaughton, R. (1962). "On Nets Made Up of Badly Timed Elements, I". Summer Conference Notes on Parallel Computers, Automata and Adaptive Systems. The University of Michigan. Roosen-Runge, P. H. (1966). "Toward a Theory of Parts and Wholes; An Algebraic Approach". General Systems, XI, 13-18. Somerville, Y. (1929). "Geometry of n-Dimensions". D. Van Nostrand, Princeton. von Neumann, J. (1966). "Theory of Self-Reproducing Automata"(ed by A. W. Burks), University of Illinois Press. Wielandt, H. (1964). "Finite Permutation Groups". Academic Press, New York. -144 -

UNCLASSIF IED Security Classification DOCUMENT CONTROL DATA R&D (Security classification of title, body of abstract and Indexing annotation must be entered when the overall report i classified) 1. ORIGINATING ACTIVITY (Corporate author) Za. REPORT SECURITY C LASSIPICATION LOGIC OF COMPUTERS GROUP Unclassified The University of Michigan lb. GROUP Ann Arbor, Michigan 3. REPORT TITLE ON THE FEEDBACK COMPLEXITY OF AUTOMATA 4. DESCRIPTIVE NOTES (Typo of report ad Inclusive date.) Technical Report. AUTHOR(S) (Lest name. first name, initial) Bernard Phillip Zeigler 6. REPORT DATE 7 TOTAL NO. OF PAGS 7b NO. OF REFS January 1968 160 13 8a. CONTRACT OR GRANT NO. i9. ORIOINATOR' REPORT NUMgER(S) DA-31-124-ARO-D-483 b. PROJECT NO. 08226-6-T ~c~~. SbTM. 0TI[4R REPORT NO() (Any other umbere thaet may be asllned this repor d. 10. A V A IL ABILITY/LIMITAtiON NOTICES Distribution of This Document is Unlimited. II1. SUPPL EMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY U. S. Army Research Office (Durham) Durham, North Carolina 13. ABSTRACT Given a behavior, as embodied in a finite state transition function what is the minimum level of feedback complexity required by a- logical net which can simulate this behavior? For any given level of complexity is there a transition function which cannot be simulated by any logical net characterized by this complexity level? To answer these questions we 1) Consider five main classes of behavior realization: simulation, mutual H-simulation, homomorphic realization, expansion limited realization and isomorphi realization does not and simulation allows computational slow-up which homomorphic realization does not. In mutual H-simulation the semigroup must be preserved whil expansion limited realization corresponds to the use of covers for state splitting. 2) Construct representing digraphs for logical nets and characterize the reduced digraph of a simulation. 3) Select as measures of complexity of a logical net: (a) the size of the largest strong component of its representing digraph and (b) the largest of feedback indegrees of the points in the representing digraph. Here the feedback indeg ee of a point is the number of input lines it receives from points in the same strong component. DD oJAN6 1473 UNCLASSIFIED Security Classification

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

ABSTRACT ON THE FEEDBACK COMPLEXITY OF AUTOMATA by Bernard Phillip Zeigler Given a behavior, as embodied in a finite state transition function what is the minimum level of feedback complexity required by a logical net which can simulate this behavior? For any given level of complexity is there a transition function which cannot be simulated by any logical net characterized by this complexity level? To answer these questions we 1) Consider five main classes of behavior realization: simulation, mutual H-simulation, homomorphic realization, expansion limited realization and isomorphic realization. Roughly homomorphic realization allows memory expansion which isomorphic realization does not and simulation allows computational slow-up which homomorphic realization does not. In mutual H-simulation the semigroup must be preserved while expansion limited realization corresponds to the use of covers for state splitting. 2) Construct representing digraphs for logical nets and characterize the reduced digraph of a simulation. 3) Select as measures of complexity of a logical net: (a) the size of the largest strong component of its representing digraph and (b) the largest of feedback indegrees of the points in the representing digraph. Here the feedback indegree of a point is the number of input lines it receives from points in the same strong component.

We show that for every integer d, there is a transition function which cannot be simulated by any logical net whose representing digraph has no strong components greater than d in size. A similar statement holds for feedback indegree but with simulation restricted to expansion limited (hence also isomorphic) realization. The non-existence of upper bound on the feedback indegree complexity measure for the general simulation case (or even for the homomorphic case) is still undemonstrated. We do show however, that in the homomorphic case a level of at least 2 is required. We show how the minimum level of feedback complexity required to isomomorphically realize a transition function depends on parameters associated with its semigroup. This leads to a characterization of the minimum level of feedback complexity required to mutually H-simulate a transition function. We also show how homomorphic realizations can be classed according to complexity related parameters. In establishing these results some novel mathematical machinery must be developed. We study the partition pair structure of the iterated transition function and characterize the physically possible information paths in a logical net. A curious situation arises where a delay a may determine the state of a delay 8 k-time steps in the future and yet every path from a to B may traverse more than k intermediary delays. The resolution of this difficulty is of independent interest. Finally the related topics of time-complexity trade-off and cellular space realizations are briefly discussed. Also mentioned are some biological implications.

UNIVERSITY OF MICHIGAN 3 9015 03527 6206