THE UNIVERSITY OF M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Report DEGENERATE AUTOMATA: SOME RELATIONSHIPS INVOLVING SEMIGROUP ORDER AND REGULAR EVENTS Bernard Zeigler ORA Projects 03105 and 08226 under contract with: U.S. ARMY RESEARCH OFFICE (DURHAM) CONTRACT NO. DA-31-124-ARO-D-483 DURHAM, NORTH CAROLINA and DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR December 1966 Distribution of this document is unlimited.

RESEARCH PROGRESS REPORT Title: "Degenerate Automata: Some Relationships Involving Semigroup Order and Regular Events," B. P. Zeigler, University of Michigan Technical Report No. 03105-45-T. Background: The Logic of Computers Group of the Communication Sciences Department of The University of Michigan is investigating the application of logic and mathematics to the design of computing automata. The application of algebraic techniques to the study of automata forms a part of this investigation,.Condensed Reprt Contents: This report investigates some relationships involving the order of the semigroup of an automaton and a class of automata for which this order takes on its smallest value relative to the number of states4 This class, called degenerate, is a limiting class in the sense that the semigroup order of any connected machine equals the number of states if it is degenerate, and is strictly greater than the state cardinality otherwise. Further, we show by counter-example that this result does not necessarily hold for disconnected machines even when they are reduced in appropriately defined manner. The lower bound on semigroup order is strengthened in the case of strongly connected automata. It is also shown that the class of degenerate automata, as herein defined, properly includes a variety of semigroup and group type automata studied in the literature. The relevance of semigroup order to the number of subclasses and the minimum lengths of strings in an acceptor class are related to the semigroup order, 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,

Acknowledg ements I wish to thank Dr. John H. Holland, Richard Laing and Dr Donald Stanat for their guidance in my first attempt at writing in the area of automata theory. I am especially grateful to Dr. Stephen T, H[edetniemi whose critical reading helped to clarify many obscure points. Thanks are also due to Dro Yehoshafat Give'on for his suggestions concerning simplification of the presentation. Also deserving of many thanks is Mrs. Kuniko Misawa for her patience in typing and retyping this report.

Table of Contents Page Acknowledgements...o... *, b. t. o t,. e. V Preliminary Notation, Definitions, and Theorems.. 1 Introduction *, o....,.,,,,,..,. 4 0. Some Relationshiops Involving Semi-group Order and Regular Events....... * * 6 1.0, Degenerate Machines c. t....... e.... 10 1.1. A Definition of Machine Reduction o ^ 17 1.2, Semi-Group Order and Degenerate Machines........ 20 References r. o. t. c. I D 24 vii

Preliminary Notation, Definitions.. and Theorems.e shall be concerned with transition systems (hereafter called,nachlines) of' the form T' = <S, S vl> where S = input alphabet set Q = internal state set M Q x S —+ Q = the transition function 2 S* = set of all words on S, typically x,y c S*, Z(x) = length of' x 3 b = <{x}, * > ) is the monoic (hereafter loosely called "semigroup") associated with T where def x (q) = l(q'x) for all q e Q, (with M extended to S* via iM(qxs) = M1(M(q,x),s)) and A is the null word, so that.A(q) = Ill(q A) = q= 4 E is an equivalence relation on S* where xEy iff Va ( (q) q)= 1E is a congruence relation, i.eo [x].[y] = [xyJ where [ ] denotes a class of L, and o denotes concatenation. D The monoid S*/E = K{[x]}, o, [ ]> is isomorphic to 4. symbolicall. S*/E iso, KR is a right invariant (equivalence) relation on S where xRq y iff 4x(qi) Y yi(qi). Clearly xIy it f (Vq E Q) (xl y)x 7 lThe following are relations on the set of all right invariant relations over 8*

a. R refines R iff R < R a b a b iff xRay xRbY for all x,y c S*. b. Ra comp. (comparable) Rb iff Ra s Rb V Rb < Ra c. Ra inc. (incomparable) Rb iff %(Ra comp. Rb) iff C3x,y) (xRaY A xRbY) C3x' y')(x'Ry' \A,x'RbY')i 8. A (accessibility) is a reflexive, transitive relation on Q where ql A q2 iff (Cz)(M(qlz) = q2)..i is set of states accessible from q1, i.e., Qi = {q/qi A q}. Clearly q A q2 - Q Q Q2' 10. C (communication) is an equivalence relation on Q where ql C q2 iff ql A q2 A q2 A ql C1 denotes the equivalence class of q l' 1i. K@a) is the cardinality of set a. I1. The order of a monoid = (=B ', e > O(B) = K(B). 13. T is assumed to have n states, i,e,, K(Q) = n. 14, A transition system T = <S, Q, M, ql> with initial state ql is connected iff Q1 Q= - _ I 1 Q

We quote the following well-known ideas from Nelson's [7] develop:ment of the tiartmanis decomposition theory: Definition 3,5,7, Let T. = S, Q ql Mi> and T.= Q. q. M. be two connected transition systems, The mapping h Qi-+ Q. is a transition homomorhism if and only if 1) h(q~) = q0 2) h(Mi(qis)) = Mj(h(qi) s) for all s e S, qi C Qi' Furthermore, if h is one-one, onto, it is a transition isomorism. Corollar 3,58, The followings are properties of h: a) Clause 2) of Definition 3 5,7 may be replaced by h(Mi(qipx)) = M.(h(qi),x) for all x c S*. b) There is at most one onto homomorphism between Ti and Tj. c) There is a decision procedure for determining whether any map h is a transition homomorphism.

Introduction This report investigates some relationships involving the order of the semigroup of an automaton and a class of automata for which this order takes on its smallest value, relative to the number of states, This class, called degenerate automata in Definition 1,1, has the property that the order 0( t) n (where n is the number of states). In fact we shall show (Theorems lo9 and 1,10) that for any connected machine 0(t) = n if it is degenerate, and 0(t) > n if it is not degenerate~ Hence the connected degenerate automata are precisely those automata whose semigroup order achieves its smallest value, Further, we show by counterexample that this result does not necessarily hold for disconnected machines even when they are reduced (in the sense of Definition 1,,l3) Theorem 1,12 strengthens the lower bound for strongly connected automata. The class of degenerate automata properly includes a variety of automata by Trauth [2] is such that, is isomorphic to a gro of autos morphisms (ioe,, isomorphisms from the machine onto itself) which characterize the automaton, Trauth defines the class of uasi-erfect automata as those group-type automata which are connected, Perfect automata turn out to be quasi-perfect automata with abelian groups, It is the perfect automata which are investigated by Fleck [3) and Weeg [4] and which appear as strongly connected commutative machines in Laing [5], The group-type automata in turn belong to a class of state-independent All symbols are defined in the preliminary definitions. 2These results provide a converse for a theorem of Oehmke [1] which showed that the order of the semigroup of endomorphisms (see above) of a connected machine never exceeds n.

automata investigated by Beatty [6] ~ Finally, the connected degenerate automata turn out to be those automata for which ~ is isomorphic to a semigoup o'f endomorphisms (i*e., homomorphisms of the machine i nto itself) (Theorem 2) and includes the state independent machines as a proper subclass. In sum, the following inclusion relations may be establishedc degenerate state independent abelian (connected) group-type 1/ quasi-perfect perfect See also recent work by R e Ba:/er "Automorphism Groups and Quotients of Strongly Connected Automat<. and Monadic Algebrasl' IEEE 1966 Symposium on Switching and AutLomata Theory,

0. Some Relationshis Involving Semi.group Ord.er and Regular Events before further investigating the degenerate automata, we pause to consider the relationship of semi-group order to the behavior of an automaton viewed as an acceptor, We consider a notion of "fineness of discrimination" and relate this to the lengths of the minimum representatives of the congruence classes S*/Eo We tentatively identify the longest of these as measuring the "effective memory span" of the machine, The arguments presented are not complete and are meant only to suggest the relevance of these notions to the understanding of automata behavior, In regard to the "'fineness of discrimination" and refering to the preliminary definitions we note that xEy-~ (Vq.) (xRqi y) To interprete this statement we think of our machine T = <S, Q M> as an acceptor automaton with initial state qi9 i.ec T = (<S M, qi> (with final states unspecified), The statement then says that if two words xwy are not distinguished by the congruence E, i,e,, xEy, then it is impossible that they are distinguished by any acceptor T (since for any right congruence R it must be that xR y) o Conversely, noting that q1 q. %xEy = — Cqi) (xRq y) we have that if two words are distinguished by E. then there exists an acceptor which will also distinguish them.. In other words, a bound on the fineness of discrimination of T viewed as an acceptor is imposed by the fineness of the partition S*/E, Now, one measure of the fineness of a partition is the number of classes in it, (In fact, an ordering of partitions based on this number preserves the order induced by a partial ordering based on class inclusion.) Further the cardinality of S*/E is

just the order of the semi-group, 0(4)) and for a machine with n states, 1, 0(4)) < n Notice, then, that an ordering based on 0(4) over machines with the same number of states may provide additional information to that obtained from the partial ordering induced by homomorphism which relates machines with different numbers of states3 We see the semi-group order determines the number of classes belonging to S*/E which, when united, form classes of S*/R for some ql. We interpret the "fineness of discrimination" as related to the number of such sub-classes comprising any acceptor class., We now argue that such discri, mination involves the length of words. Definition Os1o x is a minimum representative of [x1], a class induced by E, iff x is among the shortest of all words in [x], i, e,,(x-) = min Z(x) Ix] Definition 0;'2, T has effective memory span, Z(x) iff x is among the longest of the minimum representatives of all classes of S*/E. i e. Z(x) = max 2(x), S*/E The designation '"effective memory span" is introduced here only as a suggestive name for Z(x). Whether this concept fares well as a measure of memory must await further investigation. The following theorem establishes bounds placed on the effective memory span by the order of the semigroup. Theorem 0, 1, For T = <S, Q, M> and 4q the semi-group of T, let K(Q) = n, K(S) n. Consider for example, set of all compositions obtained by interconnecting a fixed number of machines0 Each of these compositions has the same number of states but the orders of the transition semigroups may differ markedly~ The relation of the semigroup order to the connection pattern might then be explored.

Then (x)< 0(b) min{{ 1 n m l or equivalently logm O0(,) ( 9(X) < 0(~) where ~O(+) = 0(.= ) for m sufficiently large. m Proof: Let x = s IS2 0s *0 ( We shall show that the (x) + 1 classes associated with heads Xi = S1S2 'Si (i = 0 1i,,I e(;), x0 A) are distinct, Suppose to the contrary xiExj, i < j Then since E is a congruence we may add the tail, Sj9 + eS,(*) corresponding to the head xj to both xi, xj, thus obtaining x.Ex. X E ==xst, (X Ex* s.. s 1j i j+l z(x) j j+l (x) -e xisj + 1oS(X) Ex But also 9 (xl) (x 2 (X S. + *) < xji+) so that x is not 1ut 3lso l~xi) < Il~j j l 91 (X) a minimum representative contrary to hypothesis, This establishes that Z(x) < K(S*/E) = 0(f)l The upper bound on 0(f) is obtained by assuming that all words of length less than or equal to Z(x) are non-equivalent minimum representatives, Qt E,, D We conclude that the semigroup order brackets the effective memory span of a machinec Thus, for example, flip-flops (degenerate) and delays (non=degenerate) are types of 2Estate, 2-symbol connected machines with effective memory span of 1, That of a 3-state (2-symbol, connected) degenerate machine is always less than that of a 3.state machine with 0(b) - 15. Notice that the effective memory span may be less than

the degree of definiteness [10], Thus, while a flip-flop has indefinite storage (degree of definiteness = co) its effective memory span is only.. Continuing our attempt to relate the relations E, Rq we observe that E-induced subclasses of S*/Rq are those satisfying left as well as right invariance, hence the well-known Theorem 0,2, Let T be connected, Then xEy #-> (Vq) (M(q.x) N M(q,y)) s C(V z) (M (M (ql z) ) = M (M (q D Z) y) > (Vz) (zxR zy) ql The E-induced subclasses of R then appear as those which are preserved ql under prefixing of any word,, Alternately these classes are invariant under time translation (with i(z) the shift interval), Clearly one and only one of the classes of S*/R contains the subq! class associated with the longest minimum representative, [x]; If S*/Rq has more than one class- T is therefore able to define a set of words q! containing a time invariant class of words at least k(x) long,. For degenerate automata, Definition l11 states that the classes of S*/R are just those of S*/E. It follows that all classes of S*/R are time invariant, i e,, xR y > — (Vz) (zxR zy). Further, since 0(4) S n, it follows that the longest minimum representa-= tive of these classes can be no longer than n symbols in length

1,0, Degenerate Machines Definition 1,o1 A machine T <S Q, M> is deenerate iff there is a state q1 e Q such that xR y.-Y xEy 1ql for all x#y e S* (universal quantification will be assumed whenever xy e S* appear unquantified), Since in general K(S*/R ) = K(Q1) < n we have immediately from Definition 1.l that O((0) = K(S*/E) = K(S*/R ) < n, q! We shall presently return to the converse of this statement, ies., to the question of whether degenerate machines are the only ones for which 0 (f) < no Let us refer to a state q1 appearing in Definition 1,1 as a critical state, the motivation being that equivalence of words under the right invariance relation of a critical state is necessary and sufficient for equivalence under the congruence E, Since from preliminary Definition 6 we have xEy = (Vq)(xRqy) we have the following equivalent but useful definition of degeneracy, Definition 1, 1 A machine T = <S O Q9 M> is degenerate iff there is a critical state in Q, it e, a state ql. such that R < R for all q e Q-1 ql q Models of degenerate machines are generated by Caley representations of monoids. Let <S, o, 1> be a monoid; the corresponding Caley machine is defined as Note that there may be more than one critical state. If all states are critical T is state independent. i.e. R = R for all qi.qi C 10

11 T(S) = < S, bl> where M(s,s') = sos' for all ss eC St It has been established (Myhill [8]) that T(S) is well defined and that its transition monoid is isomorphic to S, Moreover, we can show that T(S) is degenerate with critical state 1 This is so since M(l,x) = M(l,y)4-> lx = ly --- ax = ay...:) M(ax) = M(ay) for aU;.;ate 4a S, Now consider the set of submachines of T generated by members of Q considered as initial states, Definition 1.2. For each q: G Q we can define an initial state machine Tl. = <SK Qia qi' M.> where Qi = {q/qi A q} qi = initial state of T. Mi is M restricted to Qi4 It is easy to check that T. is a well defined connected machine, Note too that R is the right invariance relation corresponding to T.i qi We now apply preliminary Theorem 3656,18, to a pair qlaqi of a degenerate machines, R < R iff there is a homomorphism from T1 onto Ti, iLe., a map hq: Q1 I Qi such that hq (ql) = qi i and M(h q(q),9s) q hq (M(q1,s)) for all s E S and q e Q1 Since the domain of h is Q1 and not necessarily the total set Q, h is not a proper endomorphism, but what we shall refer i~

12 ao as a suWt) o endnorhism n Clearly if T is connectex with nl the initial and critical state, then h:is indeei an endomornhism, ie thus have nroved the 'Iheoreni 1,1, T is degenerate with q, a critical state iff.' each onto qi c Q there is a sub-enaomorphism h, - Q such that ho (4q) = qi ii The followine statements are immedi. ate properties of sub-endomorphisms...emma,l l0,; 1. h (M(qpy)) = M(h (q),y) for all y e S* (from qi qi Coro 305,8,a), 2, A sub-endomorphism defined on Q1 is uniquely specified by the ql image, i, e., (hi(ql) = hj(ql)) - h = hq 3. For the sub-endomorphisms of Theorem 1,1 we have further qi qi4 qi qj Proof of 2" hi(ql) = hj(ql); M(hi(q 1)x) = M(hj(ql),x) hi(M(qlx)) = hj(M(qlx)), for all x c S* hi = hj Q E,,D We note that functional composition of sub-endomorphisms is not generally possible because of the restriction of the domain Such compo.sition is possible however for the subset {h /qi F Q } since qi EQ, — Q1 i c Q1 so that h may be taken to mar Q1 into Q1P we shall refer to such a set of sub-endomorphisms as a critical set,. A critical set with critical state ql can be written in the form H1 {hM(qx)[IhH(x )(M(qyY)) = M(\I(,x) (ql) y)} Theorem 12o A critical set of endomorphisms forms a monoid under

13 functional composition, i.e, 1 = <il o hq is a monoid. 1 Proof, Clearly h is an identity and functional composition is associative, For the rule of composition we have h(q,,x) hM(q,y) (M(ql'z)) hM(qlx)~ M(hM(qly) (ql) Z) hM (q,x) ~M (ql yz) = M(hM(q4 x) (q1)9yz)) M= (qlx.yz) M(M(ql,xy),z) hM(ql xy) (M:(ql z ) ) which demonstrates closure, E,D V We are now ready to establish the equivalence between degenerate machines and those for which the transition monoid 4 is isomorphic to a monoid of sub-endomorphisms, As noted in the Introduction a variety of machines studied in the literature satisfy the latter description, Theorem 1_3. T is degenerate iff there is a monoid of sub-endomorphisms defined on a connected subset of states which is isomorphic to the monoid of transitions, v, Proof. In the forward direction assume T is degenerate with critical state ql, According to Theorem 1,2 we have the existence of a monoid t1 = K{hi(qlx), -* h q> We shall show that g -— 4 l such that g (xx)' ql (, x) is an isomorphism( Clearly g is onto; it is moreover, one-one since

14 hM(qlx) - M(ql y) M(ql.x) = M(ql1y) - xR y -=- xEy (degeneracy) O fx y Finally to show commutivity, we have g(xoo y) = g(4xy) = hM(ql,xy) hM(qlx)hM(ql,y) (Thm. 1,2,) = g(~x) g(~y) }Hence g is an isomorphism. For the converse let H = <{hi} *, hl> be a monoid of sub-endomorphisms whose domain and range are Q1, the set of states accessible from a state, ql. By assumption 0 is isomorphic to i, Let us first show that for every state qi E Q1 there is an hi c H such that hi(ql) = qi9 in other words that {hi(ql)} = Q1l First note that since there are at least as many transition maps in 4 as there are distinct ql images, 0(D) > K{4x(ql) } = K(Q1) (1) Because of isomorphism between H1 and 4 we have using (1) that O(H) ~ K(Q1) (2) From Lemma 1,, l0 we have that for hi Z h. h (q ) P hi (ql) hence that K({hi(ql)) }) > O(H) and from (2) K({hi(ql)}) > K(Q1) - But since the range of every hi is Q1 any assumption other than {hi(ql)} = Q1 involves a contradiction

Now consider the submachine T1 = (S, Q1 Ml)> Since for each qi there is a sub-endomorphism hi such that hi(ql) = q we have that from Theorem 1,1 that T1 is degenerate with ql a critical state, Let ~1 be the transition monoid for T1 From the first part of the present theorem, P1 is isomorphic to H and hence 41 is isomorphic to 4, Since in general xEy =-A- xE1y (where E is the congruence relation for T1) D1i implies that xEy<== xEly (3) But since T1 is degenerate 1 xR y — '% xEl hence from (3) xR y4== xEy,, ie,, the original machine T is degenerate, Q,E, Di Corollary 1l, For a connected machine T, T is degenerate iff there is a monoid of endomorphisms which is isomorphic to the monoid of transitions,. Theorem 1A4., A connected machine having an abelian semigroup is degenerate Proof. Let ql be an initial state such that Q1 = Q' We shall show that ql is a critical state, Using the right invariant property of R, we have xR y At (Vz) (xzR yz)

16 Further, it follows easily from the fact that 4 is abelian that xzR zx ql and yzR zy (3) ql Since R is an equivalence relation (3) and (4) yield xR y 4 (Vz) (zxRq zy) === xEy (using Theorem 0.2), Since the converse implication always holds, Definition 1,0 is satisfied, hence the associated machine is degenerate, Theorem 1oSo For connected machines H = with hM(qx) =, iff 4 is abelian, Proof, Corollary 1,2,0 statement 4 states that h (q (q) = yhM (q ) (q) which holds for all q e Q since T is connected, Now if M(qlx) = 4 then P P = - ( x y yx so that ~ is abelian. Conversely, if ~ is abelian, then by Theorem 1.4 a set of endomor-. phisms exists, Let q = M(ql9y), then 1(ql,x) (q) = (qlx) (M (ql)) = M(ql1xy) =M M(ql,yx) = M(M(q1Ay) x) Q dE OD >

17 1 1. A Definition of Machine Reduction We have shown that for a degenerate machine 0(D) z n, We are now interested in the subclass of degenerate machines for which 0(~) = nT To do this we develop a method of reducing the number of states of a machine while keeping its transition semigroup invariant. Definition 1,3, A machine is reduced iff for every ql,q2 e Q R < R /\ C1 C2 ~.(q f C) (q A q2) q q21 2 2 2q In words, for any two non-communicating states (q l, i if R refines R then q2 is accessible from some state not in its communicating class. Our definition differs from the standard one in that we do not assume that T is connected and we allow the possibility that every state has a distinct outpliut e As seen from Theorem 1.7, the present definition coincides with the standard one for connected minimal machines. 'The sium of any machine with an isonmorphic copy of itself is an example of an unreduced machine,. Lemma 1 R < R Q) {(3q' Q1)(Rq I RI ) q! q2 2, 1 q 21 Proof. q E Q2 there is a z such that 2 2 M(q2Zz) = q Take q1 = M(q, z) c Q; Now xR' y ---,> M(q x) M(qi y) -- M(qlzx) = M(qlzy) - zxR zy ql -- M(q29zx) = M(q2,zyj -- M(qIx) = M(qIy).-.. XR9 y 2 1 Figure i., page 19( is an exmnle of' a rmchine which is reduced but IOIt comllnectc,j

18 Theorem 1,6, If a machine T is not reduced there is a machine T' with fewer states such that E = LI hence ~ is ~>, and 0(~) = 0(~') Proof, Let T = S, Q M> not be reduced, Then there are ql'q2 such that 1o R R 2 C!1 C2 3t, (3q t C2) (q A q2) (Definition 3) The idea behind the proof is that 1) R refines Rq and by Lemma 1, all states in q2's communicating class C2(C Q2) and 2) C2 is inaccessible to all states external to it, hence the whole class C, may be eliminated without affecting the word semigroup of the machine, Fonually we shall show that xEy iff xE'y where T' = <S Q - C2, M'> where M' is M restricted to Q - C2^ Note that Q Z C2 since if Q = C2 then ql C q29 i2oeo9 Ci = C2 violating condition 2 above, Furthermore M(Q-C2,x) C (Q C2, since by condition 3 no state in Q. C2 can access C2 (for if q A q2 A q C q2 then q A q2) Thus TI is well defined, Now xEy -(' ) (Vq) = (q) (q)) (Vq E (Q-C2)) (x (q) = y(q)) -- xi E'y Now note that Q1 c Q - C2 since if ql A q and also q ~ C2 then by

19 Condition 3 ql s C2 but then C1 = C2 violating Condition 2. Since C2 c Q2- and Q1 Q CC, Lemma 1 tells us that if R refines R then every state in C, is refined by some state in Q - C. Thus if q2 ' xR y for every q e Q C22, then xR y for every q e C2, q 2q Thus xE'y = (Vq e (Q C2))(xRqy) (Vq e (Q C2))(xRqy) A (Vq E C2)(xRqY).. (Vq e Q) (xR y) -e —> xEy Q E, D Noting that at least q2 e C2, T' contains at least one fewer state than T, Finally isomorphism clearly follows from equality of the congruence relation 1heorem 1,7, If a machine is connected then it is reduced. Proof. Assume T is not reduced. Then C2 # C and R 5 R but... 1 q (nq E C2)(q A q2). In particular, q1, C2 (since C C So q A q2 QED: Theorem 1,8, A degenerate machine is reduced iff it is connected, Proof~ Let T be degenerate with R - R for all q, Assume T is reduced.. Clearly ql A ql. Let q2 $ ql" If q2 C ql then the theorem is proved. If not, then by Condition 3 of Definition 1.3 there is a q3 which accesses q2 but is not accessible from q2, Now either q3 C ql in which case the theorem is proved, otherwise by Condition 3 again, there is a q4 such that q4 A q3 A q A q4 Now it cannot be that q2 A q4 (since then q2 A q3) thus q4 ~ (q2 " Q3) or since Q3 7 Q2 (the inclusion

20 is proper since "q2 A q3) q4 t Q3A Evidently this process must stop since at every stage j: qj+l Qj while Qj D Qij1 'D Q2- So that at most Qn = Q Tlhus for some, j, qj = q and furthermore A q qj A qj A 2 -" q31 A qA q2. The converse follows from Theorem 1,o7 QFE,,D 1,2. Sei u Order and Deen Machineg Theorem 1.9, A degenerate machine T has 0(~) = n if 1. it is connected. or 2 it is reduced. Otherwise 0Q'(D) < n. Proof, Connectedness., reduced by Theorem 1.6, If T is connected then K(Q1) = n and by Theorem 1,3 0(H) = 0(4) = n~ If T is not reduced then by Theorem 1 6, there is a machine T', with fewer states such that O0(~' = 0(V),o But T' is also degenerate since for all states q e Q C2 it is still true that Rq < Rq1 Therefore O(P') < n-1. Q, L, In regard to the converse of Theorem 1.-7 it might be conjectured that for a reduced non-degenerate machine, 0(4) > n+l., Since reduction does not necessarily imply connectedness for non-degenerate machines it may happen in fact that 0(4) < n as the following example shows. al,"bl a1a2 (,q 1~3 i al,b1aa2,b2,c 1,bl la2 b2Pc c c a b a2b2, bc 1c ba2' b2c q-al blbl a2 ~b2 'c a1al Dbl a2 "b2.c Figure 1o

21 The machine of Figure 1 is composed of two separate reduced degene,rate components which do not enter into any homomorphic relation since a Rq b1 va "e. _ and. aa R a, while ai a2 It is easy to verify that while having 8 states and bei;g' non-degenerate and reduced, the semigroup of the machine has only 6 distinct functions, The dead states q2 q3,q4,q'',q4 are of course to blame for the small order. Regarding the machine as at acceptor and applying the appropriate reduction would remove many of these states with the concomitant effect of altering the word semigroup, Theorem 1.10, A connected non-degenerate machine has 0(t) > n+l. Proof, Assume ql is the initial state, Then there are n distinct functions, 4x differing at least in the ql-images, Because R cannot refine all Rq q C Q, (otherwise T would be degenerate), there is a q2, say such that x Rq xq while \XIRq x2 In other words xl(ql) = x(q1) while x (q)2) i 2x (q2). Thus there are n-l distinct functions differing at 1 2 least in the ql-images, and at least 2 functions distinct from the n=l others having identical ql-images but different q24images0 Hence there are n+l distinct functions. Figure 2 disp.lays a connected non-degenerate machine of 3 states having 0(b) = 4. 0 Figure 20

22 Thecrem 1 10 can be strengthened for strongly connected machines. First we have the following lemmas. Lemma 22 K(S*/R ) = Q1b 1 Lemma 3, If R inc R2 and K(S*/R1) < K(S*/R ) then there are at least 2 classes in S*/R1 which are split in S*/R2~ Proof0 Since R1 and R2 are incomparable at least one class in S*/R is split in S*1R2o If only one class is split, then since K(S*/R1) < K(S*/R2), it follows that R2 < R1 But this contradicts the hypothesis that R1 inc~ R20 We develop the following lemmas by using the fact that lo ql A q2-=- K(Q1) > K(Q 2) 2. ql A q2 1\ 'q2 A ql K (Q) > K(Q2) Lemma 4o R compo.R qA q2 = Rq R Lemma 5ao (R compo R ) A q C q - R = R -.. ql q2 1 ql q2 Lemma 5bc R = R q2 (q A q -> q C q) ql q2 2(1 2 1 2) Since ql C q2 iff ql A q2 q2 A ql, apply Lemma 4 twice, obtaining 5a,. Thcoremh 1o11, If T is strongly connected and for every pair q!,q2, Rq, comp, Rq2, then T is degenerate. Proof., Lemma 5a applies to all pairs of states, hence ql = Rq = o0R = Rqn~ But then by Theorem 1,1, T is degenerate, in fact state independent, Theorem 1412. A strongly connected non-degenerate machine T, has O0(4) > n+2., Proof. Theorem 1,11 is contradicted unless there are ql,q2 such that Rq inc. Rq2. Noting that K(Q1) = K(Q2) and applying Lemmas 2 and 3, there are at least 2 classes in S*/R which are split in S /R ql qo

23 The argument of Theorem 1,10 goes through except that now there are n-2 distinct functions differing at least in there ql-images, at least 2 functions distinct from then n-2 others having identical ql1images but different q2-images, and at least 2 functions distinct from the others having the same ql-images but different q2 images, QEoDo

REFERENCES 1. Oehmhke, R, Hi,, "On the Structures of an Automata and Its Input Semigroup," J. ACM 10 (Oct, 1963), pp0 521-525. 2. Trauth, Jr:,, C. Ho0, "Group-Type Automata," J, ACM 13 (1966) ppi 170 -175, 3,.. Fleck, A, CO, "Isomorphism Groups of Automata," Jo ACM 9 (October 1962), pp0o 469-476o 4, Weeg, G. PO, "The Automorphism Groups of the.Direct Product of Strongly Related Automata," J,, ACM 12 (April 1965), pp0 187-195, Sc. Laing, R, and J0 B Wright, "Communutative Machines," The University of Michigan Technical Report, December 1962o 6, Beatty, JO C, "On Some Properties of the Semigroup of a Machine Preserved Under State Minimization," IBM Research Paper RC1199, May 1964. 7. Nelson, R, J,, Introduction to Automata, Case Institute of Technology0 8, Myhill, J,, "Finite Automata, Semigroups and Simulation," paper delivered at University of Michigan Summer Conference on Automata Theory, 1966. Reference to McNaughton, page 5^ 9 Bavel, Z0, "On the Structure and Automorphisms of Finite Automata," Department of Computer Science, University of Illinois, October 1965,. 10, Perles, M,, O0 M, Rabin and E, Shamir, "The Theory of Definite Autos rnata," Hiebrew University of Jerusalem Technical Report No, 6, 214

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 Room 239, Building 10 Navy 100, Fleet Post Office Box 39 Washington 25, D.C. New York, New York 09599 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 Port Washington Decision Science, Inc. Long Island, New York 6508 Pacific Highway Attn: Technical Library 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 CONTROL DATA R&D (Security claeesficatton of title, body of abstract and indexing annotation must be entered when the overall report is classifIed) 1. ORIGINATIN G ACTIVITY (Corporate author) 2.. REPORT SECURITY C LASSIFICATION Logic of Computers Group Unclassified The University of Michigan 2b. GROUP Ann Arbor, Michigan 48104 3. REPORT TITLE DEGENERATE AUTOMATA: SOME RELATIONSHIPS INVOLVING SEMIGROUP ORDER AND REGULAR EVENTS 4. DESCRIPTIVE NOTES (Type of report and Incuiveo dates) Technical Report 5. AUTHOR(S) (Last name. first name, Initial) Zeigler, Bernard 6. REPORT DATE 74. TOTAL NO. OF PACES 7b. NO. OF RErF December 1966 25 10 8a. CONTRACT OR GRANT NO. 9c. ORIGINATOR'S REPORT NUMBER(S) Nonr 1224(21) 03105-45-T b. PROJEC T NO. c..6. OTI R RPPORT NO(S) (Any other mubere tht may be assigned this rporU d. 10. AV A ABILITY/LIMITAtION NOTICES Distribution of this document is unlimited. Qualified requesters may obtain copies of this report from DDC. 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY Office of Naval Research Department of the Navy Washington, D.C. 13. ABSTRACT This report investigates some relationships involving the order of the semigroup of an automaton and a class of automata for which this order takes on its smallest value relative to the number of states. (U) This class, called degenerate, is a limiting class in the sense that the semigroup order of any connected machine equals the number of states if it is degenerate, and is strictly greater than the state cardinality otherwise. Further, we show by counter-example that this result does not necessarily hold for disconnected machines even when they are reduced in appropriately defined manner. The lower bound on semi-group order is strengthened in the case of strongly connected automata. It is also shown that the class of degenerate automata, as herein defined, properly includes a variety of semi-group and group type automata studied in the literature. (U) The relevance of semi-group order to the acceptance properties of automata is suggested. In particular, the number of subclasses and the minimum lengths of strings in an acceptor class are related to the semi-group order. (U) D DJAN 6 1473 U UNCLASSIFED Security Classification

UNCLASSIFIED Security Classification 14. LINK A LINK B LINK C......KEY WORDS..ROLE WT ROLE WT ROLE WT 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 tast name, first name, middle initial, tory notes. If military, show rank and branch of service. The name of the principal iauthor 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, 14. KEY WORDS: Key words are technically meaningful terms subproject number, system numbers, task number, etcor 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 report 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 lim- itations on further dissemination of the report, other than those UNCLASSIFIED Security Classification

UNIVERSITY OF MICHIGAN ll9l01l503l2lt6lialll3l3!llmal 39015 03527 6339