THE UN I V E R S I T Y O F MI C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Communication Sciences Technical Report DECOMPOSITIONS OF AUTOMATA USING NORMAL SUBMONOIDS Bernard Zeigler ORA Projects 08226 and 03105 supported by: UOS. ARMY RESEARCH OFFICE (DURHAM) CONTRACT NO. DA-3L-I24-ARO-D-485 DURHAM, NORTH CAROLINA and DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON DoCo administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR December 1967 Distribution of this document is unlimited.

RESEARCH PROGRESS REPORT Title: "Decompositions of Automata Using Normal Submonoids," B. Zeigler, University of Michigan Technical Report 03105-50-T. Background: The Logic of Computers Group of the Department of Communication Sciences of The University of Michigan is investigating the application of logic and mathematics to the design of computing automata. The applicationof the techniques and concepts of abstract algebra to automata forms a part of this investigation. Condensed Report Contents: Aspects of decomprui-tion of automata using normal submonoids are discussed. A simplified cascade connection procedure is given which can be specialized to the case of normal subgroups, but which introduces some novel features, e.g., the use of feedback in the tail machine, when applied to normal submonoids in general. Differences in efficiency between decompositions based on semi-direct products of machines versus those of semigroups are also discussed. For Further Information: The complete report is available in the major Navy technical libraries and can be obtained from the Defense Documentation Center; A few copies are available for distribution by the author.

Section 1 Decompositions Based on Normal Submonoids An automaton (or machine) is a triple M = <(, Q, 0> where X is an (input) monoid; Q. a set (of states) and *, a map (QX) + Q (called the operation or action of X on Q) satisfying the conditionslo qol = q for all q ~ Q, where 1 is the identity of X, 2, qo(x1x2) = (qox1)ox2 for all q e Q, x1, x2 C Xo In the usual interpretation, X is a free monoid on a set of generators, S (the input alphabet) and the operation o is obtained by extending to X, the transition function (QDS) -+ Qo (As is customary we supress mention of o where no ambiguity arises.) The monoid, X/EM of an automaton M = <X, Q> is the quotient monoid of X modulo the two-sided congruencex -. y <=- qox = qoy for all q c Q ioeo X/EM is the set of equivalence classes of EM under multiplication [x]o[y] = [xy] A monoid machine is an automaton M[X/=] = (X, X/-> where - is a twosided congruence on X and [x]oy - [xy] for all xy c Xo It is easily verified that the monoid of M[X/=] is precisely X/E- (For more on the relation between monoid machines and "ordinary" machines see [2] and references thereino ) Now let K- be a submonoid of X (by which we mean 1 c K and xy c K implies xy; ' K)o K is said to be normal if xK A Kx for all x C Xo The equivalence x _ y iff Kx = Ky 1We use here the formulation given in Yo Give'on [1]. 2Kx = {kxlk s K)}o

is already a right congruence (for Kx a Ky implies Kxz - Kyz for all z ~ X) with equivalence classes [x]o Thus there is a machine M[X/K]. X, X/SK> with operation [x]'y = [xy] for all x,y ~ Xo It is easily demonstrated that if K is a normal submonoid of X, the relation SK is a two sided congruence (see [3], Chapter 1 for a detailed account of semi-group congruences)~ Thus M[X/K] is a monoid machine if K is normal. In general [x] c Kx for all x e X (since y K x implies y E Ky - Kx) and it i's easily verified that if X is finite, [x] - Kx (for all x e X) just in case K is a subgroup of units (elements of X having inverses), In the event [x] e Kx for all x c X the normality conditions can be weakened in the following sense: for M[X/K] to be a monoid machine it is necessary and sufficient that xK C Kx fpr all x c Xo (Proof: use [1] = K to establish that [x] [y] = [xy] iff KxK = Kx iff xK C Kx)o That M[X/K] may be a monoid machine if xKC Kx for some x e X is demonstrated in the monoid machine: F ig 1 ltaab - lab The monoid is X = (a,bla2 = a, ab = a, b2 = 1} where K {l,b} is a subgroupo X/-K = {KKa} where Ka = Kba = {abal, Here aK = {a}, baK = (ba} so both aK and baK are strictly included in Ka while X/K is

multiplicative and M[X/K] a monoid machine, In order to interconnect automata we shall have to supply them with outputs0 Let M = <X, Q> and Y an (output) monoido A map Z: (QX) + Y (in which we shall denote Z(q,x) = xq with the mnemonic that both x and xq are strings and xq is the output string resulting from input x in state q ) is an admissible output map for M under the conditions: 1o 1q = 1 for all q C Q (the l1s refer to identities of X and Y respectively)O 20 (x1x2)q = xqxq~xl for all q C QD xlx2 C Xo The reader may wish to convince himself that an admissible map is a no memory (or one-state) device (if X, Y are free, condition 2 implies that Z is fixed once values have been assigned for the generators and for all q e Q and that Z is length preserving)~ Now let M1 X- sX Q>and M2 = <YD R> be two machines with Z ~ (QX) + Y an admissible map for M1o The semi-direct product of M1 M2 via Z is a machine M1 z M2 = <X9 Q x R> with operation defined by (qjr)x = (qxrxq) for all (qpr) C (Q,R) and x C Xo It is easily verified that M1 z M2 satisfies the well-definedness conditions given above, Diagrammatically, M1 z M2 is MI M2 Figo 2

In order to capture the apparently different configuration MMX2 - Fig 3 we take X to be the submonoid of the product of free monoids X1, X2 such that x {(x1,x2)1(X ) = 2)) 1 where Z denotes length in terms of the generators, Make the operation of M1 independent of X2, ioe,, q(xl9x2) - qx1 for all q C Q, (X11X2) c X and the output of Z independent of the present value of X1, i,e,, (XS1DX2S2) q = (X1)X2)q'xl for all (x!,x2) C X and generators s1 of X19 ~ 2 of X20 Fig. 3 is the configuration inherent in semi-direct products of semigroups and, as we shall see, the independencies imposed may result in unnecessarily uneconomical decompositions when adapted to machines, The question of when is the semidirect product of monoid machines again a monoid machine bears on the relation between semidirect products of monoids and of machines, Proposition 1o Let M[X/-x], M[Y/-V] be monoid machines and Z: (X/-x,X) + Y/,y an admissible map such that u[1] = V[1] implies u[X] = VtX] for all x, u, v C Xo Let M~1 denote the semi-direct product machine M[X/-x] ~z M[Y/] restricted to states accessible from ([1], [1])o Then M1 1 is a monoid machine0,1

Proofo Define the right congruence on X u v iff ([1],[1])u = ([ll], [1])v iff u vand u[1] = v[1] Then the map ([x]b[x] ]]) + [x] is a machine isomorphism between M1 and M[X/_]o Showing that = is also a left congruence completes the proof since then M[X/E] is a monoid machine and by isomorphism so is Mil 6 But left-sideness of X/E follows from the assumption: U 1 ] _[1] implies u[X] v[X] Y Y implies X[1] Nx = Xt1] V [X] implies (xu)[1] [1] So that for all x e X u - v implies u E v and u[l] Y v[ implies xu xv and (xu)[1] (xv)[1] x ~ ~ Y implies xu xv QEoDo Now let X, Y be semi-groups and' Z: (X,Y) + Y such that -o (Yly2) = YY2 2y yXlX2 = (yX2)Xl for all XpXlX2 e X, YeY1lY2 E Yo Then X 6Z Y is a semi-group semi-direct product where (X1,yl1)(x2 Y2) = (XlX2PylY2 X1) If X,Y are monoids and we wish to preserve (1,1) as right and/or left identity we stipulate that 3a0 1X = 1 for all x e X and/or 3bo yl y for all y ~ Yo Now in order to interpret the semi-direct product of semi-groups in terms of machines we are forced to the configuration of Fig. 3 which appears as:

X M[X] -- M[Y] The reader familiar with (semi-) group theory may observe that the independencies involved in this configuration (the fact that Y does not affect M[X] and X does not directly affect M[Y]) are inherent in the notion of semi-direct product extensions though mot true of extensieons in general). Further, conditions 1 and 3a will satisfy the admissibility criterion for Z, and either of conditions 2 or 3b will assure that the hypothesis of Proposition 1 holds, Thus as expected, all semi-group semi-direct products can be interpreted as special cases of machine semi-direct products (preserv3 ing monoid-machinedness) but not converselyo3 This means that it may be possible to obtain more efficient decompositions by using machine rather than semi-group semi-direct productso The Wreath product (also a semidirect product) decomposition of groups is a case in point, as will be shown. We now proceed to apply the preceeding ideas to the series-parallel decomposition of automata, Our approach is both a simplification and generalization of certain of the constructions employed in the Krohn-Rhodes theory of decomposition, In particular we generalize the notion of decomposition by subnormal series to monoids and show how to decompose group machines more efficiently than can be done using the Wreath product, This latter method was first discovered by Ra Bayer (see [4] for both the Wreath product and Bayer's construction) but we show how it pops out of our more general approach0 Let K be a submonoid of a monoid X, with ~ the right congruence define&K above0 To each equivalence class [x] we assign a unique representative x' C [x] (called a leader in group theory), ioeo, xl - x2 iff xl = x20 Now every x C X belongs to some [x] C Kx, hence has a representation x = k x' for 3Because associativity (yXlx2 - (yX2)xl) is required of semi-group, but not machine productso

some kx e Ko We shall assume for simplicity that only one such kx exists~ In the more general case an obvious but more complicated construction is involved which does not add anything new to the basic idea, We have the following easy but important lemmas: Lemma 1o (xy)' = (xey)9 (for all x,y X) o Proofo x - x~ implies xy x'y implies (xy)' = (x'y)' QoEBDo K K Lemma 20 ky k k (for all x,y c K)o xy. xiy Proofo x = k xQ _o x implies xy = k xey = k k (x~y) X XBy = k k xy(xy) using Lemma 1o QEoDo We want to decompose monoid machines with monoid Xo To do this it is convenient to consider machines of the form M[X] = <X, X>. There is little lost in this, for with a little more care we can obtain the same results for machines whose input monoid is freely generated by the letters (ioe, the carrier) of X, which is the more standard formulation0 Theorem Lo Let X be a monoid and K a submonoid of Xo There is an isomorphism from M[X] into a semi-direct product of M[X/K] and M[K]o Proofo That the code x *-+ ([x],k ) is a one-one representation for every x e X follows from the fact x = k X 0o Now define the connecting map X Z: (X/=KO X) + K to be y[X] = kxVy for all x9y c Xo Checking that Z is admissible we have 1[X] = k = 1 (since x9 = lox') and (yly 2) X] x'yk (xy1)y2 = y[X] y2,XYl I[ us ing Lemmas 1 and 2 (y12)[ x YlY2 xY (xYYl)Y2 1 2 Now note that for all x,y e X ([x],kx)y = ([x]ykxy [X) = ( [SY] kxkx y) = ([xy],kxy) which shows that every transition xoy + xy is correctly effected0 QoEoDo

We recall that M[X/K] is a monoid machine if K is a normal submonoido Just as in the restricted case for groups, we may apply the above procedure to decompose both M[X/K] and M[K], thus obtaining a "subnormal" series of monoids and corresponding monoid machines. (Of course, a question of uniqueness, established for group decomposition, arises,) Decomposition by this method must halt when a "simple" monoid is reached. A monoid X is simple if for any normal submonoid K, either X/=K a X or X/=K X 1o For finite automata, the Krohn-Rhodes theory shows that no new primitives are introduced in this way (assuming that, the "simple" monoids are decomposed in the standard way). However, decomposition based on normal submonoids, where possible, is more efficient than that based on the existence of left ideals' in that it does not require the introduction or reset inputs. For infinite automata, where the existence of appropriate left ideals and subsemigroups is not guaranteed, decomposition based on normal submonoids may provide an avenue where other procedures fail8 "As an example, the monoid of Fig0 1 has classes K = {1,b}, Ka = {a,ba} such that KaoKa = Kao Choosing representatives of K and Ka as '1l" and "a" respectively, we obtain the code between M[X] and M[X/K] ~z M[K] as 1 +-+ (K,1), b -+ (Kb), a +-+ (Ka,l) ba ++ (Ka,b)0 The Z map is given by K Ka a 1 1 b b 1 and the monoid machine decomposition is 4For a finite semigroup S, if S is neither cyclic nor left simple then there exists a proper left ideal T C S, T # S and a proper sub-semigroup V C S,:V ~ S so that S = T U V0 M(S) is then simulated by M(V) with added reset in series with M(T Ul) o See [5] or [6] for details0

9 K K KaZ 1 b Ka Ka Ka b b I We note that in the case of X being a group, kx is directly computable -1 as k = x(x'), and our construction requires only the use of one copy of 1M[X/K] and one copy of M[K], The Wreath product construction however also requires one copy M[X/K] but n copies of M[K] where n = IXI/IKI. The reason for this inefficiency, alluded to before, lies in the relation between semidirect products of machines and those of monoids, The Wreath product decomposition on a group X, is a semi-direct product of X/K and nr K., a direct i=1 product of n copies of Ko Let (vi, 0 v.. VI) be an ordered set of representatives of the cosets Kv oo, Kvl, 0oo Ky'. The code x *-+ (Kx,(oookvxoOO)) is a one-one map between X and X/K % K. The Z map is given by vX X~~ kvx Vn X) ((uxl ) oo, (v x)' X (Vn X)X i 1 1 3 n n 1 (ViX) IX1'...'k~Ynr) 'X1) So that xx ++ (Kx,( oookv,x..)) (Kxl(ob~kv lxi.e)) (KXKXl,(oookv xoo){ook x..o) x ) 1i 1 (KxKxl (kvxk ix) ~ X ++ (KXX, (o okV'XX V) (using Lemma 2) as required, Implementing this as a machine decomposition yields the following configuration: (KK,o 0oK), - ~X/K<~~,7 Z AMK

10 We see that the inefficiency is due to the fact input X is not allowed to pass to the Z map directly (as in the case in the construction of Theorem 1). To make up for this an expensive coding is required allowing Z to reconstruct the necessary information 5 All this is due to the restrictions placed on semidirect products of monoids which are not necessary for semi-direct products of machinesO In case K is normal submonoid of a monoid X but = coincides with the K identity (x,y E X implies x = y iff x = y) it is still possible to obtain the coarser two sided congruence, defined for all x,y ~ X by x =y iff there are kl,k2 C K such that klx = ky K 1 k2 We 'leave it to the reader to verify that _ is indeed a congruence or see [2] and that K refines -o Using - we can obtain a decomposition of M[X] K K K which, however, requires feedback, a subject treated in a coming report.. Roughly this is because every x is completely specified by two (rather than one) elements of K in addition to its representative and the next value qf one of these can be computed only with knowledge of all three quantities. Because the construction is rather messy, we relegate its discussion to the Appendix. Note that Z satisfies the associativity requirement.by inducing permutations on the vector (kvx, x.o, kv x) which contains all the necessary i 1 n information to compute the transition.

APPENDI X Let X be a monoid, K a normal submonoid of X and the congruence K as defined above~ Let x' denote the unique representative of [x] in X/_O K Then every x s X satisfies at least one equation of the form Q x = k x' X X for some 2,k c Kb X X Let K(x) = {(zx, kx) IXX = k x'} We shall impose the condition that if x,y (x # y) are in the same class, their associated sets K(x), K(y) are disjoint, vizo *) x K y and x 9 y implies K(x)/f K(y) =0 for all x,y c X. Lemma 30 (2xkx) c K(x) implies (2x (xy,kxkx ) c K(xy) where Z(xy) is some element in K depending on x and y, and kx, is a right member of some (xyPk xoy) e K(xly)o Proof~ Since K is normal (xK = Kx for all x e X) the equation 2X yX y = x'yL0 has a solution QO ~ Ko By definition (of K(x'y)) xV'yy = kxoy(xy)' (using Lemma 1) o So implying kxX = kxkxy(xy)' implying kxxyo = kxkxt y(xy) (using the definition of K(x)) implying x,y) xy = kxkx y(xy)e (again using the normality of K) implying (2x (xky),kxkxy) E K(xy)0 QoE0D0 11

12 Theorem 3, Let K be a normal submonoid of a monoid X such that condition *) holds, M[X] is a homomorphic image of a submachine of a semidirect composition of M[X/E] = (X X/E>, M[K], and M [K] (where Mf denote K K a machine with feedback, see definition 1, Section 2). Proofo The required composition is diagrammed as k X _ The relevant submachine will have state set Q- = {([x],x,k) I[x] E X/K-,(x,kx) E K(x)}, K XX The connecting map Z1: (X, X/-?) K is defined by y[X] =k x'y for all y c X, [X] E X/K where kxy is arbitrarily chosen but fixed right member of some (X, y kx,y) e K(x'y). The map Z2 (X, X/K, K, K) + K is y K defined by.7([x],zx~kx) = y (X'xk (xy) for all y E X, ([x],k x,) E Q where 2(xy) may be computed as in Lemma 3, i.e., (tx (xy),kxkx y) c Kxy, The operation of the machine will now be =x (] k kxy ) = ( [XY] x xy ) k xkxy) = ( [x], xy kxy) where (2xykxy)= (xz(xy), kxkx,) E K(xy). It is now obvious that the identification ([X],Qx,kx) + X is a homomorphism onto M[X]o The condition *) guarantees that no ambiguity

13 arises, iLeo, x # y implies ([x]9kxx ) t ([y]l,9yky)o Note that although feedback is required around the last M[K], no resets have been added to it so that its monoid has not been enlarged nor has it been made to act merely as a delay~ Finally9 we observe that condition *) is equivalent to requiring certain left cancellation properties hold with respect to Ko Propositionn *) holds if, and only if, for all x,y c X, k c K, x - y and kx = ky implies x = yo Proofo Suppose x t y, x _ y and (tk) e K(x) f K(y)o Then Qx = kx' and Zx = kx so Qx Q-y implies x = y a contradiction0 Conversely, suppose x = y, x $ y9 and kx = ky for some k c K8 By K normality, find some Q0 c K such that kx = x= ~x kx implies Qxt0 kXx tO implies X k = kXX O implies 2 kx = k X (again using normality)o But also Z ky = k xAx" so (zxkpkxtL) E K(x) n K(y) and *) does not holdo QoEoDo The observation and proof of this proposition are due to Stewart Bainbridge

REFERENCES 1. Y. Give'on, "Categories of Semimodules," Systems Research Center, Case Institute of Technology, SRC 100-C-66-40. 2. B. P. Zeigler, "Degenerate Automata: Some Relationships Involving Semigroup_ Order and Regular Events," University of Michigan Technical Report. 3. K. H. Hofmann, and; P. S.:Mostert, Elements of Compact Semigroup, C. E. Merrill Booksj Inc., 1966. 4. M. Arbib, The Wreath Product Made Simple, Stanford University. 5. K. Krohn and J. Rhodes, "Algebra Theory of Machines: I. Prime Decomposition Theorem for Finite Semigroups and Machines," Trans. Amer. Math. Soc. 116 (1965) 450-464. 6. M. Arbib, The Theory of Abstract Automata. 14

DISTRIBUTION LIST (One copy unless otherwise noted) Technical Library Naval Electronics Laboratory Director Defense Res. & Eng. San Diego 52, California Room 3C-128, The Pentagon Attn: Technical Library Washington, D.C. 20301 Dr. Daniel Alpert, Director Defense Documentation Center 20 Coordinated Science Laboratory Cameron Station University of Illinois Alexandria, Virginia 22314 Urbana, Illinois Chief of Naval Research 2 Air Force Cambridge Research Labs Department of the Navy Laurence C. Hanscom Field Washington 25, D.C. Bedford, Massachusetts Attn: Code 437, Information Attn: Research Library, CRMXL R Systems Branch U. S. Naval Weapons Laboratory Director, Naval Research Laboratory 6 Dahlgren, Virginia 22448 Technical Information Officer Attn: G. H. Gleissner, Code K4 Washington 25, D.C. Asst. Dir. for Computation Attention: Code 2000 National Bureau of Standards Commanding Officer 10 Data Processing Systems Division Office of Naval Research Branch Office Room 239, Building 10 Box 39, Fleet Post Office Washington 25, D.C. New York, New York 09510 Attn: A. K. Smilow Commanding Officer George C. Francis ONR Branch Office Computing Laboratory, BRL 207 West 24th Street Aberdeen Proving Ground, Maryland New York 11, New York Office of Naval Research Office of Naval Research Branch Branch Office, Chicago Office 230 North Michigan Avenue 495 Summer Street Chicago, Illinois 60601 Boston, Massachusetts 02110 Commanding Officer Naval Ordnance Laboratory ONR Branch Office White Oaks, Silver Spring 19 1030 E. Green Street Maryland Pasadena, California Attn: Technical Library Commanding Officer David Taylor Model Basin ONR Branch Office Washington,D.C. 20007 1076 Mission Street Attn: Code 042, Technical Library San Francisco, California 94103

DISTRIBUTION LIST (Concluded) The University of Michigan Lincoln Laboratory Department of Philosophy Massachusetts Institute of Technology Attn: Professor A. W. Burks Lexington 73, Massachusetts Attn: Library National Physical Laboratory Teddington, Middlesex, England Office of Naval Research Attn: Dr. A. M. Uttley, Supt. Washington 25, D.C. Autonomics Division Attn: Code 432 Commanding Officer Dr. Kenneth Krohn Harry Diamond Laboratories Krohn Rhodes Research Institute, Inc. Washington, D.C. 20438 328 Pennsylvania Avenue, S. E. Attn: Library Washington 13, D. C. Commanding Officer and Director U. S. Naval Training Device Center Dr. Larry Fogel Orlando, Florida 32813 Decision Science, Inc. Attn: Technical Library 6508 Pacific Highway San Diego, California Department of the Army Office of the Chief of Research National Bureau of Standards and Development Applications Engineering Section Pentagon, Room 3D442 Washington 25, D. C. Washington 25, D.C. Attn: Miss Mary E. Stevens Attn: Mr. L. H. Geiger National Security Agency Fort George G. Meade, Maryland Attn: Librarian, C-332

Unclassified Security Classification DOCUMENT CAi.-r-:L DATA - R&D (Security claselfication of title, body of astract and indexing annotation must be entered when the overall report is classafied) 1 ORIGINATIN G ACTIVITY (Corporate author) Za. REPORT SECURITY C LA$SSIFICATION Logic of Computers Group Unclassified The University of Michigan GROUP 2b. GROUP Ann Arbor, Michigan 48104 3. REPORT TITLE DECOMPOSITIONS OF AUTOMATA USING NORMAL SUBMONOIDS 4. DESCRIPTIVE NOTES (Type of report and inclueive date,) 5. AUTHOR(S) (Lost name. first name, itntial) Zeigler, Bernard 6. REPORT DATE 7A. TOTAL NO. Of PAGES 7b. NO. OF REFS December, 1967 14 6 8a. CONTRACT OR GRANT NO. 9a. ORIGINATOR'S REPORT NUMBIR(S) Nonr 1224(21) 03105-50-T b. PROJECT NO. c. ob. OTHER RPORT NO(S) (Any other numbers tht may be assigned this report d. 1 O. A VA IL ABILITY/LIMITAtION NOTICES Qualified requesters may obtain copies of this report from DDC. Distribution of this document is unlimited 11. SUPPL EMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Office of Naval Research Department of the Navy Washington 25, D.C. 13. ABSTRACT Aspects of decomposition of automata using normal monoids are discussed. A simplified cascade connection procedure is given which can be specialized to the case of normal subgroups, but which introduces some novel features, e.g., the use of feedback in the tail machine, when applied to normal submonoids in general. Differences in efficiency between decompositions based on semidirect products of machines versus those of semigroups are also discussed. DD 1,JAN 641473 Unclassified Security Classification

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

UNIVERSITY OF MICHIGAN 3 9015 03527 6180