THE UN IVER S IT Y OF MICHIGAN COLTLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Note THE THEORY OF ALGEBRAIC AUTOMATA I: MORPHISMS AND REGULAR SYSTEMS Yehoshafat Give'on ORA Projects 07105 and 05662 under r..o.ntrat with: DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON, D.C. and U. S. ARMY RESEARCH OFFICE (DURHAM) CONTRACT NO. DA-31-124-ARO(D)-G433 DURHAM, NORTH CAROLINA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR January 1964

i-jS~~~~~~, 1, - S t; % In I

INTRODUCTION This is a preliminary report on a study of an algebraic generalization of the concept of regular events. Among all the possible ways of generalization we chose the one suggested by the characterization of regular events by means of homomorphisms with finite ranges (cf. [RS] and [YG] 1963). Following this suggestion, our attention is directed to the study of homomorphisms of monoids and their effect on subsets of monoids. Furthermore, we are able now to suggest a general algebraic framework in which several and various domains in the area of automata theory (like finite-state transductions, commutative machines, and context-free languages) can be studied and generalized uniformly. In this report, we present the study of the basic and immediate properties of regular systems in monoids and the effect of homomorphisms on such systems. I wish to thank J. W. Thatcher (now at the IBM Research Center in Yorktown Heights) and S. T. Hedetniemi of the Logic of Computers Group for their continuous interest and invaluable help. 1

1.1 ALGEBRAIC PRELIMINARIES AND NOTATIONS Let W be any monoid (i.e., a semigroup with identity). A binary relation w defined in W is said to be algebraic in W iff it is compatible with the operation in W; i.e., iff (w, w2) ~ r implies (ww, ww ), (w w, w w) w for any w, wl, w2 W. 1 2 r is said to be a congruence (relation) in W iff r is an algebraic equivalence relation defined in W. If W is a congruence in W, then an operation can be well defined in W/r by Ir(w )W(w ) df w(w w ).11 2 ~r 2 (where w(w) denotes the equivalence class in W/r which contains w) and a mapping: W -+ W/= by W(w) adf w(w) As one can easily prove, * is a homomorphism and thus it is said to be the homomorphism (of W) induced by i. On the other hand, for any homomorphism * of W we denote by * the binary relation defined in W by (WlI w ) W E iffdf (W ) - *(w2) As one can easily prove, * is a congruence in W (it is said to be the congruence induced by 0 in W) and from * a w follows W, a.

Studies of the relationship between the homomorphisms of W and the congruences in W can be found in the literature on monoids and semigroups ([CP], [JM]). Since the relations i 4-+ r and 4 -+ 4 induce a certain duality within the context of this paper, and since the traditional distinction between the homomorphisms of W and the congruences induced by them in W can be easily proved to be unnecessary, we shall often identify the homomorphism 4 of W with the congruence 4 induced by it in W and use the term morphism * to denote simultaneously 4 and 4. Moreover, we shall choose to use either the mapping notation or the relation notation for the morphisms according to the convenience of each notation in the specific context. Let. be a morphism of W and let E be a subset of W. The subset of W, c (E), defined by c(E) =df U{O(w):w e El is said to be the -Eclosure of E and E is said to be +-closed iff cs(E) = E. Clearly, the operation c$ on the subsets of W is a closure operation, i.e.: (i) E ~ c (E), (ii) E E2 implies c (El) c c(E2), (iii) c (c (E)) = c (E). We denote by C[W] the class of all subsets of W which are 4-closed. For example, if I is the identity on W then CI[W] is 6O(W), the class of all subsets of W. As an immediate property of C [W] we have the following lemma: LEMMA 1: Cs[W] is a Boolean algebra of sets which is isomorphic to 6D(W/4) under 4~ (which is 4 as a mapping operating on the subsets of W). 3

REMARK: We shall denote both * and bE and even Oc* by "~". We shall be interested in the following three operations on morphisms: The direct product of the morphisms 41 and 4 of W is denoted by 1 N_ 2 41 i 42 and defined by 1 2 ~1 2 df 1 2 The direct sum of 41 and 42 is denoted by 41 2 and is defined by ~1 2 df 1 2) where w* denotes the transitive-closure of.rr Obviously, these operations can be extended by induction to n-ary operations for any n. The following theorem summarizes the main properties of these operations. THEOREM 2: Let' n; be n morphisms of W, then: n n (i) i 4i and * 4i are also morphisms of W; iPl i=l n (ii) i *i is the maximal morphism of W which is included in i=l n n all the i., since B 4i = (.i; 1 i=l i=l n (iii) * *i is the minimal morphism of W which includes all the i=1l n n i., and in fact, * 4i = ( Oji)*; i=l i-1 n (iv) C n [W] = (C [W] where nec. denotes the class of i ). i=l 4i i i11 the intersections n E. of all E. e C.; i 1

(v) Cn [W] n nC [W]; i=l (vi) B and 0 are commutative and associative operations; (vii) if W/0i is finite for all 1 i i - n then so are n n W/ B *. and W/ *.i. i=1 1 i=1 The cartesian product of the morphisms 1 and * of W and W respectively, is denoted by * x * and defined to be a morphism of 1 2 x * )(w x x (w ) l x 2)( ) 2df 1(W1) 1 2 2 (where "x" denotes the operation of the cartesian product of sets.) Again this operation can be extended by induction. THEOREM 3: Let!*... n; be morphisms of W,..., Wn respectively, then: n n (i) x 0i is a morphism of b Wi i=l i=l n n (ii) C n [ I Wi] = xeC [Wi] where xeCi denotes the class x.i i=l i=l ii i i=1 of the cartesian products xEi of all Ei Ci; 1 (iii) the cartesian product of morphisms is an associative and essentially commutative operation; (iv) if Wi/Oi is finite for any 1 - i - n, then so is n n BW./ X i*. i=l 1 i=l 1

Finally, let * be a morphism of W. A morphism i of W is said to be a morphism of 0 iff i is included in *. The significance of this relation is given in the following theorem: THEOREM 4: If * is a morphism of the morphism 9 of W then the following diagram W -- ~ W/* W/o can be completed by /lp:W/i9 - W1/ to be a commutative diagram, i.e., in a unique way, Furthermore, we have C /,[~W/] = IcWI and in particular, for any F c W/G = ipg1())

1.2 REGULAR EVENTS IN MONOIDS a We wish to characterize a family of subsets ofAmonoid W in a fashion similar to the way the regular events are characterized as certain subsets of a finitely generated free monoid ([RS], [YG] 1963). DEFINITION 1: A W-regular system is a system A = <p, F> where: (i) p is a morphism of W with a finite range, (ii) F is a subset of the range of p. The morphism p is said to be the structure of A and T( ) =df p'1(F) = UF is the event generated by. A subset E of W is said to be regular in W iff E is the event generated by some W-regular system. We denote by RW the class of all subsets of W which are regular in W, that is, R11 =df U{cp[W]:W/p is finite} As an immediate result of Df. 1 we get: LEMMA 5: RW is closed under set complementation. From the properties of the direct product of morphisms we derive the following construction of Boolean combinations of W-regular systems: For any Boolean set function $S we denote by Bp the corresponding Boolean proposition function which is isomorphic to aS and thus the following relationship holds: let BS be a Boolean set function of n variables and let S,..., Sn be any n subsets of S, then Bs(S,... Sn) = {s E S:Bp(S ~ S,1' * S ~ S)}

Given n W-regular systems 7Ai = <Pi, F.> and a Boolean set function BS of n variables, we define: A-A n (A i,... d, n)df:< p. B*(F,..., F )> df i=l 1 n where n (F... Fn) =df { ( plPi)(w): Bp(P(w) C F..., Pn(w) c Fn)} Obviously, T(B(ji..., AXn)) = = *(F,..., Fn) = {w: p(W ~ UF1,..., w e UFP)} n -S (UF1,..., UFn) S(T( A1)..9 T(A)) Thus we have: THEOREM 6: RW is a Boolean algebra of sets. In the rest of this section we shall explore, with the expected results, the relationships between the following concepts: (i) W-regular systems and RW; (ii) right invariant relations in W; (iii) finite-state automata with W as their input; (iv) non-deterministic finite-state automata with W as their input. The methods used to establish the expected relationships are taken from the study of ordinary finite automata (cf. [RS], [RB], and [Y(G] 1960).

Let f be an equivalence defined in W which is right-invariant (i.e., (W, W ) E f implies (wlw, w w) C f for any w, wl, w2 W). We associate with f the following system ( = <S, so, rf> where: (i) S W/f. (ii) s = f(X), where X is the identity element of W, (iii) Tf: S x W + S is defined by Tf(f(w ), w) =df f(w w) [Note that Tf is well defined just because f is right-invariant.] Now, for any SF Q S we have: T(f, SF) =df {w c W: rf(sO, w) C SF = {w C W: f(w) C SF} USF Hence, if E t W is a union of certain equivalence classes of a rightinvariant equivalence f defined in W, then E is defined by an automaton (which is finite state iff W/f is finite), with W as its input (cf. [SG]) in a manner similar to that by which ordinary regular events are defined by Rabin-Scott finite automata. On the other hand, let (a= <S, s, T> be a system with: (i) S is a set and s c S (ii) T: S x W 4+ S is a mapping satisfying: T(s, X) = s for all s c S, T(s, w w ) ='(x(s, w ), w2) for all s e S w, w2 ~ W; 9

[(iii)-optional - for each s c S there is w e W such that T(sO' w) = s]. We define the binary relation f~ in W by: (w, w ) e f iffdf T(S ) T( w ) 2 df o 1 o,2 Clearly, fT is an equivalence and the cardinality of W/fT is less than or equal to that of S. If S is finite, then equality holds iff requirement (iTi) is satisfied. Furthermore, fT is right-invariant. Now let SF G S. The system < Q, SF> is said to be a W-automaton (which is a finite-state W-automaton iff S is finite) with the structure (~. The set: T(a, SF) -df {w c W: T(SO, w) ~ SF} is said to be the event defined by <l, SF>. Clearly, we have: T(Q, SF) =U {{T(so w) T: t( w ) = (s, w)}: T(o, w) e S} = U{fi(w): T(SO, w) c SF} = USF where SF =df {f(w): T(s, w) e SF} In conclusion we have: LEMMA 7: A subset E of W is a union of certain equivalence classes of a right-invariant equivalence (with a finite index) in W, iff E is defined by some (finite-state) W-automaton. The connection with W-regular systems is established by the following lemma: 10

LEMMA 8: Let E be a subset of W, then E is regular in W iff E is defined by a finite-state W-automaton. PROOF: Let <C1, SF> be a finite-state W-automaton with aQ= <S. so, T>. Define in W the binary relation pT by: (w, w ) E p iffdf for all s e S: T(s, w ) = T(s, w ) Clearly, p is a morphism of W with a finite range (which is less than or equal to the cardinality of S x S,) and pT is included in fT, i.e., pTw ) W pT(w ) implies T(so, w ) = T(S, w ) for all w, w e W. 1 2 0 0 2 1 2 Hence, if we define F {p (w): T(s, w) e S } df T' F we get a W-regular system <p, F> which generates T(a, SF). The converse follows directly by Lemma 7. Before we turn to establish the identity of the W-regular events and the events defined by non-deterministic W-automata, we wish to give an alternative proof of Lemma 8 by the means of the construction of the transition monoid M(t_) associated with the structure Q1 of W-automata. (For the case of the free monoid cf. [RB], [YG] 1960 and 1962.) Let aQ= <S, so, T> be a structure of W-automata. We define M(O) to be the set of all functions T:S + S defined for any w e W (using the suffix notation for functions) by: II.

sTw =df T(s, w) M(O,) is a monoid of functions since TX (where X is the identity element of W) is the identity on S and for any w, w e W we have: STWW ST; T w1W2 wI w2 This implies the existence of a morphism PT of W with W/pT = M(= ) which is defined by: PT (w) =df tw Clearly, if S is finite then M((Q) is finite and for any SF s S if we define SF df {: SoTw SF} we get, for a finite S, a W-regular system <PT ST> which generates T(4, SF). Let us define a system f = <S, r> to be a structure of (finite-state) non-deterministic W-automata iff: (i) S is a (finite) set, (ii).: S x W - (S) is a mapping from S x W into the class of all subsets of S, @(S), satisfying i(s, w w ) = U{ (s W ): s' Ic (S, w )} for all s ~ S and w, w C W. 2 We associate with 32 the monoid M(A) of the binary relations lw defined in S for any w C W by: (s, s 2) c W iffdf s2 E (s, W) From requirement (ii) follows that for any w, w e W we have: W12 1W ~ 2 12

and therefore M(n) is closed under the complex-product of binary relations and TX is its identity element. Thus M('M) is indeed a monoid of binary relations and it is the morphic image of l7 under p which is defined by: QM(w) df w For any S, SF 5 S we say that the non-deterministic W-automaton 0 F <S,S > defines the event T(So, O, SF) df {w C W: T(s, w) C SF for some s c SO Obviously, we get: (So,,0 SF) = Iw: Trw n (S x S ) 0} = {w e w: PT(w) E [So,, SF]} where [So, X, SF] =df {n(w) e MM(E): n(w) n (S X SF) # 0} Hence, if S if finite then T(S,, SF) is generated by the W-regular system <p=, [SO, X, SF]> Thus, similar to the "free" automata, we can regard the non-deterministic (finite-state) l-automata (as defined here) as a special case of W-regular systems where the range of their structure is a monoid of binary relations defined in a certain (finite) set, 13

1.3 THE EFFECT OF HOMOMORPHISMS ON W-REGULAR SYSTEMS Theorem 4 leads us to the following definition: DEFINITION 2: A morphism J of W is said to be a morphism of the W-regular system, = <p, F> iff * is a morphism of p. In this case, the W-regular system <p/*, F> is said to be the morphic image of 5 (under _), or alternatively, the +-image of 4 and will be denoted by ~/i. And it implies directly: LEMMA 9: Let * be a morphism of the W-regular system i = <p, F> and let E c W; then E is generated by A iff *(E) is generated by i /i. In this section we study the effects of the morphisms of 1V on Rw. Later we shall study the properties of the morphisms of W-regular systems. Our main result is summarized by the following theorem: THEOREM 10: Let 4 be a morphism of W and let E 5 W. Then ~(E) is regular in W/o iff co(E) is regular in W. In particular we have: (i) if E is generated by the W/4-regular system i' = <p, F> then 2.1 (E2) = c ( - (E2)) is generated by the W-regular system = <PO4, F >; (ii) if E is any subset of W such that c (E) is generated by the W-regular system A = <P, F> then 4(E) = 4(c%(E)) is generated by the W/m-regular system A' = <0/(4 * p), (p/(q O p))(F)>. PROOF: Immediate; for the proof of (ii) apply Theorem 4, Lemma 9 and Theorem 2 ((iii) & (v)). 14

As an immediate but important corollary we get: COROLLARY 10.1: If W is a finitely generated monoid, say by V, and E is a subset of W then: E is regular in W iff 4-1(E) is a ("free") regular event over V as an alphabet, where 4 is the natural homomorphism of the free monoid generated by V onto W. These results motivate us to consider the two classes of events introduced in the following two definitions. DEFINITION 3: Let O be a morphism of W; we denote by 4RW the class of the +-images of the regular events in W. That is: ORW =df {~(E): E C Rw} Clearly, Theorem 10 implies: COROLLARY 10.2: If O is a morphism of W then %W/O i RW In Lemma 1 we noticed that fE, which is O operating on the subsets of W, is a one-to-one correspondence between C [W] and Q(W/:). Now, from Theorem 10 we infer: COROLLARY 10.3: If 4 is a morphism of W then IE (restricted appropriately) is a one-to-one correspondence between Rs n C4[W] and RW/~. DEFINITION 4: Let c be a morphism of W; we denote by C,(Rw) the class of all the ~-closures of the regular events in W. That is: C(Rw) =df {c~(E): E s Rw}

Clearly, we have: LEMMA 11: If 9 is a morphism of W' then ~c (restricted appropriately) is a one-to-one correspondence between C (Rv) and Rh,. Thus, we get the following conclusion of Theorem 10: THEOREM 12: Let ~ be a morphism of W then,R; = R/~ iff C (RIV) = Rw that is, iff c, is regularity-preserving in 1-1. We can summarize these results by the following diagram: ic tc R(W) - V — (W/) UUI W {W - + C (KW) c RC, G nC[W] < whlere: (i) 4E is q operating on the subsets of W, i.e., ~C(S) =df {4(s): s e S} (ii) i is the identity on its contexts; (iii) c{ is the operation of 4-closure; (iv) o — - shows one-to-one corresnondence. 16

BIBLIOGRAPHY [RBJ J. R. BUCHI, "Mathematical Theory of Automata: Notes for a Seminar," given by J. B. Wright and J. R. Buchi, The University of Michigan, Fall 1960. [CP] A. H. CLIFFORD and G. B. PRESTON, "The Algebraic Theory of Semigroups, Volume I," AMS Surveys, No. 7, 1961. [SG] S. GINSBURG, "Some Remarks on Abstract Machines," Trans. of the AMS, Vol. 96, No. 3, September 1960. [YG] Y. GIVE'ON, "Boolean Matrices and Their Application to Finite Automata," Technical Report No. 5, Applied Logic Branch, The Hebrew University of Jerusalem, September 1960, "The Application of Algebraic Systems to Finite Automata," Technical Report 04995-1-T, Office of Research Administration, The University of Michigan, June 1963. [JM] J. MEZEI, "Structure of Monoids with Application to Automata," Proc. of Symp, on Math. Theory of Automata, Polytechnic Institute of Brooklyn, 1963. [RS] M, O. RABIN and D, SCOTT, "Finite Automata and Their Decision Problems," IBM Journal, Volume 3, No. 2, April 1959.....~~~~1

DISTRIBUTION LIST (One copy unless otherwise noted) Assistant Secretary of Defense Bureau of Ships for Research and Engineering 2 Department of the Navy Information Office Library Branch Washington 25, D. C. Pentagon Building Attn: Code 607A, NTDS Washington 25, D.C. Bureau of Naval Weapons Defense Documentation Department of the Navy Center 10 Washington 25, D.C. Cameron Station Attn: RAAV, Avionics Division Alexandria, Virginia Bureau of Ships Chief of Naval Research 2 Department of the Navy Department of the Navy Washington 25, D.C. Washington 25, D.C. Attn: Communications Br., Code 686 Attn: Code 437, Infor. Syst. Br. Naval Ordnance Laboratory National Security Agency White Oaks Fort George G. Meade, Maryland Silver Spring 19, Maryland Attn: R-4, Howard Campaigne Attn: Technical Library Director, Naval Research Labs. 6 Massachusetts Institute of Technology Tech. Infor. Officer, Code 2000 Research Laboratory of Electronics Washington 25, D.C. Cambridge, Massachusetts Attn: Professor W. McCulloch Commanding Officer 10 Office of Naval Research David Taylor Model Basin Navy No. 100, Fleet Post Office Washington 7, D.C. New York, New York Attn: Technical Library Commanding Officer, ONR Br. Office Naval Electronics Laboratory 346 Broadway San Diego 52, California New York 13, New York Attn: Technical Library Commanding Officer, ONR Br. Office University of Illinois 495 Summer Street Control Systems Laboratory Boston 10, Massachusetts Urbana, Illinois Attn: D. Alpert Chief of Naval Operations OP-07T-12 University of Illinois Navy Department Digital Computer Laboratory Washington 25, D.C. Urbana, Illinois Attn: Dr. J. E. Robertson

Technical Information Officer Massachusetts Inst. of Technology U. S. Army Signal R&D Laboratory Cambridge, Massachusetts Fort Monmouth, New Jersey Attn: D. W. Baumann, Dynamic Attn: Data Equipment Branch Analysis and Control Lab. U. S. Naval Weapons Laboratory Burroughs Corporation Dahlgren, Virginia Research Center Attn: Head, Computation Division Paoli, Pennsylvania G. H. Gleissner Attn: R. A. Tracey George Washington University National Bureau of Standards Washington, D.C. Data Processing Systems Division Attn: Prof. N. Grisamore Room 239, Bldg. 10, Attn: A. K. Smilow Washington 25, D. C. Aberdeen Proving Ground, BRL Aberdeen Proving Ground, Maryland Lockheed Missiles and Space Company Attn: J. H. Giese, Chief Comput. Lab. 3251 Hanover Street Palo Alto, California Office of Naval Research Attn: W. F. Main Resident Representative The University of MicHigan The University of Michigan Ann Arbor, Michigan Ann Arbor, Michigan Attn: Professor A. W. Burks, Dept. of Philosophy Commanding Officer ONR, Branch Office Census Bureau John Crerar Library Bldg. Washington 25, D.C. 86 East Randolph Street Attn: Office of Assistant Director Chicago 1, Illinois for Statistical Services Mr. J. L. McPherson Commanding Officer ONR, Branch Office National Science Foundation 1030 E. Green Street Program Dir. for Documentation Res. Pasadena, California Washington 25, D.C. Attn: Helen L. Brownson Commanding Officer ONR, Branch Office University of California 1000 Geary Street Los Angeles 24, California San Francisco 9, California Attn: Department of Engineering, Professor Gerald Estrin National Bureau of Standards Washington 25, D.C. Columbia University Attn: Mr. R. D. Elbourn New York 27, New York Attn: Department of Physics, Naval Ordnance Laboratory Professor L. Brillouin Corona, California Attn: H. H. Weider

University of Illinois The RAND Corp. Champaign Urbana, Illinois 1700 Main St. Attn: John R. Pasta Santa Monica, California Attn: Numerical Analysis Dept. Naval Research Laboratory Willis H. Ware Washington 25, D.C. Attn: Security Systems General Electric Research Laboratory Code 5266, Mr. G. Abraham P. 0. Box 1088 Schenectady, New York Diamond Ordnance Fuze Laboratory Attn: Information Studies Section Connecticut Ave. & Van Ness St. R. L. Shuey, Manager Washington 25, D.C. Attn: ORDTL-012, E. W. Channel Mr. Sidney Kaplan 1814 Glen Park Ave. Harvard University Silver Spring, Maryland Cambridge, Massachusetts Attn: School of Applied Science University of Pennsylvania Dean Harvey Brook Institute of Co-operative Research Philadelphia, Pennsylvania The University of Chicago Attn: Dr. John O'Conner Institute for Computer Research Chicago 37, Illinois Stanford Research Institute Attn: Mr. Nicholas C. Metropolis Menlo Park, California Attn: Dr. Charles Rosen Aeronautical Systems Division Applied Physics Laboratory Electronic Technology Laboratory Wright-Patterson AFB, Ohio Northeastern University Attn: Lt. Col. L. M. Butsch, 360 Huntington Ave. ASRUEB Boston, Massachusetts Attn: Prof. L. O. Dolansky Laboratory for Electronics, Inc. 1079 Commonwealth Ave. New York University Boston 15, Massachusetts New York, New York Attn: Dr. H. Fuller Attn: Dr. J. H. Mulligan, Jr. Chairman of E. E. Dept. Stanford Research Institute Computer Laboratory Marquardt Aircraft Co. Menlo Park, California 16555 Saticoy St. Attn: H. D. Crane P. O. Box 2013, South Annex Van Nuys, California General Electric Co. Attn: Dr. Basun Chang Schenectady 5, New York Research Scientist Attn: Library, L.M.E. Dept. Texas Technological College Hunter College Lubbock, Texas New York 21, New York Attn: Paul G. Griffith Attn: Dean Mina Rees Dept. of Elec. Eng.

Dr. Stanley Winkler University of Pennsylvania IBM Corporation Mechanical Languages Projects Federal Systems Division Moore School of Elec. Eng. 326 E. Montgomery Ave. Philadelphia 4, Pennsylvania Rockville, Maryland Attn: Dr. Saul Gorn, Director Post Office Department Applied Physics Laboratory Office of Research and Engineering Johns Hopkins University 12th and Pennsylvania Ave. 8621 Georgia Ave. Washington 25, D.C. Silver Spring, Maryland Attn: Mr. R. Kopp Attn: Document Library Res. & Dev. Division Bureau of Supplies and Accounts, Chief L. G. Hanscom Field Navy Department AF-CRL-CRRB Washington, D.C. Bedford, Massachusetts Attn: Code W3 Attn: Dr. H. H. Zschirnt National Aeronautics & Space Admin. Department of the Army Goddard Space Flight Center Office of the Chief of Res. & Dev. Greenbelt, Maryland Pentagon, Room 3D442 Attn: Chief, Data Systems Div. Washington 25, D.C. Attn: Mr. L. H. Geiger Federal Aviation Agency Bell Telephone Laboratories Bureau of Research & Development Murray Hill Laboratory Washington 25, D.C. Murray Hill, New Jersey Attn: RD-375, Mr. Harry Hayman Attn: Dr. Edward F. Moore Mr. Donald F. Wilson National Biomedical Res. Found., Inc. Naval Research Laboratory 8600 16th St., Suite 310 Washington 25, D.C. Silver Spring, Maryland Attn: Code 5144 Attn: Dr. R. S. Ledley David Taylor Model Basin University of Pennsylvania Washington 7, D.C. Moore School of Elec. Eng. Attn: Aerodynamics Laboratory, Code 628 200 South 33rd St. Miss Cravens Philadelphia 4, Pennsylvania Attn: Miss Anna Louise Campion Lincoln Laboratory Mass. Institute of Technology Division of Automatial Data Lexington 73, Massachusetts Processing /AOP/ Attn: Library Department of State Washington 25, D.C. Dr. C. R. Porter Attn: F. P. Diblasi, 19A16 Psychology Department Howard University Auerbach Electronics Corp. Washington 1, D.C. 1634 Arch St. Philadelphia 3, Pennsylvania

Electronics Research Laboratory Hebrew University University of California Jerusalem, Israel Berkeley 4, California Attn: Prof. Y. Bar-Hillel Attn: Director National Physical Laboratory Institute for Defense Analysis Teddington, Middlesex Communications Research Division England Von Neumann Hall Attn: Dr. A. M. Uttley, Supt. Princeton, New Jersey Autonomics Division

UNIVERSITY OF MICHIGAN 3 9015 02826 1058111111 3 9015 02826 1058