THE UNI VERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Note NOTES ON MATHEMATICAL AUTOMATA THEORY J. W. Thatcher ORA Projects 03105 and 05662 under contract 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 December 1963

INTRODUCTION The formulation of the concept of finite automaton in terms of monadic algebras is due to J. R. Buchi ([3], [5]). The author of these notes was first introduced to this notion in a seminar conducted jointly by Buchi and J. B. Wright in the fall of 1960. The equivalence with the usual definitions (see, for example, Rabin and Scott [14]) is clear. But, in the author's opinion, the present definition has definite advantages. In considering the theory of the structure of finite automata (as opposed to the behavior), the set of final states can be dropped from the definition. Here, results from the study of abstract algebras yield directly, for example, the decomposition theorems for finite automata to be found in Hartmanis [7]. But at least as important as the direct application of known results from abstract algebra, is the insight and motivation that derives from such a formulation within the domain of a well developed branch of mathematics. The purpose of these notes is to present some of the basic concepts and results of finite automata theory within this algebraic framework. Much of this material is already available in the notes of the seminar [3] referred to above. 1

I. MONADIC ALGEBRAS Definition.1: A k-monadic algebra is an abstract algebra, i = (A, oa o ato., with one distinguished element and k monadic operators. A pure monadic algebra has no distinguished element. The modifier "k-monadic" will often be omitted. Also the letter a will denote an arbitrary k-monadic algebra with components as in Definition 1. The following concepts are concepts of abstract algeibra and are reviewed here for the special case of monadic algebras.l Let a be a k-monadic algebra. The algebra,'^ = (A ta,',...O1 is a subalgebra of( if A' c A, a( is the restriction of ai to A' (cZi = ailA') and aO =aO An element a c A is a generator of CZ if for every a' c A there exists an operator a which is a composition of the ai such that aa = a'. (Suffix notation will be used for the operators of a monadic algebra.) An algebra is said to be monogenic if there exists an element a c A such that a is a generator of Z. Let 0 be a second monadic algebra, 2

A function h from A onto B is a homomorphism of a-onto 3 if: i) h(ao) = b ii) h(aOj) = h(a)Pj a e A, j = 1,2,...,k. We will write a - (Q3 if there exists a homomorphism from 62Zonto. If h is a one-to-one homomorphism of CConto 43then aOis isomorphic to (3, 6? r.2 A congruence relation on a monadic algebra Qis an equivalence relation, A, on A with the property: a at a' + aaj C at'a j = 1,2... k. Every homomorphism h on a monadic algebra induces a unique congruence relation denoted h: a th a' h h(a) = h(a') Further, given the conguence relation Ar on Z., the natural homomorphism h is defined h (a) = ~a where ja is the congruence class to which a belongs. This homomorphism maps 6 onto the quotient algebra e/it where, /nI = ( A/it, rta,c il/it,...,*kt > 5

and, A/t = (a: a e A) (jTa)ajl = aCj j = 1,2,...,k. Definition 2: 6 is a reduced k-monadic algebra if ao is a generator of Z. For an arbitrary k-monadic algebra, 6Z, the reduced monadic algebra, rd(a), is the subalgebra of generated by ao. The domain of rd(Z) will denoted rd(A). Alternatively Z is reduced if a contains no proper subalgebra; rd(ez) is the smallest subalgebra of Z. In the following discussion allmonadic algebras will be assumed to be reduced. The term monadic algebra will mean reduced monadic algebra unless stated explicitly to the contrary. 4

2. THE FREE MONOID - LATTICES OF CONGRUENCE RELATIONS Let Nk be the set of all words on k distinct letters, Zk = (1,2,...,k] including the word X of zero length. The length of a word x is the number of letters in x. Let Ok be the free monoid on k generators; L =k = (Nk,concatenation,h. Throughout this paper the variables, x,y,z,w,xi,yl,..., will range over Nk. Every homomorphism of'7k determines a congruence relation on'k. Explicitly an equivalence relation it on Nk is a congruence relation if: x it y + VzVw[zxw rt zyw]. We will also be interested in right congruence relations which are equivalence relations, which satisfy x At y - vz[xz t yz]. Similarly a left congruence on -Wk is an equivalence relation i for which x t y + vz[zx zy]. For equivalence relations it1,it2 on any domain Vte will use the notation t1i c it2 for set theoretic containment of ordered pairs (ji refines t2). The lattice operations will be denoted 5

Iti U It2 = lub(it1it2) lt n it2 = glb(tl,3t2). The meet, Ati r T2, is the set theoretic intersection of iti and t2 as sets of ordered pairs. The join, itl u t2 is the smallest equivalence relation containing ti and t2. Alternatively, t u t2 is the transitive closure of the set theoretic union of Ail and 92. For two relations i1,J2, the product of 1t and i2 (composite, relative product or Peirce product) is the relation t1t2 defined by, x it1iT2 Y * Zz[x Itl Z AZ t2 y]. Two relations I1,It2 commute if I1it2 = t291. Note that if this is the case 4 then At1t2 = Xt1 v 242. The universal relation on a domain will be denoted A\, the identity will be denoted $. Let Rk and Rk be the sets of right congruences and congruences on m7k respectively. Then ( and U are lattice operations on Rk and on Rk.5 We will denote the lattices by 6Pk and <k: 6k = ( Rk^nyy)l Ok = < k,(.YAy, > Definition 3: Let t be an arbitrary equivalence relation on Nk. The relations a, t, and i are defined as follows: i) x jt y < Vz[zx t zy] 6

ii) x i y < vz[xz t yz] iii) x X y v* vzvw[zxw zyw]. I is the induced left congruence, X the induced right congruence, and X the induced congruence of i. Theorem 1: jX (lg ) is the maximal right congruence (left congruence, congruence) which refines K. This theorem in the form presented here is due to Buchi. It is the fundamental part of the minimality theorem for (finite) automata. 7

3. DERIVED MONADIC ALGEBRAS Let (/= (S,.,e) be an arbitrary monoid with identity e and generators sl,...,sk. Define for s c S. the right translation, Rs of by s by: Vs'1 (s)Rs = S's. The dot will usually be omitted in the product operation. Let (^y =< ([Rss C SI,composition,Re) It can easily be verified that /Y~ Pj (Caley's theorem for monoids). From the monoid Jwith k generators we define the k-monadic algebra J derived from j 6'' = (Se,Rs"' Rsk) Note that since sl,... sk are generators of the monoid /, e will be a generator of the monadic algebra ~o The free monoid.k was defined above. The associated monadic algebra is 9k = Nk r;,.L'.. erk) the free k-monadic algebra. In the notation for 9?k, rj is the right translation of'/?k by the generator j: x rj = xj, j~ Z. 8

4. CONGRUENCES AND TRANSITION ALGEBRAS In the last section the free monadic algebra was derived from the free monoid. Alternatively the standard method of constructing the free algebra could have been employed, the result being isomorphic to i.k' Suppose that O6 is an arbitrary (reduced) k-monadic algebra. Since Y7 k is free on the generator X, the mapping of X onto the generator ao of G can be extended uniquely to a homomorphism I k onto C>. This relationship is important in both the theory of structure and behavior. Deriving jk in the manner above and associating a word in Nk with every composition of functions in a monadic algebra (Definition 4) we are able to use this property of the free algebra conveniently. Definition 4: Let 2.-be a k-monadic algebra. For x C Nk, the transition operator of x is the operator cx on A defined by the recursion: ac0 = a aoxj = (acx)oj. Thus if x is the word, jlj...in, then ax is the composition of functions Uj1,Yj2",'',ajn' %a1'J2'= e *.jjjn' 2....e jn n This correspondence indicates the motivation for the choice of suffix notation 9

for the monadic operators. The condition that an equivalence relation iT be a congruence relation on <- was stated in Section 1. A simple induction shows that this is equivalent to the condition: a it a' + Vz[Laaz t a'a]. Similarly, the second condition for a homomorphism can be stated: (ii) Vx[h(aox) = h(a)Px] Proposition 1: If t is a congruence on "2k then t is a right congruence on 4k and conversly. Proof: If t is congruence we have from the observation above that for all x,y,z in Nk; x j y + [x rz 3t y rz xz Jt yz1 Proposition 1 establishes the fact that the congruences on ~k are precisely the right congruences on "?k. Let aC be a k-monadic algebra. The mapping of X onto the generator ao of cZ is extended to the homomorphism Z: k +-L by y (x) = aoOx. The congruence relation thC on 7k will be denoted at: x ~t, y +- hy (x) = ~b (y) + ao0xc = aoay. 10

From Proposition 1 and the definition of 1h~ we have: Proposition 2: Let a-be a reduced k-monadic algebra. i) T/k _ 6 (the homomorphism is h ) ii) T,, is a right congruence on'i/k Proposition 3: Let 2..and (. be reduced k-monadic algebras, then with isomorphism if and only if 7ta = / ~3 Proof: Let g be the homomorphism C onto o The homomo-rphism h, is unique and gha = hB since gh is a homomorphism 71k onto 3. Hence, x a y y h. (x) = h, (y) +g (x) = gh (y)* h(x) = gh (y) + x TC y If g is an isomorphism then = j. Conversely, assume Jr. c r. We define the homomorphism g: C( + (- as follows: g(h (x)) = h3 (x)o g is well defined since?th (x) is a homomorphism onto al. We show that g is a homomorphism by, g(hc (x)oy) = g(hl(xry)j = h6(xry) = h =(x) y, 11

since hC and hO are homomorphisms. The mapping is onto since hu is onto. If Jt = Jt6 then, [h (x) = h (y)][h6 (x) = h, (y), and g is an isomorphism. Proposition 4: Let C6 be a reduced k-monadic algebra and let a be a congruence on -k. (i) Jt = a 7k/a (ii) 6Or tt/7^ Proof: (i) the homomorphism ha from 7k onto ik/a was defined in Section 1 with ha(x) = ax. But, x 3 Y t* ax = cy a x a y. (ii) From (i) with a = U we have i = rAi. From Proposition 3 the equivalent congruence relations yield the isomorphism (ii). Let 2k be the partially ordered set of isomorphism types of reduced kmonadic algebras. Proposition 4 establishes a one-to-one correspondence between /k and /\k. Let r be this correspondence. Then -(a') = it K1 (t ) ='k/K 12

' and'-1 are well defined by Propositions 1 and 2. From Proposition 4 we have: t-1l(6) 1 a VK-1Qr) = n. Further, 4 is order preserving by Proposition 3. This one-to-one correspondence induces lattice operations on nk. In particular: Proposition 5: k is a lattice with meet and join v: at6B = glb(a,6) = -l(r (a ^( ) 1V28 = lub( L,o ) = t-l(t(a)( )) Propositions 4 and 5 may be interpreted to say that the theory of reduced k-monadic algebras reduces to -the theory of right congruences on lk. The set of functions Co for x c Nk forms a monoid ~ which will be called the transition monoid of 06': Fa = ([C: x c Nk) = ( F,composition,oaj. Note that the set F6 of transition operators is a subsetof the set of all functions from A into A. If A is finite Fi is finite. Since it is assumed that Zis reduced, I| I > |A|. Now the derived algebra of ( can be formed. We will denote this by 13

a = <(F,, a,, * *R*), Definition 2: A k-monadic algebra, 6b, is a transition algebra if a. For an arbitrary k-monadic algebra, e is called the transition 8 algebra of. The second part of this definition is justified by observing that L Z ~A. This follows from Caley's theorem. Note that since a transition algebra is isomorphic to a derived algebra of a monoid it follows that a transition algebra is always reduced. Proposition 6: Let 6be a reduced k-monadic algebra. i) it is a congruence on'.' ii) - _ t iii)'7k 5 U 5 iv) it is the maximal congruence of /1k refining the right congruence it' Proof: (i) The homomorphism h: ~ + Z is defined by h (x) = x. Since h is a mapping of Nk onto F it is a candidate for a monoid homomorphism Ak onto A. Indeed, h (xy):= xy = axy = h (x)h (y). With h_ a homomorphism of''rk we have (i). (ii) Let x,y be elements of Nk. 14

x 3 y, a = O + aO = aO * x W y. x y ox y Hence r C it. (iii) From (ii) we have Z < 61 by Proposition 3. (iv) Assume nT is a congruence on 2/k refining Ta. Then for any x,y in Nk, x a y + Vz zx a zy + VZ zx J6t zy + vz aoazG x = aoazy -+ a aax = aOy a A ~x= -ay o x Xr y. Hence c refines i and (iv is established). From the homomorphism h: -c + k we have the Corollary: For a k-monadic algebra, J,; k/_ Proposition 7: Let a be a reduced k-monadic algebra. The following statements are equivalent: i), is a transition algebra. ii) T = r iii) 3rZ is a congruence on k.' iv) aox = aOy + a =a Yx y Proof: We will show (i) + (ii) + (iii) - (iv) - (i). By Definition 5, if 6is a transition algebra then 6Z =and by Proposition 3 it = t Since it is a congruence (Proposition 6, (i)) tc..is also congruence. If Cit is a congruence then t- = it by Proposition 6 (iv) and 15

ax ao x= r, y - x T_ y+c x: = ay Statement (iv) in turn implies X = t and by Propositions 3 and 4 CZ, We obtain a further characterization of finite transition algebras by the following: Proposition 8: If Tfis a finite reduced k-monadic algebra then CL-is a transition algebra if and only if IFm I = IA|. Proof: If IF I = IAI then the homomorphism CLO onto OLmust be one-toone. Conversely if the homomorphism is one-to-one and A is finite, IF I = IAI. Let T be the partially ordered set of isomorphism types of k-transition algebras. From Proposition 6 (i) l/wk is a partial order isomorphism between t k and A k. Hence withA and Vas specified above Tjk is a sublattice of i.k 16

5. THE DIRECT PRODUCT OF MONADIC ALGEBRAS The direct product of two k-monadic algebras Oand dOis the monadic algebra 06- x 6 = (A x B,<aO,bo>,ai x P,... x Pk, X where A x B is the cartesian product of the sets A and B and for any pair <a,b> ~ A x B the operations ai x Pi are defined by, <ab> ai x i = <aaibPi> Let yi be the operator Ci x Di. From the recursive definition of Yx we note that: = ax x l. By induction assume that 7x = Cx x Px Then <mP> (ax x x)(i x i) = <aax,bPx> (ai x Pi) = <aaxi bPxi>. Hence yxi = axi x Pxi. And we have that for every x e Nk Yx = Ax x PxAlthough both a and 3 may be reduced (as is our general assumption) it is not necessarily the case that a x 3 is reduced. We will use the notation x x 63 = rd( cx x ). 17

Hence CZ x 3 (the reduced direct product) is the smallest subdirect product of 6C and Q. Theorem 2: (A generalization of a theorem of Birkhoff [1] applied to the special case of monadic algebras.) Let 7 be a reduced k-monadic algebra and let Ia be two congruence relations on CZ. Then hc/ _x C/a') 6?/7t n a. Proof: We first observe that the pair <aaat> is in the domain of aJt x 8J/a if and only if'ta ( aat $'. Suppose a"' 7a A aa Then assume ao0x = a". We have <Aaoaao> (cx/I x cx/a) = <a1,,aa,1> = -aaa1> Conversely if the above equation holds a"e ta n cat and ta Ca' #. We define the natural mappings: $: rd(A/g x A/a) + A/s r0 a by O(taca) = a a C a, This is well defined and onto by the observation above. That $ is a homomorphism follows from the fact that (ganaa)Ox/na = Caax n aaOx * The mapping is one-to-one since Aa n aa = na'r a't if and only if ja = ta' and aa = aa' - The following corollaries follow directly from Theorem 2: 18

Corollary 2.1: If 9n is a reduced k-monadic algebra and Xt and a are congruences on 0o/ then: T r = _ 6Za / x Z/r a C Corollary 2.2: If 6i, is a reduced k-monadic algebra and Xi and a are congruences on ff then: Xr a = /| a<- x 6a / jgc n a The hypotheses of Corollary 2.2 may be restated by saying that Et and C commute and T V( = /. The following corollary is essentially the theorem of Birkhoff ([2] Theorem 4, page 87) restricted to two factors which are monadic algebras. Hartmanis [7] states this result as a necessary and sufficient condition for the decomposition of a machine into the direct product of simpler machines. Corollary 2.3: For a reduced k-monadic algebra a, with congruences and Ta, 67r x X 61 if and only if the following three conditions hold: i) r,a commute ii) Vt a = iii) jr n a = $. Corollary 2.4: Let a and 6 be two k-monadic algebras. The induced 19

congruence Ar( x, is precisely At n 6t. Corollary 2.5: The operation A in the lattice of isomorphism types of reduced k-monadic algebras is precisely the operation x (reduced direct product). 20

6. MONADIC ALGEBRAS - BEHAVIOR Definition 6: An interpreted k-monadic algebra is a system denoted W[A'] were 61 = <A,ao,al,...,>) is a monadic algebra and A' is a subset of A. For any monadic algebra aC and any subset A' C A there is the corresponding interpreted monadic algebra Ci[A']. Let aC[A'] and e[B'] be two interpreted monadic algebras. A homomorphism h from ta onto 3 is a homomorphism AL[A'] onto /3[B'] if in addition iii) a e A' + h(a)c B'. We say h is a strong homomorphism if we replace (iii) by: iii') a e A' 4+ h(a)e B'. AA'] is isomorphic to 3[B'] just in case there is a strong homomorphism from aZ[A ] onto 6[B'] which is one-to-one. We will use the notation.a[A'] <i n[B ] for the existence of a homomorphism from a[A'] onto [B' (not necessarily a strong homomorphism). Definition 7: Let [A'] be an interpreted monadic algebra. The behavior of a[A'] is a subset of Nk: bh6 [A'] = (x: aocx E A') 21

A subset r of: Nk is definable by a monadic algebra a if there exists an A' C A such that b1i (A') = r.9 Note that for a fixed algebra (7, bhf can be viewed as a function from pA into pNk. In fact the range of bh~ is a boolean algebra of subsets in pNk with bh (A') n bh (A") = bh (A' n A") Nk - bh (A') = bh (A - A'). It should also be observed that every subset r of Nk is definable by some monadic algebra. In particular r is defined by wk[F]. Definition 7 corresponds to the usual definition of behavior; the set of all words which cause transition from the initial state to one of a set of designated "final" states. Alternatively we obtain: Proposition 9: For any monadic algebra 6L and any subset A' c A, bh (A') = h-(At). With this characterization of definability we can indicate the correspondence between definability and homomorphisms. Proposition 10: (Buchi) let 06 and 6 be two reduced k-monadic algebras with c6 - (5. Then if r c Nk is definable by 3, r is definable by a-. Proof: Let g be the homomorphism e onto 6 and let r = h-l (Bt). Since he = gh, we have r = h1 g-l(B') and hence r is definable by 61 with A' = g-l(B'). 22

Proposition 11: Let a[A'] and ([B'] be two interpreted reduced kmonadic algebras. [A'] /3[B'] -bh (') c bh (B') with equivalence of behavior just in case the homomorphism is a strong homomorphism. Proof: Let g be the homomorphism if C6 onto 6. Then, bh (B') h -(B') = (B') h (A'): bh () since g-l(B') c A', where g is an interpreted monadic algebra homomorphism. And g'1(B') = A' if g is a strong homomorphism. The transition algebra of CZ was defined above. We can find a corresponding interpreted transition algebra as follows. Let A' = (ca: aoZx E A') The honomomorphism from (6, onto 0k is not a strong homomorphism from $[TA'] onto 0[A'] and hence bh (A') = bh (A') from Proposition 11. Hence we have the Proposition 12: Any subset r c Nk definable by a monadic algebra Zis definable by its transition algebra'6. For a subset r c Nk, the relation of r is the dichotomy y: x r y * (x e r + y e r). Proposition 13: If a is a k-monadic and P c_ N is definable by eZ then 23

27 Proof: Let A' c A such that r = bh (A'). If x g y then aoo0x = aocy and hence aox e A' + aOay e A'. And by definition x e bh (A') * y e bh, (A'). Proposition 14: If t is a right congruence on'k refining the dichotomy y then F = bh (r/i). 1k/ Proof: r/I is well defined since T C Y. 77k/r is a monadic algebra since it is a congruence on'?k. h is the homomorphism k -+* )ik/it and indeed hK is a strong homomorphism'T/k[r] onto /-k/it[r/it]. Hence Proposition 14 follows from Proposition 11. From Propositions 13 and 14 we obtain the necessary and sufficient conditions for a subset r c Nk to be definable by a k-monadic algebra (U. Corollary: r is definable by CU if and only if it c 7. The existance of a maximal algebra (with respect _), for which r is definable is insured by this Corollary and Theorem 1. Theorem 3: r is definable by k/27 where y is the induced right congruence of y. If r definable by CL then 6-L _ Lk/21 Proof: From Theorem 1, y is a right congruence on ik hence )7k/. is well defined and y < y. Hence by the Corollary (and Proposition 4) r is definable by Xk/2y 7 is the maximal right congruence refining y. By the Corollary again and the partial order isomorphism of Kk and'" /k' 77k/27 is maximal among machines for which r is definable. 24

7. NON-DETERMINISTIC AUTOMATA - TRANSITION SYSTEMS Definition 8: A pure k-transition system -t is a relational system: 7 = (T,T1,...Tk) where Tl,... Tk are binary relations on T. Note that the study of pure transition systems includes the study of pure monadic algebras by restricting the relations to be functional. Definition 9: For any x e Nk, the transition relation of x, Tx, of a pure k-transition system'7is defined by the recursion: T = (<tt>: t e T) Tx: = txtj j = l,...,k. Tx = TxTj The relation TX is the identity relation on T. In general the relation T y is the product TxTy. Analogous to the case for monadic algebras, the set of transition relations, TX for x e Nk, under product forms a monoid with identity, TX. Explicitly, we define the transition monoid ( of a transition system l as follows: FT = (Tx x c Nk ~ = ( r-, product, T)>. eD

Hence from the transition system'7 we can form the transition algebra associated with j7~: T ~i= <5-,TXRTl..,R k.). The direct product of two transition systems -aand % —is the system 64 x = ( S x T, a x TI,...,k x Tk ), where, analogous to the case for algebras, the relations are analysed by components: <s,t> ai x Ti <stt'> s ai s A t Ti t'. S x T is the cartesian product of the domain of land /7. 26

8. BEHAVIOR OF TRANSITION SYSTEMS Definition 10: An interpreted transition system denoted 7lT~,T'] is a transition system = T,T7,.. Tk where T~, T and subsets of T. Definition 11: The behavior of an interpreted transition system [TO,T'] is a subset of Nk defined as follows bh (T0~T) =: t u t x u. )1-F ( tt c.'T~u c T' x A subset F of Nk is definable by a transition system /-rif there exist subsets To T' of T with bh (T,T') = r. Every monadic algebra 7JA'] can be formulated as a transition system 7-[TO,T'] where T~ is chosen as the singleton set (ao) and T' = A'. Then every behavior of a monadic algebra is the behavior of a transition system. We will now obtain the converse. Let 7 be the transition algebra associated with a pure transition system / Define the set T' as follows: T'= TX: t T~ u T' t Tx u} The subset T' of the set F_ is the set of all transition relations which relate an initial state with one of the final states. 27

Theorem 4: Let'TT~,T'] be any interpreted transition system and let [T] be the interpreted transition algebra defined above. Then bh (T~,T') = bh (T'). Proof: Let x be any word in Nk. We have by the definitions above: x e bh(T~,T') -T x e T' <- x e bh_[T'] where we recall that: x e bh [T']<* TTTx e T' <+ TX T' Corollary: (Myhill) any subset r of Nk definable by a transition system, ^, is definable by the transition algebra "-. Further if f- is finite then -is finite. The second part of this Corollary follows from the fact that F is finite if T is finite. In particular, IT12 i I < 2, since the number of relations in F< is no greater than the total number of relations definable over the set T. 28

FOOTNOTES 1. See, in particular, Birkhoff [2], Forward on Algebra and Chapter VI and Birkhoff [1]. 2. When the binary transition function is used, as Weeg [16] observed, functions which we would like to call homomorphisms are not quite such since the alphabet is not effected by the mapping (this, of course, is not always the case, for example, see Ritchie [15]). The "operation preserving functions' are precisely homomorphisms in the formulation being presented. 3. A reduced algebra is one in which every state is accessable. If CL is a pure monadic algebra then the property of being reduced corresponds to that of strong connectedness (Moore [11]). In a strongly connected automaton every state is a generator. That homomorphisms preserve strong connectedness follows from the fact that in any algebra the homomorphic image of a generator is a generator. 4. Congruence relations which commute play an important role in the decomposition theorems for algebras. The pioneering paper discussing the importance and properties of such relations is Dubreil [6]. See also Birkhoff [1,2]. 5. Rk is the set of congruences on 6Xk and by Theorem 5, page 24, Birkhoff [2], ~k is a lattice. If t, c are right congruences on f than one can 29

verify that it r o is a right congruence as is t U a. Hence 2k is a lattice. It will be shown below that /k is precisely the set of congruence relations on the free monadic algebra and the lattice property of R k again follows from Birkhoff's theorem. 6. This construction was used by Medvedev [10] in specifying the automaton defined by a semigroupo 7. This semigroup is called the semigroup of CU by Myhill [13]o In this paper some of the relationships between ( and the structure of 6Zb were studied. 8. If CZ is a transition algebra, ( is isomorphic to the monoid of endomorphism of -. Let Aft be the largest submonoid which is a group (see Kimura [8]), then is the group of automorphism of 6Z. This is called the group of 6C, by Weeg [16]. 9. In the terminology of [14] and [15], bh [A'] is the set of tapes accepted C! by a2[A']. The term behavior is used by Kleene [9]. Also, "recognizable" and "representable" are to be found in the literature in place of "definable." 10. An interesting generalization of Definitions 10 and 11 suggested by Wright is as follows: Let P be an arbitrary relation on the domain T of the transition system T7 An interpreted k-transition system is the system 7-[p ] (alternatively a relational system with k+l binary relations) and 50

bh (p) = (xITx P # 0) We obtain 10 and 11 as special cases with p = T~ x T'. 31

BIBLIOGRAPHY [1] G. Birkhoff, Structure of Abstract Algebras, Proc. Cambridge Philos. Soc., 29 (1935) pp. 441-464. [2] G. Birkhoff, Lattice Theory, A.M.S. Colloquium Publications, XXV (1948). [3] J. R. Buchi, Mathematical Theory of Automata, Notes on Material presented by J. B. Wright and J. R. Buchi, Communication Sciences 403, Fall 1960, The University of Michigan. [4] J. R. Buchi, Regular Canonical Systems and Finite Automata, University of Michigan Research Institute Report 2794-7-T, October 1959. [5] J. R. Buchi, Mathematische Theorie des Verhaltens end licher Automaten, Zeitschr. fur Angewandte Math. und Mech., 42 (1962) 9-16. [6] P. Dubreil and M. L. Dubreil-Jacotin, Theorie algebrique des relations d'equivalence, Journal de Math. 18 (1939) p. 63. [7] J. Hartmanis, Symboic Analysis of the Decomposition of Information processing Machines, G. E. Research Laboratory Report 60-RL-2315-E, Schnectady, New York, January 1960. [8] N. Kimura, Maximal Subgroups of a Semigroup, Kodai Math. Seminar Reports 6 (1954) p. 85. [9] S. C. Kleene, Representation of Events in Nerve Nets and Finite Automata, Automata Studies, Annals of Math. Studies, No. 34, Princeton University Press, Princeton, New Jersey, (1956) pp. 3-42, C. E. Shannonand J. Me Carthy, Eds. [10] I. T. Medvedev, On a Class of Events Representable in a Finite Automaton, (Trans. by Jacques J. Schoor-Kon) Lincoln Laboratory Group Report 34-73, Lexington, Mass. June 30, 1958. [11] E. F. Moore, Gedanken Experiments on Sequential Machines, Automata Studies, Annals of Math. Studies, No. 34, Princeton University Press, Princeton, New Jersey (1956) pp. 129-153, C. E. Shannon and J. McCarthy, Eds. [12] J. Myhill, Finite Automata and the Representation of Events, Fundamental Concepts in the Theory of Systems, Section V, WADC Tech. Report WADC TR 57-625, May 1957. 32

Bibliography (Concluded) [13] J. Myhill, Transformation groups associated with Finite Automata, University of Michigan Summer Conference Notes (1960). [14] M. O. Rabin and D. Scott, Finite Automata and their Decision Problems, I.B.M. J. of Res. and Dev., 3, No. 2, April (1959), pp. 114-125. [15] R. W. Ritchie, Classes of Recursive Functions of Predictable Complexity, Doctoral dissertation, Princeton University. [16] G. P. Weeg, The Structure of an Automaton and its Operation Preserving Transformation Group, J. Assoc. Comp. Mach., 9 (1962) 345-349. 33

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. 0. 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 5, 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 391 0ss | II