THE U N I V E R S I T Y OF M I C HI G AN COLLEGE OF LITERATURE, SCIEPCE, AND THE ARTS Department of Philosophy Technical Report SEQUENCE GENERATORS AND DIGITAL COMPUTERS ( A. W. "Budrks J. B. Wrighlt,.. "'-',1.. ORA Project 03105 under contract withDEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO, Nonr 1224(21) WASHINGTON, D. C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR February 1961

In addition to support received from the Office of Naval Research, this research was supported by the U. S. Army Signal Corps through Project MICHIGAN (Contract No. DA-36-039-SC-52654) and by the U. S. Army Office of Ordnance Research (Contract No. DA-20-018-ORD-16971). Some of the material in this paper was presented at the International Conference on Information Processing, UNESCO, Paris, 15-20 June 1959. An abstract and report of the discussion was published in the Proceedings, UNESCO, Paris, 1960, p 425e This paper grew out of some researches on well-behaved nets (see Sec. 3.1); Hao Wang participated in these early investigations and supplied an essential part of the proof of Lemma 3.3-1 for the case of well-behaved nets. J. Richard Biichi has made many helpful suggestions during the course of our work.

TABLE OF CONTENTS Page LIST OF FIGURES v 1. INTRODUCTION 1 1.1. Sequence Generators 1 1.2. Special Cases of Sequence Generators 6 1.3. Reduced Form Algorithm 12 2. SEQUENCE GENERATORS WITH ONE PROJECTION 19 2.1. Definitions 19 2.2. Subset Sequence Generator Operation 28 2.3. Decision Procedures 34 3. SEQUENCE GENERATIONS WITH TWO PROJECTIONS 39 3.1. Definitions 39 3.2. The Displacement Operator and the i-shift Operation 44 3.3. Time-shift Theorem 54 4. GENERALIZATIONS AND APPLICATIONS 59 4.1. Computation 59 4.2. Formulas and Sequence Generators 66 4.3. Sequence Generators and Conditions 75 4.4. Sequence Generators and Regularity 80 4.5. Infinite-sequence Generators 85 4.6. Probabilistic Sequence Generators 88 BIBLIOGRAPHY 93 DISTRIBUTION LIST 97 __111L

I

LIST OF FIGURES Fig. Page 1. (a) Binary counter; (b) Three-projection sequence generator r = (S, G, R, I, 9, D) associated with the binary counter (a). 2 2. (a) Ill-formed net with behavior F(t) -~ E(t + 1); (b) Sequence generator r = (S, G, R, I, 9) associated with net (a). 3 3. (a) Sequence generator r = (S, G, R); (b) rt, the reduced form of r. 4 4. (a) Semi-deterministic non-solvable sequence generator; (b) Sequence generator neither solvable nor semideterministic. 23 5. (a) Deterministic sequence generator r = (S, G, R, I, 9); (b) Internal state sequence generator r z (S, G, R, I, i, D) correspondin'g to (a). 26 6. The construction of a subset sequence generator. (a) r = (S, G, R, P); (b) r*, the subset sequence generator of r. 29 7. Examples which illustrate Lemma 2.2-1: For any sequence generator r = (S, G, R, P),r* is semi-deterministic. (a) Sequence generator r = (S, G, R, P). r is semi-deterministic. (a')'*, the subset sequence generator of r. F* is semi-deterministic. (b) Sequence generator r = (S, G, R, P). r is not semi-deterministic. (b') y*, the subset sequence generator of r. F* is semi-deterministic. (c) r = (S, G, R, P). r is not semi-deterministic. (c') r*, the subset sequence generator of r. r* is semideterministic. (d) ( = R. P).'r is not semideterministic. (d') r*, the subset sequence generator of r'. r* is semi-deterministic. 31 8. Illustration of Lemma 3.1-4: r is zero-univalent if and only if (S, G, R, P) is semi-deterministic. (a) r = (S, G, R, P, Q). r is zero-univalent and uniquely solvable, but (S,G,RP) is not semi-deterministic. (b) P*t = (S, G, R, P, Q). (S, G, R, P) is deterministic, and a fortiori semi-deterministic. 43 v

LIST OF FIGURES (Continued) Figo Page 9. Illustration of the i-shift construction, for Y = 1. In accordance with Lemma 3.2-1, Ql[(r) i = )] (ri). (a) r = (S, G, R, P, Q); (b) rl (unit-shifted sequence generator of r). 48 10. Illustration of Corollary'3.2-2. [r is 1-univalent] (r, less its last projection, is solvable) (r is uniquely solvable) if and only if [rl is 0-univalent] (rl, less its last projection, is solvable) (rl is uniquely solvable). (a) r = (S, G, R, P, Q). (S, G, R, P) is solvable but not deterministic. r is unit-univalent and uniquely solvable. (b) rl, the unit-shifted sequence generator of r. "l, less its last projection, is solvable, but not deterministic. 1", is zero-univalent and uniquely solvable. 51 11. Fl*t, where r is Figure 10(a)e r and Fl (less their last projections) are not deterministic, but rl*t (less its last projection) is deterministic. X 1[O(r) ] = e(rl1'*t). This illustrates Ltmma 342-3. 53 12. 1 = (S G,RP,Q,C). No sequence generator can have C(s) as its infinite behavior. 62 13. (a) F = (S,G,R,P,Q), which results from Fl*t of Fig. 11 by identifying and re-naming behaviorally equivalent states. F, less its last projection, is deterministic ( ) = (Fl*t). (b) f = (r S, G, R,P,C ), which results from P by adding a control projection C() = C(sl) = 0, C(s2) = C(s3) = 1. C(r) = @(r), where r is Fig. 10(a). (c) A net which has the computation C('). 65 14. r (SGR). 68 15. r = (S,G,R,P). 71 16. Normal form of the well-behaved net of Fig. 2(a). F(t) - E(t'). 74 17. Final-state sequence generator r = (S,G,F,R,P). F = [sl,. (Fr) is not open. 81 18. Final-state sequence generator r = (S,G,F,R,P). F = (s 1. 3(Fr) is open, but it is not the behavior of any sequence generator without final states. 82 vi

LIST OF FIGURES (Concluded) Fig. Page 19. r = (S,G,R,P). No sequence generator without final states has ~ (r), I f(r), or @ (F) as its behavior. 83 20. (a) r = (S,G,F,R,P). F = C s. (b) r = (S,G,f,R,P). F - (So). No sequence generator has the behavior &(r) ~(I ). " 85 21. Probabilistic sequence generator (S,G,R,W,P). 91 22. (a) Binary counter (probabilistic). (b) Probabilistic sequence generator (S,G,R,W,TI,) for binary counter (a). Solid lines represent transitions with probability (1 - e)/2. Dotted lines represent transitions with probability </2. 92 vii

1. INTRODUCTION 1.1. SEQUENCE GENERATORS The basic concept of this paper, that of sequence generator, is a generalization of the concepts of digital computer, finite automaton, logical net, and other information-processing systems. In this subsection, we will define sequence generator and some related concepts and will illustrate them immediately thereafter. Definitions: A sequence generator r = (S, G, R, i n) consists of a set S (whose elements are called complete states), a set G (whose elements are called generators), a binary relation R (called the direct transition relation), and functions l,, n (called projections), for some n = 0, 1, 2, 3,*..., satisfying the conditions: (1) S is finite, (2) G is a subset of S, (3) R is defined on S, and each P (for i = 1, 2,..,, n) is also defined on SO The values of the function P, which may be entities of any i kind, are called P -states. A sequence generator may be represented by a finite-directed graph whose vertices denote complete states and whose arrows indicate when the direct transition relation holds between two states. In our diagrpmswe will use rectangles at those vertices which represent generator states and circles at vertices representing complete states which are not also generators; the names of complete states and of P-states are written in the circles and rectangles (see Figs. l(b), 2(b), 3, etc.). Though our diagrams are closely related to the usual state diagrams (transition diagrams) employed to represent automata (see, for example, Moore, 1956, p4 134), there are very significant differences, The vertices (nodes) of our diagrams represent complete states, while in the usual state diagrams, the nodes represent internal states. This difference results 1

from the fact that in sequence generators complete states are basic and input and output states are derived from complete states by means of projections, while in the usual approach complete states are derived by compounding internal states and input states. (The latter process is explained in Section 1.2; we will discuss the relation of the two approaches further in Section 2.1.) So0 s01 io' gO i0) 481 do0 d A 0 B C (a) (b) Fig. 1. (a) Binary counter; (b) Three-projection sequence generator r = (S, G, R, I, G, D) associated with the binary counter (a).

E (a) io Q1 1!1 s41 s42 J0 eJ S (b) Fig. 2. (a) Ill-formed net with behavior F(t) E(t + 1); (b) Sequence generator F = (S, G, R, I, G) associated with net (a).

SIS S4': I W,: (a) (b) Fig. 3. (a) Sequence generator r = (S, G, R); (b) Ft the reduced form of r. Some comments and explanations concerning the definition of sequence generator may be helpful. If n = O, then r = (S, G, R) is a sequence generator with no projections. Though our definition of sequence generator permits any number of projections, in this paper we will be mainly interested in sequence generators with zero, one or two projections. Furthermore, the set of complete states S of a sequence generator may be a null set; in this case the domain of definition of each function Pi will be empty. It is worth noting that essentially (but not quite) the same concept of sequence generator can be obtained without using the set S of complete states in the definition and

then defining S to be the union of G and the field of R. We will use [a](j,k) (where j is a non-negative integer, k is a non-negative integer or k = wo; j - k) to denote the sequence < a(j), c(j + 1),..., a(k) > when k is finite and the sequence <cu(j), a (j + 1), c (j + 2),.. > when k = If P is a projection P( [o](j,k)) abbreviates the sequence < P((c(j)), P(CI(j + 1)),...,P(ac(k)) > when k is finite and the sequence < P(C(j)), P(a(j + 1)), P(a(j + 2)),...> when k = X Definitions: Let r = (S,G,R,PlO,.O Pn) be a sequence generator and let k be a non-negative integer or w. [s](O,k) is a F-sequence if (1) s(O)cG and (2) for each j, j < k, R(s(j), s(j + 1)). A complete state s is (F-accessible3 [r-admissible] if s occurs in some ( —-— ) [infinite] F-sequence. These concepts may be illustrated by reference to the direct transition diagram of Fig. 3(a). The sequence < s7, > is a P-sequence, while the sequence < s3, S4i S5, S6,Ps4,-s6Y S4,S, S4is6.. > is an infinite F-sequence. Complete states s7, ss, and s9 are F-accessible but not F-admissible; complete states S3,S4,S5, and s6 are F-accessible and F-admissible, while states SO,SlS2y and slo are inaccessible (and hence inadmissable). Definitions: Let p be a binary relation and oC a set; we define p(ac) = (yl (2x)p(x,y) & x ea). A complete state s of r = (S, G, R, pl,. a, pn) is a terminal state of r if R((s)) is null, A terminal state of r is a complete state for which there is no successor by the direct transition relation Ro Complete states ss8 and slo are the terminal states of Fig. 3(a), Note that if r has no terminal states, every F-accessible state is rF-admissible and vice versa. In Burks and Wright, 1953, p. 1364, we defined the concept of an admissible state of a net. When a net is converted into a sequence generator (see Section 1.2 below), these states will be accessible rather than admissible in the senses of these terms defined above, 5

We will sometimes need to combine several projections to make a composite projection of them. For this we will use the notation 1 2 n P X P x.o.X P which is defined by [P1 X P XO x Pn](S) ( = < P (s), P2(s),..., P (s) >. 1.2. SPECIAL CASES OF SEQUENCE GENERATORS Many concepts in the theory of information processing turn out to be special cases of the concept of sequence generator or are closely related to this concept, We will discuss a number of these in the present subsection. Since digital computers (automata) and logical nets are of special interest to us, we will show in detail how the concept of sequence generator applies to them. In later sections we will derive both new and old results about automata and nets from our new theory of sequence generators, We will begin with well-formed nets, review the method of deriving a finite automaton from a well-formed net, and then show how to derive a sequence generator from a finite automaton. We will use the definition of well-formed net of Burks and Wright, 1953, P0 1361, modified to allow arbitrary switching elements and delay elements whose initial output states are one, as well as de2 lays whose initial output states are zero. In net diagrams, certain nodes (junctions) are designated as net outputs and are distinguished by stars [see Fig. l(a) ]o A well-formed net (w.fvn.,) may be analyzed in terms of its input states, delay output states, and net output states, A digital computer represented Sequence generators may also be derived from automata containing delays whose initialoutput states are unspecified; these are called "abstract delays" in Burks and Wang, 1953, P. 201, and Burks, 1959, Section 3. But we will not complicate the present discussion by considering automata with such delay element s. 6

by a w.fn, operates as follows. The "state" of a net at a given time is determined by its input state i and its delay output state d at that time; these pairs < i,d > are called the complete states of the net, For each time t (t = 0,1,2,..o) the complete state < i,d > determines the net output state e at the same time (t) in accordance with an output function., i.e., e = \(i,d). At time 0 the delay output state dO is uniquely determined by the initial delay output states of the delay elements. For each time t the complete state < i,d > determines the delay output state d1 at the next moment of time (t + 1) in accordance with a direct transition function T, i.e., d1 - T(i,d). The net of Fig. l(a) is a well-formed net which represents a binary counter. A is the input node, the starred node C is its net output node, and B its delay output node (the initial state of B is zero). The state of C at t indicates the binary count, i e., the number modulo 2 of 1's which have appeared (during the interval of time 0,,, o t) on the input node A. The state analysis is given by the following table, where 0 is the initial delay output state. i(t d(t) d dEt + 1) I= (t _ T(i,d) i,d) A B B C1 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 0 Definition: A finite automaton is a sextuple < (i), [d), (e), do0 T, X > where [i}, (d), [e) are finite non-empty sets (whose elements are called input states, internal states, and output states, respectively), do C (d) (dO is called the initial internal state), T is a function from the Cartesian product (i] x (d) into (d} (called the direct transition function), and A is a function from the Cartesian product (i] x (d} onto (e) (called the output function). 7,

(This is essentially the definition of Burks and Wang, 1956, p. 203; see also Moore, 1956, po 133.) The procedure for analyzing a well-formed net which is described in the preceding paragraph clearly converts a well-formed net into a finite automaton., This procedure is reversible; that is, given a finite automaton, one can construct a well-formed net which realizes it, Thus the concepts of well-formed net and finite automaton are basically equivalent and either can be taken as a formal definition of the concept "finite digital computer." (See Church, 1955, Kleene, 1956, p. 5, and Burks, 1959, Section 3, for other definitions of these concepts.) A three-projection sequence generator r = (S, G, R, I, 9, D) may be associated with a finite automaton as follows. The elements of S are the complete states < i,d > and the elements of G are the complete states < i,dO > The direct transition relation is defined by R(< il,d >, < i2,d2 >) - [d2 = r(il,dl)] and the input, output, and internal state projections by I(< i,d >) = i, G(< i,d >) = k(i,d), and D(< i,d >) = d, respectively. The sequence generator associated with the binary counter of Fig. l(a) is represented by Fig. l(b). As before, the rectangles represent elements of G. The subscripts on the complete states correspond to the nodes of the counter in the order A, B. < SOO,SiosSllsooo Slosso1 > is an example of a finite r-sequence; in it the input sequence io,il,ili,io,io produces the output sequence eo,el,eo, e~olel (and thus three "ones" on the input leave the counter recording "one") Note that, though the internal states do,d1 are represented in Fig. l(b), the nodes of the graph correspond to complete states and not to internal states, as is the case with the usual state diagrams used to represent automata. We have shown how to transform a well-formed net into a finite automaton and vice-versa, We have also shown how to derive a sequence generator from a finite automaton, The latter process is not in general reversible, Only 8

certain sequence generators (those which are deterministic) may be realized by finite automata (see Section 2.1). Our next application of sequence generators is to arbitrary "nets," including nets that are not well-formed, We will use the concept of Burks and Wright, 1953, p. 1353, modified to allow arbitrary switching elements and both kinds of concrete delays. Each switch element translates into a switch equivalence which gives the state of the switch output as a truth function of the switch input, and each delay element translates into two delay equivalences, called the "initial delay equivalence" and the "recursive delay equivalence." The initial delay equivalence gives the initial state of the delay output and the recursive delay equivalence equates the delay output at any time other than 0 to the delay input at the previous time. Hence, each net translates into a conjunction of equivalences. If the net is not wellformed, this conjunction will not directly correspond to (will not give the structure of) a digital computer, but it may specify a computation or behavior condition on a digital computer (see Section 4), and on this account is of interest. Figure 2(a) shows a net with input node E and output node F. The non-input switch element driving node A represents the contradictory or "always false" truth function. The initial state of the delay AB is "true," which for coding reasons we represent by "1"; the initial state of the delay GC is 0. The switch equivalences for this net are A(t) - O, F(t) - F(t), and C(t) [E(t) & Bt)]o. B(O) - 1 and C(O) - are the initial delay equivalences, while B(t + 1) - A(t) and C(t + 1) - F(t) are the recursive delay equivalences. A two-projection sequence generator r = (S, G, R, I, G) may be associated with an arbitrary net in the following way:3 A complete state s is an assign3If the net is well-formed either the procedure about to be described or the procedure described earlier may be used, The resultant sequence generator will, —of course, be different in the two cases. 9

ment of a truth value to each node of the net which makes the switch equivalences of the net true. An element s of S is a generator (element of G) if s assigns to the delay output nodes truth values which make the initial delay equivalences true. R(sl,s2), where sl, s2 C S, if and only if the truth values which sl assigns to the delay input nodes and the truth values which S2 assigns to the delay output nodes satisfy the recursive delay equivalences, For each complete state s, (I(s)) [9(s)] is s cut down to the (input) [output] nodes [i.e., [I(s) [(s) ] is the net (input) [output] state contained in s the input projection will not exist if there are no input nodes, The sequence generator r = (S, G, R, I, 9) associated with Fig. 2(a) is represented by Fig. 2(b). Though there are 6 nodes in the net, there are only 8 complete states. The subscripts on the state symbols sl, s37, etc., are the decimal codings of the binary representations of the states of the nodes taken in the order E, A, B, C, F, G; e.g., the subscript on so decodes into 001001, showing that in this state nodes B and G are active while the remaining nodes are inactive. The subscript of the input state i is the state of node E and the subscript on the output state e is the state of node F. < slo, s37, s2, s38, s37 > is a F-sequence which has a derived input sequence < io, il, i0, io, il > and a derived output sequence < eo, el, leo eo, e1 >, It can be proved that F(t) = ~ E(t + 1); such behavior would not, of course, be possible in a well-formed net. Our process for associating a sequence generator with an arbitrary net is different from our process for associating a sequence generator with a wellformed net in the following basic respect. In the latter case we first defined input states, delay output states (internal states), and output states for the net, and then compounded complete states from input states and internal states, On the other hand, in associating a sequence generator with an arbitrary net, we first defined states (complete states) over every node, 10

and then derived input and output states by means of projections. It turns out that in general not every assignment of truth values to the input nodes of an arbitrary net is an input state. In fact, we know of no way of defining states for parts of a net (input, internal, and output states) without presupposing states for the whole net (complete states)o Indeed, it was our work with arbitrary nets which led us to consider sequence generators (in which complete states are basic; input, internal, and output states derivative). This completes our discussion of the method of transforming an arbitrary net into a two-projection sequence generator. This process may be reversed; that is, given any sequence generator with two projections, one can find a corresponding net, It is not difficult to construct this procedure (for going from a sequence generator to a net) from the information to be given in Section 4.2, so we will not describe it here. There are other entities besides nets and well-formed nets (digital computers) which are either sequence generators or are closely related to sequence generators. The concept of a non-deterministic automaton of Rabin and Scott, 1959, Definition 9, is quite similar to our concept of a sequence generator. Sequence generators are in a certain sense equivalent to formulas constructed from truth functional connectives, monadic predicates, one individual variable "t" (which ranges over discrete times), the successor function, and zero (see Sections 4o2 and 4.3). The following are special cases of sequence generators: a finite state grammar (Chomsky and Miller, 1958, p. 95); sequential circuits representable in combinatory logic (Fitch, 1958, p. 263); incompletely specified automata, i.e., automata in which certain sequences of input states are proscribed (Aufenkamp and Hohn, 1957, Section IV); automata with terminal states (ibid., Section VII); and the flow diagrams used in programming a digital computer. A sequence generator may be used to characterize a class of finite sequences defined by a regular expression (see Section 4.4), Finite graphs may 11

be used to analyze certain games (K6nig, 1936; and McKinsey, 1952, Chapter 6). There is an obvious relation between finite graphs and sequence generators, and hence some problems concerning games may be studied by means of sequence generators; we will give an example in the next subsection. Though he makes no reference to automata theory, Putnam, 1957, pp. 44-49, uses sequence generators to establish some results about satisfiability; he uses the concept of admissibility in connection with "F-sequences" which are infinite in both directions. We remark finally that Harary and Paper, 1957, in applying relational logic to linguistics use ideas closely related to the concept of sequence generator. Though we have noted a number of applications of the concept of sequence generator, we wish to make it clear that we are not attempting in the present paper to solve all the problems that have been considered for these applications. In the next subsection we will establish some results concerning infinite F-sequences for sequence generators without projections. In Section 2 we will treat some concepts in which a single projection plays an essential role, and in Section 3 we will work with concepts in which two projections play a special role. In Section 4 we will present some generalizations and further applications of sequence generators. 1.3. REDUCED FORM ALGORITHM Algorithms play a fundamental role in this paper, so we will make a few informal comments about them. An algorithm presupposes a well-defined set of entities, called "the domain of the algorithm." An algorithm is a finite system of rules which may be mechanically applied to any entity of its domain, An algorithm which terminates in a finite number of steps when applied to any entity of its domain is called a "terminating algorithm." The Reduced Form Algorithm to be described soon is a terminating algorithm, since, when it is 12

applied. to any sequence generator, it will eventually terminate in a sequence generator. An algorithm with a domain D is called a decision procedure for a class A which is a subset of D, if for every element of D which belongs to A, the algorithm terminates in "yes," and for every element of D which does not belong to A, the algorithm terminates in "no," The truth table procedure is a decision procedure for the class of tautologies of the propositional calculus. Before formulating the Reduced Form Algorithm, we will describe informally what it does. Let us call a state s of a sequence generator 1 = (S, G, R, l,..,p ) "extendable" if there is an infinite sequence of complete states < s(O), s(l), s(2),.. > such that s(O) is s and R[s(i), s(i + 1)] for i = 0, 1, 2,*,.. (Note that s is not necessarily a generator, and so the infinite sequence of complete states is not necessarily a r-sequence.) In Figo 3 states so and sl are extendable, while states s7 and slo are not. The Reduced Form Algorithm may be applied to any sequence generator rI. In part 1 of the algorithm the operation of deleting terminal states is iterated until we arrive at a sequence generator r with no terminal states. Since a sequence generator has non-extendable states if and only if it has terminal states, r is essentially the result of deleting all non-extendable states from r. In part 2 of the algorithm, one begins with the generators of r (and hence of r), and by a succession of steps obtains the accessible states of r. A new sequence generator rt, called the reduced form of r, is defined on the basis of the states so obtained. Since a state is admissible if and only if it is both extendable and accessible, rt is just r cut down to its admissible states (see Theorem 1.3-1). Algorithm (Reduced Form Algorithm): Consider any sequence generator r = (S,G,R,P1,l,Pn) (1) Form a new sequence generator by deleting all the terminal states of r. Iterate this process until you arrive at a sequence generator with no terminal 13

states. Call this final sequence generator r (S,G,R,P..,n) (2) Define Ai inductively by Ao = G Ai +1 = (Ai) Form the sequence AoA1,,A2... stopping when Am+CC U~i=oAi. (Note:,"CC B" means that of is either included in B or equals D.) Let S = Uio Ai, G = G. and let [R3 [pi] be the (relation R] [projection Pi] cut down to S. Define rt r (s G R A 40-l We will illustrate the Reduced Form Algorithm. Let r = (S,G,R) be the sequence generator represented by Fig, 3(a), with those complete states which belong to G being designated by rectangles. In part 1 of the algorithm we delete states s8 and slo, then state s7, and then state se. S consists of the remaining complete states, G contains S3 and s6, and R is R cut down to S. We have at the end of part 1 the sequence generator r represented by the result of deleting everything to the right of state s5 in Fig. 3(a). In part 2 of the algorithm we form the sequence (s3,s66 [=Ao], (S4 [=A1], (S5,s6) [=A2], (s4,se6[=A3]. Simultaneously we form the sequence (s3,se][=Ui=oAi], 1 2 (S3,s4,s6)[=Ui=o Ai], ss3,s4,s5,s6e[=Ui=o Ai], stopping at this point since (s4,s6)C (s3,s4,s5,s6], i.e., A3CUi=oAi. Hence S = (s3,s4,s5,s6] and rt, the reduced form of r, is represented by Fig. 3(b). Theorem 1.3-1: The Reduced Form Algorithm, when applied to any sequence generator r, always terminates in a sequence generator rt. The set of complete states of rt equals the set of F-admissible complete states. As a step toward proving this theorem, we first establish Lemma 1.3-2: Let p be a binary relation and 8o a set. Define 5i for i = 1,2., inductively by bi+l = p(6i) and let ae = ITi=o 5i for R = 0,1,2,... If, for some j, ij = j+l then for all e,cCe a:.

Proof: We note first that since the operator p may be distributed over the union, ac+1 = caup(e). We now assume cj = ~tj+l and prove that olC aj, proving first by induction that for all I - j, c~ = xj. The initial step is covered by the hypothesis that cej+l = (Cj. For the general step assume ak = aj, where k > jo By the fact noted above, (k+l = Q~kUP(c~k) and cj+1 = apjUP(aj)o Combining the four preceding equalities, we get 0ak+l = aj, To conclude the proof, we note that it follows directly from the definition of a that for I < j<, Ccajo We turn now to the proof of Theorem 1b3-1. We will use freely the notation of the algorithm. (I) We prove first that the Reduced Form Algorithm, when applied to any sequence generator r, always terminates in a sequence generator rt. Since S is a finite set, the first part of the algorithm terminates in a sequence generator F. The criterion for stopping in part 2 of the algorithm is based on a monotonically increasing sequence of subsets, of S, which is a. finite set, so the second part of the algorithm will always terminate. Finally, it is clear that a sequence generator rt is defined in part 2 of the algorithm. (II) We prove next that the set of complete states of Ft equals the set of r-admissible complete states. (IIA) We consider a F-admissible complete state s1 and show that s1 e S. Since s1 is r-admissible, there is an infinite sequence [s](O,o) of F-admissible states such that for some k, [s](k) = s1o A complete state of r is deleted by part 1 of the algorithm only if it cannot belong to an infinite F-sequence, and so [s](O,k) is a r-sequence. Hence' by the definition of Ak in the algorithm, s1 e Ak and s1 C Uk=oAi. We now apply Lemma 1.3-2, letting p = R and 50 = G. By (I) above, part 2 of the algorithm terminates; in the notation of the algorithm A Um+i Ui=o Ai. The result of Lemma 1.3-2, put in this notation, is that for all 2, UB=O Aij -uI= Ai. We have already shown that sl E UTJ= Ai, and 15

so si e U'i=o Ai. But in the algorithm S is defined to be UTi=o Ai and so Si C S. (IIB) We next consider a complete state s1 e S and show that s1 is r-admissible. In the notation of the algorithm S = 1io__ Ai and so sl e Ui=o Ai. Hence s1 is f-accessible. Part 1 of the algorithm terminates in a sequence generator r with no terminal states. As remarked in Section 1.1, every accessible state of a sequence generator with no terminal states is an admissible state. Consequently, there exists an infinite r-sequence [s]J(O,c) such that for some k, sl = [s](k). By the nature of part 1 of the algorithm, [s](O,cw) is also an infinite P-sequence, and so s1 is F-admissible. Corollary 1.3-3: (a)> Every' complete state of rt is rt-admissible. (b) The set of infinite F-sequences equals the set of infinite Pt-sequences. (c) Every finite Pt-sequence is an initial segment of an infinite F-sequence. We will next discuss the Reduced Form Algorithm and some alternatives to it. Applied to an arbitrary sequence generator r, part 1 of the Reduced Form Algorithm produces the set of extendable states of P. Applied to an arbitrary sequence generator r, part 2 of the algorithm produces the set of r-accessible states, Since a complete state is admissible if and only if it is both extendable and accessible, the two parts of the Reduced Form Algorithm applied to a sequence generator r in either order produce the same sequence generator rt. A sequence generator r derived from a well-formed net in the way indicated in Section 1.2 has no terminal states; consequently, when part 2 of the Reduced Form Algorithm is applied to r, it produces rt. There is an alternative procedure for finding the r-admissible complete states of a sequence generator. Let x be the number of complete states of r. Form all F-sequences of length x + 1; it can be proved that a state is F accessible if and only if it occurs in one of these sequences. To find the F-admissible states, we operate on each sequence as follows: proceeding through the 16

sequence < s(O), s(l),...,s(x) > check an occurrence of a state whenever that state has occurred earlier in the same sequence; then delete all states which follow the last checked state. It can be shown that a state is r-admissible if and only if it occurs in one of the resultant sequences. This method of finding the F-admissible states can be made the essence of an alternative reduced form algorithm which is simpler to formulate and easier to prove adequate than our Reduced Form Algorithm. It is less efficient, however: in the example given earlier, m = 2 while x = 11. These differences seem to result from the following fundamental difference between these two algorithms. In the Reduced Form Algorithm the length of the computation is not specified in advance; rather, parts 1 and 2 each contain an internal "stop criterion": one proceeds until he is stopped by these criteria. In contrast, the alternative algorithm first establishes the length of the computation on the basis of a general property of the sequence geneIator. (the number of- complete-f states); since this length is established a priori, it is of course determined by the worst case, even though in most cases far fewer steps would have sufficed. This is analogous to the contrast between asynchronous circuits, in which completion of an operation is sensed and the next operation begun immediately, and synchronous circuits, in which the same amount of time is allowed for a given operation in every case, and this is, of course the time required for the worst case (plus a "safety factor"'). We have presented the more efficient of these two algorithms, although it is more difficult to formulate and prove adequate, because finding the reduced form is basic to so many automata algorithms; see, for example, Sections 2.3 and 3.4. But though in many later cases we know of more efficient algorithms (see, for example, the alternative to the h-univalence Decision Procedure in Section 3.4) we will not present them because we feel that perspicuity of theory and simplicity of exposition are more important there. 17

We mentioned in Section 1. 2 that certain puzzles give rise to sequence generators. The so-called "15 puzzle" is a good example since it may be solved by means of our Reduced Form Algorithm. The puzzle consists of a 4 x 4 array of 15 movable blocks (numbered 1 through 15) and one empty position. A "move" consists in changing a pattern into any one of the (at most) four patterns obtained by shifting a block into the (neighboring) empty space. The problem is to achieve a stipulated pattern by a succession of moves starting from a given pattern. A sequence generator r = (S,G,R,P) corresponding to the puzzle may be defined as follows, The 4 x 4 matrices whose entries are the numbers 0 through 15 are the complete states of r; there are 16! of these. The starting pattern is the sole generator of r. Two states sl and s2 stand in the direct transition relation R if there is a move taking the pattern corresponding to sl into the pattern corresponding to s2. The projection P has the value 1 on the single pattern stipulated to be the goal and O otherwise. The problem is solved by constructing a finite r-sequence < s(O), s(l), s(2),..,s(t) > such that P[s(t)] = 1, if such a sequence exists. Clearly this sequence exists if and only if the complete state with a projection of 1 is P-accessible. Whether or not this is the case can be determined by applying part 2 of the Reduced Form Algorithm to r: if such a sequence exists, 4 it will be found in the course of carrying out the algorithm. It turns out that exactly half of the complete states of r are r-accessible and that each of these F-accessible states is also r-admissible. 4There is a much simpler algorithm for finding the P-accessible states of this particular sequence generator. See Wo W. R. Ball, Mathematical Recreations and Essays, Macmillan, 1940, pp. 299-303. 18

2. SEQUENCE GENERATORS WITH ONE PROJECTION 2.1. DEFINITIONS In the last sub-section we made no particular use of the projections of a sequence generator. In this section we shall define some concepts which apply primarily to sequence generators with one projection and will prove some theorems about these concepts. In most applications this single projection is an input projection, an output projection, or a combined input-output projection. In the next section we will work with sequence generators having two projections. These two projections will usually be an input and an output projection. Definition: The behavior of r = (S, G, R, Pl, P2,.., pn), where n > O, is the set P([s](O,k')), where P = Plx P x n and [s](O,k) is a r-sequence (finite or infinite). "(F)" denotes the behavior of F. The infinite behavior of r, denoted by ttW( r)", is the set of infinite sequences in 6(r)o Corollary 1.3-3b can now be reformulated as follows. Corollary 2.1-1. ( r) = -(rt) It is worth noting that in general it is not true that for a sequence generator F = (S, G, R, P) there exists a sequence generator P such that the set of r-sequences equals the behavior of r. This may be shown by a simple example. Let S = [Sosl1S2], G = (So], R = (< SoS1 >, < sl,s2 >, < s2, so >], and P(so) = P(sl) = Po, P(s2) = P-. There is one infinite F-sequence < So,SlJS2,SoSlSSS2,oSlS2s0 > and the behavior of F consists of the sequence < PoPoPlPoPoPl,o. > and all its initial segments, and does not include the infinite sequence < poPoPo0.. >. Consider a sequence generator = (S, G, R) such that (popljCS and such that < PoPoPlPoPoPlaa > is an infinite r-sequenceB It follows from the existence of this sequence 19

that R(po,po) and po e G, and hence that < poPoyPo,yp, > is an infinite r-sequenceo Some remarks about the application of the concept of behavior to nets will be appropriate. By the methods of Section 1,2, we can associate with every net (well-formed or not) a sequence generator r = (S, G, R, I, 9), where I is the input projection and 9 is the output projection, The behavior of a digital computer (wofun.) consists of the relationship between its inputs and its outputs, and similarly for an arbitrary net, The behavior of a net may be regarded as the set of sequences (finite and infinite) of pairs < i(O), e(O) >, < i(l), e(l) >, < i(2), e(2) >,... for which there is a F-sequence [s](O,k) such that i(t) = Ils(t)) and e(t) = G[s(t)) for every t. This is clearly (rP), the behavior of the sequence generator r = (S, G, R, I, 9) In Section 2.3 we present a Behavior Inclusion Procedure to be applied to a pair < r, f > to decide whether the behavior of r is included in the behavior of r; when applied to the pair < r, r > as well as to the pair < r, r >, this tells us whether the behaviors of r and r are equal. Thus, through these considerations, the Behavior Inclusion Procedure can be used to decide whether the behavior of an arbitrary net N is included in or equal to the behavior of a net N. In the case of well-formed nets, however, a much more efficient algorithm for deciding equality of behaviors is known (Burks, Wang, 1956, Section 2.2); a basic part of this algorithm consists essentially of finding the reduced form (Section 1,3) of a sequence generator associated with the combined nets, Actually this algorithm applies to any deterministic sequence generator (this concept is defined below); moreover, if r and r are both deterministic and (r)C(r) ), then (r)ef r)), so this algorithm also answers the question as to whether p(r) C (f) for the case of deterministic sequence generators. The following lemma will be needed in subsequent proofs. It is a classical 20

interpretation of Brouwer's Fan theorem (Heyting, 1956, pp. 42-43) and is closely related to K6nig's Infinity Lemma concerning infinite graphs (Konig, 1936, p. 81). Our lemma, however, is stronger than Konig's Infinity Lemma in that it does not require that the Ci's be pairwise disjoint; because of this difference, we present a proof of it here. Lemma 2.1-2: Let < aoYl~,2,9.~ > be an X-sequence of finite non-empty sets and let p be a binary relation. If for every x e:ci+1 there is a y e ai such that p(y,x), then there is an infinite sequence < zo,zlz2,.. > such that for each i, zi C ai and p(zi,Zi+l). Proof: Let i consist of all finite sequences < xiXi+l,.,xi+k > where k = 0,1,2, x,,xj c 0j for i _- j d i + kand p(xj, xj+l) for i _ j < i + k. It follows from the requirement on p in the hypothesis of the lemma that for each i,k, and element Yi+k of ai+k there is an element of Pi < Yi, Yi+l,of., yi+k >. Since this is so for any k, each 5i is infinite. We will now define by induction the desired sequence < ZoZl,Z2,0. >o Initial step: Since Po is infinite while ao is finite there will be some element zo of aO such that an infinite number of elements of z begin with: zo. Let 50 be the subset of Po all of whose elements begin with zo. General step: Assume given a sequence < Zo,zl,. o, Zi > (where i = 0,1,2,...) which belongs to o and satisfies the condition that the set 5i of elements of Pi which begin with zi is infinite, The result 5i+1 of deleting the first element of each member of Pi is an infinite subset of i+l. Since ci+l is finite, there will be some element zi+l of ai+l such that p(zi, zi+l) and an infinite number of elements of si+l begin with zi+1. Let 5i+l be the subset of si+l, all of whose elements begin with zi+l; 5i+l is a subset of Pi+l and hence 6i+L is also. Hence < Zo,Z,.,.,z.,izi+1 > belongs to o and satisfies the condition that the set ji+i of elements of -i+i which begin with zi+1 is infinite. Thus the inductive hypothesis has been established for the 21

sequence < Zo,z1,..,zi, zi+1 >e This completes the proof of Lemma 2.1-2. It may be shown by means of this lemma that a sequence of P-states is an element of the behavior of a sequence generator if and only if every initial segment is. Theorem 2.1-3 (Infinity Theorem): Let r = (S,G,R,P) be a sequence generator with behavior (rF) and let [p](O,k), k = 0,1,2,...,I, be a sequence of P-states. [p](O,k) E P(F) if and only if for every finite i < k, [p](O,i) c 4(r). Proof: The proof of the theorem for finite k is obvious. It is also obvious that [p](O,yw) C 6(r) implies that for every finite i, [p](O,i) e 3(r). it remains to be proved that if [p](O,i) c j3(r) for every finite i, then [p](O,yc) -c (r). We define ai by sl C ai if there exists a F-sequence [s](O,i) such that [pl(O,i) = P( [s](O,i)) and sl = s(i). It is clear that each ai is finite and non-empty. We let p = R and show that the hypothesis of Lemma 2,1-2 is satisfied, Suppose s2 C ai+l By definition of ai+l there exists a F-sequence [S3](0, i + 1) such that [p](O,i + 1) = P([ss](0, i + 1) and S2 = [s3](i + 1), Let S4 = S3(i) By the definition of ai, S4 e ai and by the definition of a r-sequence, R(sl,s2). By Lemma 2.1-2 there is an infinite r-sequence [S5](0,wo) and by the definition of ai we have P([s5](0,w)3 = [p](O,U). Hence [p](O,cu) C(r)). The following is a corollary of the Infinity Theorem. Let r = (S, G, R, P) and r = (S, G, R, P) be two sequence generators and suppose that for every finite k, if [p](O,k)cE 3(r) then [p](O,k)c C(Fr); then ((r) C(I'r). For consider any infinite sequence [p](0,o) e @(r). By the Infinity Theorem, for each k [p](O,k) c @(r). Then by hypothesis, for each k [p](O,k) 3(r) ~ Finally, by the Infinity Theorem [p](O,f) @( r). This result holds for r and P interchanged, of course, so we have: if for every finite k [p](O,k) e (r) -- [p](O,k) 3((r), then 3(r) = (f). Thus the Infinity Theorem shows that the "finite" behavior of a sequence generator determines its (complete) behavior. 22

Definitions: Let r = (S, G, R, P) be a sequence generator. r is solvable if every infinite sequence of P-states belongs to its behavior. r is (semi-deterministic] [deterministic] if it satisfies the conditions: (1) For any P-state p, there is (at most one) [exactly one] complete state s of r such that seG and P(s) - p. (2) For any complete state s1 and any P-state p of r, there is (at most one) [exactly one] complete state s2 such that R(sl,s2) and P(s2) = p. It is obvious from the definition of (semi-determinism) [determinism] that there is a decision procedure for the class of (semi-deterministic) [deterministic] sequence generators. The problem of solvability is not so simple, but we will later develop a decision procedure for solvability (see Theorem 2.3-2). Let us illustrate these concepts. The sequence generator of Fig. l(b) less its last two projections, is clearly deterministic. The sequence generator of Fig. 4(a) is semi-deterministic but not solvable, while the sequence generator of Fig. 4(b) is neither semi-deterministic nor solvable. PO Pi( P P1 () (a) (b) Fig. 4. (a) Semi-deterministic non-solvable sequence generator; (b) Sequence generator neither solvable nor semi-deterministic. By simple inspection it can be ascertained that the sequence generator (S, G, R, P) of Fig. 10(a) is neither semi-deterministic nor deterministic. It is, however, solvable, as the following considerations show. Given any sequence of P-states, divide it into a sequence (finite or infinite) of 23

subsequences (finite or infinite), where each subsequence is either an iteration of po or an iteration of Pi and the two types of subsequences alternate. Now a F-sequence so, so,..., s, s1 produces a P-state sequence Po, po,..., Po followed by at least one occurrence of Pl, while a r-sequence S3, s.. S2 produces a P-state sequence Pl, Pl, ~ ~ ~, P1, Pi followed by at least one occurrence of Po. Hence for any sequence of P-states [p](O,k) one can construct a r-sequence [s](O,k) such that [p](O,k) = P( [s](O,k)), and so (S, G, R, P) is solvable. Consider next (S, G, R, I) of Fig. 2(b). (S, G, R, I) is not semi-deterministic, since the input sequence < io, io0 io > is the projection of both < s9, sl, sl > and < s9, sl, S2 >. But (S, G, R, I) is solvable, as may be shown by an analysis like that just given for Fig. 10(a); indeed, except for labeling, the behavior of Fig. 2(b) is the same as the behavior of Fig. 10(a). The following lemma may be established by simple mathematical inductions with reference to the appropriate definitions. Lemma 2.1-4: Let r = (S, G, R, P). (a) If r is (semi-deterministic} [deterministic] (solvable), then rt is (semi-deterministic) [deterministic] (solvable). (b) If every complete state of r is F-accessible, then F is [semi-deterministic) [deterministic] if and only if for every finite sequence of P-states [p](O,t) there exists (at most one) [exactly one] F-sequence [s](O,t) such that P([s](O,t)3 = [p](O,t). (c) If F is deterministic, then r is solvable. Other senses of semi-determinism and of determinism may be obtained by replacing every occurrence of "complete state" in the above definition of semi-determinism and determinism either by "admissible complete state" or by "accessible complete state." We will call the concepts obtained by making the latter substitution "semi-determinism1" and "determinisml1" It may be 24

shown that these two concepts are equivalent to the conditions stated in the consequent of part (b) of Lemma 2.1-4l In the case of arbitrary nets determinism1 becomes the determinism of Burks and Wright, 1953, p. 1359. The process described in Section 1,2 associates with a finite automaton a sequence generator F = (S, G, R, I, 9, D) such that (S, G, R, I) is deterministico Conversely, given a sequence generator r = (S, G, R, I, 9), where (S, G, R, I) is deterministic, we can define a corresponding finite automaton. Let the set of input states (i) and the set of output states [el be the ranges of the projections I and 9, respectively. The set of internal states [d3 of the automaton is a set of sets of complete states of r defined as follows: e (d a = G M\ (as)(a = R(s)), where a ranges over non-null subsets of S. Let the initial internal state do = G. The direct transition function r is given by T(i,d) = R(-sI s e d & I(s) = where "ris.." means "the complete state s satisfying the condition ".. "o Finally, the output function X of the net is defined by \(i,d) = G(isI s e d & I(s) i) We will give an example. Figure 5(a) is a deterministic sequence generator. The set of input states for the associated automaton is (io,i1) and the set of output states is (eo,e1,e2,e3,e4)} The set of internal states consists of the sets (so,slj, (s2,s3), and (s3,s4), which we will call do,d1, and d2, respectively. do is the initial internal state since [so,sl] = G. The direct transition and output functions are given by the table below. 25

c2 do < 53 S0 <i~~~~~~~~~~~~~~~~~~~j do>~ ~ ~ ~~~~~~<0,di ioy Q0 io.9 go ON a)t (b) Fig. 5. Determinigtip sequence generator r sG t > ( InterhaL state spquencCe generator G, Rq Iy i F i cOrresparlding, to (a).

= T( i,d) = %(i,d) io do dl ed il do d2 81el io dl do e2 il do d. e3 io d2 do 84 i1 d2 do e3 In Section 1.2 we gave a process for converting a finite automaton into a three-projection sequence generator. When this process is applied to the finite automaton just described, the result is the sequence generator r = (S, G, R, I, 9, D) of Fig. 5(b). It should be noted that 3(r) = 3(S, G, R, I, I ). Hence when the two procedures just described are applied successively to a sequence generator r = (S, G, R, I, 9), where (S, G, R, I) is deterministic, the result is a sequence generator = (S, G, R, I, 9, D) with an internal state projection D and such that the behavior of (S, G, R, I, I) is the same as the behavior of r. This is an opportune time to compare the state diagrams that we have been using, which may be called "complete state graphs," with those ordinarily used in discussing automata, which may be called "internal state graphs." The nodes of a complete state graph represent complete states and the lines represent transitions between complete states; these lines are unlabeled since the input states, output states, etc,, are derived from the complete states by means of the projections. The nodes of an internal state graph represent internal states; the labeled lines represent transitions between internal states, with the labels indicating the inputs that cause the transitions and the outputs which are produced by the transitions. Since the definition of sequence generator (Section 1.1) is in terms of complete states, complete state graphs give a more direct representation of sequence generators than do internal 27

state graphs, We have considered definitions of sequence generators in terms of internal states, but none of these is both as general and as simple to formulate and work with as the definition we have given. However, certain kinds of sequence generators can best be analyzed in terms of internal states and are more simply represented by internal state graphs than by complete state graphs. For example, deterministic sequence generators can be analyzed in terms of internal states in the way we have just shown; moreover, the resulting internal state diagram is always simpler than the corresponding complete state diagram. Whenever the practicality of a technique of analysis is of interest and the internal state diagram is simpler than the complete state diagram, the former should, of course, be used. Any property of a one-projection sequence generator and any operation applicable to a one-projection sequence generator can be extended to a sequence generator F = (S, G,- R) without projections by adjoining to it a constant projection P (i.e., a projection with only one P-state); r is solvable, deterministic, etc., if (S, G, R, P) is solvable, deterministic, etc. For example, a well-formed net without input nodes has associated with it (by either of the techniques of Section 1.2) a sequence generator (S, G, R) with one infinite (periodic) F-sequence. For constant P, (S, G, R, P) is solvable and semideterministic, and hence deterministic, and so is (S, G, R); see, for example, Fig. 6(a). 2,2. SUBSET SEQUENCE GENERATOR OPERATION We will next define an operation, denoted by " called "the subset sequence generator operation." This operation may be applied to any sequence generator r to obtain its subset sequence generator r*. The complete states of r* are sets of complete states of r. The generators, the direct transition relation, and the projections of r* are defined in terms of r in such a way 28

{)(b) S (a) (b) Fig. 6. The construction of a subset sequence generator. (a) Ir (S, G, R, P); (b) r*, the subset sequence generator of r. that r* has the same behavior as F (Theorem 2.2-3 below) and r* is always semi-deterministic; even though r may not be (Lemma 2.2-1 below). Definition: The subset sequence generator operation, denoted by "*," applies to any sequence generator r = (S, G, R, p,p2,*.*,pn) where n > 0, and produces a sequence generator F* = F = (S, G, R, f f2 fn) Let P = Plx P2x...x pn (1) A subset x of S is an element of S if and only if x is non-null and P has the same value for all elements of x. This definition can be expressed symbolically as follows, where A is the null set, and the variable x ranges over subsets of S: xe S:-: x / A & (S1,s2) ([(s1 E S) & (s2 E S) & (S1 E x) & (s2 C X) [P(s1) = P(s'2) ) (2) The elements of G are maximal subsets of G which are elements of S. Formally, s C G:-: s C S & scG & (sl) ([sl C S & (sc slcG)] (s = s1)) 29

(3) Two complete states s' and s2 of S stand in the direct transition relation R if and only if s2 is a maximal set of direct successors (by R) of elements of 1.o Formally, R(s1,s2): S1 C S & S2CR(S1) & (;3) { [3 e S & (2 C;3 cR(l)) ])(2 = S3) i (4) All the elements of a state s of S have the same P state (for i = 1,2,...,n), and we take this common-value to be the Pi-state of s. Formally, Pi(s) = pi(s) where s e s, s C S. (r* is called "the subset sequence generator" of F. Our concept of a subset sequence generator is similar to concepts used by Myhill, 1957, p. 122, Medvedev, 1958, p. 13, and Rabin and Scott, 1959, Definition 11.) It should be noted that the concepts of behavior (Section 2.1) and subset sequence generator are essentially one projection concepts in-'the sense that when many projections. pl,p,,,P are given, the composite projection Plx P2x...x pn is used in the definitions of'the concepts. In subsequent theorems and algorithms we will, for the sake of simplicity, usually state our results for sequence generators with one projection, since it is obvious how to extend them to the many-projection case. The construction of subset sequence generators is illustrated in Figs. 6 and 7. Note that the generators and complete states of the subset sequence generator r* are determined without reference to the direct transition relation of r. Figure 6 shows that even though F is in reduced form, F* may not be, though in fact, if r is in reduced form, then rF* has no terminal states and so (r*) = 0(r*t) In Fig. 7 we begin with a semi-deterministic sequence generator, add to it in various ways to obtain three sequence generators, r, r, F which are not semi-deterministic, and then derive the subset sequence generator of each of these. All the subset sequence generators F*, F*, F*,'* are semideterministic, as they must be by the next lemma. None of the sequence 30

Up S p0 p1 PO p1 (a) (a') (b) (b') (c) (c') (d) (d') Fig. 7. Examples which illustrate Lemma 2.2-1: For any sequence generator r - (S, G, R, P),r* is semi-deterministic. (a) Sequence generator r = (S, G, R, P). r is semi-deterministic. (a') F*, the subset sequence generator of?. r* is semi-deterministic. (b) Sequence generator - (S, G, R, P). F is not semi-deterministic. (b') r*, the subset sequence generator of r. r* is semi-deterministic. (c) i = (S, G, R, P). r is not semideterministic. (c') r*, the subset sequence generator of r. ]'* is semi-deterministic. (d) 1r = (S, G, R, P). r' is not semideterministic. (d')'r*, the subset sequence generator of r. r* is semi-deterministic. 31

generators r, r, F, r is solvable; r*, r*, r*, and r* are not solvable either (cf. corollary 2.2-4). Lemma 2:2-1: For any sequence generator r = (S, G, R, P), rF* is semi-deterministic, Proof: Let r* = = = (S, G, R, P)o It follows from the construction of G that for any s1,s2, if sl e G, s2 C G, and P(s) = P(s2), then sl = s2, and it follows from the definition of R that for any s,s:2, if R(s,sl), R(s,s2), and P(*l) = P(;2), then sl = s2 Given a sequence generator r = (S, G, R, P), by the above lemma its subset sequence generator r* = r = (S, G, R, P) is semi-deterministic. Hence for any given finite sequence of P-states [p](O,t) there is at most one complete state satisfying the condition that there exists a F-sequence [s](Ot - 1), ~s such that P([s](O,t - 1), sl = [p](O,t). Moreover, this state sl is a set of -states of r. We will use the locution "the state s1 E S corresponding to [p](O,t)" to refer to this set of states al if it exists, otherwise to the null set, Lemma 2.2-2: Let rF* = = (s, G, R, P) be the subset sequence generator of r = (S, G, R, P), let [p ](O,t) be any finite sequence of P-states, and let ax be the set of states s1 for which there exists a F-sequence [s](O,t - 1), s1 such that P([s](O,t - 1), sl) = [p](O,t). Then c is the state s, e S corresponding to [p ] (O,t). Proof: (I) We first prove by an induction on t that for any finite F-sequence [s](O,t) there is a r-sequence [s](O,t) satisfying the conditions (a) P([s](O,t) = P [S](o,t) (b) s(t) e S(t) Initial step: given the F-sequence s(O), it follows by the definition of G that there exists a complete state s(O) such that s(O) C s(O) and s(O) e G. 32

General step: The inductive hypothesis is that for every r-sequence [s](O,k) there is a F-sequence [s](O,k) satisfying the conditions (a) and (b). Consider any F-sequence [s](O,k + 1). By the inductive hypothesis there exists a F-sequence [s](O,k) such that [s](O,k) and [s](O,k) satisfy (a) and (b). Since R(s(k), s(k + 1)) it follows by the definition of R that there exists a complete state sl such that s(k + 1) e sl and R('(k), es). Hence P(s(k + 1) = P(sl) and [6](O,k), sl is a F-sequence, and so [s](O,k + 1) and [s](O,k), sl satisfy conditions (a) and (b). (II) We next prove by an induction on t that for any finite F-sequence [s](O,t) and complete state s1 e s(t) there is a F-sequence [s](O,t) satisfying the conditions (c) P([s](O,t)} = P {[](O,t) (d) s(t) = s1. Initial step: given a F-sequence s(O) and a state s1 e s(O), it follows by the definition of G that sl is the desired F-sequence. General step: the inductive hypothesis is that for every F-sequence [s](O,k) and state s1 e s(k) there is a F-sequence [s](O,k) satisfying conditions (c) and (d). Consider any F-sequence [s](O,k + 1) and a state s2 e s(k + l),x By the definition. R there exists a state s1 satisfying the conditions s1 e s(k) and R(sl,s2)o By the inductive hypothesis there is a F-sequence [s](O,k) such that P([s](O,k)] = Pf[s](O,k)] and s(k) = sl. [s](O,k), s2 is the desired F-sequence. This completes the proof of Lemma 2.2-2. Theorem 2.2-3: For any sequence generator r = (S, G, R, R) with behavior (r), g(r) = i(r*). Proof: By the preceding Lemma 2,2-2, for every finite tEp](O,t) Ce (r) if and only if [p](O,t) e 3(r*). The theorem to be proved now follows by the Infinity Theorem (2.1-3). It should be noted in this connection that the 33

proof of the Infinity Theorem makes implicit use of r*, the subset sequence generator of r. In fact, the sequence < %o,Y1,ca,... > employed in the proof is an infinite F*-sequence. Corollary 2.2-4: For any sequence generator r = (S, G, R, P), r is solvable if and only if r* is solvable. 2.3. DECISION PROCEDURES Behavior Inclusion Procedure: Consider two sequence generators r = (S, G, R, P) and r = (.s, G, R, P), and let Ca) [a] be the number of states in (s3 [S]. Form all (F-sequences) [F-sequences] of length 1 + a2a or less and form the set (a) [&] of their (P-projections) [P-projections]. Write "yes" or "no" as aCZ or not. Theorem 2.3-1: Let A be the class of pairs of one-projection sequence generators < r, r > such that dB(r) CZ(F), i.e., such that the behavior of F is included in that of rF The Behavior Inclusion Procedure is a decision procedure for A. Proof: (I) It is obvious that if (3(r) C(r) then a C, i.e., that the algorithm yields "yes. " (II) We assume that aC&, i.e., that the algorithm yields "yes," and prove that t(r)C ~3(). Let r = (s, G, R, P) = P * and let "a be the set of P-projections of F-sequences of length 1 + a2a or less. By Theorem 2.2-3 = and j(r) = r(I), so we will assume that ac a and prove that (IIA) Let (cat [~t] be the subset of sequences of ((r) l [~(r) ] of length t + 1 or less. We will now establish by induction that for every t, at C t' Initial step: since by assumption aC6O and by definition X = ~a 2 and: a. a, so C G for k = a.2. 34

General step: we assume that akC ak for k 2 a. 2 and prove that ak+lC ak+l. Consider an arbitrary r-sequence [s](O,k + 1) for k' ao2a, Let [p](O,k + 1) = P~[s](O, k + 1) ]) By the inductive hypothesis there exists a r-sequence [s](O,k) such that P[-s](Ok) } = [p](Ok). We will show that there exists a complete state so satisfying the conditions (1) ~R[;(k), so] (2) P(s) = p(k + 1), i e., that there exists a F-sequence < [s](O,k), So > such that P( [s](O,k), so = [p](O,k + 1). It follows from the nature of the subset sequence generator construction that r has no more than 2 complete states, and hence the number of pairs of complete states < s,s > is no more than a. 2a Since k 2 ao2a there exist tl,t2 such that 0 < tl < t2 ~ a2 <k, s(tl) = s(t2) and s(tl) = s(t2) Let (3) [sl](o,Q + 1) = ([s](O,tl), [s](t2 + l,k + 1)) (4) [sl](O,R) - {[S](Otl), [S](t2 + ltk)} (5) [Pl](O, + 1) = ([p](O,tt), [P](t2 + 1, k + 1)) where Q = k - (t2 - t1). Note that (6) P([s](O,A + 1)) = [pLI(O,e + 1) (7) P [s1](O,9)3 = [P1](O,~) Because (s(tl) = s(t2) [s(tl) = s(t2)] we have that ([sl](o,a + 1) is a F-sequence) [sl;](Oe) is a F-sequence And since + 1 _ k there exists by the inductive hypothesis a F-sequence [s2](0,a + 1) 35

such that (8) P{['](o, + 1)} = [p1](O,d + 1). It follows from (7) and (8) that (9) P([s2](o,e)) = P({[s](o,9)) = [p1](O,9) and since r is semi-deterministic (Lemmas 2.1-4 and 2.2-1) we have that (10) [S2](0,Q) = [s](O, ). It follows from (4) that (11) 30(k) = s(k) and hence by (10) (12) sa(Q) = s(k) Since [s2](o0, + 1) is a F-sequence we have that R{(2(t), s2(l + 1)} and hence by (12) that (13) R (s (k), s2( + 1)}. Now by (8) and (5) (14) P({s2( + 1) 3 -p(k + 1). Conditions (13) and (14) show that s2(e + 1) satisfies conditions (1) and (2) and hence that S2(Y + 1) is the desired state So. (IIB) We have shown that if {cCc then for every t, ~tC t' It follows by the Infinity Theorem (Theorem 2.1-3) that if aCcOU, then 3B(F)Qc(P). As remarked earlier, this is equivalent to: if cCcl then 3(r)CB(F). This completes the proof of Theorem 2o3-1. 36

In formulating the Behavior Inclusion Procedure we have not attempted to minimize the computation required. Many simplifications will occur to anyone who uses this algorithm. For example, since any two elements of a complete state s C S must have the same projectionthe bound 1 + a-2 may be greatly reduced. Note also that if F is already semi-deterministic, it is not necessary to make use of r* in the proof, and the bound 1 + a.2i may be replaced by 1 + aa. The Behavior Inclusion Procedure may be used as the basis of a decision procedure for solvability. Let r = (s, G, R, P) be given. By definition r is solvable if every infinite sequence of P-states belongs to its behavior (Section 2.1). F = (S, S, R, P), where R(sls2) for all sls2 e Shas as its behavior the set of all sequences of P-states, Hence the behavior of r includes all infinite sequences of P-states, so r is solvable if and only if (D(r) c ~(F). By Theorem 2.3-1 the Behavior Inclusion Procedure is a decision procedure for behavior inclusion, so we have proved the following theorem. Theorem 2.3-2: Let r = (S, G, R, P) be a sequence generator and let ~(sl,s2) for all sl,s2 e S. The Behavior Inclusion Procedure applied to the pair < (S, S, R, P), r > is a decision procedure for the solvability of rF. When the Behavior Inclusion Procedure is applied first to the pair < r, r > and then to the pair < r, r > the result is "yes" in both cases if and only if @(r) = 5(1) v This "behavior equivalence procedure" may be used to reduce the number of complete states of a sequence generator so as to obtain a behaviorally equivalent sequence generator with fewer states, Consider r = (S, G, R, P). We will say that two complete states s1 and s2 are "behaviorally equivalent" if BL(s, (si), R, P)] = C[(S, (s23, R, P)]. Let F be the result of identifying all behaviorally equivalent states of F. 37

F will in general have fewer states than r and yet 3(r) = dB(r). Moore' s concept of two sequential machines being indistinguishable by any experiment is a special case of our concept of behavioral equivalence, and the above process of identifying behaviorally equivalent states is analogous to the "reduction procedure" of Moore, 1956, and Mealy, 1955. We have examples to show that the procedure we described does not always lead to a behaviorally equivalent sequence generator with a minimal number of complete states and that the procedure of Moore and Mealy does not always lead to a behaviorally equivalent sequential machine with a minimum number of internal states.* * Moore and Mealy showed that identifying behaviorally equivalent states of a sequential machine does lead to a minimum number of internal states if either the sequential machine is "strongly connected" (Moore) or it has exactly one generator (Mealy). The counter-examples mentioned above are not strongly connected and have more than one generator. 38

3. SEQUENCE GENERATORS WITH TWO PROJECTIONS 3.1. DEFINITIONS The results of the last section concern primarily one projection of a sequence generator. In the present section we will work mainly with twoprojection sequence generators. Definition- r = (S, G, R, P, Q) is h-univalent (h = 0, 1, 2,...; c) if for every two infinite F-sequences [sl](O,cw), [s2](0,c,) and any time t, if P([sl](O,t + h)) = P([s2](O,t + h)) then Q(sl(t)) = Q(s2(t)). (By definition, t + n3 = W.o) Note that h-univalence is essentially a property of a set of infinite sequences of pairs < p,q >, and hence a property of dB3(r), the infinite behavior of r. As a consequence the following lemma holds. Lemma 3.1-1: Let r = (S, G, R, P, Q) and r = (S G, R, P, Q). If W(r) = W(r), then r is h-univalent if and only if F is h-univalent. This lemma, together with Corollary 2.1-1 and Theorem 2.2-3, immediately yields Lemma 3.1-2: Let r = (S, G, R, P, Q). The following three conditions are equivalent: (1) r is h-univalent, (2) r* is h-univalent, and (3) rt is h-univalent. There is a close connection between zero-univalence and semi-determinism which'is brought out by the following lemma. Lemma 3 1-3: (a) Let r ( (S,G,R,P,Q) and r = rt. r is 0-univalent if and only if for any two finite F-sequences [s1](O,t) and [s2](O,t), if P([sl](O,t)) = P([s2](0,t)) then Q([sl](O,t)) = Q([s2](0,t)). (b) Let r = (S,G,R,P) and r = rt. r is semi-deterministic if and only if for any two finite P-sequences, [sl](O,t) and [s2](0,t), if P([sl](o,t ]) = P([s2](0,t)) then [sl](O,t) = [s2](0,t)o 39

Note that the sequence generator of part (a) of the lemma has two projections, while that of part (b) has one projection. Part (a) may be established by using Corollary 1.3-3 and the definition of univalence; part (b) follows from Corollary 153-3 and Lemma 2.1-4b. It follows from Lemma 3.1-3 that for any projection Q, if (S,G,R,P) is semi-deterministic then (S,G,R,P,Q) is O-univalent. The converse is not in general true, but the following lemma asserts a connection between the O-univalence of a sequence generator and the semi-determinism of a related sequence generator. Lemma 3.1-4: Let r = (S,G,R,P,Q) and let r*t = r = (s, G,R,P,Q). r is zerounivalent if and only if (S,G,R,P) is semi-deterministic. It might seem that since r is the reduced form of the subset sequence generator of r, it would follow immediately by Lemma 2.2-1 that if r is O-univalent then (S,G,R,P) is semi-deterministic. This is by no means the case. It can be shown from Ltemma 2.2-1 by means of the definition of the subset sequence generator operation that (S,G,R,PxQ) is semi-deterministic, while the conclusion of Lemma 3.1-4 is that (S,G,R,P), which is a different sequence generator, is semi-deterministic. For any projection Q, if a sequence generator (S,G,R,P) is semi-deterministic, then (S,G,R,PxQ) is semi-deterministic, but the converse is not in general true. Proof of Lemma 3.1-4 ("Only if" part): We assume that r is O-univalent and prove that (S,G,R,P) is semi-deterministic. (I) We will use three sequence generators in the proof besides r. These are F = (S,G,R, P,Q)I F = (SGR,PxQ), and F = (S,G,R,P). We will first establish some results that will enable us to use Lemma 3.1-3a on r and Lemma 3,1-3b on r and r, (A) By construction r = rt and by Lemma 3.1-2 r is O-univalent. (B) By construction Fr rt and by Lemma 2.1-1 r is semi-deterministic. (C) By construction r = rFt. Our task is to prove that r is semi-deterministic. (II) Since r, r, and r have S, G, R in common, the sets of r-sequences, 40

F-sequences, and r-sequences are identical with one another. Consider now any two finite F-sequences [s1](O,t) and [s21(0,t); these are also arbitrary r-sequences and arbitrary r-sequences. Using (IA) and applying Lemma 3.1-3a to r, we obtain (1) If P([sl](o,t)) = P([s2](0,t)), then Q([sl](O,t)) = Q([s2](0,t))o Using (IB) and applying Lemma 3.1-3b to r, we obtain (2) If P([s1](O,t)) = P([s2](O,t)) and Q([sl](O,t)) = Q([s2](Ot)), then [s1 ] (O,t) = [s2](o,t). Combining (1) and (2) and noting that [s1](O,t) and [s2](0,t) are arbitrary F-sequences, we get (3) For any two finite P-sequences [sl1](,t) and [s2](0,t), if P([sl](O,t)) = P([s2](0,t)), then [sl](O,t) = [s2](0,t). Using (3) and (IC) and applying Lemma 3.1-3b to r, we obtain (4) Tr is semi-deterministic, which completes the proof of the "only if" part of the Lemma. ("If" part): We assume that (S,G,IR,P) is semi-deterministic and prove that F is O-univalent. Since every complete state of P is F-accessible, by Lemma 2.1-4b we have that for every finite sequence of P-states [p](O,t) there exists at most one F-sequence [s](O,t) such that P[s(0,t) [](,t) =. Hence for any two F-sequences [sl](O,cj), [s2](0,c) and any time t, if P([sl](O,t)) = P([s2](0,t)), then s1(t) = s2(t). Since a projection is a (single-valued) function, we have that if P( [sz](O, t + 0)) = P( [s2](o,t + o)) then Q(sl(t)) = Q(s2(t)), so P is O-univalent. P = r-t, and by Lemma 3.1-2 r is O-univalent,,This completes the proof of Lemma 3.1-4. 41

We next apply this lemma to an example. Consider r = (S,G,R,P,Q) of Fig. 8(a). Note that the complete states s2 and s4 have the same projections (po and qO) and stand in the same relation to state so. Thus the two F- sequences, SO) S4, SO So, S2, So have the same sequence of P-projections Po, Po, Po and hence (S,G,R,P) is not semi-deterministic. These two F-sequences do have the same sequence of Q-Projections qod q2, gq and in fact F is O-univalent. By Lemma 3.1-4 (S, G, R, P) of Fig. 8(b) must be semi-deterministic. An examination of the states (S, G, R, P) shows that it is deterministic, so a fortiori it is semi-deterministic. (The determinism of (S, G, R, P) will be discussed after Lemma 3.2-3 below.) Note that the main difference between r and F*t in Fig. 8 is that the two states S2, s4 of r have become a single state (s2, s43 of rF*t Definition: r = (S, G, R, P, Q) is uniquely solvable if (1) (S,G, R, P) is solvable and (2) (S, G, R, P, Q) is o-univalent. We remarked earlier that h-univalence is essentially a property of the infinite behavior of a sequence generator, and this remark applies to unique solvability as well, Thus r is uniquely solvable if and only if for any infinite sequence of P-states [p](O,c) there: is exactly oneisequence of Q-states [q](O,w) such that the sequence < p(O), (O) >, < p(l), () > o o 42

s4 Io SSo 2 PO' q2 PO, qo Po' q2 S, Pl'ql Pl1Q3 (a) Is:: " s: Poi, q2 (b) Fig. 8. Illustration of Lemma 3.1-4: r is zero-univalent if and only if (S,, G, P) is semi-deterministic. (a) r = (S, G, R, P, Q). r is zero-univalent and uniquely solvable, but (StG,R,P) is not semi-deterministic. (b) r*t = r = (s, G, R, P, Q). (S,,, P) is deterministic, and a fortiori semi-deterministic. 43

belongs to P(r). To put the point in another way: a sequence generator r = (S, G, R, P, Q) is uniquely solvable if and only if its behavior defines a single-valued function (transformation) from the set of all infinite sequences of P-states into the set of all infinite sequences of Q-states. Various consequences follow from this fact, The result of replacing "h-univalence" by "uniquely solvable" in Lemma 3,1-1 is also a lemma. A similar remark holds for Lemma 3.1-2 except that St may have fewer P-states (values of p) than r. It was shown in Section 2,1 that well-formed nets and deterministic sequence generators are equivalent in a certain sense: for every wf.n, there is a corresponding deterministic sequence generator and vice-versa. The wf,n, gives the structure of an automaton while the associated deterministic sequence generator gives the corresponding complete state diagram. An analogous relation holds between the well-behaved nets of Burks and Wright, 1953, P. 1358, and uniquely solvable sequence generators. Consider any net and label all its non-input nodes as output nodes. The procedure of Section 1,2 will associate with this net a sequence generator which is uniquely solvable if and only if the original net is well-behaved, 3,2. THE DISPLACEMENT OPERATOR AND THE i-SHIFT OPERATION We will first define a displacement operator Xk which applies to sets composed of finite sequences of pairs and/or uw-sequences of pairs. Roughly speaking, O k has the effect of leaving the first element of each pair where it is and displacing the second element of each pair k places to the rightb Displacing the second element of the first pair k places to the right will leave k gaps, since the first pair is not preceded by any pair. It will be convenient always to fill these gaps with the same element; we will use the null set IA for this purpose~ 44

Definition: Let the universe of discourse V consist of all finite sequences of pairs and all c-sequences of pairs and let A be the null set. The operator 0o (without superscript) is defined to apply to any sequence of V as follows: d0 (< Xo, < X1 Y1 >, < x,, 2, Y2 >, < x3, y3 >,.. ) = (< Xo, A >, < xl, yO >, < X2, Y1 >, < x3, Y2 >,.~ ~ ) (< Xoy, Yo >,o < Xn-,y Y>n-, < Xn Yn- < Xn Yn >) (< X0, A >, < x1, yo >,, < Xn-, Yn-2 >, < Xn, Yn-i >). The operatore& is extended to apply to an arbitrary set a of V by 19(ao) = (vl (u) [u C a & v = (u)], where v and u range over elements of V. Finally, we define k, k = 0,1,2... to apply to an arbitrary set a of V by the induction (-) = a i+1(a) = i(a,~ is called the displacement operator. We next define a shifting operator which may be applied to an arbitrary sequence generator r = (S, G, R, P, Q) to produce the i-shifted sequence generator r F' = (S, G, R, P, Q). The effect of this operation is to displace the behavior of r, so that the behavior of r, i.e., (F) equals the displaced behavior of r, i.e,,')' [~() ], as is shown in Lemma 3.2-1 below. To help make clear the definition of ra, we will make some remarks about Fl. Extend Q to apply to A, so that Q(A) = A. The generators of rl arCe the pairs < A, s >, where s belongs to G. Suppose Son Sol S2, 53, S4 45

is a F-sequence with the resulting behavior element < Po, qo >, < Pl, ql >, < P2, q2 >, < P3, q3 >, < P4, q4 >. Then < A, s >, < So s >, < s1, S2 >, < S2, S3 >, < S3, s4 > is the corresponding Fl-sequence with the resulting behavior element < Po, A >y < Pl, qo >, < P2Y ql >, < P3s q3 >, < P4, q3 >o rP may be obtained by shifting r, times in this way. Definition- The unit-shift operation, denoted by "O," applies to any sequence generator r = (S,G,R,P,Q) and produces a sequence generator r0 = r = (S,G,R,P,Q) defined as follows. (We wish to assume throughout that A is not an element of S; if it is, S should first be redefined so it is not,) The elements of G are all the pairs < A, s > where s belongs to G: < A, s > c G - scG (2) The elements of S are all the pairs < sl, s2 > which either belong to G or are connected by the direct transition relation R: S = (< sl, s2 > < sl, s2 > G v R(sl, s2)) (3) Two complete states < sl, s2 > and < S3, s4 > of S stand in the direct transition relation R if and only if S2 = s3s R(< sl S2 > < S3 S4 >) [ < Sly S2 > < S3, S4 > C S & s2 = S3]. (4) The P-projection of a complete state < sl, s2 > of S is the P-projection of its second element s2: P(< si, s2 >) = P(s2), where < sl, s2 > E SO

(5) Extend Q to apply to A, stipulating that Q(A) = A. The Q-projection of the complete state < sl, s2 > of S is the Q-projection of its first element: Q(< sl, s2 >) = Q(sl), where < sl, s2 > C S. The i-shift operation, denoted by "X," applies to any sequence generator r = (S,G,R,P,Q) and produces a sequence generator rP; it is defined in terms of the unit-shift operation by means of an induction: r~ = r rO+ = (r<)o The e-shift construction is illustrated in Fig. 9. Part (a). shows a sequence generator r with two projections, while part (b) shows l, the result of shifting r one unit of time. Note that both r and rl are in reduced form; this is a special case of the general fact that if r is in reduced form then Ih is in reduced form. Note next that the generator < A, so > can only occur as the first state of a P1-sequence. Since r1 is defined by induction on rFO it follows by induction that if a F -admissible complete state occurs in some Fe-sequence at a time T < 0 then all occurrences of this state are at time T. Thus the FP-admissible complete states are partitioned into two sets, those that occur only before time X, and those that occur only at time 2 or later. The i-shift operation is of interest because it shifts behavior in the same way the displacement operator o Q does. Compare the behaviors of r and Fl. The behavior element [an element of <(,(r) ] (1) < Po, qo >, < Po go >, < P, ql > P, < Po, o > is derived from the F-sequence So, So, Sln Sil, So 47

PO;-A Pqo l (a) <A; So>> <Sl' So> P'IO PO Ilo <sO, S> <Si Sl> (b) Fig. 9. Illustration of the i-shift construction, for Y = 1. In accordance with Lemma 3.2-1, VD[~(rF)] O- (rp). (a) r = (s, G, R, P, Q); (b) l1 (unit-shifted sequence generator of F). 48

The corresponding Fl-sequence is < A, so >, < So, so >, < So, s1 >, < sl, si >, < sl, so >, which gives rise to the behavior element [an element of 3(r1) ] (2) < po, A >, < p, >, <, qq, < 1,o >, < p, q >, < P, ql >. Note that this last sequence (2) is the result of displacing sequence (1) by one unit. This is an example of the general fact that ((rl) = ~[ 3(r) ], which is a special case of the following lemma. Lemma 3.2-1: Let r = (S,G,R,P,Q). Then (a) o2)[(r)] = ~(r) (b) 7 9 [=(r)] ( r) Proof: (IA) We prove- first that a[) V[ (r) ] -= (r<>). Let r< = - = (S,G,R,= It follows from the definition of the unit shift operator: that there is a one-one correspondence between the set of infinite F-sequences and the set of infinite F-sequences with corresponding sequences being of the form (1) So, S- $ 2, S, e ~e (2) < A, so >, <'So, s_ >, < sl, s2 >, < s2, ss >,. v. When P x Q is applied to (1), we get (3) < Po, gO >, < Pl, ql >, < p2, 2 >, < P3, q3 >, as an element of @e(r), and when P x Q is applied to (2), we get (4) < Po, A >, < p, qo >, < P2, q~ >, < P3, q2 >, - as an element of AV(I). By definition of o, 49

N[(3)] = (4), Hence (IB) Applying mathematical induction to result (IA), we get (IIA) An argument similar to that of (IA) may be given for finite F-sequences and finite F >-sequences. When the result is combined with result (IA), we get O[g(r) ] = ~(r~). (IIB) Applying mathematical induction to (IIA), we get w2 [@(r)] = ~(r1)o Corollary 3.2-2: Let = (S,G,R,P,Q) and r P - F = (S,c,R,P,Q). [r is (a + h)-univalent] ((S,G,R,P) is solvable) (r is uniquely solvable) if and only if [Fr is h-univalent] [(S,G,R,P) is solvable) (Fr is uniquely solvable). This corollary is illustrated by Fig. 10. Consider r of this figure. It was shown in Section 2.1 (in the paragraph preceding Lemma 2.1-4) that (S, G, R, P) is solvable. Also, r is unit-univalent. To see this, observe that every immediate successor (by the direct transition relation R) of a given complete state s has the same P-projection; e g., R(so) = (so,sl) and P(so) = P(sl) = Po. Since (S, G, R, P) is solvable and r is unit-univalent, r is uniquely solvable. Turn now to rl, the unit-shifted sequence generator of P. Since (S, G, R, P) is solvable and r is unit-univalent and uniquely solvable, by Corollary 3.2-2 Cl (less its last projection) must be solvable, and r 1 must be zero-univalent and also uniquely solvable, 50

(a) " PO, ql <SO. SO <SI, 2> 2 -S<> 63,, s3> PO;A (b) Fig. 10. Illustration of Corollary 3.2-2. [r is 1-univalent] (r, less its last projection, is solvable] (r is uniquely solvable) if and only if [Il is O-univalent] (rl, less its last projection, is solvable) ( Fl is uniquely solvable). (a) r = (S, G, R, P, Q). (S, G, R, P) is solvable but not deterministic. r is unit-univalent and uniquely solvable. (b) ~rl the unit-shifted sequence generator of r. Fl, less its last projection, is solvable, but not deterministic, Cl, is zero-univalent and uniquely solvable. 51

Lemma 3.2-3: Let r = (S,G,R,P,Q) and rh*t = = (, GRP, Q)o Then (a) if r is h-univalent for some finite h and (S,G,R,P) is solvable, then (SGRP) is deterministic (b),) h[8n(r) ] =(J(f). Proof- (IA) We will prove first that (S,G,R,P) is solvable. It is given that (S,G,R,P) is solvable. By Corollary 3.2-2, Lemma 2.2-4, and Lemma 2.1-4a, (S,G,R,P) is solvableo (IB) We prove next that (S,G,R,P) is semi-deterministic. It is given that r is h-univalent. By Corollary 3.2-2, 1h is 0-univalent. By Lemma 3.1-4, (S,G,R,P) is semi-deterministic. (IC) It follows from Lemma 2.1-4b and the definition of solvable that if every complete state of any sequence generator r = (S,G,R,P) is F-accessible, then r is deterministic if and only if r is both semi-deterministic and solvable. Applying this principle to (S,G,R,oP) and using (IA) and (IB), we conclude that (SG,R,P) is deterministic This proves part (a) of the lemmao (II) By Lemma 3.2-lb (1) h Lh[w(r) ] = 63(rh) By Theorem 2.2-3 3(rh) - ((rh*) and hence (2) CDo(rh) = e(F(h*) But by Corollary 2.1-1 (3 cu h) ( h *) = (?h*t). Combining (1), (2), and (3) gives part (b) of Lemma 3.2-3 and completes the proof of the present lemmao We may apply this lemma to Fig. 8. As noted in Section 3.1, (S,G,R,P) is not semi-deterministic but (S,G,R,P,Q) is O-univalent. It is easy to see that (S,G,R,P) is solvable, Applying Lemma 3.2-3 with h - O, we conclude that (S,G,R,P) is deterministic and that fW(r) = ~t0(r)o These two facts may 52

be confirmed by inspection of Fig. 8(b). Actually (r) = d3(F) in Fig. 8, i.e., the finite behaviors of r and r are equal as well as the infinite behaviors. There is a variant of Lemma 3.2-3 which covers this point. Since our main interest in the present section is in infinite behavior, we will merely state this result without proof. Let F = (S,G,R,P,Q) be h-univalent and (S,G,R,P) solvable; then Fh* less its Q-projection is deterministic, h[e(F) ] =43(h* ), and if F is in reduced form then C(rh*) = 3B( h*t). Figure 11 also illustrates Lemma 3.2-3. We begin with r = (S, G, R, P, Q), < A, s3L 11 s F<siSO isFure10 (s pr ci<osO, S1>r <ss, s3> i o CQ1 PO, C'O Fig. 11. *l t where r is Figure lO( a). * and tl (less their last projections) are not deterministic, but Cl*t ~less its last projection) is deterministic. l[C3(1F) ] = 5~(1l t). This illustrates Lemma 3.2-3. 53

where F is unit-univalent and (S, G, R, P) is solvable, Lemma 3.2-3 tells us that rl*t (less its last projection) is deterministic, and also that )l[u)(rp) ] = ~~(rl*t)o [rl is shown in Fig. 10(b); it has 12 complete states. Pl* has 28 states, but only 6 of these are Pl*-admissible, so Fl*t has only 6 states. ] 3.3. TIME-SHIFT THEOREM We will prove now a lemma which is used in proving one of our main theorems (the Time-shift Theorem) and in validating a procedure for h-univalenceo Lemma 3553-1 (Fixed Bound Lemma): Let r = (S, G,R,,P,Q) be a sequence generator with k r-admissible complete states. Then r is o-univalent if and only if it is k -univalent. Proof: The proof in one direction is obvious, To prove that if r is c-univalent it is k2-univalent, we consider any two F-sequences [sl](O,wu), [s2](O,w) and any time t such that P( [sl](O,t + k2)) = P([s2](0,t + k2)). Since there are k2 distinct pairs of complete states, there are two times tl, t2 such that t' t1 < t2 5 t + k, sl(tl) = sl(t2), and s2(tl) = s2(t2). Form the sequences [S3](O,)) = [s l](O,t2 - 1), [Sl](tl1t2 - 1), [Sl](tlt2 - 1),. o CS4](0,i) = [S2](,t2 - 1), [S2](tl1t2 - 1), [s2](tl,t2 - 1),. o These are both P-sequences since they are composed of segments of P-sequences linked by the direct transition relation. Since P([sl](O,t + k2)) = P([s2](O,t + k2)) we have by construction P([s3](0,co)) = P([s4](O0,c)). Because r is wo-univalent, Q([S3](0,a0)) = Q([s4](0,0C)) Then by construction Q(sl(t)) = Q(s3(t)) and Q(s2(t)) = Q(s4(t)), and so Q(sl(t)) = Q(s2(t))v Hence r is k -univalent. Consider a sequence generator r = (S,G,R,P,Q). If (S,G,R,P) is deterministic 54

then (S,G,R,P,Q) is uniquely solvable, but the converse does not in general hold [see Fig. 8(a)]. We noted earlier (Section 3.1) that unique solvability is essentially a property of the infinite behavior of a sequence generator. This suggests the question: what is the relation of the behaviors of uniquely solvable sequence generators to the behaviors of deterministic ones? This question is answered by the following theorem, which shows that for every uniquely solvable sequence generator there is a deterministic sequence generator whose infinite behavior is a displacement of the infinite behavior of the given sequence generator. In Section 4 we will introduce a concept of "computation." Using this concept, the result may be expressed: the behavior of every uniquely solvable sequence generator can be computed by a finite automaton. Theorem 3.5-2 (Time-shift Theorem): Let r = (S,G,R,P,Q) have k F-admissible complete states and let rk t -= = (S,G,R,P,Q). Then (a) if r is uniquely solvable, then (S,G,R,P) is deterministic 2 (b) oS (k ) 3 r Proof: This follows immediately from the definition of uniquely solvable (Section 3.1) Lemma 3.2-3, and the Fixed Bound Lemma (3.3-1). Consider the Time-shift Theorem in relation to r of Fig. 10(a) and the derived Cl*t of Fig. 11. r is uniquely solvable and has 4 r-admissible complete states. Then the Time-shift Theorem tells us that le6*t, less its last projection, is deterministic. This is clearly so, for rl*t, less its last projection, is deterministic, and further applications of the 0-shift operation will obviously not destroy this property. We pause to note an analogue of the Time-shift Theorem in which the shifting takes place in the opposite direction. The displacement operator e was defined to produce a right-shift of the Q-projections of a F-sequence; that is, it shifts the Q-projections ~ steps later in time, leaving the 55

P-projections as they were. One could easily extend this operator to cover shifts in the opposite direction (i.e., with the Q-projections moved earlier in time); this could be symbolized by using the same operator o, allowing negative as well as positive integer values for Q. Similarly, the ~-shift operator can be extended to produce shifts of the Q-projections to the left; again, we can use the same symbolism r9 and signify left-shifts by negative values of B. We then get the following partial analogue to the Time-shift Theorem. Let r = (S,G,R,P,Q) be a sequence generator, with (S,G,R,P) deterministic. Let r, where i is negative. Then r is uniquely solvable, and 2[f(r) ] = ~u(- ). Combining this with the Time-shift Theorem, we obtain the following result: the set of infinite behaviors of uniquely solvable sequence generators is exactly the set of displaced infinite behaviors of deterministic sequence generators. It is not obvious from the definition that the class of h-univalent sequence generators is decidable. However, this is in fact the case, as we will now show. h-univalence Procedure (where h is any non-negative integer of c): Let r = (S,G,R,P,Q) be the given sequence generator. Find k, the number of admissible complete states, by the Reduced Form Algorithm. Let m = min (h,k2). Form F = r= (S,G,R,P,Q). Answer "yes" or "no" as (S,G,R,P) is semideterministic or not. Theorem 3.3-3: The h-univalence procedure is a decision procedure for the class of h-univalent sequence generators. Proof: We will use the notation of the algorithm. By the Fixed Bound Lemma r is h-univalent if and only if r is B-univalent. By Corollary 3.2-2 r is i-univalent if and only if r is O-univalent. By Lemma 3.1-4 r is O-univalent if and only if (S,G,R,P) is semi-deterministic. As noted in Section 2.1, it is obvious from the definition of semi-determinism that there is a decision 56

procedure for the class of semi-deterministic sequence generators. This completes the proof of the theorem. It can be shown that the following is a characterization of h-univalence. Let r = (S,G,R,P,Q), k the number of I-admissible complete states, and i = min(h,k2). Then r is h-univalent, if and only if, for any two F-sequences [sl](O,w) and [s2](0,cO) and any time t - k2, if P([sl](O,t + 2)) = P([s2](O,t + O) then Q(sl(t)) = Q(s2(t)). This characterization can be made the basis of a decision procedure for h-univalence which is more efficient than the one we have given. Since unique solvability is defined in terms of solvability and n-univalence (Section 3.1), by combining the c-univalence Procedure with the decision procedure for solvability of Theorem 2.3-2, we obtain a decision procedure for unique solvability. 57

4I GENERALIZATIONS AND APPLICATIONS 4. 1. COMPUTATION We will next define a concept of "computation" which corresponds more closely to the way a digital computer is used than does the concept of behavior; essentially the same concept is defined in Burks, 1960. Computers are employed to produce answers to questions; the questions go in as inputs, the answers appear as outputs. Generally speaking, the answer is not produced immediately, but only after a time delay. Moreover, except in realtime computation, the answer will not appear at the same rate as the input information is received. In contrast, all outputs of a computer are part of its behavior, whether they contribute to the answer or not. For these reasons the concept of behavior does not fit the question-answer mode of using a computer as closely as the concept of computationvto be defined. Computation differs from behavior in that in the case of computation not all -"output states" are interpreted as part of the answer, but only those selected as the "computed output states" by the sequence generator itself. The concept of computation reflects the fact that in our theory the internal operations of a sequence generator are strictly correlated to the basic time scale, while the computed outputs are not. In the definition of computation we will need the Co-operator (selection operator). Suppose ix expresses some condition on the natural numbers. 1t(pxx)Tx" designates the smallest number satisfying the condition Ox if there is one; if no number satisfies Ox,then t"(lx)Ox"t is undefined. For example, (px) (x > 32) = 10, while?(~x) (X2 = 2) " is undefined. Definition: Let r = (S,G,R,P,Q,C) be a sequence generator with the projection C having only the two values 0, 1. Let [s](O,~) be an arbitrary 59

infinite r-sequence and define x y(t) = Q(s([ix) ( C(s(y)} = t + 1}); y=O 00 note that if Z C(s(y) is finite then y(t) is undefined for any W l y=O W t => o Cs(y)). If Z C(s(y) I is unbounded, then the sequence Y=O y=O < P(s(O)3, y(O) >, < P(s(1) ), y(1) >,. 00 is an infinite computation element of r. If Z C[s(y)) = k (k being finite),. y=O then the sequence < P(s(O) 3, y(O) >,...,< P(s(k - 1), y(k - 1) >, <P{s(k) } >, < P{s(k + 1) >, is a finite computation, element of r. The computation of r, denoted by C(r), is the set composed of all infinite computation elements and all finite computation elements of F-. An example will help make the concept of computation clear. Contsider a sequence generator r which has only two infinite F-sequences. These are shown below, together with the projections of each and the derived sequences [y](O,k). I[S](0,W) -= slyS2o, Sl, s2, S3,.. P([sl](O,co)) = Po, Pi, Pi, P3, PS, P3, o Q( [s](O,~C)) = q, q, l, ql, ql, ql, CUS1 4) 0 go= 0, 1,, 0, 0,.. [71](o,z) - go, ql [S2](0,C) So, Slo S2, S4Y S5 Ss4, S5, S4, S5, ~ P([s2](o,~)) = PO, Pi, Pi, P3, Ps, P3, P5, P3, P5, Q([s2](0,()) = qo, qo, q1, q2, q3, q2, q3, q q3, C([s1](O,c)) = 0, i, 1, 0, i, 0, i, 0,,. o o [Y2](0,a) = qo, q, q5, q3, q, 60

Hence the computation C(r) is the set consisting of the two sequences < Po, Po >, < Pi, ql >, < P1 >, < P3 >, < P3 >, < P3 >, < Po, o >, < i, qo >, <Pi, qs >, < P3 q3 >, < P5, q3 >, Note that the first of these is a finite computation element of r while the second is an infinite computation element of r. We will now show that the concept of computation is a bona fide generalization of the concept of behavior. Let a be the class of all two-projection sequence generators. Let 5 be the class of all three-projection sequence generators r = (S,G,R,P,Q,C) such that C has the values 0O li.and every element of C(r) is infinite. Then the class [fr(r) IrFea of infinite behaviors of elements of a is a proper subclass of the class (0(r) lrcF of the computations of elements of B. To see that CFe(r) real -a 0(r)Creels note that for each element r = (S,G,R,P,Q) of a: there is an element = (S,G,R,P,Q,C) of 8 in which C(s) = 1 for every seS, so that m(r) = C(r). That the inclusion of [(&(r) Irea in (C(r) IreF) is a proper one is shown by Fig. 12. In Fig. 12, P(so) = P(s2) = O, P( sl) = P(s3) = 1, P(s) = Q(s) for every s E S, C(so) = C(sl) = 1, and C(s2) = C(s3) = O. The sequence generator I of this figure has the property that CCrl) f Ie@(r) I r~at. To see this, note that since P(s) = Q(s) for every seS, the computation C(F) consists of all infinite sequences of the form where P(s) is either zero or one. By the Fixed Bound Lemma (3.3-1) no uniquely 61

solvable sequence generator can haveC (P) as its behavior, and since, as we remarked in Section 3.1, unique solvability is essentially a property of the infinite behavior of a sequence generator, no sequence generator can have C(M) as its infinite behavior. Since w-univalence and unique solvability apply to sequences of pairs (Section 3.1), these concepts may be extended to cover the computation of a sequence generator; the computation C(r) of the sequence generator of Fig. 12 is uniquely solvable. 0,0 0d,0 1 I I O0 [ 1 70 Fig. 12. r (s,G,R,P,Q,C). No sequence generator can have C(r) as its infinite behavior. Since computation is a bona fide generalization of behavior, the existence of certain algorithms for behavior (Section 2.3) does not guarantee the existence of corresponding algorithms for computation. It is not known whether either of these two algorithms exist: an algorithm to decide whether the computation of one sequence generator is included in the computation of another, a decision procedure for the computational equivalence of two sequence generators. We do have an algorithm to decide of any pair of sequence generators r = (S,G,R,P,Q,C) and r = (S,G,R,P,Q,C) such that C(r) is c-univalent, whether the computation:(r) is included in the computation:(r) or not, but this 62

algorithm and its justification are too long and involved to be included here. There is a procedure for deciding of a sequence generator r = (S,G,R,P,Q,C), where C has only the values O, 1, whether all, some but not all, or none of the elements of C(m) are infinite. One first finds the reduced form rt. Note that C(rt) = C(r) for any r. Then each non-repetitive cycle of complete states of rt is examined to determine whether C(si) = 1 for any state si of this cycle. If C(si) = 1 for some state si of this cycle, there will be an infinite Ft-sequence made of iterations of the cycle, which rt-sequence will give rise to an infinite computation element of C(rt) and hence of 6(F). On the other hand, if for every state si of a cycle C(si) = O., then there is an infinite rt-sequence made of repetitions of this cycle which will give rise to a finite computation element of C(r). Let us now ireturn to the Time-shift Theorem (3.3-2) and extend it to cover the case of computation. Let r = (S,G,R,P,Q,C) have k F-admissible complete states and let C have only the values O, 1. The Y-shift operator was defined for two-projection sequence generators, but it may easily be extended to cover sequence generators with a computation projection C in the 2 following way. Form (S,G,R,P,QQxC); apply the k 2-shift operator to it with the modification that < A, O > is the QxC projection of those admissible complete states that occur before time k2 (cf. Section 3.2). Call the result (S,G,R,P,QxC). Then form (SGRPQC)*t = r = (S,G,R,P,Q,C). Now apply Lemma 3.2-3 and 3.3-1, noting that a displacement of the infinite behavior of a sequence generator with a computation projection does not alter its computation, since the behavior includes the computed output. The net result of all this is as follows. Given a sequence generator r = (S,G,R,P,Q,C) with C having the values O, 1, there is an effective procedure for constructing r = (S, G,R,P,Q,C) such that:

(a) If (S,G,R,P, QxC) is uniquely solvable, then (S,G,R,P) is deterministic, (b) C(r) = C(F). When the foregoing statement is applied to the case where C is always one, it implies that the infinite behavior of any uniquely solvable sequence generator is the computation of a deterministic sequence generator. This justifies the statement made prior to the Time-shift Theorem (353-2) that the infinite behavior of any uniquely solvable sequence generator can be computed by a finite automaton. We will illustrate this with an example (Fig. 13). We begin with r of Fig. 10(a), which is uniquely solvable (but not deterministic). In this case a unit-shift, followed by an application of the * and t, suffices to produce a deterministic sequence generator rl*t, shown in Fig. 11. r of Fig. 13(a) is a simplification of this. To r we now add a projection C which is 0 for the generators, 1 otherwise, obtaining r of Fig. 13(b). r is a deterministic sequence generator which computes the infinite behavior of the original r, i.e., C(t) = ~C(r). By a slight generalization of the process described in Section 2.1, we can pass from the deterministic sequence generator r to a finite automaton and to a w.f.n. The w.f.n. which produces the computation C(r) is shown in Fig. 13(c). It is perhaps worth noting that the computation of this net [Fig. 13(c)] is the infinite behavior of the net of Fig. 2(a). The concept of unique solvability may be generalized to cover computation. Let r = (S,G,R,P,Q,C) be a sequence generator, C having the values O, 1. The computation C(rF) is "uniquely solvable" if for each infinite sequence of P-states [p](O,co) there is exactly one element of C(r) which contains [p](O,n) (i.e., which is composed of this sequence of P-states together with zero or more Q-states). The motivation behind the concept of a computation being uniquely solvable is this. We may think of a sequence generator with an input projection P, an output projection Q, and a control projection C as specifying a computational relation between infinite input sequences and computed 64

P1, A I O pl)AyO ~2 S3 2 3\\I~ ~r/~ O."C11 ~ —---------— ~ —-Q~ P1.9O j C0, ol, (0111...) output 0\1 (a) (b) (c) Fig. 15. (a) f' (SGRPQ), which results from Il*t of Fig. 11 by identifying and re-naming behaviorally equivalent states. F, less its last projection, is deterministic.g(I') =6(rl*t). (b) = (SGRPQC), which results from P by adding a control projection C(~O) = C(~1) = 0,9 C(2) = C(~3) 1. C(r) - "0(v), where r is Fig. 10(a). (c) A net which has the computation C(hO.

output sequences, and the sequence generator does it uniquely if each input sequence determines exactly one computed output sequence. It is easy to construct examples of sequence generators r = (S,G,R,P,Q,C) such that (S,G,R,P,Q) is not uniquely solvable, though the computation C(r) is. Thus we are led naturally to the question: Is there a decision procedure which will tell whether the computation 6(r) of a sequence generator r - (S,G,R,P,Q,C) is uniquely solvable? It is also of interest to know whether the analogue of the Time-shift Theorem (3.3-2) holds for uniquely solvable computations, i.e., whether or not the following is true of a sequence generator r = (S,G,R,P,Q,C), with C having the values O, 1: if C(r) is uniquely solvable, then there is a sequence generator r = (S,G,R,P,Q,C) such that (S,G,R,P) is deterministic and C(r) = C(r). We do not know the answer to either of these questions. 4.2. FORMULAS AND SEQUENCE GENERATORS We will now discuss the relation of some formulas of symbolic logic to sequence generators. Because of limitations of space we will not give a detailed or rigorous treatment of the subject but will rely heavily on examples and will present theorems without proofs. The language L being considered here is a first-order monadic predicate calculus with a successor function and zero. The symbols of L are: an infinite list of monadic predicate variables A, B, C,...; an infinite list of individual variables t, tl, t2, ~..; the successor function'; the individual constant O; all truth-functional connectives; and parentheses. The individual variables range over natural numbers 0, 0', 0",.... The predicate variables range over predicates of natural numbers, i.e., over sets of natural numbers. Consider an arbitrary w.f.fo of L; the result of universally quantifying 66

all the individual variables of L is called an A-formula (arbitrary-formula). B(tl) - B(t2) is a w.f.f. of L, and so -(tl)(t2) [B(tl) B(t is an A-formula. (tl) (t2)[B(tl) - B(t"') ] means that for all times t1, t2, B is true at time t1 if and only if B is true at time t2 + 3. Note that since language L does not contain quantifiers, an A-formula is not a w.f.f. of L; this does not matter for our purposes. The extension of an A-formula with predicate variables B1, B2, ~ ~ ~, Bk is the set of all k-tuples of predicates which satisfy the formula, i.e., for which the formula is true of the natural numbers when Bi is interpreted as the i'th predicate of the k-tuple. We will regard a predicate, e.g., Bi, as an infinite binary sequence [s](O,w) in which s(t) is 1 or 0 according to whether Bi(t) is true or false. When predicates are viewed in this way, a k-tuple of predicates becomes an w-sequence of k-tuples or column vectors, i.e., a k by cl binary matrix. We will give some examples. (t1) (t2) [B(tl) - B(t2 ) is satisfied by 1111... but not by 1010..., for in the later case B(O) i B(O"'). The extension of (t) [B(O") & (B(t) - B(t"))] consists of all sequences of the form 1, xl, 1, 2, 1, x3, 1, 4,... The extension of (t) B2(O) & [Bl(t) - B2(t')]) consists of all two by omega matrices of the form Xo0 X1 X2 X3. ~ ~ 0 x1 X2 X3... Sequence generators without projections may be translated into a particular kind of A-formula, called an M-formula. For example, the sequence generator of Fig. 14 may be translated into 67

(t) [(B(o) & B2(0)) v (B1(o) & B2(0))] & I(Bl(t) & B2(t) & B7(t') & B2(t')) v (Bl(t) & B2(t) & B1(t') & B2(t'))}. The bracketed conjunct of this A-formula contains no individual symbol other than the constant zero; it tells us what the generators are. The braced conjunct contains no individual symbols other than t and t'; it tells what direct transitions are possible. Clearly, the set of infinite F-sequences of Fig. 14 O O0 0 1 0 [ B2 B B2 Fig. 14. r (s,G,R). equals the extension of the formula given above. Any A-formula consisting of a universal individual quantifier operating on a conjunction, the first conjunct having only zero as argument, the second conjunct having only one variable with at most one prime as argument, is called an M-formula (minimal formula). Our previous example illustrates the fact that any sequence generator r = (S,G,R) can be translated into an M-formula Owith k predicates by coding its states into binary k-tuples, the extension of Sbeing the set of F-sequences. Conversely, any M-formula!may be translated into a sequence generator r = (S,G,R) such that the set of infinite F-sequences is the extension of W. We will consider next two types of A-formulas more general than M-formulas. 68

Any A-formula of the form (t),(O, 0',..., ti) & )2(t, t,... t ), where Ji, J2, indicate the maximum number of primes of arguments of ~z and ~2, respectively, is a D-formula (decomposable-formula). "[B(O) & B(1) & ((B-) & Bt')) - B(t") ]"is a D-formula whose extension is the single infinite sequence 001001.... In Section 2.1 (immediately after corollary 2.1-1) we proved that there is no sequence generator r = (S,G,R) whose set of infinite P-sequences consists of the single sequence 001001.... It follows by the results described in the preceding paragraph that there is no M-formula whose extension consists of this sequence, i.e., there is no M-formula logically equivalent to the D-formula given above. Any A-formula with at most one individual variable is an O-formula (onevariable formula). (t) [B(O)D (B(t) - B(t')) ] is an O-formula whose extension consists of 111... together with all binary sequences beginning with zero. It can be proved that there is no D-formula with this extension, i.e., (t) [B(O).(B(t) - B(t'))] cannot be decomposed into a D-formula (t) (tz &;2) logically equivalent to it. Thus O-formulas are stronger than D-formulas, just as D-formulas are stronger than M-formulas. A-formulas are stronger than all these, for it can be proved that there is no O-formula with the extension of the A-formula [B(tl) v B(tj) ] v [B(t2) v B(t) ]. This formula is equivalent to the condition that a binary sequence cannot have both consecutive ones and consecutive zeros. There is thus a hierarchy of A-formulas, with sequence generators corresponding to the formulas of lowest level, i.e., the M-formulas. This suggests generalizing the concept of sequence generator so there is a kind of sequence generator corresponding to each level of the hierarchy. This could be done, as an example will make clear. The generalized sequence generator r = (S, RG) is defined as follows. S is the set (0,1]. RG is the triadic relation [< 100 >, < 111 >, < 000 >, < 001 >, < 010 >, < 011 >3. An infinite F-sequence 69

of this generalized sequence generator is any binary sequence [s](O,c) such that all t, RG(s(0), s(t), s(t')). Note that generators and the direct transition relation are not defined separately in r = (S,RG). The set of F-sequences of (S, RG) is equivalent to the extension of the O-formula (t) [B(O)~ (B(t) - B(t'))]. In this example the states of the sequence generator are zero and one, with the associated A-formula having one predicate (B). In general, of course, the states will be k-tuples of zeros and ones and the associated A-formula will have k predicates. Proceeding in a similar manner one can define generalized sequence generators corresponding to D-formulas and to A-formulas, with the result that for each formula rof a given type there is a corresponding generalized sequence generator F such that the extension of Oequals the set of infinite F-sequences of r. While these generalizations are of interest in showing the relations of formulas to sequence generators, they are not as easy to work with as the corresponding D-formulas, 0-formulas, and A-formulas. In contrast, sequence generators are easier to work with than the corresponding M-formulas. Moreover, by employing projections it is possible to reduce any A-formula Xto a sequence generator r = (S,G,R,P) so that the infinite behavior PW(F) equals the extension of, and in this way to investigate A-formulas of all kinds by means of sequence generators with projections. After defining some terms we will explain this process in more detail. A LA-formula is the result of prefixing a sequence of existential predicate quantifiers to an A-formula; "rO-formula," t"D-formula," and "'M-formula" are similarly defined. We will call the set of k-tuples of predicates which satisfy a 7A-formula the behavior of the formula. For example, the binary sequence 00110011... is the behavior of the M-formula (ZC)(t)([B-7) & XC-)] & [C(t) i C(t')] & (B(t') i (B(t) - C(t)))]). 70

Fig. 15. r = (S,G,R,P). Our preceding examples show that the sets of extensions of M-formulas, D-formulas, O-formulas, and.A-formulas get progressively larger. In contrast, the set of behaviors of ZA-formulas equals the set of behaviors of ZM-formulas. Given any ZA-formula, one can, by a procedure of Church, 1960, p. 36 ff., construct a behaviorally equivalent ZO-formula. There is, moreover, a process for reducing a ZO-formula to a behaviorally equivalent ZM-formula. A description of the process is too long to include here, but the essential steps are illustrated in the following example. Consider the O-formula (t) [B(O')D (B(t") = B(t)]. We introduce a predicate C1 which is defined by the conditions Cl(t') = Cl(t) and B(O') - Cl(O), so that Cl(t) - B(O') for all t. Since these conditions imply that Cl(t) - B(O'), we may substitute Cl(t) for B(O') in the original O-formula and conjoin the two conditions to obtain a ZD-formula (C1)(t)[B(O')- C1(o)] & [(Cl(t)D(B(t") - B(t))} & (Cl(t')- Cl(t) ] which has the same behavior as the given O-formula. We next introduce a 71

predicate C2, defined by the condition B(t') - C2(t), which implies that B(t") - C2(t') and B(O') - C2(0). Finally, we substitute C2(t') for B(t") and C2(0) for B(O') in the ZD-formula just obtained and conjoin the condition B(t') - C2(t), thereby obtaining a EM-formula (CC2)7(CZ1)(t) [C2(0)-C() C ] & [(Cl(t)~(C2(t') B(t))) & (C1(t') -C1(t)3 & (B(t') - C2(t) ] which has the same behavior as the D-formula and hence as the original 0formula. Each EM-formula S may be converted into a one-projection sequence generator r = (S,G,R,P) such that v(er) is the behavior of, and conversely. Again we will not state the algorithm for this conversion but will illustrate it. Consider the EM-formula (7C)(t)[[B ) & C- )] & [(C(t) C(t')) & (B(t') i (B(t) - C(t)))]). Drop the existential quantifier and convert the resultant M-formula into a sequence generator (S,G,R) in the way indicated before; see Fig. 15. Next, add a projection P defined so that P(B(t) & C(t)) = B(t), obtaining r = (S,G,R,P). o(r) is the behavior of the original M-formula. The reverse procedure of going from an arbitrary one-projection sequence generator to a EM-formula with the same behavior is only slightly more difficult. To sum up: given a ZA-formula, one can effectively construct a EM-formula which has the same behavior. Given a ZM-formula ~ one can effectively construct r = (S,G,R,P) such that W"(r) equals the behavior of Conversely, given r = (S,G,R,P) one can effectively find a EM-formula'whose behavior is @w(r). Hence the class of infinite behaviors of one-projection sequence generators equals the class of behaviors of ZA-formulas, and so LA-formulas may be investigated by means of sequence generators with one projection. 72

One can go further than this by classifying the free predicate variables of a EA-formula so as to correspond to several projections. For example, one can divide the free predicate variables of a EA-formula into two categories, the first corresponding to a projection P. the second to a projection Q. When this is done, the two-projection concepts and theorems of Section 3 apply to EA-formulas. It is worth noting what the Time-shift Theorem (3.3-2) becomes when looked at in this way. A deterministic sequence generator corresponds to a ZM-formula in which the Q-predicates (outputs) and bound predicates at time t +-1 are defined recursively in terms of themselves at time t and of the P-predicates (inputs) at times t and t + 1; this is essentially what Church, 1960, p. 11, calls a system of "restricted recursions." One may also consider recursive definitions in which the values of the Q-predicates and bound predicates at time t depends on the values of the P-predicates at later times; these recursions are essentially what Church, 1960, p. 12, calls "unrestricted singulary recursions," and can be expressed by a special type of ED-formula. Put in these terms, the Time-shift Theorem becomes: for every uniquely solvable LA-formula there is a logically equivalent ZD-formula which is composed of unrestricted singulary recursions. This ED-formula is of a special form which may be thought of as a normal form for uniquely solvable ZA-formulas. A normal form ZD-formula translates into a well-behaved net (see the last paragraph of Section 3.1) which consists of a well-formed part (corresponding to a deterministic sequence generator) together with a sequence of delays (which shifts the inputs earlier in time), and so the Time-shift Theorem can also be interpreted as saying that every well-behaved net has a normal form. Figure 16 gives the normal form for the well-behaved net of Fig. 2(a). The upper part produces the time-shift H(t) - E(t') while the lower part, which is well-formed, produces F(t) -~ H(t); hence F(t) — ~ E(t')', as in Fig. 2(a). 73

1 0E ~~ F Fig. 16. Normal form of the well-behaved net of Fig. 2(a). F(t) =- E(t'). One can think of a uniquely solvable ZA-formula whose free predicate variables are divided into P-predicates and Q-predicates as giving an implicit definition of the Q-predicates in terms of the P-predicates. Looked at in this way the Time-shift Theorem tells us that for every ZA-formula which implicitly defines the Q-predicates in terms of the P-predicates, there is a ED-formula which recursively defines the Q-predicates in terms of the P-predicates. 74

4.3. SEQUENCE GENERATORS AND CONDITIONS Suppose one wishes to design an automaton or other deterministic information-processing system. Using a formula, a diagram, or a set of tables, one:mayspecify the output of the system as a deterministic function of the inputs of the system. Sometimes, however, the designer has in mind only a condition or requirement which he wishes the behavior of the device to satisfy, there being many different behaviors which satisfy this condition. The designer may wish to consider all systems whose behaviors satisfy the given condition and select from among these by some criterion, such as minimality of components. A well-known example of this is the use of "don't care" cases in formulating a switch requirement. Because the requirement imposes no restrictions on the switch behavior for the "don't care" inputs, it may be satisfied by different switching functions. The designer wishes to select from all switches which satis'y this requirement one with a minimal number of switching elements. Many different languages may be used for expressing conditions on information-processing systems and for describing such systems. Consider first the language of ZA-formulas (Section 4.2). Suppose Sand rare ZA-formulas whose free predicate variables are divided into input variables and output variables.'may describe a computer system and 6'may express some relation between inputs and outputs which a designer would like the digital system to satisfy. The idea of a system ~satisfying condition Scan be formulated in logical terms by saying, first, that Sand'have the same input variables and the same output variables, and second, that ~i~is valid. Whenever the pair, < satisfies these two conditions we will speak of formula'being.. "a solution of" formula air. Let us see next how to formulate these ideas in sequence-generator terms. In passing between formulas and sequence generators, one must do some coding

or decoding, since the predicates of the formulas are two-valued, whereas a sequence generator has, in general, more than two states. If this coding is handled properly, the following definition of "r is a solution of r" is essentially the same as the definition of " V is a solution of " just given. Let r = (S,G,R,P,Q) describe some digital system and let P = (S,G,R,P,Q) express a condition. P and P are interpreted as input projections and Q and as output projections. r is a solution of r whenever, first, #B(r) c (@@(r), and second, every P-state occurring in @(r) occurs in @@(r). There are several kinds of design algorithms which make use of conditions. Buchi, Elgot, and Wright, 1958, define three kinds of algorithms for sets of formulas whose free predicate variables are divided into input variables and output variables. We will define analogous kinds of algorithms for sequence generators. Let a and P be two classes of two-projection sequence generators. A solution algorithm for < c, > is a decision procedure which applies to any pair < r,P > such that rea and PrE and answers the question: is r a solution of F? A solvability algorithm for < a5, > applies to any rep and is a decision procedure for the question: does there exist a rax such that r is a solution of r? A synthesis algorithm for < a,l > applies to any reg and produces a rea such that r is a solution of rF if there is one. Note that as a synthesis algorithm is here defined it may be non-terminating, but that a synthesis algorithm combined-with a solvability algorithm is terminating, producing a sequence generator of the desired kind if one exists, terminating in a "no" otherwise. Note also that, if a can be recursively enumerated, the existence of a synthesis algorithm for < a, > follows from the existence of a solution algorithm for < al, >, since the elements of a can be enumerated and each compared with the given element of a by the solution algorithm. Clearly the Behavior Inclusion Procedure of Section 2.3 constitutes the 76

basis of a solution algorithm for any classes of sequence generators a,. Now there are decision procedures for the sets of deterministic and semideterministic (Section 2.2), solvable (Section 2.3), h-univalent, and uniquely solvable (Section 3.3) sequence generators. Consequently, if a is any one of these sets it can be recursively enumerated, and so there is a synthesis algorithm for a and any set of sequence generators 5. For our next result we need the concept of one sequence generator being "a part of" another. r = (S,G,R,P,..., pn) is a part of r (S,G,R,P,., P ) whenever ScS, G cG, R CR and each pi is pi cut down to S. As an example of this concept we mention that the reduced form rt is a part of r. Clearly if r is a part of f, d(r) ().). The following is a theorem: let r = (S,G,R,P,Q) be semi-deterministic with respect to PxQ; there is a P-deterministic r = (S,G,R,P,Q) which is a solution of F if and only if there is a P-deterministic r = (S,G,R,P,Q) which is a part of r and such that every P-state occurring in:43((F) occurs inf 3((F). There is a proof of this theorem which consists of two steps. In the first step the theorem is established for the special case where no two complete states of the given condition r agree on both of their projections. In terms of formulas (Section 4.2), this means that the theorem is proved for conditions which are M-formulas. The second step is to extend this justification to EM-formulas, that is, to extend the proof of the theorem to the general case, where the given condition r is an arbitrary two-projection sequence generator.,The second step of the proof involves a construction which is of some interest in its own right. Let F = (S,G,R,P) and r = (S,G,R,P). The cross product of these two sequence generators r x r = r (S,G,R,P) is defined by 77

s = (< s,s >Is e S & e S & P(s) = P(s)) G = (G x G) S R (< sl, sl >, < S2, S2> = [R(sl, S2) & R(s, 52)1 P (< s, >) = P(s). The preceding construction can be used to establish the following lemma: Let P = (S,G,R,P,Q) be a sequence generator which is semi-deterministic with regard to PxQ and r = (S,G,R,P,I), where I(s) = s. There is a P-deterministic sequence generator r = (S,G,R,P,Q) which is a solution of r if and only if there is a P-deterministic r which is a solution of r. This theorem leads directly to a combined solvability-synthesis algorithm for < c, >, where a is the class of all two-projection sequence generators which are deterministic with respect to the first projection, and a is any class of two-projection sequence generators; the essential steps of the algorithm are to apply the subset sequence generator operation to the given condition and to examine each part of the result for determinism. By the results of Section 4.2, this gives us a combined solvability-synthesis algorithm for < a, >, where a is the class of systems of restricted recursions (i.e., representations of deterministic information processing systems) and p is any class of EA-formulas, the free predicate variables of all formulas being divided into input variables and output variables. This extends a result of Church, 1960, pp. 33a ff., 36 ff.,which is a solvability-synthesis algorithm for < ac, >, where a is the class of systems of restricted recursions but P is any class of A-formulas. Wang, 1959, p. 312, Theorem 6, has a result which is (in our terms) a solvability-synthesis algorithm for <, >, where a consists of systems of unrestricted singulary recursions and f is any set of O-formulas. Our last stated lemma holds with "uniquely solvable" replacing "P-deterministic." 78

By applying this lenrna, Wang's result can be extended to provide a solvabilitysynthesis algorithm for < ah >, where Ce consists of systems of unrestricted singulary recursions and B is any set of ZA-formulas, the free predicate variables of all formulas being divided into input variables and output variables, as before. We give next an example (already to be found in the literature) of the use of conditions. Sometimes an automaton is given with "input restrictions" by drawing an internal state diagram which does not provide transitions for all inputs (Aufenkamp and Hohn, 1957, Section IV). One is then interested in an automaton which has the same behavior as this diagram with respect to all input sequences which are provided for. This situation may be described in sequence-generator terms. The internal state diagram with input restrictions may be converted into a r = (S,G,R,P,Q) which is semi-deterministic with respect to P (see Section 1.2); in fact, the semi-determinism is not required for what we are going to do. We define a r = (S,G,R,P,Q) which will have F as a part. Let B consist of complete states < p,q > for all P-states p and Q-states q. S = SUtB. R is R extended so that (1) R(sl, s2) for all sl, s2 e B and (2) for any s E S and any P-state p, if there is no s1 C S such that R(s, sl) and P(sl) = p, then R(s, s) for every s e B. P and Q are P and Q extended to cover the elements of B so that P (< p,q >) = p and Q(< p,q >) = q. The original problem now becomes that of finding a P-deterministic r = (S,G,R,P,Q) which is a solution of r (cf. the penultimate paragraph of Section 2.1). An answer will always be given by the solvability-synthesis algorithm for deterministic sequence generators. described two paragraphs, back. The solution, solvability, and synthesis algorithms we have been discussing are defined in terms of behavior. It is worth noting that other solution, solvability, and synthesis algorithms may be defined by using different concepts in place of behavior in the definition of "r is a solution of r"; 79

for example, the set of r-sequences of a sequence generator, the computation of a sequence generator (Section 4.1), or the behavior of the final state sequence generators to be introduced next, We do not have space to discuss these algorithms. 4.4. SEQUENCE GENERATORS AND REGULARITY We now extend the concept of sequence generator to include a set F of final states. r = (S,G,F,R,P) is defined as in Section 1.1, with the additional proviso that F cS. The definition of F-sequence is altered to require that the last complete state of a finite r-sequence belong to F (be a final state) and to require that an infinite r-sequence contain infinitely many occurrences of members of F. (Contrast the concept of an infinite computation element of Section 4.1 and note that the functions of the sets G and F could be performed by two two-valued projections; for an illustration of this, see the last example of Section 1.3.) Behavior is defined as in Section 2.1, using the new concept of r-sequence. It will be convenient to have a concept of finite behavior 3f for both ordinary and final state sequence generators: @(O(F) = 3(r) - c)(r). We will assume that those earlier concepts (e.g., determinism) which are easily extended to cover sequence generators with final states are in fact so extended. Final-state sequence generators are of interest in connection with "regular sets." A regular set is a set of finite sequences defined in terms of certain algebraic operations on a given finite set of finite sequences. It has been shown that the following three sets are equivalent: (1) The set of regular sets (2) The set of finite behaviors f(P) of final state sequence generators r = (S,G,FR,P). (3) The set of finite behaviors Cf(S) of final-state sequence generators 80

r = (S,G,F,R,P) which are deterministic. See Kleene, 1956, Copi, Elgot, and Wright, 1958, and Myhill, 1957. The concept of a final-state sequence generator is a bona fide generalization of the concept of a sequence generator without final states. For every sequence generator (S,G,R,P) of the latter kind there is a behaviorally equivalent sequence generator of the former variety, namely, (S,G,S,R,P). But not every behavior of a final-state sequence generator is the behavior of some sequence generator without final states. This may be shown by means of the concept of "open behavior." A behavior (finite or unrestricted) of a sequence generator, is said to be "open" if every initial segment of an element of the behavior belongs to the behavior. The Infinity Theorem (2.1-3) implies that the behavior of a sequence generator without final states is open. The corresponding theorem does not hold for final-state sequence generators, as the simple example of Fig. 17 shows; s(r) consists of the single sequence Po,Po and hence is not open. Clearly, then, no sequence generator without final states has the behavior of Fig. 17. so s Fig. 17. Final-state sequence generator r = (S,G,F,R,P). F = (sl]. C(r) is not open. Though the behavior of a final-state sequence generator is not in general the behavior of a sequence generator without final states, any open finite behavior of a final-state sequence generator is the finite behavior of some sequence generator without final states. That is, for any F = (S,G,F,R,P), if Of(r) is open, then there is a F = (S,G,R,P) such that f(Fr) = f(F). Given any F = (S,G,F,R,P), whose 3f(r) is open, the desired r may be constructed 81

as follows. By the results of paragraph two of this subsection, there exists a P-deterministic sequence generator P = (S,G,F, R,P) whose ~f(P) = f ('). Since 4f(r) is open, Bf(r) is open. Now construct F = (S,G,R,P), where G = Gn F and R is R cut down to F x F. It can be shown from the openness of of(r) and the determinism of F that every complete state which belongs to a F-sequence is an F. Consequently, f(r) = f(r). Hence f(r) = f(r), and F is the desired sequence generator without final states. The result just established for open finite behaviors does not hold for open behaviors in general. That is, there is a r = (S,G,F,R,P) with open 4(r) for which there is no behaviorally equivalent sequence generator without final states. An example is given in Fig. 18. @(r) consists of all finite sequences of po and is thus open. But -if the behavior of a sequence generator without final states contains all finite sequences of P6, by the Infinity Theorem (2.1-3) it must also contain the infinite sequence Po, Po, pO,.... Hence 3(F) is not the behavior of any sequence generator without final states. so Sl Po Po Fig. 18. Final-state sequence generator r = (S,G,F,R,P). F = (sl1. (pr) is open, but it is not the behavior of any sequence generator without final states. We will conclude this subsection with a discussion of Boolean operations on sequence generator behaviors. Let 9(r), Yf(r),3(p) be the sets of all, all finite, all infinite sequences of P-states, respectively. The complement of a behavior is defined with respect to the appropriate one of these: " (r) = (r) - (F), \ f(F) = f(F) - f(F), and, -(p) = M(r) - M(r). Consider first sequence generators without final states. Let r' be the 82

sequence generator represented by the state diagram obtained by juxtaposing the state diagrams for r and F, treating the complete states of F and r as distinct. Then clearly 6( F) = ~(r) v ~(f) f) = L(Fr) V ((F) Let F = r x r, where "x" is the cross product operation defined in Section 4.3. It may be proved that -(i) = @(r) n e(r). Thus the union and intersection of sequence-generator behaviors are always sequence-generator behaviors. But the complement of a sequence-generator behavior is not generally a sequence-generator behavior. This is shown by Fig. 19; it can be proved by means of the openness of the behavior of a sequence generator without final states and the Infinity Theorem (2.1-3) that no sequence generator without final states has B@(r), ~f (r), or ac(r) as its behavior. so PO Fig. 19. r = (S,G,R,P). No sequence generator without final states has ~ B(rF), ~ f(r), or ~ F3~() as its behavior.

The situation is very different with final-state sequence generators. The class of finite behaviors of sequence generators with final states is closed under union, intersection, and complement (Rabin and Scott, 1959). Consider next infinite behaviors. In Section 4.2 we showed how to pass between various kinds of formulas and sequence generators without final states. There are also formulas which correspond to sequence generators with final states. J. Richard Buchi (unpublished) discusses such formulas which he calls T"quasi-Zl-formulas" and establishes that the complement of a set represented by a quasi-Zl-formula may be represented by a quasi-.1-formula. The same result is,in sequence-generator terms, that for every r = (S,G,F,R,P) there is a r = (S,G,F,R,P) such that ~(r) = ~ ~(r). As before, if r is the result of juxtaposing r and P, @(r) = $U(r) U ~fC(p). Hence by De Morgan's theorem, the class of infinite behaviors is closed under union, intersection, and complement. Consider finally (complete) behaviors. As before, if F is the result of juxtaposing r and r, 6(r) = (r) U (rF). However, the intersection of the behaviors of sequence generators with final states is not always a sequence-generator behavior, and hence by De Morgan's theorem the complement of the behavior of a sequence generator with final states is not always a sequence-generator behavior. This is shown by Fig. 20. @(r) of Fig. 20(a) consists of all finite sequences terminating in P1 and all infinite sequences with infinitely many occurrences of Pl. [((r) of Fig. 20(b) consists of all finite sequences terminating in po and all infinite sequences with infinitely many occurrences of po. Hence 6(r) ) @(r) contains only infinite sequences. But no sequence-generator behavior contains only infinite sequences, and therefore no sequence generator has the behavior d(r) (](). Section 2.3 contains a decision procedure for the inclusion of the behavior of one sequence generator without final states in the behavior of another. This is also a procedure for the inclusion of finite behaviors and 84

(a) So | I (b) Fig. 20. (a) r (S,G1F,R,P). F= (s1}. (b) r = (S,G,F,R,P). F =(sol. No sequence generator has the behavior 3(r) ((P). a simple modification of it gives a procedure for the inclusion of infinite behaviors. It follows from the fact that both the class of finite behaviors and the class of infinite behaviors of final state sequence generators are effectively closed under union and complement that there are decisions for "Is'( r) C4( r)?", "Is Cf(r) C 3fi(i)?", "Is de(r) ~d(P)?", where r and r are final-state sequence generators. 4.5. INFINITE-SEQUENCE GENERATORS In this subsection we will discuss briefly a generalization of the original concept of sequence generator obtained by dropping the requirement that the set of complete states S be finite (Section 1.1). The resultant generalization is called an "infinite-sequence generator.".Actually much of the content of this paper applies to infinite-sequence generators as well as finite ones. All our concepts apply to infinite-sequence generators except for the various decision procedures and the reduced form rt, and it is easy to define the reduced form of an infinite-sequence generator.

Many of our theorems apply to infinite-sequence generators too, with only minor modifications being needed in the proofs we have given to cover this extension. Of course the various decision procedures we have given make essential use of the finitude of the number of complete states of sequence generator, and the Time-shift Theorem (3~3-2) applies only to finite-sequence generators. In the first part of this paper we have made implicit use of infinite sequence generators. It will be seen on examination that Lemma 1.3-2 is in fact about an infinite-sequence generator (S, 50, p), where S is any set (finite or infinite) on which p is defined. The following theorem is very close to Lemma 2.1-2. Let r = (S,G,R) be an infinite-sequence generator with G finite and R(s) finite for every s c S; if every set in the cu-sequence G, R(G), R2(G), R (G),... is non-empty, then there is an infinite F-sequence. By means of this lemma the proof of the Infinity Theorem (2.1-3) can be rewritten, with minor modifications, to yield the following extension of the Infinity Theorem: Let r = (S,G,R,P) be an infinite sequence generator with G finite and R(s) finite for every s c S; then any sequence of P-states belongs to B(F) if and only if every finite initial segment of it belongs to B(I'). The tree operator to be defined next was used implicitly in the proof of the Infinity Theorem as well as in step (2) of the Reduced Form Algorithm. The tree operator "tt' applies to any (infinite or finite) sequence generator r = (S,G,R,P n) and produces its "tree generator" rt e * e 1 r r (SG,eR,P, ) S= the set of finite r-sequences R (s, [s](O,j + 1)) [([s](O,j + 1) e ) 8e (s = [s](O,j))] Pi([s](Ok)) = Pi(s(k)), for i = 1,.., n. 86

Note that if R(s) is always finite, then R(s) is always finite. Moreover, if S is finite, then S is infinite if and only if r has a r-admissible complete state. We conclude with some examples of infinite-sequence generators which have already been discussed in the literature, though not under this name. A Turing machine as defined by Turing, 1936-37, consists of a finite automaton to which is attached an infinite tape; odd-numbered squares are used for writing the digits of a real number. Such a machine corresponds to a sequence generator (S,G,R,Q), where S is the set of states of the machine (including its tape), G is the set of initial states of the machine, R is given by the transition rule, and the output projection Q when applied to a complete state s gives the number written on the odd-numbered squares of the tape when the machine is in that state. R(s) is always a unit set. For the specialpurpose machine (whose tape is initially blank), G is a unit set. For the universal machine, G is an infinite set consisting of those states whose tape part represents a program for a special purpose machine. The concept of computation (Section 4.1) can be extended to infinite-sequence generators. In particular, this can be done for Turing machines in such a way that two machines (one of these may be universal) are computationally equivalent if and only if they compute the same number in Turing's sense. This fact was part of the motivation for defining the concept of computation inasmuch as a similar statement cannot be made in terms of behavior. The basis von Neumann uses for his construction of a self-reproducing automaton consists of an infinite number of cells each capable of 29 states, with the state of each cell at time t + 1 determined by the states of itself and its neighbors at time t (Shannon, 1953; Burks, 1960, Section 4). This basis corresponds to a sequence generator (S,G,R), with S and G both infinite, and R(s) finite but unbounded. Burks, 1959, Section 6, Church, 1960, p. 21 ff., 87

and Holland, 1960, have given definitions of infinite automata with inputs and outputs. These correspond to infinite-sequence generators with two projections; in the latter two formulations, infinitely many input states are allowed, with the consequence that R(s) is infinite. Any Post canonical language (Post, 1943) in which each production rule has only one premise may be represented by an infinite-sequence generator (S,G,R). S is the set of strings, G is the set of axioms, and R is given by the production rules. Although we will not attempt to give a definition of "effective sequence generator," it should be noted that all the examples of infinite-sequence generators given above are effective in the sense that in each case integers may be assigned to the states in such a way that S,G,R, and the pi's are all recursive. 4.6. PROBABILISTIC SEQUENCE GENERATORS For -the sake of completeness we will discuss the relation of probabilistic to non-probabilistic sequence generators before concluding this paper. Let r = (S,G,R,P,..., pn), n = 0, 1, 2,..., be an infinitesequence generator with non-null G. Let W be a weight function which assigns positive initial probabilities summing to one to the elements of G and, for each s e S, assigns positive transition (conditional) probabilities summing to one to the elements of (< s, s1 >jR(s, sl), provided this set is non-null.5 (S,G,R,W,P,.., pn) is a "probabilistic sequence generator." Note that, as we use the terms, "probabilistic" and "deterministic" are not contradictories. "Deterministic" was defined in Section 2.1 for non-probabilistic sequence generators; its opposite is "indeterministic," not "probabilistic." Moreover, given a deterministic sequence generator (S,G,R,P) one can form a 5There is an alternative concept which is more difficult to define but easier to use in some applications: for each P-state p the initial probabilities sum to one over (slseG & P(s) = pl, and for each p & seS the transition probabilities sum to one over (< s, sl >|R(s,sl) & P(sl) = p}. 88

probabilistic sequence generator (S,G,R,W,P) from it by adding a weight function W. The weight function W induces a probability distribution on the finite r-sequences of r = (S,G,R,P) and hence on the elements of 63f(). The probability of a finite r-sequence [s](O,k) is the initial probability of s(O) multiplied by the probabilities of the transitions < s(O), s(l) >, < s(l), s(2) >,..., < s(k - 1), s(k) >. The probability of any element of @f(r) is the sum of the probabilities of those r-sequences which produce that behavior element. A stochastic process in which the probability of a state Occurring at time t depends only on the preceding states of the sequence can be represented by a sequence generator whose states are finite sequences of states of the stochastic process; compare the tree sequence generator rt of Section 4.5. A Markov chain with c~onstant transition probabilities is a probabilistic sequence generator without projections (S,G,R,W) such that (S,G,R) has no terminal states (see, for example,Feller,1957, p. 340). If S is finite, then (S,G,R,W) is a finite Markov chain. It is worth noting that many of the concepts employed in analyzing a finite Markov chain (S,G,R,W) depend only on the underlying non-probabilistic sequence generator (S,G,R) and not on the probability function W. We will give some examples. s is an absorbing state if and only if R(s) = (s3. (It should be recalled in this connection that every probability assigned by W is positive; hence if the probability of s succeeding s is one, then R(s) contains only s.) Let Rf(sl, s2) s2 eJ R(s1). s is a transient state if and only if there is a state slES such that IR(s, sl) but not RI(sl,s); s is a persistent state if s is not transient. A sequence generator (S,G,R) which satisfies these two conditions is ergodic: first, for any two complete states sl, s2eS, RI(sl, s2) and RW(s2, sl), and second, the greatest common 89

divisor of the lengths of all cycles of complete states is one (cf. Shannon, 1948, p. 435). It was remarked immediately after Corollary 2.1-1 that the concept of a sequence generator with projections is a bona fide generalization of the concept of a sequence generator without projections; for example, the sequence 001001001... belongs to the behavior of a sequence generator but it is not a r-sequence of any sequence generator (cf. the discussion of various ways of generalizing sequence generators in Section 4.2). Similarly, probabilistic sequence generators with projections are bona fide extensions of probabilistic sequence generators without projections. In any probabilistic sequence generator (S,G,R,W,P) the probability of a given complete state occurring at any time depends only on what complete state occurred at the preceding time. This is not so for the P-states, for since the same P-state may be assigned to different complete states the occurrence of a P-state at t can be made to depend on what P-states occurred at times prior to t - 1. An example is given in Fig. 21; the probability that po will occur, given that the three preceding P-states are Pi, Po, po, in that order, is o.8, while the probability that po will occur, given that the three preceding states are pl, Pl, po, in that order, is 0.5. We give some examples of probabilistic sequence generators. Shannon, 1948, p. 384 ff., defines a "discrete information source." A discrete information source is a finite Markov chain r = (S,G,R,W) to which has been added a set of symbols, each transition of r producing one of these symbols as outputs. One can construct another sequence generator P = (S,G,R,W,P), where S consists of pairs of elements of -S and P is an output projection,-such that r- will produce the same output sequences with the same probabilities as the original discrete information source. Von Neumann, 1956, p. 61 ff., investigates finite probabilistic nets 9o

So ___ ~.8.5 ~. Po S2 Pi Fig. 21. Probabilistic sequence generator (S,G,R,W,P). (cf. Moore and Shannon, 1956). These are well-formed nets composed of combined switch-delay elements. An element produces the correct (desired) output at each time with probability 1 - e and the complement (incorrect) output with probability e. Thus in Fig. 22(a), the output B is defined probabilistically as B(O) with probability 1 - E, B(O) With probability e B(t + 1) - [A(t) i B(t) ] with probability 1 - c, B(t + 1) i [A(t) i B(t) ] with probability e. Given a probabilistic net, one can 1'.rive a probabilistic sequence generator from it by methods similar to those of Section 1.2. Figure 22(b) is the probabilistic sequence generator (S,G,R,W,I,G) for the binary counter of Fig. 22(a); I is the input projection and G is the output projection. The solid 91

lines represent the desired (correct) transitions, the dotted lines the erroneous transitions; cf. Fig. 1. Note that (S,G,R,I,G) of Fig. 22(b) is not deterministic. In a similar way, a probabilistic sequence generator (S,G,R,W,Q), may be obtained from a probabilistic Turing machine; here Q is the output projection, S is infinite; see de Leeuw et al., 1956. B A 0 (a) SO If~, ~r~\\~o, I I S__,oo, S,_,ol Fig. 2 o2 ( io. I abil-Eisti (e/2) f (e/2), v abilistic sequence generator ( S,G,R,W,I,) for binary

BIBLIOGRAPHY Aufenkamp, D. D., and Hohn, F. E., "Analysis of Sequential Machines," Institute of Radio Engineers, Transactions on Electronic Computers, 1957, EC-6, 276-285. Buichi, J. R., Elgot, C. C., and Wright, J. B., "Non-Existence of Certain Algorithms of Finite Automata Theory," Abstract, Notices of the American Mathematical Society, April 1958, 5, No. 2, issue 30. Burks, A. W., "Computation, Behavior, and Structure in Fixed and Growing Automata," in M. Yovits and S. Cameron (eds.), Self-Organizing Systems, Pergamon Press, New York, 1960, pp. 282-311. Burks, A. W., "The Logic of Fixed and Growing Automata," Proceedings of an International Symposium on the Theory of Switching, 2-5 April 1957, Harvard Univ. Press, Cambridge, 1959, Part I, pp. 147-188. Burks, A. W., and Wang, H., "The Logic of Automata," Journal of the Association for Computing Machinery, 1957, 4, 193-218, 279-297. Burks, A. W., and Wright, J. B., "Theory of Logical Nets," Proceedings of the Institute of Radio Engineers, 1953, 41, 1357-1365. Chomsky, N., and Miller, G. A., "Finite State Languages," Information and Control, 1958, 1, 91-112. Church, A., "Application of Recursive Arithmetic to the Problem of Circuit Synthesis," Summaries of talks presented at the Summer Institute for Symbolic Logic, Cornell University, 1957, Institute for Defense Analysis, Princeton, 1960. Church, A., Review of Edmund C. Berkeley: "The Algebra of States and Events," The Journal of Symbolic Logic, 1955, 20, 286-287. Copi, I. M., Elgot, C. C., and Wright, J. B., "Realization of Events by Logical Nets," Journal of the Association for Computing Machinery, 1958, 5, 181-196. de Leeuw, K., Moore, E. F., Shannon, C. E., and Shapiro, N., "Computability by Probabilistic Machines," in C. E. Shannon and J. McCarthy (eds.), Automata Studies, Princeton Univ. Press, Princeton, 1956, pp. 183-212. Feller, W., An Introduction to Probability Theory and Its Applications, 2nd Edition, Wiley, New York, 1957. 93

Fitch, F. B., "Representation of Sequential Circuits in Combinatory Logic," Philosophy of Science, 1958, 25, 263-279. Harary, F., and Paper, H. H., "Toward a General Calculus of Phonemic Distribution," Language, 1957, 33, 143-169. Heyting, A., Intuitionism, an Introduction, North Holland, Amsterdam, 1956. Holland, J. H., "Iterative Circuit Computers," Proceedings of the 1960 Western Joint Computer Conference, 1960. Kleene, S. C., "Representation of Events in Nerve Nets and Finite Automata,," in C. E. Shannon and J. McCarthy (eds.), Automata Studies, Princeton Univ. Press, Princeton, 1956, pp. 3,41. Konig, D., Theorie der Endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft M.B.H., Leipzig, 1936. Mealy, G. H., "A Method for Synthesizing Sequential Circuits," The Bell System Technical Journal, 1955, 34, 1045-1079. McKinsey, J. C. C., Introduction to the Theory of Games, McGraw-Hill, New York, 1952.. Medvedev, I. T., "On a Class of Events Representable in a Finite Automaton," translated by J. J. Schorr-Kon from a supplement to the Russian translation of Automata Studies, C. E. Shannon and J. McCarthy, (eds.), Group Report 34-73, Lincoln Laboratory, Lexington, Mass., 1958. Moore, E. F., "Gedanken Experiments on Sequential Machines," in C. E. Shannon and J. McCarthy (eds.), Automata Studies, Princeton Univ. Press, Princeton, 1956, pp. 129-153. Moore, E. F., and Shannon, C. E., "Reliable Circuits Using Less Reliable Relays," Journal of the Franklin Institute, 1956, 262, 191-208, 281-287. Myhill, J., "Finite Automata and Representation of Events," in Fundamental Concepts in the Theory of Systems, WADC Technical Report 57-624, ASTIA Document No. AD 1557 41, 1957. Post, E. L., "Formal Reductions of the General Combinatorial Decision Problem, " American Journal of Mathematics, 1943, 65, 197-215. Putnam, H., "Decidability and Essential Undecidability," The Journal of Symbolic Logic, 1957, 22, 39-54. Rabin, M. 0., and Scott, D., "Finite Automata and Their Decision Problems," IBM Journal of Research & Development, 1959, 3, 114-125. 94

Shannon, C. E., "Computers and Automata," Proceedings of the Institute of Radio Engineers, 1953, 41, 1235-1241. Shannon, C. E., "A Mathematical Theory of Communication," The Bell System Technical Journal, 1948, 27, 379)423, 623-656. Turing, A. M., "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, Series 2, 1936, 42, 230-265, and 1937, 43, 544-546. von Neumann, J., "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components," in C. E. Shannon and J. McCarthy (eds.), Automata Studies, Princeton Univ. Press, Princeton, 1956, pp. 43-98. von Neumann, J.., "The General and Logical Theory of Automata," Cerebral Mechanisms in Behavior., Wiley, New York, 1951, pp. 1-41. Wang, H., "Circuit Synthesis by Solving Sequential Boolean Equations," Zeitschrift f1ir mathematische Logik und Grundlagen die Mathematik, 1959, 5, 291-322. 95

DISTRIBUTION LIST (one copy unless otherwise noted) Assistant Sec. of Def. for (2) Office of Technical Services Res, and Eng. Technical Reports Section Information Office Library Branch Department of Commerce Pentagon Building Washington 25, D. C. Washington 25., D. Co Bureau of Ships Armed Services Technical Informa-(10) Department of the Navy tion Agency Washington 25, D, C. Arlington Hall Station Attn: Code 671 NTDS Arlington 12, Virginia Chief, Bureau of Ships Chief of Naval Research (2) Department of the Navy Department of the Navy Washington 25, D. Co Washington 25, D. C. Attn: Code 280 Attn: Code 437, Information Systems Branch Chief, Bureau of Ships Department of the Navy Chief of Naval Operations Washington 25, D. CO OP-07T- 12 Attn: Code 687E Navy Department Washington 25, D. C. Naval Ordnance Laboratory White Oaks Director, Naval Research (6) Silver Spring 19, Maryland Laboratory Attn: Technical Library Technical Information Officer Washington 25, D. C. David Taylor Model Basin Attn: Code 2000 Washington 7, D. C, Attn: Technical Library Commanding Officer (10) Office of Naval Research Naval Electronics Laboratory Navy No, 100, Fleet Post Office San Diego 52, California New York, New York Attn: Technical Library Commanding Officer University of Illinois ONR Branch Office Control Systems Laboratory 346 Broadway Urbana, Illinois New York 13, New York Attn: D. Alpert Commanding Officer University of Illinois ONR Branch Office Digital Computer Laboratory 495 Summer Street Urbana, Illinois Boston 10, Massachusetts Attn: Dr. Jo E. Robertson 97

Technical Information Officer Naval Ordnance Laboratory U.S. Army Signal Research Corona, California and Dev. Lab. Attn: H. H. Weider Fort Monmouth, New Jersey Attn: Data Equipment Branch George Washington University Washington, D. C. Director (3) Attn: Prof. N. Grisamore National Security Agency Fort Geo. G. Meade, Maryland Dynamic Analysis and Control Laboratory Attn: Chief, REMP Massachusetts Institute of Technology Cambridge, Massachusetts Naval Proving Ground Attn: D. W. Baumann Dahlgren, Virginia Attn: Naval Ordn. Computation Center Burroughs Corporation Research Center National Bureau of Standards Paoli, Pennsylvania Washington 25, D. C. Attn: A. J. Meyerhoff Attn: Dr. S. N. Alexander Hermes Incorporated Aberdeen Proving Ground, BRL 75 Cambridge Parkway Aberdeen Proving Ground, Maryland Cambridge 42, Massachusetts Attn: Chief, Computation Lab. Attn: Mr. Reuben Wasserman Office of Naval Research Lockheed Missiles and Space Division Resident Representative 3251 Hanover Street University of Michigan Palo Alto, California 820 E. Washington Street Attn: D. G. Willis Ann Arbor, Michigan Univ. of Michigan Commanding Officer Ann Arbor, Michigan ONR, Branch Office Attn: Dept. of Philosophy, John Crerar Library Bldg. Prof. A. W. Burks 86 East Randolph Street Chicago 1, Illinois Census Bureau Washington 25, D. C. Commanding Officer Attn: Office of Asst. Director for ONR Branch Office Statistical Services 1030 E. Green Street Mr. J. L. McPherson Pasadena, California National Science Foundation Commanding Officer Program Director for Documentation ONR Branch Office Research 1000 Geary Street Washington 25, D. C. San Francisco 9, California Attn: Helen L. Brownson National Bureau of Standards Univ. of California - LA Washington 25, D. C. Los Angeles 24, California Attn: Mr. R. D. Elbourn Attn: Dept. of Engineering, Prof. Gerald Estrin 98

Columbia University Harvard University New York 27, New York Cambridge, Massachusetts Attn: Dept. of Physics, Attn: School of Applied Science, Prof. L. Brillouin Dean Harvey Brook Hebrew University The University of Chicago Jerusalem, Israel Institute for Computer Research Attn: Prof. Y. Bar-Hillel Chicago 37, Illinois Attn: Mr. Nicholas C. Metropolis, Massachusetts Institute of Technology Director Cambridge, Massachusetts Attn: Prof. W. McCulloch Commander Wright Air Development Division Benson-Lehner Corporation Wright Patterson Air Force Base, 1860 Franklin Street Ohio Santa Monica, California Attn: WCLJR, Maj. L. M. Butsch Attn: Mr. Bernard Benson Laboratory for Electronics, Inc. Atomic Energy Commission 1079 Commonwealth Ave. Washington 25, D. C. Boston 15, Massachusetts Attn- Div. of Research Attn: Dr. H. Fuller Naval Research Laboratory Stanford Research Institute Washington 25, D. C. Computer Laboratory Attn: Security Systems Menlo Park, California Code 5266, Mr. G. Abraham Attn: H. D. Crane Cornell University General Electric Co. Department of Mathematics Schnectady 5, New York Ithaca, New York Attn: Library, L.M.E, Dept., Attn: Profo Mark Kac Bldg. 28-501 Dr. A. M. Uttley The Rand Corp. National Physical Laboratory 1700 Main St. Teddington, Middlesex Santa Monica, California England Attn: Numerical Analysis Dept., Willis H. Ware Diamond Ordnance Fuze Laboratory Washington 25, D. C. Hunter College Attn: Library New York 21, New York Attn: Dean Mina Rees U.S. Army Signal Research and Dev, Lab. General Electric Research Laboratory Fort Monmouth, New Jersey P. 0. Box 1088 Attn: M, Tenzer Schenectady, New York Attn: Information Studies Section R. L. Shuey, Manager 99

Radio Corporation of America Office of Chief Signal Officer Moorestown, New Jersey Department of the Army Attn: Missile and Surface Radar Washington, D. C. Division, Sidney Kaplan Attn: R and D Division SIGRO-6D Mr. L. H. Geiger University of Pennsylvania Institute of Co-operative Research Bell Telephone Laboratories Philadelphia, Pennsylvania Murray Hill Laboratory Attn: Dr. John 0 Conner Murray Hill, New Jersey Attn: Dr. Edward F. Moore Stanford Research Institute Menlo Park, California National Biomedical Research Inst. Attn: Dr. Charles Rosen 9301 19th Avenue Applied Physics Group Hyattsville, Maryland Attn: Dr. R. S. Ledley Northeastern University 360 Huntington Avenue National Bureau of Standards Boston, Massachusetts Washington 25, D. C. Attn: Prof. L. 0. Dolansky Attn: Mrs. Frances Neeland Marquardt Aircraft Company University of Pennsylvania 16555 Saticoy Street Moore School of Electrical Engineering P. 0. Box 2013 - South Annex 200 South 33rd Street Van Nuys, California Philadelphia 4, Pennsylvania Attn: Dr. Basun Chang, Attn: Miss Anna Louise Campion Research Scientist Varo Manufacturing Company Texas Technological College 2201 Walnut Street Lubbock, Texas Garland, Texas Attn: Paul G. Griffith Attn: Fred P. Granger, Jr. Department of Electrical Engineering Data Processing Systems Staff IBM Corporation Department of State Military Products Division Washington 25, D. C. Owego, New York Attn: F. P. Diblasi Attn: Dr. S. Winkler Dr. Saul Gorn, Director Post Office Department Computer Center Office of Research and Engineering University of Pennsylvania 12th and Pennsylvania Avenue Philadelphia 4, Pennsylvania Washington 25, D. C. Attn: Mr. R. Kopp, Research and Applied Physics Laboratory Development Division Johns Hopkins University 8621 Georgia Avenue Air Force Cambridge Research Center Silver Spring, Maryland L. G. Hanscom Field, Attn: Supervisor of Technical Reports Bedford, Massachusetts Attn: Chief, CRRB 100

Bureau of Supplies and Accounts, Chief Navy Department Washington,' D,. C. Attn: Cdro J. C. Busby, Code W3 Auerbach Electronics Corporation 1634 Arch Street Philadelphia 3, Pennsylvania National Aeronautics and Space Administration Goddard Space Flight Center Greenbelt, Maryland Attn: Chief, Data Systems Division Federal Aviation Agency Bureau of Research and Development Washington 25, D. C. Attn: RD-375, Mr. Harry Hayman Mr. Donald F. Wilson Code 5144 Naval Research Laboratory Washington 25, D. C. David Taylor Model Basin Washington 7, D. CO Attn: Aerodynamics Laboratory, Code 628 Miss Cravens Chief, Bureau of Ships Code 671A2 Washington, D. CO Attn: Lcdr, E. B. Mahinske, USN Lincoln Laboratory Massachusetts Institute of Technology Lexington 73, Massachusetts Attn: Library 101

3 9015 02082 i