ALQEMAEC Q'TRUQTfiflfi Q-F AUTOMATA Thesis {or H10 Degree of pk. D. MICHIGAN STATE UNIVERSITY Arthur C. Fleck 1964 THESIS This is to certify that the thesis entitled Algebraic Structure of Automate presented by Arthur Charles Fleck has been accepted towards fulfillment of the requirements for Ph.D. degree in Mathematics G" i7 ‘29ch Major priessor Dme April 17, 196k 0-169 "L LIBRARY Michigan State University ABSTRACT ALGEBBAIC STRUCTURE OF AUTOMATA by Arthur C. Fleck In order to give a description of the contribution of the thesis under consideration it is necessary to sketch a brief history of this subject. For purposes of this discussion there are two natural reference points. These will be indicated in what follows and we will orient this discussion around them. The first reference point which we indicate occurs in conjunction with the appearance of the papers of Huffman [1], Mealy [2] and Moore [3] . These were the pioneering works for the area of investigation under con- sideration here. Prior to the appearance of these papers the mathematical model of a computing device proposed by Turing 4 was widely studied. While this model is of considerable theoretical importance it was not directly applicable to the physical devices and associated problems which began to appear in the early 1950's. In order that the reader understand the full significance of the remarks to follow we will digress to indicate the essential pro- perties of the Moore type model. However, we do this in the more precise and formal language of Ginsburg [5] rather than as it originally appeared. A sequential machine, C, is a quintuple, C - (S,I,O,M,N), where S (states) is a Arthur C. Fleck finite nonempty set, I (inputs) and 0 (outputs) are (nonempty) semigroups, M is a (next state) function M: S x I-—9 S such that M(s,xy) . M(M(s,x),y) and N is a (output) function N: S x I-—9 0 such that N(s,xy) = N(s,x) N(M(s,x),y). Briefly then, if a sequen- tial machine is in a given state and an input is applied, an output and a transition to a new state occur. Notice that for two distinct elements x,y G I, the same trans- itions may be defined by x and y but these inputs may still be distinguished by the output function. The main interest in such a model, as with Turing machines, is in its behavioral preperties. That is in the prOperties of the (presumably observable) inputs and outputs. The reason for distinguishing the works mentioned above is the view- point taken by them. Besides establishing the definition of the model, the main concept thich is studied by these authors is that of (behavioral) equivalence of machines. Briefly, the meaning taken for equivalence here is that if two machines are presented with the same sequence of inputs they will produce the identical sequences of out- puts (with approiate choices of states). The results of these authors concerning this concept consists of con- struction and investigation of reduction algorithms. That is, given a machine construct an equivalent machine in which the number of states is minimized. Thus the basic motivation here was the (behavioral) comparison of devices with the idea in mind of finding the 'simplest' device (behaviorally) equivalent to a given one. Investigation Arthur C. Fleck of these algorithms usually revolved about structure and uniqueness prOperties of the 'reduced' machine. The second set of papers which will be singled out for reference are characterized by a basic change in approach to investigation of this model. Briefly we can class these investigations as efforts to solve questions of the general form, 'Given a device, what work can it do?‘ That is, how can the output behavior be influenced by choices of inputs and state? This viewpoint is perhaps best exemplified in the works of Rabin and Scott [6] and Ginsburg and Spanier [5],[7]. Before getting on to the job at hand several points should be made. First of all, there is little agreement on exactly how the output association should be defined. Thus each of the authors previously mentioned is in dis- agreement with the others on this point. In Specific, the definition of sequential machine put forth earlier does not exactly agree with those of the mentioned authors but is what Ginsburg has termed a quasimachine [8] . The differ- ence of detail sometimes produces subtle or unexpected results. For instance the uniqueness(of reduced machine) result of Moore ( [3] , Theorem h) requires strong con- nectedness while that of Ginsburg ( [8] , Theorem 1.3) does not. -On the other hand another classic (l:6] , Theorem 15) shows, roughly speaking, that every two-way automaton is equivalent to a one-way automaton. Never the less a common ground is found in the way the internal transformations are treated. Thus an increase in knowledge Arthur C. Fleck in this area should be of general value. We will now indicate how the results of this thesis relate to these earlier investigations. In Part I the following is accomplished: (1) the basic definitions, including that of the model, are introduced and their interrelations noted (2) the concepts of Open set and continuous function are investigated. In regards to (1) it is clear that a work which studies the relationship of structure to algebraic pro- perties and as function invariants must make a perfunctory mention of the structures to be discussed and their inter- relationships. we will concentrate therefore on a dis- cussion of the model. As indicated earlier, it is the belief that a better understanding of structure properties will aid in analysis of behavioral problems which moti- vated the model here. Apart from this consideration, the model here presents a rich mathematical system. As to particulars, in the definition the semigroup of inputs is assumed to have an existance apart from the automaton in which it is imbedded. Two distinct inputs are not identified because they define the same Operator on the set of states. It is clear that this cannot be done if one hepes to make use of this analysis in a system where such inputs may be distinguished by the outputs which they cause. Also, from a mathematical point of view, this is not an unusual consideration. On this point, there is a direct analogy to the definition of a group with Oper— ators [9] . Arthur C. Fleck While, due to special restrictions, the concept of cpen set produces an uninteresting tepology, it serves two useful purposes. First, it eliminates the previous dependence of the definition of connectedness on an as- sociated graph. Second, it naturally suggests the inves- tigation of continuous functions in this setting. It can be observed that all of the reduction algorithms mentioned earlier can be thought of as defining a function from one machine to another. While these different algorithms were produced for different models, the transition (structure) was uniform. Thus the study of structure invariants of (continuous) functions provides a generalized and uniform treatment for several previously separated results and partial results (see, for example,[:3] , [8] , [10] ). This general investigation was carried out without the usual assumption of the so called 'sequential' prOperty. However, the force of this prOperty was found to be necessary in the results on structure invariants of functions. The remainder of this thesis has a less direct bearing on existing results. The remarks made above concerning the model are all that will be made in this regard. The techniques applied here are familiar. In several cases the problems attacked are analogous to problems in other disciplines, while in general the methods of solution are not. In Part II a class of functions analogous to the homomorphisms is introduced. After a brief investigation Arthur C. Fleck of the structure invariants of these functions, we are lead to what may be thought of as the automorphism group of an automaton. The motivation is then to find the relation- ships that exist between the prOperties of the group and those of the automaton. In this investigation the fre- quency of the necessity of the force of the sequential property is sufficient to impel this assumption. Then, in certain cases, we are able to identify the action of the inputs with that of the group elements. This shows, to some extent, how the structures considered restrict the actions of the inputs. Roughly, this is similiar to determining inner automorphisms, but there is no di- rect connection. The main results here indicate under what circumstances a complete or partial description of the automorphism group can be so obtained. At this point another semigroup is introduced by means of a natural equivalence relation on the inputs. This semi- group seems to reflect the structure of both the input semigroup and the automaton, and hence its automorphism group, in rather subtle ways. We show here a reflection of the automorphisms in this semigroup. In Part III a particular structure, that of the direct product, is investigated. This structure, as presented here, was introduced by Rabin and Scott [6] in their study of acceptable sets of tapes. However, the problem of producing sufficient conditions for re- alising this structure has not been considered. Per- haps this is because it is not yet clear how to incor- Arthur C. Fleck porate this concept in a model with outputs. At any rate this is a worthwhile problem to which a reasonable contribution is made by means of the devices introduced earlier. The main results give, in one case, necessary and sufficient conditions and, in another, sufficient conditions for the presence of the structure. 9. 10. Arthur C. Fleck LIST OF REFERENCES (ABSTRACT) Huffman,D. A., “The synthesis of sequential switch- ing circuits“, Jour. Franklin Inst,, 257,1954. Nealy, G. H., 'A method for synthesizing sequen- tial circuits”, Bell Systems Tech. Jour., Vol. 3h, 1955. Moore, E. F., 'Gedanken experiments on sequential machines', Automate Studies, Princeton, 1956. Turing, A. N., 'On computable numbers with an ap- plication to the entscheidungs problem", Proc, London Math. Soc., Vol. 41, 1936. Ginsburg, 8., "Some remarks on abstract machines“, Trans- Amer. Math. 800., 96, 1960. Rabin, M. 0. and D. Scott, 'Finite automata and their decision problems', IBM Jour.gof Res, and 2214, Vol. 3, 1959. Ginsburg, S. and E. H. Spanier, 'Distinguishabil- ity of a semigroup by a machine", Proc, Amer, MatthSoc., 12, 1961. Ginsburg, 5., An Introduction to Mathematical Machine Theory, Addison-Wesley Pub. Co., 1962. Jacobson, N., Lectures:in Abstract Al ebra, Van Nostrand Co., 1951. Ginsburg, S., "Connective properties preserved in minimal state machines“, Jour.,Assoc. Computing Mach,, 7, 1960. ALGEBRAIC STRUCTURE OF AUTOMATA BY Arthur C. Fleck A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1964 ACKNOWLEDGEMENTS The author is indebted to G. P. Weeg for his direction, encouragement and enthusiasm as regards this thesis. Perhaps, since it affects the whole of this dissertation, it should be mentioned that the idea for the model taken here is due to him. The author also wishes to acknowledge his appre- ciation to the Division of Engineering Research of Michigan State University since a considerable portion of this research was conducted under its support. 11 TABLE OF CONTENTS Introduction 1 PART I Structure Preserving Properties of Continuous Functions 3 PART II The Group and Semigroup of an Automaton 16 PART III The Direct Product of Automate #0 Summary 53 List of References 55 111 Table I List of Tables iv 3h Figure Figure Figure Figure Figure Figure I O\U\¢UN List of Figures I5 20 30 an M4 INTRODUCTION While this work studies an abstract algebraic system, the character of this system obligates us to make a brief historical mention of mathematical models for computing devices. The most notable such model is that of A. N. Turing[1]. Although Turing's model is a useful theoret- ical concept, it is perhaps of no practical value. This fact has caused another model, the so called 'sequential machine', recently to become the object of a considerable amount of study. Early investigationsof this model were directed toward its application to computer design. Prom- inent among these investigations are papers by Mealy[2], Moore[3] and Ginsburgfh]. Studies of more abstract prop- erties of this model then followed from Rabin and Scott[5], Ginsburg[6], Weegf7] and others. The sequential machine model includes two essentially distinct components. The first is that of 'inputs' and internal transformation; the second is that of 'output'. The object in what follows is to study the structure (in- ternal transformation) of such systems in isolation. Thus the model here contains no reference to the concept of output and, as is usual in this case, the term automaton is applied. We first ascertain restrictions on functions on automata which indicate two general classes of functions with desirable structure properties as invariants. This leads to the association of several algebraic entities with each automaton. At the core of the work are the -1... -2. results which relate the structures of these algebraic systems to the structure of the automaton itself. The following results are dealt with in three parts. In Part I some structures and their interrelationships are introduced. The invariance of these structures under continuous functions is then examined. We are able to show that the class of continuous functions is the largest class under which the strongly connected property is in- variant. In Part II we examine the properties of operation preserving functions which play a role analagous to homo- morphisms in the usual algebraic studies. This leads to the association of an 'automorphism' group with each auton- aton and finally a characterization of the input semigroup. The relationships between the structures of these systems and those of the automaton itself are then investigated. For the class of perfect automata a description of the group and semigroup is given. In Part III we seek structure conditions on the autom- aton and its associated algebraic systems which will insure its representation as a direct product. For the class of perfect automata we are able to give a complete solution and for the class of strongly connected automata, a partial solution. PART I STRUCTURE PRESERVING PROPERTIES OF CONTINUOUS FUNCTIONS Introductory Concepts Most of the results of Part I concerning the inter- relations of structures on automata follow easily. However to pursue a discussion of structure preserving properties of functions it is necessary to have these structures and their interactions formally set down. The bearing of the open set concept on structure is also evident. However, the open set concept leads to an interesting new property to require of functions. Judging from the results concern- ing these (continuous) functions and the manner in which they are obtained, continuity defined by the open set concept is both a worthwhile and natural concept. Many of these results (some of which were reported in[8]) are both surprising and apparent. The definition of an automaton taken here parallels that of Rabin and Scott [5] and more exactly that of Ginsburg[6] (except for outputs). Occasionally a display of a weighted, directed graph (state or transition diagram) will be used but only to specify an example. The explan- ation of this device is delayed until that time. Definition 1.1. An automaton, A a (S, I, h) is a triple where S is a non-empty set (the set of states), I is a non-empty semigroup (the set of inputs), M is a func- ‘tion (the next state function) taking S x I (Cartesian -3- -4- product) into S. It should be pointed out that while such models historically arose to study sequential switching circuits, the model here allows far greater applicability. For instance we could consider S (together with an operationlto be a group and I to be the semigroup of endomorphisms (or group of automorphisms) of S. Another interesting spe- cialization occurs when S ={1, 2, "', A} and I is taken as a subgroup of Sn (the symmetric group). Finally we might identify S and I and consider that M defines a binary operation on this set. It is frequently interesting to apply one or more of these specializations to what fol- lows but this will be left to the reader. For completeness it should be noted that the system described by Definition 1.1 can be considered as a set together with a semigroup of operators on the set. How- ever, this view point will not be taken in what follows. We now examine some structure properties (i.e. prop- erties of the next state function) of automata. Many of the structures defined below are discussed briefly in the literature but in most cases the properties have never been formally set down and their interrelations examined. Definition 1.2. A set of states, T CZ S, of an automaton A - (S, I, M) is 2253 if given any s e T and any 1 € I, M(s,x) € T. Such a set is defined elsewhere in the literature as a stable set [6] or a submachine, but the term "open” ta -5- is used here due to the topological nature and interpre— tation of the definitions and results to follow. Lemma 1.1. The union of arbitrarily many open sets of states of an automaton A = (S,I,M) is an cpen set of states of A. Lemma 1.2. The intersection of arbitrarily many Open sets of states of an automaton A = (S,I,M) is an open set of states of A. Lemmas 1.1 and 1.2 follow from a direct application of the definitions. Thus, as suggested by the terminology, we have Pr0position 1.1. For any automaton A = (S,I,M) the collection of open sets of states of A yields a t0pology on S, the set of states. Proof: Obviously the null set, C) , and the set S are cpen. This together with Lemmas 1.1 and 1.2 estab- lishes a tapology [9]. We apply the term proposition here, and in what follows, to a more or less self contained result which is of somewhat lesser importance. In the light of Lemma 1.2 it is not anticipated that tOpological structures will be of interest here. Our investigation is rather oriented toward automata structures. Definition 1.3. An automaton A = (S,I,M) is sequential luf' M(s,xy) a M(M(s,x),y) for all s E S and x,y E I. -6- It should be noted that under the definition of an automaton by Rabin and Scott[5] (and similar considera. tions due to Moore[3], etc.) where the input composition is taken to be Juxtaposition, the next state function is usually defined on a set of generators and then extended to the entire (free) semigroup by means of the relation in Definition 1.3. Thus a ”finite automaton” is usually considered to be sequential by definition. Definition 1.3 deserves one more comment. It will be seen that not only is sequentialness a natural concept, but for many of the results of this section it is indeed necessary. Definition 1.h. An automaton A = (S,I,M) is strongly connected if given any s1, s2 e S, there exists an x 6 I such that M(sl,x) a 32. In this context, the concept of strongly connectedness was first defined and investigated by Moore [3]. Proposition 1.2. If an automaton A = (S,I,M) is strongly connected, then there is no proper cpen subset of S. Proof: Assume UCZ S is a proper open subset. Then s - u w 4> . If slé U and 32: s - U, then M(s1,x) e U for all x e I since U is open. But 82 f U, hence M(sl,x)# 82 for all x e I. Thus A is not strongly connected, 8 con- tradiction. Hence there is no proper open subset of S. Lemma 1.3. If an automaton A = (S,I,M) is sequential, then for each s 6 S, T -is Is e S, M(s,x) = s 3(i.e., s 1 1 1 -7- the set of all s1 such that M(s,x) = s for some x e I) 1 is an open set. Proof: Assume T8 is not open. Then there exists 8 e T and x é I such that M(s ,x) ='s d T . Now since 1 a 1 2 S s1 6 Ts’ s1 M(M(s,y),x) = M(sl,x) = a M(s,y) for some y 6 I. But then M(s,yx) = 32 € Ts’ a contradiction. Thus T, is open. Theorem 1.3. If A s (S,I,M) is a sequential autom- aton with no proper open subset of S, then A is strongly connected. Proof: Assume A is not strongly connected. Then there exist s1, 3 6 S such that M(sl,x) # 32 for all 2 x 6 I. Now by Lemma 1.3, T a {ale 6 S, M(s ,x) = a} s1 1 is open. But s2 * T8 . Hence T8 is a proper open subset 1 (T8 is not empty since I is not empty), a contradiction. Thu; A is strongly connected. Two remarks are appropriate at this point: first, Proposition 1.2 and Theorem 1.3 can be stated as a neces- sary and sufficient condition for strongly connectedness when the definition of an automaton assumes the property of sequentialness [6]. However, for our purposes it will be necessary to use PrOposition 1.2 without the sequential prOperty. Second, Theorem 1.3 and Lemma 1.3 are false if the sequential property is omitted as can be seen by the following example. -8- (X Figure 1 The device used to specify the automaton of Figure 1 is called a state (or transition) diagram. Its meaning is: the set of states, S -=ia,b}, is the set of vertices of the graph; the set of inputs, I a $1}, is the set of weights of the directed edges: the next state function, M(a,oc)=b, M(b,a() = a, is specified by the directed edges and their weights: the input combination is specified in the margin (if not understood). Notice that the automaton Figure 1 is not strongly connected, but there is no proper open subset of states. This is possible since the property of sequentialness is not present. Also T is not open, so that sequentialness a is needed for Lemma 1.3. Definition 1.5. An automaton A - (S,I,M) is triangular if given any s1, s E S, there exists x,y 6 I and s € S 2 such that M(s1,x) a s - M(sz,y). Definition 1.6. An automaton A - (S,I,M) is separated if there exist non-void, cpen sets U,V<:IS such that UlJ V a S and Old V a 4): otherwise A is connected. We mention that an automaton is connected if and only if its state diagram constitutes a connected graph. The -9- open set concept seems to be the simplest way to put forth this concept. Proposition 1.4. If an automaton A = (S,I,M) is triangular, then A is connected. Proof: Assume A is not connected. Then there exist non-void, cpen U, V CS such that U U V = S and U f) V = (A . Now let s1 6 U and s2 6 V. Then since A is triangular there exist x,y e I and s E S such that M(sl,x) = s = M(sz,y). But then s e U and s e V for the desired con- tradiction. Thus A is connected. We now introduce one more structure concept and con- clude the discussion of the interrelations arising. Definition 1.7. An automaton A = (S,I,M) is reversible if whenever there exists an x 6 I such that M(s1,x) - s2, then there exists a y e I such that M(sz,y) a s1, where s1, 82 e S. This concept resembles closely that of strongly con- nectedness except that it is not assumed that a transition exists between every pair of states. However, we have the following: Theorem 1.5. If A - (S,I,M) is a sequential automaton, then a necessary and sufficient condition that A be strongly connected is that A be connected and reversible. Proof: (Sufficiency) Suppose that A is not strongly connected. Then there exist s1, 82 E S such that M(sl,x) # s2 for -10- all x E I. Now by Lemma 1.3 T s {3|s e S, M(sl,x) = s} 31 is open. But since A is reversible S - Ts is also open. For 1 suppose there exists s 6 (S - T8 ) such that M(s,z) = 1 t € T8 for some 2 E I. Then by reversibility there exists 1 w 6 I such that M(t,w) 8 8. But then T8 is not open, 1 a contradiction. Now T8 and S - T8 are both Open and T81 is not empty since Ilis not empty. Also 32 E (S - T81) so S - T81 is not empty. But we have TleJ (S - T31) - S and T8 fl (S - T8 ) = ¢l. Thus A is not connected, a contradiction. Thus A is strongly connected. The necessity of the condition is entirely obvious in the light of Proposition 1.2 and follows without the sequential property. Corollary 1.5.1. If A = (S,I,M) is a sequential automaton, then a necessary and sufficient condition that A be strongly connected is that A be triangular and reversible. Proof: Apply Proposition 1.#, Theorem 1.5 and the definitions. Corollary 1.5.2. If A - (S,I,M) is a sequential, reversible automaton, then the complement of every open set is cpen. Proof: The proof of this fact is essentially the proof given in Theorem 1.5 to show T81 being cpen implies S - T81 is open. Also as was pointed out by R. Brown, if A is sequen- -11- tial and the complement of every cpen set is open, then A is reversible. It is also interesting to note that sequentialness cannot be removed from the hypotheses of Theorem 1.5 for Figure 1 provides a counterexample in this case. Continuous Functions In this section the structure invariants of trans- formations on automata are studied. In particular the concept of a continuous function of one automaton into another is defined and its structure preserving properties studied. Definition 1.8. For two automata, A - (S,I,M) and B a (T,J,N), by function, h, of A into B, written h:A~49B, is meant a function of S into T. That is a function on an automaton is merely a function on its set of states. For h, A and B as in Definition 1.8, the following usual notation will be used: by the image, h(X), of a set X CIS under h is meant the set h(X) s {t|h(x) =- t,x 6 X} and by inverse image h-1(Y), of a set I C T is meant the set h'1(Y) = {sIs E S, h(s) € I}. Definition 1.9. A function h:A- ’B, where A = (S,I,M) and B - (T,J,N), is continuous if for any cpen YT be a func- tion. Then the following statement holds (1) f'1(A n s) -- rim 0 r'1(s): A. BCT. Theorem 1.7. Let A = (S,I,M) be a triangular autom- aton and B s (T,J,N) be a sequential automaton. Then if h:Am—4>B is a continuous, onto function, B is triangular. Proof: Assume B is not triangular. Then there exists t1,t2 Q T such that N(t1,x) # N(t2,y) for all x,y 6 J. Certainly t1 # t2 or else N(t1,x) = N(t2,x) for all x e I. Now by Lemma 1.3 the sets Ttl = [t|N(t1,x) = t} e {t|N(t2,x) = t} are open and Tt fl th - (b . 2 1 Now by Statement (1) d) . flab) = h'1(Ttlfl th) a h'1(Tt1)fl h-1(Tt2)s and Tt -13- Let T - h'1(Tt ) and T = h‘1(Tt ). Then we have 1 1 2 2 TlfW T2 2 ¢>. Also since h is continuous T1 and T2 are Open sets. Now Tt and Tt are not empty, since J is not 1 2 empty. Also h is onto so T1 and T2 are not empty. Let s1 6 T1 and 82 6 T2. exist s 6 S and w,z E I such that M(sl,w) = s s M(sz,z). Then since A is triangular, there Now either s e T1, s 6 T2 or s e (S -(T1 T2)). In the first case T2 is not Open, in the second T is not Open 1 and in the last case neither T1 nor T2 is Open, a con- tradiction in any circumstance. Thus B is triangular. PrOposition 1.8. Let A = (S,I,M) and B a (T,J,N) be two automata and let A be connected. Then if h:A‘~% B is a continuous, onto function, B is connected. Proof: NO proof of this theorem need be given here since all the concepts involved are tOpological in nature and the topological counterpart of this theorem is valid. Theorem 1.9. If A a (S,I,M) is a strongly connected automaton and h is any function onto A, then h is con- tinuous. The proof Of Theorem 1.9 is trivial in the light of PrOposition 1.2 but we have the following interesting corollary Corollary 1.9.1. If h is any function of one autom- aton onto another which preserves strongly connectedness, then h is continuous. Thus we have that the set of all functions on autom- -14- ata which preserve strongly connectedness is contained in the set Of all onto, continuous functions. Moreover if we combine Corollary 1.9.1 with Theorem 1.6 we can make the following important and desirable statement: For the set of all sequential automata, a necessary and suf- ficient condition that a function preserve strongly connectedness is that it be continuous. We have seen that continuous functions on automata have several desirable structure preserving prOperties. We also point out that for almost all the results where a continuous function preserves a structure it is neces— sary to the proof that the image automaton be sequential. It is easy to construct examples which show that with this restriction removed those theorems are in fact false. For instance, any function from a strongly connected (in fact any) automaton onto the automaton of Figure 1 is necessarily continuous. However, recall that this autom- aton is not strongly connected. Also if our ideas were extended to models with outputs, both the reduction pro- cesses of Mealy [2] and Moore [3] would be continuous. To conclude this section, we state an example which shows that the reversible prOperty is not necessarily preserved by continuous functions. -15- «VIE Figure 2 In figure 2 the input composition is the usual Juxtapo- sition (generatorscx,fi3) in both cases and the sequential property is assumed for products of generators in both A and B. Of course the transitions are not completely labaled and not all transitions are depicted. For instance in A, M(-b,,erx) = -b and in B, M(a2,oB, where A = (S,I,M) and B a (T,I,N), satisfies h[:M(s,x)] = N(h(s),x) for all s e S and x e I, then h is Operation preserving. If h is also one-to-one and onto, we say h is an isomorphism. A concept similar to this, but for machines with outputs, has been briefly discussed by Ginsburg [6]. -16- -17- We notice that Definition 2.1 applies only when A and B have semigroups of inputs which are identified. This re- striction could be removed by establishing a correspondence between the input set Of A and the input set of B (if they were different), but this complicates the discussion un- necessarily while yielding no significant refinement in the results. Proposition 2.1. If h:A-—-)B, where A = (S,I,M) and B a (T,I,N), is operation preserving, then h is continuous. -l 1 e h (T1) Cs. Then for each x e I consider 3 s M(sl,x). h(sz) a 2 h[M(s1,x)] - N[h(s1),x] . t1. Now since h(sl) e T1 and Proof: Let T1 C T be open and let s T1 is Open, h(sz) 8 t1 6 T1. But then 82 € h'1(T1) and thus h'1(T1) is Open and h is continuous. Proposition 2.1 shows that the class of all operation preserving functions is a subclass Of the class of con- tinuous functions, possessing therefore all the properties developed for continuous functions. The following three results show that Operation pre- serving functions have a much stronger structure preserving nature than continuous functions. In particular, Proposi- tions 2.2 and 2.3 show that the restriction of sequential- ness can be removed from the image machine for Operation preserving functions and PrOposition 2.# shows that re- versibility is preserved by Operation preserving functions. Proposition 2.2. If h:A—>B, where A = (S,I,M) and B a (T,I,N), is an operation preserving, onto function and N N ex 31 th CO Son and A is triangular, then B is triangular. Proof: Let t1,t2 6 T. Then since h is onto there exists s1, s2 6 S such that h(s1) = t1 and h(sz) - t 2 Now since A is triangular there exists x, y E I and s e S BUCh that M(slp x) I s 8 M(sz,y). But then h[ M(sl,x)] = N(h(s1),x) - N(t1,x) = h(s) - h[ M(sz,y)] = N(h(sz),y) - N(t2,y). Hence B is triangular. Proposition 2.3. If h:A-——>B, where A - (S,I,M) and B = (T,I,N), is an onto, Operation preserving function and A is strongly connected, then B is strongly connected. Proof: Let t1, t2 € T. Then since h is onto there exists sl,s e S such that h(sl) - t and h(sz) - t 2 1 2‘ Since A is strongly connected there exists x e I such that M(sl,x) - s , hence N(t1,x) = t and B is strongly 2 2 connected. Proposition 2.4. If h:A-——9B, where A a (S,I,M) and B a (T,I,N) is an onto, operation preserving function and A is reversible, then B is reversible. Proof: Let t1, t e T such that N(t1,x) s t for 2 2 some x E I. Then since h is onto there exists s1 6 S such that h(sl) - t1. But then for s2 - M(s1,x), h(sz) - h[ M(s1,x)] - N(h(sl),x) - N(t1,x) - t2. Thus h(sz) - t 2 Now A is reversible so there exists y E I such that M(s2,y) - s1 and then t1 - h(sl) - h [M(sz,y)] . N(h(sz),y) - N(t2,y). Thus B is reversible... In view of the example in Figure 2 and Theorems 1.6 and 1.7 we see that operation preserving functions have a -19- much stronger structure preserving nature than continuous functions. This idea is further emphasized by the fol- lowing proposition which has no counterpart for continuous functions. Proposition 2.5. If h:A-—4>B, where A = (S,I,M) and B . (T,I,N), is an onto, operation preserving function and A is sequential, then B is sequential. Proof: Since h is onto, for each t e T there exists s e s such that h(s) = t. Then N(t,xy) =- N(h(s),xy) =- h [ M(s,xy)] = h[h(h(e,x).y)] - N(h[M(s,x)] ,y) - N(N(h(s),x),y) - N(N(t,x),y) since h is operation preserving and A is sequential. Thus B is sequential. It is interesting to notice that Proposition 2.5 is not true if the input compositions are distinct. The example below shows an Operation preserving function car- rying a sequential automaton onto a non-sequential automa- ton. Notice that the only thing that distinguishes the two automata is the input composition. 1 x y = x+y (mod 2) B = 0(3 3M 1 x y s x . y Figure 3 In Figure 3 define h(x) by h(x) z x' for x 6 {a,b} and h is Operation preserving. The Group of an Automaton For the remainder of this thesis it will be assumed that all automata under consideration are sequential. Many of the results of the next few sections were indicated in [10]. Proposition 2.6. The set Of all functions h:A-—e9A, where A - (S,I,M), which are one-tO-One, onto and operation preserving form a group. Proof: The only group property which warrants atten- tion is showing that the system contains inverses. Let Th:A-——9A be one-to-One, onto and operation preserving. Then h'1:A——)A defined by h'1(x) - y if and only if 11(y) - x is one-to-one and onto and hh'1(s) - h‘1h(s) -21- = s = 1(8). Now let M(s,x) = s and M(h’1(s),x) = s2. 1 Then h(sz) - h[N(h'1(s),x)]- M(h h-1(s),x) = M(s,x) . s1. Thus h'1(sl) - 82 so that h'1[:M(s,x)] x h'1(sl) = s -1 2 a M(h'1(s),x). SO h is also Operation preserving and the system is clearly a group. Proposition 2.6 is an interesting result in that it associates with each automaton a group. In this connection we make Definition 2.2. For each automaton A = (S,I,M) we denote by C(A) the group associated with it by Proposition 2.6. The general development to be followed now is sug- gested by the question: What relationships exist relating the structure of the automaton to the structure of the group associated with it? Lemma 2.1. If A = (S,I,M) is a strongly connected automaton and hi’ h :A-——9A are Operation preserving with 2 h1(so) - h2 (so) for some 30 6 S, then h I h2 (i.e., 1 h1(s) s h2(s) for all s E S). Proof: Suppose that h1 and h2 are functions satis- fying the hypothesis Of the lemma and let a E S be an arbitrary state. Then since A is strongly connected, there exists an x e I so that M(so,x) = s. Then 111(8) = h1.[M('o’X)] =- M(h1(so).x) = M(h2(so),x) - h2[M(so,x)] - h2(s). Thus h1 2 hz. Thus, if A is strongly connected and h € G(A). h has -22- nO fixed points unless h is the identity. Hence G(A) is a group Of regular permutations. It follows from this, as pointed out by Weeg [11], that if A has a finite number of states, the order Of G(A) divides that number. Theorem 2.7. If A a (S,I,M) is a strongly connected automaton, then K[G(A)] S 1([8], where K[X] denotes the car- dinality Of the set X. Proof: Assume K[G(A)] > K[S] and let so 6 S be any fixed state. Consider the set of states §:h(so)} where h ranges over all Of G(A). Since K[G(A)]f> K[S], there must be distinct h1, h2 E G(A) so that h1(so) s h2(so) for otherwise there is a one-tO-One correspondence between G(A) and a subset of S (i.e., h(——) h(so) ). But then by Lemma 2.1, h 5 hz, a contradiction since h1 and h were 1 assumed to be distinct. Thus K[G(A)] _<. K[S]. 2 Representation of the Group Elements The following results arise from the fact that a group is associated with each automaton. Now each element of the group of an automaton is a function from its set Of states to its set of states. If we restrict the next state function to a single input symbol this is precisely the manner in which it maps. With this motivation in mind we now state the question to be answered here: when can the elements of the group of an automaton be expressed in terms of its next state function? TO resolve this question we introduce, and give some investigation to, one new concept. -23- Definition 2.3. Let A = (S,I,M) be an automaton and h:A-——>A. Then h is representable if there exists an x 6 I such that h(s) 3 M(s,x) and hx(s) E M(s,x) is a representation. Definition 2.“. Let A - (S,I,M) be an automaton. The middle,7h , of I is the set Of all x 6 I such that M(s,xy) - M(s,yx) for all y e I and s e S. Notice that the center Of I is contained in the middle and 7h is a subsemigroup of I. Definition 2.5. Let A c (S,I,M) be an automaton. Then A is abelian if I =7h)(the middle). Also if A is strongly connected, A is called perfect. PrOposition 2.8. If A = (S,I,M) and B a (T,I,N) are automata and h:A———9B is operation preserving and onto, then 771‘ C/mB, where ’77? and 7773 are the middles for A A and B respectively. Proof: Let.xe’h1A,t e T and y e I, then there exists an s E S such that h(s)st and N(t,xy)-N(h(s),xylsh [M(s,xyI]=h[M(s,yxX]-N(h(s),yx)-N(t,yx) so xe’l’hB since t and y were arbitrary. Corollary 2.8.1. If h:A-——9B is Operation preserving and A is abelian, then B is abelian. The next result shows that for a strongly connected automaton, we can determine if an input is in the middle by the way it acts on a single state. Proposition 2.9. Let A = (S,I,M) be a strongly con- -24- ‘ nected automaton. Then if M(so,xy)=M(so,yx) for some 30 E S and all y e I, x is in the middle of I. Proof: Let s f S. Then there exists 2 E I such that M(so,z)=s and then M(s,xy)-M(M(so,z),xy)=M(sO,z(xy))= M(so,(zx)y)sM(M(sO,zx),y)=M(M(so,xz),y)=M(sO,(xz)y)= M(so,x(zy))sM(so,(zy)x)=M(so,z(yx))=M(M(so,z),yx)=M(s,yx). Thus x is in the middle. ’ The next several results will show when a represen- tation of group elements is possible. Lemma 2.2. Let A a (S,I,M) be an automaton. Then the representation hx(s)2M(s,x) is Operation preserving if and only if x 6‘77), the middle. Proof: Assume x e 7T1. Then hx[M(s,yfl =M(M(s,y),x)= M(s,yx)=M(s,xy)=M(M(s,x),y)=M(hx(s),y). SO hx is opera- tion preserving. Now assume that hx is Operation preserving. Then hx[M(s,yI]=M(hx(s).y) or M(M(s,y),x)=M(s,yx)=M(M(s,x),y)= M(s,xy) so x 6 37}. Lemma 2.3. Let A a (S,I,M) be a strongly connected automaton and x 6 7T7, the middle. Then the representa- tion hx is onto. Proof: Let s,t E S. Then since A is strongly con- nected there exists y E I such that M(M(s,x),y)=t. Then t=M(M(s,x),y)=M(s,xy)=M(s,yx)=M(M(s,y),x)=hx[M(s,y)]. Thus hx is onto. Theorem 2.10. Let A =(S,I,M) be a strongly connected -25- automaton with n states. Then each representation by an element of the middle is in G(A) and the set of all such elements constitutes a subgroup of the center of G(A). Proof: The burden of the proof is supplied by Lemma 2.3. Since for x e'hl, hx maps 3 onto S and since S is finite, hx is also one-to-One. But by Lemma 2.2, hx is Operation preserving and so hx E G(A). Also for x,ye'h7, hxh a hx and xye/Tn. Thus the set of representations y y by elements of the middle is a closed subset of a finite group and hence is a subgroup. Also for g E G(A) and x c.7h, hxg(s) a M(g(s),x) = g[M(s,x)] = ghx(s) so hx is in the center Of G(A). Corollary 2.10.1. Let A a (S,I,M) be a strongly connected automaton with n states. Then the middle is empty if and only if the identity 1(8) 5 s is not repre- sentable. Lemma 2.4. Let A s (S,I,M) be a perfect automaton. Then hx is one-tO-one and onto for all x E I. Proof: By Lemma 2.3, hx is onto. To show hx is one-to-one assume hx(s) . hx(t) 8 s1 where s # t (i.e., hx is not 1-1). Then since A is strongly connected there exists y E I such that M(t,y) a s. Then M(sl,y) 2 M(hx(t),y) - M(M(t,x).y) - N(t,xy) = M(t,yx) - M(M(t,y),x) - M(s,x) a hx(s) - 81‘ Thus hy(81l = M(sl,y) a s But 1. by Lemma 2.2 hy is Operation preserving and hy(s1) - 1(s1) a s1. Thus by Lemma 2.1, hy(s) ! i(s) E 3. SO t = hy(t) s M(t,y) - s, a contradiction since t i 8. Thus hx is -26- One-tO-One. Examples can be constructed to show that Lemma 2.4 is not true for arbitrary strongly connected automata. However, for the class Of perfect automata we now see that we have the desired representation. Theorem 2.11. Let A = (S,I,M) be a perfect autom- aton. Then a necessary and sufficient condition that h E G(A) is that h be a representation. _Proof: By Lemmas 2.2 and 2.4 if h is a representa- tion, then h 6 G(A). Now let g 6 G(A) and s 6 S. Then for s = g(so) 0 there exists x e I such that M(so,x) s 8. Then g(so) = hx(80) and hx is operation preserving by Lemma 2.2. Thus by Lemma 2.1, g E hx and so g is representable. Corollary 2.11.1. If A = (S,I,M) is a perfect autom- aton, then G(A) is abelian. Proof: For hx’ hy E G(A) we have hxhy = hxy = hyx = hyhx. Corollary 2.11.2. If A = (S,I,M) is a perfect autom- aton, then K[G(A)] = KfSL Proof: Choose 30 6 S and for g E G(A) define ca : G(A)—+8 by (Mg) = g(so). Then 0((g) = «(M implies g(so) = h(so) and so by Lemma 2.1, g s h. Thus cx is one- to-one. Also for s 6 S, there exists x e I such that M(so,x) = 8 since A is strongly connected. But then hx(so) a s and hx 6 G(A). Thus 0£(hx) a s and so ex is onto. Thus K[S] s K[G(A)]. -27- It is natural to ask if the converse Of Theorem 2.11 is true. It is not but we have Proposition 2.12. If for an automaton A = (S,I,M) each element of G(A) is representable and each represen- tation is in G(A), then A is reversible and abelian. Proof: Let M(s,x) - t. Then hx e G(A) and so hx'l exists and bx"1 is representable, say hx'1(u) I M(u,y). Then M(t,y) s and so A is reversible. Also M(s,xy) s ’ "(M(B.X).y) M(hx(s).y) a hx[M(s.yI]= M(M(S.y).X) = M(s,yx) since hx e G(A). Thus in a I and A is abelian. Thus a partial converse to Theorem 2.11 may be stated 88 Corollary 2.12.1. If A is connected and if each element Of G(A) is representable and each representation is in G(A), then A is perfect. Proof: This follows immediately from Proposition 2.12 and Theorem 1.5. Proposition 2.13. Let A a (S,I,M) be a strongly connected automaton with n states. Then if the middle of I is empty, O(G(A))'v. Then gu(so)s M(s0,§u)= M(so,§')= gv(so). u-v+1 8 Thus by Lemma 2.1, gucgv or g g. Thus u-v= mt or u- v+mt for some positive integer m. Then we have ._ -1 ._ - ._ - (Ev)mt+18'ivimt x(v )mts Eu x(V lint: EV x(v 1)mt= 000 = ._V -v x . Thus x is periodic. But we noticed in the proof Of Lemma 2.5 that if (§”)mt+1= E”, then (36V)mt is idempotent. But the only idempotent is a two-sided identity and so ivmta 1( the two-sided identity) or ivmt+1= i’and‘i is periodic. Thus by Lemma 2.5, J1 is a group. Then let J2 be the kernel of the homomorphism ,5 and then the quotient group Ji/JZ is isomorphic to G(A). PART III THE DIRECT PRODUCT OF AUTOMATA Strong. Relatedness In this section a particular structure is studied, the direct product. The algebraic devices Of the pre- vious sections are applied with considerable success, though many problems are still unsettled. A necessary and sufficient condition for the direct product to be strongly connected is given. The main results of this section concerns the following problem. Given an autom- aton, when can it be written as a direct product of automata? This seems to be a difficult and, at the same time, important problem. Sufficient conditions for writ- ing a given automaton as a direct product are given here and as a matter Of fact the proof of these results show how to construct the ”factors". However the condition given here is, no doubt, too strong to be useful in ap- plications. Nevertheless, this is a step in the right direction and it is hOped that the solution here may suggest the proper line Of attack under more general circumstances. Definition 3.fl. Let A - (S,I,M) and B - (T,I,N) be two automata. The direct product, A x B, is the automaton A x B s (S x T, I, M x N) where M x N [(s,t),x] -= (M(s,x), N(t,x)). This definition parallels exactly the definition Of -40- -41- Rabin and Scott I: 5]. Definition 3.2. Two automaton A a (S,I,M) and B =(T,I,N) are strongly relateg if given any 81’ 32 6 S and any t1,t2 6 T there exists an x 6 I such that M(sl,x) = s and N(t1,x) = t2. 2 Obviously if two automata are strongly related, each automaton is strongly connected. As we shall see, the only desirable prOperty which this relation pos- sesses is symmetry. Proposition 3.1. Let A = (S,I,M) and B a (T,I,N) be two automata. Then a necessary and sufficient con- dition that A x B be strongly connected is that A and B be strongly related. Proof: Suppose that A x B is strongly connected. Then given any (sl,t1) 6 S x T and (s2,t ) 6 S x T there exists an x e I such that M x N [(sl,t1),x:]= (32, Hence M(sl,x) a 82 and N(t1,x) - t2 and so A and B are t2). But M x N [ (sl,t1),x]= (M(sl,x), N(t1,x)). strongly related. Now suppose that A and B are strongly related. Then given any (sl,t1) e S x T and (s2,t2) E S x T there exists (sz,t2) - (M(sl,x), N(t1,x)) a M x N [(sl,t1),x:). Thus A x B is strongly connected. The object of Proposition 3.1 and Definition 3.2 was to show the relationship which must exist between two automata in order that their direct product be strongly -42- connected. Proposition 3.2. Let A = (S,I,M) and B = (T,I,N) be two automata which are strongly related. Then if there exists an onto, operation preserving function, h:A+——9C, where C is the automaton C = (R,I,P), C is strongly related to B. Proof: Let r1, r2 6 R and t1, t2 E T. Then since h is onto there exist 81’ 82 E S such that h(sll = r1 and h(sz) = r2. Then since A is strongly related to B there exists an x 6 I such that M(sl,x) = s and 2 N(t1,x) = t But then r2 = h(sz) = h[M(sl,xfl - 2. P(h(sl),x) = P(r1,x) since h is Operation preserving. Thus C is strongly related to B. Hence if A x B yields a strongly connected automaton and C is any Operation preserving image Of A then C xB must yield a strongly connected automaton. Proposition 3.3. If A = (S,I,M) and B = (T,I,N) are strongly related automata, then there is no operation preserving function between A and B (A and B non-trivial). Proof: Suppose that there exists an Operation preserving function between A and B, say h:A-——9B. Then let 81‘6 S and t1 = h(sl) and t2 6 T be such that t2 # h(81). Now since A and B are strongly related there exists an x 6 I such that M(sl,x) = 81 and N(t1,x) = t2. But then t2 = N(t1,x) = N(h(sll,x) = h[M(sl,x)] = h(sl) since h is operation preserving, a contradiction. Thus no such h exists. -43- Corollary 3.3.1. For any automaton A, A is not strongly related to itself and hence A x A is not strongly connected. Proof: The identity function is an operation preserving function from any automaton to itself. Thus by Proposition 3.3, A is not strongly related to A. The Group Of A Direct Product Proposition 3.4. Let A a (S,I,M) and B x (T,I,N) be automata. Then G(A) x G(B) is isomorphic to a subgroup of G(A x B). Proof: Let g 6 G(A), h 6 G(B) and (s,t) 6 S x T. Now consider (g,h) e G(A) x G(B). Let ((g,h))(s,t) =- (g(s),h(t)) and then (g,h)[ M x N((s,t),x)] - (g,h)[(M(s,x),N(t,x))] - (g [M(s,x)] ,h[N(t,x)] ) = (M(g(s),x),N(h(t),x)) a M x N [(g(s),h(t)),x] since g and h are operation preserving on A and B respectively. Thus (g,h) defines an operation preserving function on A x B. Also the function defined by (g,h) is one-tO-One and onto since g and h separately are one-tO-One and onto. Thus the function defined by (g,h) is in G(A x B) and so G(A) x G(B) Q; G(A x B) by means of the obvious identification. TO show that, in general, equality does not hold in Proposition 3.4 we include the following example: A: Figure 5 again the input composition is taken to be Juxtaposition (generators 1, 2) for both A and B and the next state functions are extended to the entire input semigroup by the sequential property. Then we have -45- Then, writing the groups as permutations, we have G(A) = [1,F} where F = (ab) G(B) = {I} G(A x B) =[I,H,H2 where H = (ac ad ae)(bc be bd) K . (ac bc)(ad bd)(ae be) and of course G(A) x G(B) a; {1.x} . Notice here that A and B are even strongly related. As would be expected, it is easily verified that an isomorphism between two automata A s (S,I,M) and B a (T,I,N) induces an isomorphism between G(A) and G(B). Unfortunately it is also easy to find counter examples to the converse Of this statement, for instance consider automaton A of Figure 3 and the automaton obtained by interchanging 0 and 1. Automate As Direct Products We have, thus far, examined briefly the manner in which the direct product affects structure and groups of automata. An interesting question is: under what conditions can a given automaton be written as a direct product of two non-trivial automata? Furthermore if a given automaton can be written as a direct product how can its “factors" be determined%’ The following result gives at least a partial answer to these questions. Theorem 3.6. Let A a (S,I,M) be a strongly connected l T -46- and G(A) be transitive. Then if G(A) is isomorphic to a direct product of groups, A is isomorphic to a direct product of automata. Proof: Without loss of generality we may identify G(A) with the direct product Of groups H X L. We now show that A is isomorphic to B X C, where B = (H,I,N) and C = (L,I,N'), N and N' being defined below. Let ¢:H x L—)S be defined as follows: let so 6 s be fixed and define d>((h,g)) z (h,g)(so) for (h,g) e H X L. By Lemma 2.1, A is one-to-one. By hypothesis, 4? is onto. We now define N(h,x) s h: if and only if 1 M( d) ((h,g)),x) - 4) ((h1,g1)). This definition is not ambiguous since (P is one-to-one and onto. However, we must show that this yields a well-defined definition of N. Now M( ¢((h,g)).x)-M((h.gl(Sol.x)=(h.g)[:M(80.IX]. Now suppose M(so,x) = (k,m)(so)(by hypothesis there is such a group element). Then M( ¢((h,g)),x) 8.. (h,g)(k,m)(so) = (hk,gm)(sol = ‘b(hk,gm). But then M( . SO» ¢ is Operation preserving and is thus an isomorphism. A way to generalize this result will be indicated shortly but we show now that the condition of Theorem 3.6 is both necessary and sufficient in the case of perfect automata. Theorem 3.7. Let A = (S,I,M) be a perfect autom- aton. Then a necessary and sufficient condition that A be isomorphic to a direct product of automata is that G(A) be isomorphic to a direct product of groups. Proof: To show sufficiency we notice that by Theorem 2.11, A satisifies the conditions of Theorem 3.6. Now suppose A is isomorphic to B X C, where B=(T,I,N) and C = (H,I,N'). First, since A is perfect and isomorphic to B X C and the perfect structure is invariant under operation preserving functions, B X C is perfect. Also, the projection functions pB:B X C-——9B and pc: B X C-——9C defined by pB((t,r)) a t and pC((t,r)) x r are onto and operation preserving. Thus B and C are each perfect. Now by Theorem 2.11, for g E G(B X C) we have g((t.r>>:N x Ni(