THE U N I V E R S I T Y OF M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Communication Sciences TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA Yehoshafat Give on ORA Projects 03103 and.' 06689,.. al.;.... ~..-. under.ontrat~ -'th-:'''.' U. SO ARMY RESEARCH OFFICE (DURHAM) GRANT NO. DA-ARO(D)-31-124-G588, PROJECT NO. 4049-M 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 February 1965

TABLE OF CONTENTS TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA I: 1. The Representation and Completeness Theorem for Categories of Abstract Automata TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA II: 2. A Note on Some Well Known Functors of Automata TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA III: 5. Composition Series of Automata 4. Extensions of Q-Automata TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA IV: 5. The Characterization of Projective Automata

-a~ ~ ~ ~ ~~~~~-1 &3 c 5s

TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA I: 1. The Representation and Completeness Theorem for Categories of Abstract Automata

ABSTRACT In this paper the author formulates the categorical theory of abstract automata. Two immediate basic problems are posed. First, one wonders how restricted the study of abstract automata is when one confines himself to those properties which are formulated by means of the notions of category theory only. This is a mathematical question whose answer should be proved. The author proves the completeness of the categorical study of abstract automata for a wide class of input monoids, a class which includes all types of monoids employed in the theory of finite automata. In order to get this result, a general representation theorem for abstract automata is derived. The second, question is psychological. How well does the categorical study of automata suit our intuitions and our problem? The answer:: to such a problem is not a matter of proof. The development presented in this.paper has convinced the author of the potentiality of this new approach toward automata. Thus, this paper serves as a prelude to a series of papers which will exploit homological and categorical algebra methods for the sake of a mathematical theory of automata. iii

O. INTRODUCTION 0.1 In this paper we represent automata in a general domain of systems which can be regarded as "input" or "recognition" systems. By the provision, of suitable homomorphisms for such systems we get a category, denoted by Am Our main concern in this paper is to answer the following question: is a category-theoretic study of A sufficient for the study of automata represented by input systems? We are able to prove that the complete categorytheoretic study of k is a complete study of r. To use our terms, we prove that 4 is categorically complete. 0.2 In addition to the proof of the completeness theorem (in the sense defined in the sequel) for A we get the following results. A representation theorem for automata and.input.systems, in general, is derived. It is proved that every such a system is isomorphic to a system whose states are functions taken from a specific standard family of functions, and whose transition function is essentially function composition. The manner in which we develop our presentation suggests a close analogy between automata theory and the almost classical theory of modules 1

and abelian categories. Results which follow this suggestion, like the study of composition series of automata and extension theory for automata will appear in forthcoming papers. These results dictate in fact a thorough study of the category of automata (as defined in this paper), which will be covered in a series of forthcoming papers. 0.3 Some elementary acquaintance with category theory is needed. In particular we shall make use of the following notions: (i) Category, its objects and its morphisms. (ii) Covariant and contravariant functors. (iii) Epic, monic and isomorphism morphisms versus surjective, injective, and bijective functionso (iv) Right and left equivalence of morphisms; subobjects and quotient objects versus sub-systems and quotient sasems (v) Universal and couniversal diagramso The reader who is not familiar with these notions is referred to the literature on homological algebra and on category theory. (E-g.: Eilenberg and Maclane 1945, Cartan and Eilenberg 1956, Northcott 1960, Maclane 1963, 2

Freyd 1964, Hilton 1964, MacLane 1964.) 0.4 In general we use the ordinary notation and conventions used in algebra. In particular, we shall apply the following scheme for explicit description of functions:: T1 + T2: t + t' (This will always mean that A is a function from T1 to T2 such that for all teT: (t) = t'.) We shall intentionally omit the universal quantifications like "for all wcW" and"for all seSA", whenever we feel that such an omission is agreeable, 0.5 A scheme of definition Q(x) of predicates in categories is said to be categorical iff its only nonlogical primitive is morphism composition, For example the notion of "x is a monic morphism" is defined by means of a categorical scheme: "x is a morphism which is left cancellable under morphism composition" 3

0 6 A predicate QI(x) in a specific category C is said to be represented by the categorical scheme Q(x) iff Q (x) is logically equivalent with Q(x) in C. For example "x is an epimorphism" in any abelian category is represented by the scheme "x is epic" which is categorical (since it is defined as "x is a morphism which is right cancellative under morphism composition,). Note that "x is an epimorphism" in the category of monoids is not represented by "x is epic". 0.7 A category C is said to be categorically complete iff any predicate in C (either of morphisms or of objects through their identity morphisms, cf. Freyd, 196)4) which is invariant under isomorphisms of C, is represented by means of categorical schemes. 0.8 For any input monoid W we define a category C of abstract automata with W as input We shall see that for a wide class of monoids W, the catep gory & is categorically complete, by proving that for any automaton A in ~ (i.e., any object of t) one can construct (though not in an effective manner) by means of categorical predicates in A, an automaton Mor(A,) which is isomorphic to A. A more general treatment of this problem will be given in a forthcoming papero 4

1. THE CATEGORY A l~l Following Rabin-Scott s model for finite automata (Rabin and Scott 1959)^ we are interested in systems of the form A - (^s x W >SA) where (i) SA is any non empty set, to be called the set of states of A; (ii) W is any monoid (with 1W as its identity element), the input monoid of A; (iii) TA: SA x W + SA (s, w) + TA(s,w) is a function, the transition function of A, satisfying the following two compatibility requirements: (iii)i TA(S, lW) ~= s (iii)2 TA(S, w1w2) TA(TA(S, Wl),' W2) 1.2 Thus the input-to-state-traanitionr part of a Rabin-Scott's automaton, or of a sequential machine with output, is such a system with the free monoid generated by the input alphabet as its input monoid. 5

A seemingly different model for automata was suggested by Bichi (Btichi 1960). Namely that of monadic algebras (Birkhoff 1935). Following this suggestion one can directly apply the methods of abstract algebra to automata theory (Bichi 1960, Thatcher 1963). In particular a definition of homomorphism of automata is derived as a special instance of homomorphisms of abstract algebras. In fact, Biichi and Wright (Bichi 1960) were the first to define homomorphisms for automata and to stress the importance of the study of automata under homomorphisms. Still, one can derive in a very natural manner, a suitable definition of homomorphisms of systems as defined above. To be explicit, a homomorphism f A + B is defined to be determined by the function f SA SB iff the following diagram is commutative. SA x W.T A S f iW f SB x W -4 SB By means of a functional equation the comnmutativity of the diagram amounts to fotA = TBo(fx iw);G

where iW is the identity function of W and f x iW is the cartesian product of the functions f and iW: (f x iw)(s, w) (f(s), w) It is a matter of a straightforward verification to realize that: 1o21i PROPOSITION: The class of systems defined in 1.1 as objects, together with the homomorphisms defined above as morphisms, is a category. 1.2.2 On the other hand, the class of monadic algebras with operators over W (Give'on, 1964) together with their homomorphisms (Birkhoff, 1935), also forms a category. 1.2.3 These two categories are isomorphic, Hence the only difference between these two models can be regarded as a difference in notation. Our forthcoming change of notation, identifies these two categories. 1.3 The systems defined in lo1 are in fact sets with (a monoid W of) operators, a natural generalization of the concept of groups with (a ring of) operators, ThS LeadS up to the use of the following common algebraic nota, tion: s w rA (s, w) 7

(sometimes we may even write Just s-w wherever- no confusion is possible). Thus the compatibility requirements for transition functions are the well known axioms of modules (for the multiplication by scalars): s*1 s and s.(wWs2) = (s-w1)~w2 Whereas a function f SA + SE is now said to determine a morphism A - B of automata iff f(sAw) f(s)-w 1 4 Let us denote the category under discussion (with a fixed monoid W) by AW. The objects of QW will be referred to as "automata" even though the term automaton is used in a more specific context. Naturally, we omit the subscript W whenever it does not cause any confusion. 105 In order to be able to prove the completeness of e we have to be acquaintedwith some categorical predicates in Jo 1o6 The proofs of the following two propositions are exercises in ver~j.i cation of definitions and they are left for the reader, 8

1..6.1 PROPOSITION: In the category AW the (morphism) predicates of being surjective, injective or bijective are categorical and they are represented' by the categorical schemes of being epic, monic or an isomorphism (resp.)o 1.6.2 -Naturally, an automaton A is said to a subautomaton of B, in symbols, $c. A B, iff SA is a stable subset of Sp in B and the transition function TA of A. is the restriction of TB of B to SA x W. 16.3 PROPOSITION: In the categoryA the set of all subautomata of any automaton A, as a predicate of automata, is categorical. It is represented by the right-equivalence classes of all monic morphisms with range A. In fact, any two monic morphisms B1 — — A and B2 —jA are rightequivalent iff B1 and B2 are isomorphic and jl(S. ) = j2(SB). 16.4 Note that B- A and B-2.J>A are right equivalent iff there is an isomorphism B e —-:32 for which the following diagram is commutative. Bi A e /2 B2 9

1,7 If we allow an empty automaton ~W to be an object of ~ with a family of morphisms ^W-_:A one for each automaton A. with the stipulation o -mr A.s> B =W...... we get that Xw is a subobject of any automaton A and it is represented by the stipulated morphism (which turns to be monic) W J A. 1.7o1 Furthermore' SUB(A), defined to be the set of all subautomata of A, is a complete lattices Let (A}) be any family of subautomata of A then dAr is defined by SA = A and ia is defined by SA =S. 1.8 In order to verify that the predicate "X is isomorphic in okW to the union of the family [Ag} of subautomata of A'" is categorical, we assume that a family of mronic morphisms ABUT ~"-0-y A ] is giveno Then we define T..~~ A to be the right-equivalence class of c~CC any X +- A provided tha.t' (i) for any a there is a monic BC.....X with 1c, = jc; 1.0

(ii) if Y -' A is any monic such that there exists a family of monic morphisms B -a. Y for which. = ji, then there is a monic X-S Y for which the following diagram is commutativ'e B..... o A \>.X (That is, the diagram B \ is universal around X.) 1.8.1 To realize that we have represented the predicate "X is isomorphic in 6 to the union of the family (AC6 of subautomata of A", note that we have applied Prop. 1.6.3 to the definition of ~SA as "the minimal subset of SA which includes all SA as subsets". II

1,9 A dual construction yields the categoricity of "X is isomorphic to 12

2. THE REPRESENTATION THEOREM FOR W 2.1 Clearly, W can be regarded as an automaton by itself. We denote by M the automaton defined by W SMWW TM (Wi w2) 2 WlW2 = wIw2 Obviously MW is an object of A-W just because W is a monoid. We expect Mw to play a very significant role int, a role comparable to that of Z, the group of integers, in the category of abelian groups. 2.2 LEMMA: For any object A of A, the map Mor SA + Hom(M9 A) s + fs(: W SA w + saw) from the set of states of A to the set of all morphisms from MW to A, is bijective. Proof: For any W-1,W2W we have fs(WljW2)' fs(w1w2) sW1iw2 S (s'Wl)-w2 f= (w1) w2 Hence fs determines a morphism MW > A. 15

If f = fs then in particular fs (1W) = fS2 (1), and so 1 = lW = fs1(lW) = fs2 ) 2 1W = S2 On the other hand, for any morphism MW-'"g-A, since we have 9(WI)W2 = g(WlW2) we have in particular fg(W)(w) = g(lw) = g(w) Hence for any morphism MW- A we have Mor(g())' fg(l) g This completes the proof that Mor is bijective. 2 3 In particular Mor w - Hom(M, MW) is also bijective. Furthermore, since fw(wt) = ww', we have also w f -f = f wwi w2 iw 2 2 3 1 COROLLARY: The monoid End(Mw), whose carrier (set of elements) is Hom(Mw, Mw), with function composition as its operation, is isomorphic to W under Mor: W + End(M ) W 14

2.4 For any object A of we define the system Mor (A) by SMor(A) = Hom(Mw, A) g w gf o 2.5 THEOREM (The representation theorem for _,). For any automaton A, the system Mor(A) is an automaton and Mor AMor Mor(A) is an isomorphism which is determined by Mor: SA + Hom(Mw, A) s + f Proof: Clearly we have (f sQf)(w ) f(wWI) = s. = (s.w).w,:f (); s w hence f of =f, and therefore s' w saw Mor(s-w) fs w = of fs w Mor(s)w which shows that Mor determinesea morphism of A into Mor(A). The rest of the theorem follows from our previous statements. 2*6 We can supplement Mor so that it becomes a functor Mor: a'>^-, This can be done naturally by defining 15

Mor(A) lMor (g) Mor(B) g for any morphism A. B, as determined by Mor(g): Hom(Mw, A) - Hom(Mw, B): f gofs Clearly Mor: rA)~ is a covariant functor of A into itself. 2.7 LEMA: Let A $ B be any morphism of automata, then for any seSA we have gofs g(s) Proof: (gofg)(w) = g(sw) = g(s).w = f (w) 207.1 COROLLARY: Mor: A o.~- is a covariant functor of A into itself which is naturally equivalent by Mor rj(A) = (A --- — Mor(A)) to the identity functor of cA. Proof: By Lemma 2.7, for any morphism A + B, the following diagram is commutative o A ~Bg I(A).(B) Mor(A) -- > Mor(B) 1 (.

2.8 In addition to End(A), the monoid of the morphisms A + A with respect to function composition, there is a more often applied monoid which is associated with A. Namely it is M(A) the monoid of transitions associated with A in the following manner. For any object we define t: W - SAA: w + Tw; Two SA SA: s - s"w and clearly we have TwloTw2 = Tw2w1 ~ Thus t(W) is a submonoid of SASA the monoid of all functions from SA to SA. We define M(A) =d(t(w):w e W) We can rephrase the requirement on fs SA.A for determining a f morphism A + A by: fcEnd(A) iff foTw = Twof for all TwcM(A). Hence we proved: 2.8.1 THEOREM: For any automaton A, End(A) is the centralizer of M(A) in SA sA 1 17

30 THE CATEGORICAL CHARACTERIZATION OF MW 3o1 Here we give a categorical characterization of MWin those cases where W satisfies the following condition on its unit-elements: 3ol.1 For any wi w2 e W if wiw2 = 1W then we have w2wl = 1W as well We shall call a monoid which satisfies this condition, a unit-commutative monoido Note that abelian monoids and right-cancellative monoids are unit-commutative. Hence, the restriction to this type of monoids does not affect the applicability of our results. 3.2 Let A be any automaton. Any subset T c S determines a subautomaton A* A(T) of A which has SA(T) =df (ttw teT & wcW) as its set of states, We say that A(T) is the subautomaton of A generated by T. A subset T S' SA is said to be a set of generators for A iff A(T) A. In particular, A is said to be monogenic iff A has a set of generators with a single generator. In such a case, when t is the only element of T, we write simply A(T) = A(t). 18

3.3 Note that MW is always monogenic. For example, it is generated (as an automaton) by Wo One may easily prove that for any monoid W MW = MW(U) iff u is a right-unit of W. 3.4 LEMMA: A is monogenic iff for any set of generators T for A there is teT such that A(t) A. 3.4.1 REMARK: This lemma, whose proof is straight-forward and left for the reader, exhibits a significant property of automata. Intuitively speaking, in automata as we have defined them in 1.1, states do not interact~ 3-5 THEOREM: An automaton A is monogenic iff there exists an epic morphism e MW - A Proof: If A. A(So) then the mapping es W - SA: ~w-: sowe determines an epic morphism MW -~^ A.(S o) On the other hand, if MW e A is epic, then e(l-w) generates Ao 3.6 REMARK: Note that an automaton is'strongly connected" iff it is generated by any one of its states. Put differently, A is strongly connected iff it has no proper nonempty subautomaton. 19

3.7 THEOREM: An automaton A is monogenic iff for any family (A c of subautomata of A the following two statements are equivalent: 72 there is for A A. 357.2 there is a for which A r A. Proof: If A is monogenic then A = A(lc) for some soeSA. Hence So S. for some a, and therefore Aa = A. On the other hand define for all seSA: A A(s) then clearly As ='A.(s) = A and therefore there is an seSA for which A = A; hence A is monogenic. 3.7.3 COROLLARY: The predicate "X is a monogenic object of ^W" is categorical. Proof: By Theorem 3-7 and 1.8. 3.e8 ZTHEOREM- Assume that W is unit-commutative. If A is monogenic and e A + MW is epic then it is an isomorphism. Proof: Let A be generated by Ho, then e(So) generates Mw and therefore e(so) u - 1W for some ueW, But W is unit-commutative and so u.eI(s) = 1 as well Assume that e(s owl) = e(so.w2) for some wl, w2eW. Then we have W1 = u'e(sO)*Wl = u-e(SOWwl) = U'e(So-W2) = u-e(so)-W2 = W2 20

and therefore e is also monic, 3~9 The characterization of MW inyJ is now straightforward: 3.9.1 THEOREM: Assume that W is unit-commutative. An object X of W is isomorphic to MW iff the following two conditions hold: (i) X is monogenic; (ii) if A is monogenic then there exists an epic X + A, 3?9.2 In other words we can say that an object ofAW is isomorphic to MW iff it is an initial object in the subcategory of monogenic automata with epic morphisms only. 3.9.3 A more general characterization of MW will be derived from a study of the projective objects in AW to be presented in a forthcoming papers 21

4. THE CATEGORICAL COMPLETENESS OF.W 4i1 Given any predicate of automata P(X) which is invariant under isomorphism of automata then we clearly have for any automaton A P(A) iff P(Mor(A)) By Theorem 3.9.1 we have that Mor(A) is categorical in the following sense. For any category Cwhich is isomorphic to aW say by J:. <- C and for any object A of c, Mor(J(A)) is well defined and it is an automaton which is isomorphic to A., Hence P(A) holds iff P(Mor(J(A))) holds. From this follows that any predicate P(X) of automata, is represented by P(Mor(X)) which is categorical. Thus we have proved: 4,2 THEOREM: If W is a unit-commutative monoid, (1 is categorically complete. 4,3 In addition to the mathematical import of the completeness of we know now that if one wishes to study automata (i.e., state diagrams) under categorical notions only, there is no theoretical objection to such a restric2 22

tion. Any property of such automata has "its representation in a form which is categorical. This does not imply that a categorical study of automata is necessarily the most appropriate mathematical approach to automata. It may however provide a persuasion to try to see what can be done in automata theory if one follows the problems and the notions that are studied in the traditional domains of category theory. Our next papers are directed towards this goal.

BIBII OGRAPHY Birkhoff, Go, "Structure of Abstract Algebras," Proc. Cambridge Philos, Soc., 29, 44i-464 (1935)o Bichi, JO RB, "Mathematical Theory of Automata," Notes on material presented by Jo. B. Wright and J. Ro BIchi, Communication Sciences403, Fall 1960, The University of Michigan, Cartan, H. & S. Eilenberg, "Homological Algebra," Princeton (1956). Eilenberg, S. & S. MacLane, "General Theory of Natural Equivalence," Trans. AMS, 58, 231-294 (1945 ) Freyd, P., Abelian Categories: An Introduction to the Theory o Functors, Harperts Series in Modern Mathematics, New York (1964) Give'on, Y., "Outline for an Algebraic Study of Event Automata," Tech. Rep. 05662, 06689, 03105-28-T, ORA, The University of Michigan (1964). Hilton, P.J., "Categories Non-Abelianes," Seminaire de Mathematiques Superiers, Universite de Montreal, Dept. de Math., Juillet 1964. MacLane, S., "Categorical Algebra," Collog. Lectures given at Boulder, Colorado, August 27-30, 1963, at the sixty-eighth Summer Meeting of the AMS (1963). MacLane, SO, Homology, Springer, N, Y., Berlin, Gottingen, and Heidelberg, (1963). Northcott, D. G., "An Introduction to Homological Algebra," Cambridge (1960). Rabin, M. 0. & Do Scott, "Finite Automata and Their Decision Problems," IBM Journal, 3, 2, 1149125 (1959). Thatcher, J. W., "Notes on Mathematical Automata Theory," Tech. Note 05602, 03105-26-T, ORA, The University of Michigan (1963).

TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA II: 2. A Note on Some Well Known Functors of Automata

ABSTRACT The provision of a suitable definition of homomorphisms of abstract automata (i.e., of state diagrams with an arbitrary fixed input monoid W) yields of category (denoted bYAw). The naturalness of the application of category theory to the study of automata follows from the fact that many, if not most, of the processes employed in automata theory turn out to be functors of or into iW. This observation, which is reviewed in the present paper, has led the author to experiment with a more thorough application of the category theory approach to 3W. The results of this application are presented in the series of papers under the common title "Toward A Homological Algebra of Automata. " iii

0. INTRODUCTION 0.1 Here we are going to present our observations which drove us to pursue the possibility of a homological theory for automata as it appears in this series of papers under the title "Toward a Homological Algebra of Automata." Our observations can be summarized by the following. Most of the general procedures employed in automata theory are in fact functors of suitable categories of automata. Some pairs of these are shown to be naturally equivalent functors. 02 We cannot estimate now the importance of these observations. At least they suggest giving to category theory the opportunity to become the mathematical general framework for the theory of abstract automata. 03 Most of the proofs of our results here are routine. Therefore most of them will be left for the reader except for certain details that seem to have some significance. Furthermore, we do not intend to study the functors that we derive before we extend our knowledge of the category of automata itself. 1

In particular we postpone the study of the "algebraic" functors of automata; like the association of semigroup of machines and several notions of products of machine, each single one of them yields a wide domain of important problems and results. Hence this note will present more problems than solutions. We hope that our forthcoming research will shed some light on these problems as well. 0.4 Naturally, this note depends on the previous paper (Give'on 1964b) with its terminology and notation. 2

1. THE TRANSITION TRANSLATIONS OF AUTOMATA 1.1 Given any automaton A we define M(A), the monoid of A, to be the monoid of the transition translations w: SA + SA s + s.w with respect to the opposite of function composition: TW1*Tw2 = Tw2OTW1 Note that we have Twow = Tw2wl 7W1 TW2 W~W1 1.2 We have noted in (Give'on 1964b) that:End(A), the monoid of endoSA morphisms of A, is the centralizer of M(A) in SA, the monoid of all functions SA - SA. 1.3 We define T(A) to be the system T(TA) T(A) = (M(A) x W --------- M(A)) 3

where T(TA) is given by'wl.2 = -'wlw2 13o1 LEMNMA: For any object A of JW, T(A) is an object of W satisfying the additional compatibility with the monoid structure M(A): (T *w2) W3 = Tw *(Tw2 W3) Furthermore, T(A) is monogenic and generated by 1M(A) Proof: From the associativity of the operation of W it follows that Twl*( rw2'W3), (Twl*Tw2)'W3, rwl*Tw2w3, Tw1 w23 are all equal to Twlw2w3. To realize that T(A) is generated by 1M(A) note that 1M(A) w= TW w = Tw 104 In order to derive a functor of automata out of A + T(A) we observe the following: l1o!l LEMMA: If Al -e- A2 is an epic morphism of C-W then lk

1 2 e*: M(A1) + M(A2): Tw + Tw is a surjective homomorphism of monoids which determines an epic morphism e* T( A) T(A2) Proof: e* is well defined precisely because of A1 e A2 being 1 1 an epic morphism of automata. For let Twl = Tw2 for some wl,w2eW then we have s*w1 = s.w2 for all seSA. Since e is a morphism of automata we infer e(s) wl = e(s.wl) = e(s.w2) = e(s).w2 for all seSA. But e is surjective, hence we have s'Twl = s' w2 for all s'eSB, which im2 2 plies Tw = w2. The rest is routine. 1.4.2 Let us denote byCe the epic-subcategory of a category C, that is the category whose objects are all the objects of C and whose morphisms are the epic morphisms of C. Using this notation, we can define T: aW.9' by adding T(A1 > A2) = T(A1) - T(A2) 5

e e 1.4.3 THEOREM: T:A^~W w is a covariant functor of the epic-subcategory ofn9W. Proof: Straightforward. 6

2. THE CATEGORY P1W OF MONOIDAL AUTOMATA 2.1 The additional properties of the automata that occur in the image of T lead us to define the following subcategory of 9W The category MW of monoidal automata has objects automata that have monoids for sets of states, such that the multiplication among the states is compatible with the transition function in the following manner: slx(s2'w) = (sl*s2)w, where "," denotes the monoid operation among the states. Such automata will be called monoidal automata. f A morphism Al -, A2 of monoidal automata is defined to be a morphism of automata Al f — A2 such that f: SA1 SA2 is also a homomorphism of monoids. 2.2 An important subcategory of /jW is the full subcategory of the monogenic monoidal automata which are generated (as automata) by the identity element of the monoid of states. Such automata will be called unary monoidal automata and we denote their category by /1. 7

2.2.1 LEMMA: If Al, A2 are monoidal automata and A2 is unary then there f exists at most a single morphism Al —. A2 of monoidal automata, and this morphism, in case it exists, is determined by a surjective homomorphism f SA1 - SA2 (REMARK: Note that in the category of monoids epic morphisms need not be surjective.) Proof: If Al -f A2 is a morphism of monoidal automata then f( l ) = and therefore f( SA. w) = f(lSA1)w = SA2 2 3 Let us denote by Sur(W) the category of surjective homomorphisms of W of the form h H = (W - MH) A homomorphism MH1 - MH2 of monoids is said to determine a morphism H1 -- H of Sur(W) iff the following diagram is commutative. 8

hi W h -h MH'' h2 W M - MH2 2.3.1 LEMM: Sur(W) is a category in which Hom(H1, H2) contains at most a single morphism and this morphism is determined by a surjective homomorphism of monoids M + MH H1 1' Proof: Immediate. 2-.4 Define A: Sur(W)/N1lW by the following. Let H be an object of Sur(W) then A(H) is defined to be the system A( h) A(H) = (MH X W -( MH) where A(h) is given by m w = m*h(w). Let HI -- H2 be a morphism of Sur(W) then let A(H1 -g-+ H2) = A(H) -9 A(H2) 2.4.1 THEOREM: A: Sur(W)'> M 1 is a covariant functor which establishes an isomorphism of categories between Sur(W) and 4. Proof: Immediate. 9

2.5 Let F Cl->C2 be a functor and C3 a subcategory of C2. We say that the image of F is essentially C3 iff for any object A of C( there exists an isomorphic object A' in the image of F and the image of F is a subcategory of C3. e e 1 2.5.1 THEOREM: The image of T:C)W BROW is essentiallyj4lW. 2.5.2 REMARK: Obviously 41 is a subcategory of~'_W and the image of T is a subcategory of /W. We shall prove the following analog of Cayley theorem that implies Theorem 2.5.1 directly. 2.5.3 LEMMA: For any object A off w we have an isomorphism of automata rI(A) A --- T(A) which is determined by (A) SA M(A) S M(A): w - Tw Proof: The function r(A) is well defined since 1SA = S w2 implies T (s) = S W1 = S*(l swl) = s*(lw2) = T(s) for any seSA. The rest is routine. 10

2.6 THEOREM: Let us denote by 1 the restriction of T to 1. Then the function r establishes a natural equivalence between T and the identity functor of,,lW Proof: Let Al -~ A2 be any morphism of)'w then we have to show that the following diagram is commutative. A~(A() A1 r(A) ( T( A1) f | f* A2 T((A2) 2. (f*ob(Al))(lSl w) = f*(W) = TW and (and) cf)(lS e) ((A))(l ) 2.6.1 C LA Ally e I 2.6.1 COROLLARY: The functor T: - -1VW is essentially idempotent; i.e., ToT is naturally equivalent with T. 11

3. FROM NONDETERMINISTIC TO DETERMINISTIC AUTOMATA 3o1 There are mainly two ways by which nondeterministic automata are transformed into (weakly equivalent) deterministic automata. Each one of them yields a functor from a category of nondeterministic automata torF4. 3.2 We define first JW, the category of (abstract) nondeterministic automata with input monoid W, as follows. The objects ofJyW are systems of the form N (SN x W - ((SNN)) where &(SN) is the set of all subsets of SN, and vN satisfies the following compatibility requirements: S W1W2 = U(s' w2:'es.w1) and s-1w = (s) The morphisms of JVw^ are defined to be of the form N1 -- N2 12

where f: SN1 SN2 s a function which yields the commutativity of the following diagram for f): SN) (S) T + f(s): sT). f W o( f) ~NN2 -,(2) 3.2.1 PROPOSITION: JVN is a category in which epic and monic morphisms are determined by surjective and injective functions. 3.3 By means of the so called "subset construction" we associate with any object N ofGJ a system (N) -= (O(sN) x W., ^ s N) ) where P(VN) is given by (for any TC SN) Tf w - U(s.w: seT)'3.3.1 LEtiA: For any object N ofJW, N(N) is an object ofi W. 13

As for the morphisms of JW we naturally define ~ -(N N2 ) = ((.(N))) 5 2A f 1 2 e N N 3.3.2 LEMMA: If N1 N2 is a morphism ofJVW then 2(N1' N2) is a morphism of<J4W. 3.3.3 THEOREM: Q:'W AW is a covariant functor. 3.4 In addition to the subset construction one can derive a deterministic automaton weakly equivalent to a given nondeterministic automaton by means of a construction which. is similar to T:'q W 1j. That is, by means of the monoid of the transition relations. 3.4.1 Note that we hope that our notation for^t confuses well the two isomorphic categories; that of nondeterministic automata and that of relational systems (cf. Thatcher 1964). 3.5 Given an object N ofJ, we define M(N), the monoid of N, to be the monoid of the transition relations W =,U((s 1w) x (s.w): sESN); i.e., 14

<s, s'>e w iff s'es*w For any object N of vW we define the system B( vN) B(N) = (M(N) x W -vN M(N)) where B(vN) is given by Pw w2 =' www = 2wOw 1i 2 - 1wiW2 WO1 2 3.5.1 LEMMA: For any object N of VW, B(N) is a unary monoidal automaton; that is, an object ofJ/w. Proof: Similar to the proof of Lemma 1.3.1. 3.6 Following Lemma 1.4.1 we derive: 3.6.1 LEMMA: If N1 -e N2 is an epic morphism of \W then 1 2 e*: M(N1) - M(N2): Pw - Bw is a surjective homomorphism of monoids which determines a morphism of monoidal automata e* B(Nl) e* B(M2) 3.7 We define therefore 15

e B:,W W by adding B(N1 + N2) = B(N1) - B(N2) and we derive the following result: 3.7~1 THEOREM: B:'A W J>W is a covariant functor with image being essentiallyJ~1. 16 e ssent ially W1.

4.. THE EQUIVALENCE OF B AND T o 4.1 From our previous results, we can derive monoidal unary automata from nondeterministic automata following the two paths in the next diagram of functors, where f e B SAW T B:SP2 W 4 A/ W is the restriction of P: J -JL toW. Obviously To6and B are not identical functors but they are similar enough to be naturally equivalent. Still, this natural equivalence is trivial because of the following general theorem. 4.2 THEOREM: Let F1, F2: C — Co be two functors from C into o. If Co is a category in which for any two objects A,B, Hom(A,B) contains at most a single morphism then a necessary and sufficient condition for the existence of a natural equivalence r: F1 ~ F2 is that for any object A of 17

C, F1(A0 and F2(A) are isomorphic, Proof: Necessity is immediate. For the proof of sufficiency, assume that A B is a morphism of C and denote by F1(A) r(A)- F2(A) the isomorphism of Co that is assumed to exist for any object A of Co Obviously, the following diagram is commutative because of the trivial structure of CO. F1(A) F2((A) Fl(f) F2(f) F1(B) n( ) > F2(B) 4.3 LEMMA: For any object N of JV/ the function 5( N): M(N) ->M(G(N)): ((vN))w w where ((N) )w ( SN)):) T - Tw determines an isomorphism B(N) (N) [To](N) 18

of j WI Proof: Straightforward. 4.[.l 3 COROLLARY: B: B + To is a natural equivalence from B: JeW MW to ToP: /W V J W' 19

5. A REMARKI ON THE RELATION BETWEEN THE SUBSET CONSTRUCTION AND THE CARTESIAN POWER OF AUTOMAT'ON 5o1 The subset-construction as applied to automata yields a covariant functor as defined by (i) 6(A) = (6(SA x W- (-A SA)) where T-rA) is given by T'w = (sow: seT); (ii) O(A1. —f A2) = (P(A1) -..Lf ( A2), where (f) is defined by ( rf))(T) = (f(s): seT)~ We shall see presently that CPis a functor which is naturally related to the functor of cartesian products of automata, 5~2 In particular, we define for any set T: T W W by 20

(i) PT(A) =(SAT x W-T(I Sa T T where SA is the set of all functions T - SA+ and PT(r) =' T is given by ~.w: T + SA: t + ~(t)w T T Naturally, we denote P (A) = A () T fT T (ii) P (A1 )= A2) A -- A2 T where f is defined by T: T fT( ) f f(): T S^: t + f(~(t)) 5.3 LEMMA: Both ( and pT are covariant endofunctors oi'9W. For any fixed automaton A, P (A) as a function of T induces in fact a contravariant functor pX(A): S T of the category of sets intoa W. Furthermore, P(T,A) = p (A) induces a bifunctor P 5 4 x^ -21 W 21

Proof: Naturally, we add to the definitions of PX(A) = AX and P(T, A) = AT the following: (T- ~> T) TT Pt T2(A) =A A A where T2 T1 p* ~ SA + SA + o and likewise P((T1,- T2), A) = A2 - ATi The verification of the lemma is routine. 514 The main difference between AT and()(A) lies in the fact that in AT the states are ordered sets over SA, while in&(A) they are just subsets of SAo This calls of course for a "forgetful transformation" from automata of the form of AT to automata of the form of 9,A) Let T be a fixed set, We define a transformation aT from the class of objects oftW to the class of morphisms ofNW by T aT(A): SA i(SA): + {>((t): tET) o 5o4oi1 LEMMA: The function ST(A) determines a morphism 22

AT CjT(A (A ) A ^ L(P(A) of~ W. Note that aT(A) covers all the nonempty subsets of SA iff SA contains a surjective function T + SA Proof: Immediate. 5.4.2 THEOREM: For any set T ~T. OT: Pt ^> (P as determined by T ) "(A) (A) %T(A) = A ( —A) is a natural transformation from pT: 4W, "9W to:'W' "'W. f Proof: Let A1 - A2 be any morphism of AW, then we have to show that the following diagram is commutative. T fT T A1 - ~........... A2 aT( Al) CaT(A2) O(A ).^; - ) Let ~ be any state of A1 then we have: [ f) ][aT(Al) ]() = [) f)]([ (t): teT)) - (f(/(t)): teT} - [T(A2) ](fT())) 23

6. EVENT FUNCTORS OF AUTOMATA 6.1 All the constructions discussed previously were introduced in order to derive transformation of automata which preserve the so called "behavior". In this section we discuss briefly the definition of events by means of automata. A more complete study of the functors that are involved in this is necessary to the understanding of the theory of finite-state event-automata ( Give' o 1964a). 6.2 Every automaton determines a function which associates with any choice of "initial" and "final" states a certain subset of the input-monoid. We define therefore for any object A of ^ W E(A): SA x(SA) +>(W) (s, T) + [w s.weT), and for any object N ofqV^ E(N): (SA) xP(SA) >Q(W): (TT2) (w (T1jw)r T2 6.2.1 Thus, a Rabin-Scott finite-automaton (Rabin, Scott 1959) is defined as <= <V, A, (so, F)> where V is a finite set (the alphabet of l.), A is an automaton with V* as input monoid such that SA is finite, and (so,F) e SA x Z(SA). 24

The event T() defined by kis [E(A) ](so,F). 6.3.1 PROPOSITION: If A1 -- A2 is a morphism of 9W then for every seSA and T C SA we have [E(A1) ](s,T) C [E(A2) ](f(s),f(T)) 6.5.2 PROPOSITION: If N1 - N2 is a morphism of A.W then for every T1, T2 C SN1 we have [E(N1) ](T, T2) C [E(N2) ](f(Tl) f( T2)) REMARK: For the sake of clarity, but with the price of rigor, we denote by f both the function as it is, and the induced function &(f) on the set of subsets of the domain of f. 6.4 THEOREM (Rabin-Scott): Let N be any object of J. Denote by [F]N, for FC SN, the set of all subsets of SM which overlap with F; i.e., [F]N= TC SN: {I F # 0) Then for any So,F C SN we have [E(N)](So,F) = [E(Q6(N))](So,[F]N) Proof: Follow the proof of (Rabin Scott 1959). 6.5 The definition of events by unary monoidal automata follows their special structure, naturally. For any unary monoidal automaton A, we define 25

E1(A): O(SA) 6(P(W): T (w s: iSwT} 6.5.1 PROPOSITION: If Al e- A2 is a morphism of unary monoidal automata then for any T C SA we have [El(A1) ](T) c [E1(A2) ](f(T)) and [E1(A) ](f-f(T)) = [E(A2) ](f(T)) 6~5.2 THEOREM: Let A be an automaton (ioe., object of fw) and let SOESA F cSA. Denote by TA[so,F]:.TA[SoF] = {Tw: s6weF} cM(A). Then we have [E(A) ](soF) = [E(T(A)) ](TA(SoF)) 6,6 These results yield in fact a natural category of event-definitions such that E, E, and El turn out to be covariant functors ofw, L'W, andJ1w (respo) into the category of event-definitions, We leave the study of this category to a later stage of the development of the categorical theory of automata. 26

BIBLIOGRAPHY Give'on, Y., (a) "Outline for an Algebraic Study of Event Automata," Tech. Rep. 05662, 06689, 03105-28-T, ORA, The University of Michigan (1964). Give'on, Y., (b) "Toward a Homological Algebra of Automata I: 1. The Representation and Completeness Theorems for Categories of Abstract Automata, Tech. Rep. 06689, 03105-32-T, ORA, The University of Michigan (1964). Rabin, M. 0. and D. Scott, "Finite Automata and Their Decision Problems," IBM Journal, 3, 2, 114-125 (1959). Thatcher, J. W., "Notes on Mathematical Automata Theory," Tech. Note 05602, 03105-26-T, ORA, The University of Michigan (1963). 27

TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA III: 3. Composition Series of Automata 4. Extensions of Q-Automata

ABSTRACT 3. COMPOSITION SERIES OF AUTOMATA The classical results of commutative algebra on composition series (i.e., the theorems of Jordan, Holder, Zassenhaus, and Schreier) are derived for automata. The relevance of these results to the study of automata is discussed briefly by means of an alternative proof of these results. 4. EXTENSIONS OF Q-AUTOMATA Previous results of the author concerning composition series for automata lead to the introduction of a specific type of quotient operation of an automaton relative to any subautomaton. Naturally, the problem of extensions, relative to this type of quotient, is posed. A complete characterization and a method of construction of all possible extensions of automata are derived for a broad class of automata. iii

i

TABLE OF CONTENTS Page 3. COMPOSITION SERIES OF AUTOMATA 1 1. Basic Notions 3 2. Composition Series 7 3. Discussion 14 4. EXTENSIONS OF Q-AUTOMATA 17 1. Definitions 19 2. Classical Results 22 3. Projective Extensions 30 4. The Characterization of Ext(C, so, A) by Means of the Connecting Homomorphism 32 BIBLIOGRAPHY 37 v

3. COMPOSITION SERIES OF AUTOMATA

I

1. BASIC NOTIONS 1.1 In this paper we regard automata as input monoids operating on sets. To be specific, we assume a fixed input monoid W and thus an automaton A is defined by its set of states, SA and the manner by which W operates on it, that is by the multiplication rule TA SA x W - SA: (s, w) + sew which assigns sw to any pair (s, w) C SA x W. We assume the following requirements on TA, the transition-function of A: (i) s'lW = s where 1W is the identity element of W; (ii S.(1) = (SW1)-W2 1.2 We do not assume anything on the size of the sets of states of our automata. Thus, for example, we have the following two particular automata: 1.2.1 Ow which has a single state only. (This specification defines OW up to an isomorphism.) On the other hand we have: 1.2.2 MW which has W as its set of states and so MW is in fact W regarded as operating on itself from the right: W1 W2 = WlW2. 1.2.3 We shall find it useful to include the "empty automaton" W in our discussion. 5

1o3 A subset SB of SA is regarded as a subautomaton B of A, in symobls, BSA. iff it is closed (or stable) under the multiplication by WO That is, iff s e SB implies s'w c SB (for any s c SA and w c W, naturally), Thus,, is a subautomaton of any automaton. This is not true of O w An automaton is said to be ple simple i t has OW as its only proper nonempty subautomatono An automaton A is called irreducible iff is its only proper subautomaton. For example, OW is irreducible 1.51l Clearly the class of all subautomata of a given automaton is closed under intersections and unions. Hence this class forms a lattice. 1.3o2 PROPOSITION: The class of all subautomata of a given automaton is a complete modular lattice In particular, let A. B and C be subautomata of a given automaton such that B c A., then A. n (C u B) (A /) C)U B Proof: Follow -the corresponding proof for sets: SA. (SC )'= ('C C SQC) CU SB 1o3o3 We can define internal direct suwn of two subautomata as their union iff they are disjointo Thus, if A. and A2 are subautomata of A then A = -(A1 0 A2) iff A (A, U A2) and (A1 0 A2) = 1.4 Homomorphisms of automata can be defined naturally. Thus, a function f f: SA + SB is said to determine the morohism + B iff f(s * W) = f(S) W( 4

Obviously we make use of all the traditional abuses of notations which are found to be quite useful and clarifying. E.g., we denote both the operation of A and that of B by the same symbol; we omit universal quantifiers that should occur at the beginning of our statements; etc. Homomorphisms of automata cannot yield directly any fruitful notion of kernels. The reason for this lies in the fact that the only communication that takes place among states is done by means of transitions from single states. However, we can define a moderately interesting notion of quotient-automata as determined by subautomata and which are related to epimorphisms (surjective morphisms or epic morphisms) of automata in a natural manner. The reader is referred to the literature for a more detailed study of various categories associated with automata (Thatcher 1964, Give'on 1964). 1.5 Let B be a subautomaton of A. We define A/B by the following:.SA/B =df (SA - SB) U (s], where s* is not an element of S; Ssw in A if s*w E SA/B sw = - sB otherwise Thus A/B is derived from A by replacing OW instead of B. For example we have the following peculiar unique situation: A/,W = A $ OW. To be more general we have (A $ B)/B = (A. 0OW) for any automata A., B. (Note that (A $ OW) = A). On the other hand we have A/B = A::iff B = W - A.

1L6 LEMMA.: A/B is completely determined by SA - SBO Fu'thermore, if SA # / then the identity function of SA SB can be extended uniquely into a function q: SA + SA/B which determines an epimorphism qB A -. A/B (the canonical epimorphism of A onto A./B). Proof: Immediate. 1.6.1 REMARK: Note that not every epimorphism of automata is equivalent to a canonical epimorphism onto a quotient automaton. l.6e2 REMARK: Our notion of quotient automata is in fact a generalization of Rees's concept of quotients for semigroups. And so our development generalizes Rees's theory of composition series for semigroups (Rees 1940). 1.6.2 COROLLARY: The mapping qB A SA + SA/B extended by the subset functor to P(qB): P(SA) - P(SA./B) (that is P(qB)(S) = (q(s): s e S) for all S SA), determines a bijective correspondence between the subsets of SA which' include B and between the nonempty subsets of SA/B, In particular, qB determines a bijective correspondence between the subautomata of A which include B and the nonempty subautomata of A/Bo 1.6,3 COROLLARY: An automaton B is a maximal proper subautomaton of A iff A/B is simple. 1.7 LEMMA: If A. and A2 are subautomata of A then we have (A U A2)/A2 - A /(A.1 n A2) In fact the isomorphism is a single point extension of the identity mapping of SA - SA2 6

Proof: By Lemma 1.6 it is sufficient to show that S(A.1 A,) - SA = SA - (A1 Ai) Indeed, (A1. A2) -A2 = A1(U A) A SA.1 - SA2 = SA1 - (SA. SA2) =SA1 - S(A.1 A2) 1.7.1:REMARK: Note that if (A1 I A2) = OW we have (A.1 A2) = (A.1 A.) and we have noticed already (cf. 1.5) that (A.1 A2)/A2 = (A 1 E 0W) and A1/0W = (A1 e OW). 1.8 LEMMA: Let A, B and C be automata. If A. 3B - Ct'henA/C ~B/C and (A/C)/(B/C) A./B where the isomorphism is a one point extension of the identity mapping of SA - SgB Proof: SA/C (SA - SC) (ss), SB/c = (SB - Sc) U(s, hence, SB/c' SA/C and so B/C rA./C; and furthermore, A./C - B/C = sA -B 2. COMPOSITION SERIES 2.1 A normal series of an automaton A is a finite sequence of subautomata A. = A0-A1'A2:- A n - n_ 7

The length of a is defined to be (c)) - no The factor series of the normal series a o A - A. A., -~A - A o. n 0= W is defined to be the sequence Q(c) = <A./A1, A A1/ /AA2,.., A.n-i/An> Two normal series Ca and 3 are said to be equivalent iff i(a) - ) (B) and Q(cO) is a permutation of Q(B)o 2.2 Let us denote by N(A) the set of all normal series of A. Since for any automaton A., A.' 0W is a normal series, N(A) is never empty. We define a partial orders in N(A) by: 0-:3 3 iff every subautomaton of A. which occurs in a occurs also in D. A normal series which is a maximal element in N(A) with respect to y and all its subautomata are different, is called a composition series of A. 22.21 Note that every finite automaton has a composition series. While Mw, for a free monoid W for instance, has no composition series, Our aim is to prove the analogous to Jordan's, Holder's and Schreier1",s theorems for automata, For the proofs of these theorems we apply the proofs of the analogous theorems for modules (for Theorem 2.5 and Theorem 2.4, see for example Zariski and Samuel 1958) and of Schreier theorem for groups with operators and for sets (Papy 1961), 2.3 THEOREM (JORDAN): If an automaton A has a composition series of length n then every composition series of A has length n. Furthermore, every normal series of A. without repetitions can be refined to a composition series, 8

Proof: By induction on n. If n 1 then A is irreducible (i.e., it has no proper nonempty subautomaton) and therefore A - OW is its only normal series. (The case for n = 0 is utterly trivial.) Assume that the theorem is true for automata having composition series of length less than n where n > 1. Since A has a composition series, say Ca A = AO A- A. -.. An- An = W of length n, A cannot have any composition series of length less than n. We shall show that for any normal series of A without repetitions, say w: A. Bo Bi-..D Bm Bm = we have, (p)' = m < n =,(). Case 1: B1 = A1 By a, B1 has a composition series of length n-l, and by I, a normal series without repetitions of length m-l. Hence by the induction hypothesis m-l < n-1, that is m < n. Case 2: B1C A1 By C0 Al has a composition series of length n-l, and by P, a normal series without repetitions of length m; hence m < n-l and so m < n. Case 3: B1 is not included in A1 Since there are no subautomata between A. and Al we have A = Al U B1. By Lemma 1.7 we get A/A1 = (A. U B1)/A.1 - B1/(A.1./ B1). Since A/A1 is simple, so is B1/(AlO( B1) and therefore there are no subautomata between B1 and (A1 i B1). 9

Since A. has a composition series of length n-l and (A1 9 B1)C A1, every normal series without repetition of (A1 ) B1) has length at most n-2, and hence (A./) B1) has a composition series of length at most n-20 Since there are no subautomata between B1 and (A1 l B1), B1 has a composition series of length at most n-l0 By induction hypothesis we have m-lE n-l and thus again m < n. 2o3ol COROLLARY: If an automaton A has a composition series then every subautomaton of A has composition serieso Proof: Let B.A. Since A has a composition series, if A 2 Bd'W is without repetitions it has a refinement which is a composition series and so does Bo If A:-B OW has repetitions then either B = A or B = OW. 2o302 COROLLARY~ If an automaton A. has a composition series then every subautomaton B of A. occurs in a composition series of A. 2~4 THEOREM (HOLDER)~ If an automaton A has a composition series then any two composition series of A are equivalent. Proof' Let a and P (by Theorem 2e3 we know that I(a) = g(B)) be any two composition series of A; say a i A A- A.o-n A n oo -.A 9 A. = B0B>.. Bn,'Bn =... For n = 0, 1 the theorem holds trivially. Assume therefore that it holds for all automata having corposition series of length less than n where n > 1. If A1 - B;1, then we have two equivalent composition series for A1 = B1 and since A./A.1 = A/B1, we have that c~ and D are equivalento 10

If not, then A = (A1 0 B1). Since (A.1 B1) CA, Al A B1 has a composition series, say y. From y we obtain two composition series 61: A = (A1 V B1) 3 A 1Z(A1 nB1)jD...; 62: A = (A1 U B1) O B1s(Al rB1l)3>..y,. Lemma 17 implies that 61 and 62 are in fact composition series. It also implies that they are equivalent. Now 51 and a are equivalent because of the occurrence of A1, and b2 and 5 are equivalent because of B1. Hence a and 5 are equivalent. 2.4.1 COROLLARY: Let B be a subautomaton of A and let A have a composition series. Denote by Q(C) the set of the quotients appearing with their repetitions in Q(y) for any composition series y of C. Then Q(A) = Q(B) Q(A/B). 2.5 Thus, we can define for any automaton A, its length (A) to be Co if A does not have any composition series; otherwise 2(A) is defined to be the length of any composition series of Ao In particular i(OW) = 0 and 2(OW) = 1. 2.6 THEOREM: If B is a subautomaton of A then 1 + (A) =- (B) + 2(A/B) Proof: Let: B = B0~BD be Bmi Bm = 0W be any normal series of B without repetitions. By Corollary 1.6.2, A/B has a normal series without repetitions of the form 11

7: A /B = CO/B Ci/B... C Cn_-/B = OW 0 W where A = CO= C1. Cn,_ = B W is a normal series without repetitions. Hence we get a normal series of A without repetitions: C C C1 S... ZCn_2:Cn l:7B1 o... Bm 1 B m = W having length m + n - 1. If either i(B) or 2(A/B) is infinite then either m or n (resp.) can be made arbitrarily large and so 2(A) = Oc, On the other hand, if both 2(B) and 2(A/B) are finite, we can assume that 3 and y are composition series for B and A/B (resp.). The assumption on y that it ends with B/B is possible because of Corollary 2.3.2. Hence, by Lemma 1.8, a is a composition series for A of length equal to i(B) + 2(A/B) - 1 = B0) + -(7) - 1 2.6.1 COROLLARY: If A1 and A.2 are subautomata of A then 2(A1) + 2(A2) = 2(A._i A2) + 2(A1 i A,) Proof: Immediate by Lemma 1.7v 2,6.2 COROLLARY: 2(A.1 0 A2) - 2(A1) I+ (A 2) 297 We turn now to prove directly the analogous theorem to Schreier's. Following the scheme of proof of Papy (Papy 1961) we prove first the "four automata lemma"; i.e., the counterpart of Zassenhaus theorem. In fact, this way of proof shows that the composition theorems for automata are much closer to these of sets than to these of groups or modules. 12

2.8 LEMMA. (The four automata lemma): Let A. B, C and D be automata such that B A and D C. Then (A. l D UB) (A. \C L)B), (C B D) C (cfl A.U D), and (A n B)/(AD L B) (Cfn A UD)/(C n BUD) REMARK: Our assumptions permit us to apply the modular law (1.3.2) and to save brackets. Proof: S(A D B) = SA ( SD J SB S(AnCUB) = SA nSc B; but SD ~ SC, hence (SD ) SB)'- (SC U SB) and SA ) (SDISB) - S^ f (Sc U S) B Similarly we have (C D B tU D) -(C cf A. ( D). Now, S(An c B)/(A n DU B) (sA C u B) s(A D ( B)() {D'B cn A D)/(C 0 B D)) (C( A. U D) S (c BU D)) 2 But S(An c U B) (A n D UB) = (SAf) S USB) - (SA SDUSB) and S(c A. U D) S(C n BUD) = (Sc "SAu S) - (SC) S SD) Hence, by the appropriate theorem on sets (cf. Papy 1961) we get S(A C VB) - S(A ( D B) = S(c/' A U D) S(C fB tB). 15

Thus by Lemma 1.6 we have established the isomorphism which is again a single point extension of an identity function. 2.9 As in other domains where Schreier's theorem holds, it is derived directly from the appropriate version of Zassenhaus' theorem. (See for example, Papy 1961). This is done by means of the mutual refinement of normal series and we leave the details of the proof to the reader. 2.9.1 THEOREM (SCHREIER): Any two normal series of an automaton A have equivalent refinements. 3. DISCUSSION 3.1 Parallel to commutative algebra, we find that an automaton has a composition series iff it satisfies both maximum and minimum conditions on its chains of subautomata. Hence, in particular, finite automata always have compositions series. 3.2 The basis for the proof of the composition series theorems seems to rely quite heavily on the set theoretic properties of the set of states of the subautomata. Thus, the impression that one gets naturally is that our theorems are related to the trivial composition series theorems for sets. In the rest of the paper we shall apply a well known construction and show to what extent the composition series have any relevance to the structure of automata (i.e., to the structure of the systems defined in 1.1). This construction will provide in fact an alternative proof for our previous theorems and also some insight into their meaning and significance. 14

3.) Let A be an automaton. We define the binary relation, on SA as fo lows: s1 N s2 iffdf s2 e slW. Denote by S* the set of equivalence classes of S defined by the A A symmetric part of, and partially ordered by - itself. That is, sl and s2 belong to the same block in S* (in symbols, [si]=[s2]) iff s1 a s2 and s2 sl; A block [si] in S* precedes [s2] (in symbols, [sl] - [s2]) iff S1 S2. 3.4 We can regard S* as nondeterministic automaton whose operation is [s]-W -=af ([s,'W]: sl e [s]). 3~5 For our needs here we do not use all the information given in St. Thus we define D(A) to be a directed graph defined by: 3.5o1 The nodes of D(A) are the blocks of SA; 3.5.2 The binary relation of D(A) is u as defined in S* (cf. 3.3). 3.6 In order to verify that in fact D(A) determines the structure of the composition series of A we need the following notion. We call a collection C5 of nodes of D(A) (i.e., of blocks in S-) an ideal of D(A) (i.e., of S3) iff it is closed to the right under,. That is, ) is an ideal iff [si] e f and [s1] V [s2] imply [s2] -.~ For example, St itself is an ideals We denote by 1(A) the class of all ideals of D(A.) partially ordered by set inclusion. 15

3.6ol LEMMA.: The mapping J: SUB (A) -I (A):B ([s]:s C S B is an isomorphism of the lattice SUB(A) of the subautomata of A and the lattice |(A) of the ideals in D(A)o Proof: Immediate 3~6.2 COROLLARY: Let A. and A2 be two subautomata of A, then A. is a maximal subautomaton of A2 iff J(A2) - J(A1) contains a single node of D(A)o Clearly we have now: 3~6~3 THEOREM: (i) An automaton A has a composition series iff S* is finite. ~ F~~~~~~~~~~ A (ii) If A has a composition series then 2(A) is exactly the cardinality of S2o (iii) If A has a composition series then the number of all composition series of A is exactly the number of all possible extensions of - into a complete order of S* A.~ 3~7 These results imply that the study of composition series of automata is in fact the study of the relation -3 associated with automata, 308 Every morphism A —> B of automata (cfo 1l4) determines a homomorphism D(A) D(f — D(B) defined by LD(f)]([s]) df [f(s)] (D(f) is well defined since slzs2 implies f(sl) Lf(s2)). Thus we have defined in fact a functor from the category of automata to the category of (directed graphs of) partial orderso 16

4. EXTENSIONS OF Q-AUTOMATA

I

1. DEFINITIONS 1.1 Our problem is to characterize all automata B such that for given A and C we have B/A = C. It is obvious that it is necessary that OW is a subautomaton of C. On the other hand, any occurrance of OW as a subautomaton of C presents of course a different task of extensions. 1.2 We define therefore a q-automaton to be a pair (C,so) where so is a state of the automaton C for which so.w = so for all wEW. A morphism C C C' is said to be a q-morphism of (C,so) into (C' so) iff so is the only state of C which is mapped by f on s. 1.3 Let B be any automaton, (C,so) be a q-automaton. Then, for a moro o phism B - (C,so), which is determined by the morphism B -> C, we can define Kera as the maximal subautomaton of B which is mapped under a onto so (or more precisely, onto the subautomaton of C generated by so). A morphism B > (C,so) is said to be a contraction iff apart from Kera + 0W0 a is injective. That is iff for any sl, s2 E SB - SKera, o(sl) = U(s2) implies sl = s2. It is said to be a canonical contraction iff for any s E SB - SKer, a(s) = s. 1.4 An extension sequence (from A to (C,so)) is a diagram x a E= (x,a): A B (C,so) where (i) A and B are automata, x (ii) A + B is monic, (iii) (Cso) is a q-automaton, (iv) B~(C, so) is a contraction, 19

(v) x(A) = Ker (vi) So & SB E = (x,o) is said to be a canonical extension iff A -> B is the inclusion morphism (i.e., x(s) = s for all s e SA) and a is a canonical contraction. 1.401 PROPOSITION: If A is a subautomaton of B then JA qA A - B (B/A,s*) qA (for the inclusion morphism jA and the canonical morphism B B/A) is a canonical extension. 1.5 An Ext-morphism r = E + E' is a triple r = (aoy) of morphisms for which the following diagram is commutative; E A — B - (C so) r 4 a | (a -l AI B I i I)SI) E':: A' A B' -+ (C' s) where naturally we require that y is a q-morphism. 1.5.1 Obviously the class of extension sequences and Ext-morphisms forms a category. 1.6 LEMMA: If F = (iA,,iC): E + E' is an Ext-morphism (where iA and. iC are identity morphisms) then B + B' is an isomorphism. Proof: We have to consider the following commutative diagram. 20

A / (Cso) x^ i'~ Assume first that 3(sl) = 3(s2) for some sl, s2 C SBIf both sl and s2 are in the image of x; say sl = x(t1) and s2 = x(t2) for tl, t2 E SA. Then we have x'(ti) = P(x(ti)) = ~(x(t2)) = x'(t2), which implies tl = t2 let alone sl = s2. If both si and s2 are outside of the image of x then we have C(S1) = ao'((sl)) = a'((S2)) = (S2)-. But a is a contraction and therefore we derive si = s2. If sl E Sx(A) and s2 E SB - Sx(A)' then o(sl) = So and a(s2) i so. But now we have again a(s1) = C'(P(Si)) = o'((S2)) = (S2) In conclusion P(si) = P(s2) always implies sl = s2 and therefore 3 is monic. Now let s E SB. If s is in the range of x', say s = x'(t) for t e SA. Then P(x(t)) = x'(t) = s. If s is not in the range of x' then there is Sb e SB such that a(sb) = a'(s). Hence o'((sb)) = (Sb) = o'(S), but s is not in Kera' and therefore we have (sb) = s. Thus f is epic. 21

1.6.1 REMARK: Note that if r = (iA,mic): E - E' is an Ext-morphism then B is the unique morphism for which (iA,,iC): E - E' is an Ext-morphism. This follows from Lemma 1.6 and the immediate fact that if (iA,,ic) is an Ext-morphism of E into itself it is the identity Ext-morphism. 1.6.2 We define two extension sequences E and E' to be congruent (in symbols, E - E') iff there is an Ext-morphism r = (iA,b,ic): E + E'. By Lemma 1.5 we have that the congruence of extension sequences is an equivalence relation. 1.7 Let A be an automaton and (C,so) a q-automaton. We denote by Ext(C,so,A) the set of all congruence classes of the extension sequences from A to (C,so). 2. CLASSICAL RESULTS 2.1 Before we characterize Ext(Cso,A) by means of the particular properties of extensions of automata we shall give several examples that show how close Ext(C,soA) is to the classical notion of extension in commutative algebra. In fact some of the proofs of the following "classical" properties, follow their seniors closely (cf. MacLane 1963). 2.2 LEMMA: If x r E: A + B + (C,s0) is an extension sequence and if (C ss s s(Ce) is a q-morphism, then there exists an extension sequence E: A -' 22 ( 22

and an Ext-morphism r = (iA^,,Y): E7 E where (E7,P) is unique up to a congruence of E7. Proof: Let B' be the subautomaton of B x C' defined by SB = ((Sb, ): r(Sb) = - (S ) SBt is a closed set of states in B x C' since (sbsC ). = (Sb*W, sc,'W), and o(sb'w) = o(sb) 7( = 7(scw = (s w) For the completion of the following diagram t T r, 1-'? I Y - i z ~ x + a E:A -B -> (C, So), define a' SB + SC?: (Sbsc?) + Sct x: SA SB: s + (x(s),so) and 5: SB, + SB " (bSc,') +b; then obviously we have uc = ya' and x'- = x. We have to check whether the following sequence is in fact an extension sequence. 23

A B' - (Cl',s) Now, o'(sb sc, ) = s iff so, s; but (sb,s )ESBr iff o(sb) - y(so) = S Hence (sbsc') is in Kera' iff sb isn x(A) and sC = SoI Let'(sbsc,) be a state of B' which is not in Ker&'; in particular we have SC,' so. From o(Sb) = 7'(sc) it follows that o(sb) # so, since y is a q-morphism. Hence, there is a unique sb E SB such that (sb) = (s, ) and therefore a' is a contraction from B' to (C', s) with Kera' x'(A). xI Obviously A — ~ B' is monic since x'(si) = x'(s2) implies in particular x(sl) = x(s2). Therefore Ey is an extension sequence. The uniqueness of (E7y,) will follow from the next lemma. 2.3 LEMMA (The Couniversal Property of E,): For any Ext-morphism rl = (ll,7y): E1 +E there is a unique factorization (up to a congruence) of rl through ry E: + E, of the form: 7(iA,) ( (),',ic) P. = (E, M-Y) E) (E1 EB) Proof: We have the following diagram for ri: E1: A1 -- B1 (C' so) l I + B 7( s x cr E: A B - (C, So) and we want to stretch it to become the following commutative diagram which includes the diagram of Fr: 24

Fr, 5i - EY: A ~'- (C!S o) L i x i a E: A - B -- (C, s). The only way to guarantee that 31 = (3' and that the above diagram is commutative is to define: ~,' sB +SB Sb + (1(Sb ), (Sb )). 2.3.1 REMARK: The uniqueness of Ey now follows immediately. For assume that for some r = (iA,3',y) we have: E' + E then by Lemma 2.3, r has the factorizat ion (iA'" Y) = (iAb,7 )(iA, 1C' i) with a factor (iA,',iC ): E' - Ey which is a congruence of Ey. Similarly we can show that if E1 - E2 then (Ely) - (E2y). 2.3.2 Hence, q-morphisms into (C,sO) induce Ext-morphisms into Ext(C,soA), and with this Ext (C,so,A), varying on (C,so), becomes a controvariant functor from the category of q-automata and q-morphisms into the category of extensions of automata (being the congruence classes of extension sequences) and Ext-morphisms. 2.4 LEMMA: For any extension sequence x a E: A - B -+ (C,so) and any morphism A - A' there is an extension sequence 25

Xv a cE: A' -- B' — + (C,so) and an Ext-morphism ar = (ca,ic): E - aE where (dE,3) is unique up to a congruence of cE. Proof: We are concerned now with the following diagram. x o E: A -— B -(C,sO) ar 4a 3I CE A'l- Bt' - (Cso) In this case we define B + B' by a congruence relation -a in B which is induced by A + A'. Set si ~a s2 (for any si^ sz E SB) iff either they are both in x(A) = Kero and then a(x-l(sl)) = a(x -(s2)), or else, if sl = s. In order to verify that -a is a congruence of B, consider the crucial case where sl -a s2 holds because sl = x(sl) s2 = x(sI) and a(sl) = c(sa). Now for any w E W we have that both sl*w and s52w are in x(A) and a(x-(silw)) oa(x-(x(sl),w)) = (x-(x(slow))) a= o(s1.) = O(si). = - ((S2). = (x-(s2)). Thus sl -a s2 implies sl.w ~a s2.w. Hence B' df B/a is well defined together with a canonical morphism B + B/-. XP ~Y The definitions of A' —, B' and of B' --- (C,so) follow naturally. The verification that we have now an Ext-morphism ca = (03,iC): E + cE5, where 26

x C oE: A' - B' - (C,so), is routine. The uniqueness of (cEc) follows from the next lemma. 2.5 LEMMA (The Universal Property of cE): Any Ext-morphism l -= (CaY y l): E + E1 can be factorized uniquely through E - coE (iA, 7',Y1) (UDiC) rl = (cE ~ El) (E-~ E).)' Proof: We define B' --- B1 by: SB = (SB)/~ SBl xi(sa) if x'(s') = [sb] B'([sb]) - Yi(a'([sb])) otherwise; which is the only way to make the following diagram commutative. The Al B I (C, So) T: f (a sC) aE A' -- B' S- (C, So)'~ EI: A' — B B1 — (Cl,so) rest follows by a direct verification. 2.5.1 Again we have that cE is determined up to a congruence; and therefore, morphisms of automata induce Ext-morphisms of extensions. Now we have that 27

Ext(C,so,A), varying on A, is a covariant functor from the category of automata into the category of extensions. 2.5.2 The following proposition (cf. MacLane 1963) which is in fact a direct corollary of Lemmata 2.3 and 2.5, implies that Ext(C,so,A) is a bifunctor. 2.5.3 PROPOSITION: Let x a E: A + B + (Cso) by an extension sequence; then for any morphism a of A and any q-morphism y into (C,so) we have ((E ) - ( oE)y Proof (MacLane): We have the Ext-morphisms (iA__1.7) (a, i2,ic) Ey -E, E - oE and their composition (O,21, a1 7) E7 > OE. By the universal properties of E +- E and E B EcE applied to (oE)y - oE and to Ey + a(Ey), we get the following two factorizations of E7 + cE: Er, i) (E)y.. E7) EB -~ (0E)7 ~ ^ oE and (X,:2:121) (1 7) EBy ac(Ey) -> aE d Consider any one of them; say, Ey ~ (oE)7. The morphism B in(otD,i) duces the Ext-morphism Ey ---- ac(Ey), and therefore by the uniqueness of 28

C(E ) we infer (aE)y a (Ey). 2.5.4 The following proposition is another example of a result derived by a direct application of the universal properties of the functor Ext(C,s, A) following the classical example (cf. MacLane 1963). 2.5.5 PROPOSITION: For any Ext-morphism r = (a,, y) ~ E1 + E2 we have aE1 Esp. Proof (MacLane): By the universal property of E -+ E, F can be factorized through ar E1 + OE: r = ri (ar), rF = (iA,, 7): CE1. But Fl is a definition of F: Eay + E2 hence oEl = Eg. 2.6 We can interpret the functor Ext(C, S, A) as applied to morphisms of A as a mapping E*: Hom(A1, A) - Ext(C, so, A): o + OE defined for any E e Ext(C, s, Al). Dually, for any EeExt(C' s', A) we have a mapping E*: Homq((C' s), (C, so)) + Ext(C, so, A): 7 E; (where Homq(X, Y) denotes of course the class of all q-morphisms from X to Y). We shall be interested mainly in the "connecting" mapping E.: Hom(A1, A) + Ext(C, so, A): a c E because it gives rise to a complete characterization of Ext(C, sol A). 29

3, PROJECTIVE EXTENSIONS 3o1 A.n automaton P is said to be projective iff for any morphism P > B and f any epic A B there exists a morphism P $ A for which the following diagram is commutative. g k/' h A. - B f 3.1.1 For example the automaton MW defined by M= W SMw W1'W2 W 1W2 is projective. This follows from the fact that the homomorphic images of MW are exactly the monogenic automata and Hom(Mw, A) is in a bijective correspondence with SA. In fact, as one can easily prove, the free automata are exactly the direct multiples of MW, and every free automaton is projective. 3.2 LEMMA: If P is projective and E1: P1 5 P q (C', s) is an extension sequence, then for any extension sequence x a E: A + B + (C, SO) and any q-morphism (C', s) - (C, so) there exists an Ext-morphism r = (a, A, Y): E1 - E Proof: By the projectivity of P we have a morphism P t B1 for which the following diagram is commutative. 50

p__- (I So) C (, s0) 0 Since q and o are contractions, the commutativity of the previous diagram implies also 3(Kerq) =Kero. Hence, since A x B is monic, there exists a morphism P1 A such that the following diagram is commutative. El: PI P,C s,r 0I >Po7s )f7 x { E ^ X. x \ a > E A B ~ (Cs ) Hence r = (ca,,7): E E 3.2.1 COROLLARY: Let i q E1: P1 - P + (Cso) be any extension sequence where P is projective; then for any EeExt(C, Sy A) there exists an ceHom(P1, A) such that caE = E. Proof: Set y = iC and get ~/\. C r - (a,, ic): E1 + E but this implies cEz =E E. A rephrasing of this Corollary, using the notation of 2.6, yields the following theorem. 1

3.2.2 THEOREM: Let E1 be an extension sequence with P projective E1: PI P - (C, So), then for any automaton A E*: Hom(Pl, A) + Ext(C, so, A) is surjective. 3.2.3 If (C, so) is a q-automaton which has a projective extension; i.e., if there exists an extension sequence of the form EI: P P (C, so) where P is projective; then, by Theorem 3.2.2 we can construct all the extensions of Ext(C, -s, A) for any automaton A. However, since not every q-automaton has a projective extension, this result is not general enough. 4. THE CHARACTERIZATION OF Ext(C, so, A) BY MEANS OF THE CONNECTING HOMOMORPHISM 4.1 In order to get a general characterization of Ext(C, so, A) we construct the following extension sequence. Denote by S x MW the automaton which has SC x W = ((s, w): seSc, wW} as its set of states and whose transition function is (s, wl)*w2 = (s, wlw2). Clearly, SC x MW is the direct sum (i.e., disjoint union) of isomorphic copies of MW indexed by the states of C. Thus SC x MW is a free automaton and in particular we have the natural morphism T C SC x MW C which is determined by 32

C: x w. sc: (s, w) s.w the transition function of C itself. The q-automaton (C, so) determines a subset of states of SC x MW: K =df ((s, w) s.w = So, which is closed under transitions. Hence it determines a subautomaton Con(C, so) of SC x MW whose set of states is K. The free extension sequence of (C, so), F(C, so), is defined to be F(C, so): Con(C, sO) + SC x MW + (qj(SC x M), so) as determined by Con(C, so) - SC x MW, where qj(SC x MW) = (SC x Mw)/Con(C, so) 4.2 The morphism S x Mw+C determines a q-morphism (qj(sc x Mw), sQ) + (C, so) in a natural manner: if s w f s then we set y(s, w) = s*w, otherwise we set Y(S') = so. This q-morphism determines an Ext-morphism r = (i, D*, y): F(C, sO) E(C, so) where E(C, so) is the canonical extension in Ext(C, so, Con(C, so)): E(C, so): Con(C, o) j (C, so)* >(C,so) S(C, so)* = KU SC- o The transition function of (C, so)* is composed of those of C and of SC x MW, 33

together with the stipulation: sw = (s, w) whenever sw = so in C. The morphism SC x MW-* -*(C, s )* is defined naturally by P*(s, w) = sw in (C, so)*. The commutativity of the following diagram F(C, so): Con(C, sO)- Sc x MW q (qj(Sc x MW), s$) r 1= Y E(C, sO): Con( s (C, sO)* *(C, s*(C o) is straightforward. 4.3 THEOREM: For any automaton A and any q-automaton (C, se), the mapping E*(C, so): Hom(Con(C, so), A) - Ext(C, so, A):' + aE(C, so) is a bijection, Proof: We define a map Con*: Hom(Con(C, so), A) - Ext(C, so, A) as follows. For any oaHom(Con(C, so), A) we obviously have a = 6as where s varies on SC with the provision that sOes'W; and as is the restriction of a to the morphism of I(s), the subautomaton of Con(C, so) whose set of states is I(s) df ((S' w): sw = os 34

Note that I(s) is isomorphic to a subautomaton of MW and that Con(C, so) = @ I(s) To summarize, we have in fact: Hom(Con(C, so), A) = Hom(I(s), A): a = (, S S S and cs = alI(s) We define Con(a) as the automaton whose set of states is S = sA- [ ) Con(a) d C SA and whose transition function is a(s, w) = 0s(s, w) if (s, w)eI(s), s.w.= svw in C if seSC and (s, w)$I(s), s w in A., otherwise Denote by Con*(a) the canonical extension sequence Con*(Uc): A Con(aO) C (C, sO) which is naturally associated with Con(ac). We leave to the reader the verification of the following statements which lead to the conclusion of the proof of the theorem. 4.3.1 Con* maps Hom(Con(C, so), A.) in a bijective manner onto the class of all canonical extension sequences A B (C, s0) of A by (C, so) with A c B, 35

4.3.2 LEMMA: For any two canonical extension sequences E1 and E2, E1 E2 holds iff E1 = E2. 4.3.3 For any OcHom(Con(C, so), A) we have the congruence cE(C, so) = Con*(a) 4.3.4 Alternatively, one can define an Ext-morphism r(a) = (a, a*, i): E(C, so) Con*(^) by defining a morphism (C, So)* o Con(a) in a very natural manner. Then, by the uniqueness of c9E(C, so) we infer 4.3.3. 36

BIBLIOGRAPHY 1. Give'on, Y., "Outline for an Algebraic Study of Event Automata," Tech. Report 05662, 06689, 03105-28-T, ORA., The University of Michigan (1964). 2. MacLane, S., Homology, Academic Press, New York, (1963). 3. Papy, Groupes, Dunod, Paris, 1961. 4. Rees, D., "On Semi-Groups," Proc. Cambridge Philos. Soc., 36, 381-400, (1940). 5. Thatcher. J. W., "Notes on Mathematical A.utomata Theory," Tech. Note 05662, 03105-26-T, ORA, The University of Michigan (1963). 6. Zariski, 0. and Samuel, P., Commutative Algebra, Van Nostrand Co., Inc., Princeton, N.J., 1962. 37

TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA IV:. The Characterization of Projective Automata

O. INTRODUCTION 0.1 Following the main problem of our first paper in this series, we want to characterize the projective objects of 4W, the category of automata (as state diagrams) with W as input. 0.2 Naturally, we follow our notation and terminology set up in our previous papers (Give'on 1964). 1

1. BASIC NOTIONS 1.1 We recall that an automaton P is projective iff for any morphism h f g p + B and any epic A + B there exists a morphism P + A for which the following diagram is commutative. g / h A ~ B 1.2 For any automaton A and any set T we define T*A to be the automaton whose set of states is T x SA = ((t, s): teT & seSA) and whose transition function is defined by (t, s).w =df (t, s.w) Obviously T-A = $ ( (t.A) and (t).A ~ A teT 1.3 It is easy to verify that for any set T, T'MW is free and projective. 2

1.4 We are trying to follow the study of projective modules as closely as possible. 1.4.1 An epic A > B is said to split iff there is a morphism B $ A for which B A B= iB g f 1.4.2 A monic B -> A is said to split iff there is a morphism A + B for which g f B + A B = iB 1.4.3 In general we say a Mnorphism f that it splits iff it is a unit in the composition algebra of the morphisms of AW. Obviously a morphism splits iff it is either a monic or an epic which splits. g f 1.4.4 A sequence A g B - A is said to be a splitting sequence of A through B iff fg = iA. Clearly in this case f is an epic and g is a monic which split. 1.5 LEMMA, An automaton P is projective iff it has a splitting sequence through some free automaton T'MW. Proof: We always have an epic Sp.MW -a P defined by Tp(S, w) = s.W Assume that P is projective then for P ~ P there exists a morphism 3

P - Sp-Mg for which the following diagram is commutative, P / Tp i SpM> P this yields a splitting sequence jp Tp P - Sp.Mw+ P of P through Sp.MW. We shall refer to this sequence as the canonical spliting sequence of P. On the other hand, assume that g f P + T MW P h e2 is a splitting sequence. Let P - B be any morphism and A-> B be an ei epic. Since T~MW is projective, there exists a morphism T.MW- A for which the following diagram is commutative. f P g -T T~MW > P e2 A > B Hence, for el = e g we have e2e1 = e2elg = hfg = h which proves that P is projective.

ol.5l REMARK: Our arguments show in fact that P1 is projective iff it has a splitting sequence through some projective automaton P2o 1.5.2 COROLLARY: Any projective automaton is a direct sum (i.e., disjoint union) of monogenic (i.e., epic images of MW) projective automata. Proof: We refer again to the canonical splitting sequence of P P SpMW p defined in the proof of Lemma 1o 5 jp Since Sp *M = e)Is.M and P —+ Sp. is monic, we have a des composition of P as a direct sum P = $Ps where s Sp = fs'eSp: jp(s')es.WJ and a family of monic morphisms.s Ps5 (s})MW defined by jp: Sp + [(s x W: s' + jp(s') s On the other hand we define a family of morphisms Tp {S}Mw P by Tp: {s} x W + Sp: (s, w) + sow o 5

Obviously, for any seSp we have: s SS s ip = ip IPP = P Tp T P P's P s = PP Pp s hence T((s.MW) = P and therefore P is monogenic. P w s s 1.5.3 COROLLARY: (The converse of Cor. 1.5.2) A direct sum of projective automata is projective. Proof: By Lemma 1.5 we have for P = UP a family of splitting sequences gs fs P - T M P s s MW s and we can assume that all the Ts are disjoint. Hence we have the splitting sequence ss s s s &P ~- (UT )M - ~ P U ss s s s s where eg and of are morphisms defined as the unions of (g ) and of (f ) ss s s s s (resp.). Thus P is projective. 1.6 Thus we have that a direct sum of automata is projective iff each summond is projective. Furthermore, an automaton is projective iff it is a direct sum of monogenic projective automata. Hence, in order to characterize the projective objects of AfW we have only to characterize the monogenic projective automata. 6

2. MONOGENIC PROJECTIVE AUTOMATA e 2.1 An automaton P is monogenic iff there exists an epic MW + P If P is projective we have a splitting sequence P M P of P through Mw. Hence, if P is a monogenic projective automaton it is isomorphic to a monogenic subautomaton of MW. 2.2 An element ueW is said to be projective iff the subautomaton M(u) of IM generated by u is projective. 2.2.1 Note that the set of states of MW(u) is the principal right ideal of W generated by u: I(u) = (u: wW). 2.3 A rephrasing of Lemma 1.5, as applied to monogenic projective automata, expressed in terms of the elements of W, yields the following proposition. 2.3.1 PROPOSITION: An element ucW is projective iff there is j(u)eW for which (i) uw1 = uw2 iff j(u)wl = j(u).w2; 7

and (ii) u = uj(u) Proof: By Lemma 1.o and by 2.1, MW(u) is projective iff there exists a splitting sequence of Mw(u) through MW: j eu Mw(u) + M(u) where MW - Mw(U) is the canonical morphism determined by eu: W - I(u): w + uw Hence, if MW(u) is projective, the morphism Mw(u) + MW is monic. That is, j(uwl) = j(uw2) iff uw1 = uw2 But j(uwi) = j(u)wi, hence (i). In addition to this, euj = iMW(u), and so u = (euoj)(u) = eu(j(u)) = uj(u) On the other hand, assume (i) and (ii) Define MW(U) M w by j I(u) - W uw j(u)w, eu by (i), j is monic. For the canonical epic MW - MW(u) we get by (ii) (euoj)(uw) = eu(j(uw)) = eu(j(u)w) = (uj(u))w = uw, 8

hence j eu MW(u)' MW > (u) is a splitting sequence and therefore Mw(u) is projective. 2.4 REMARKS: It follows immediately from Prop. 2.3.1 that if u is an idempotent of W then it is projective; set j(u) = u. However, this is not a necessary condition for u being projective. For example, if u is a left-cancellative element of W (i.e., if uw1 = uw2 always implies wl = w2), then u is projective. In fact if u is such an eu element of W, MW Mw(u) is an isomorphism. Hence in particular, if W is a group or a free monoid, or any left cancellative monoid, then the only monogenic projective automaton is MW (up to an isomorphism, of course). To be more general, if u is an element of W for which there is x in W such that u = uxu, then u is projective; set j(u) = xu. For example, if u = un for some n > 1o 2.5 From the characterization of the projective elements in W given by Prop. 2.3.1, it follows that if u is projective then j(u) is an idempotent of W: 9

uj(u) = ulw, hence j(u)j(u) = j(u) ol. This observation yields the following complete characterization of the monogenic projective automata. 2.5.1 THEOREM: A monogenic automaton is projective iff it is isomorphic to a monogenic subautomaton of MW generated by an idempotent of W. Proof: The splitting sequence J e M(u) -MW M (mu) implies that Mw(u) + j(MW(u)) is an isomorphism. But obviously j(MW(u)) = MW(j(u)) 2.5.2 REMARK: Thus, even though the class of the projective elements in W may be larger than the class of the idempotents of W, the latter class is sufficient for the characterization of the projective elements of W and of the projective monogenic automata. 2.6 The characterization of monogenic projective automata by means of splitting sequences through Mw yields Theorem 2.5.1 directly by considering the idempotents of End(Mw) as follows. An automaton P is monogenic and projective iff it has a splitting j e sequence P + M^W - P through MW. Hence, if P is monogenic and projective, 10

there exists an endomorphism MW - W which is an idempotent of End(MQ), jeje = j(ej)e = je and P is isomorphic to MW(je(lW)). From the idempotence of je follows je(lw) = je(je(lw)) = je(lw) je(w), i.eo, je(lw) is idempotent in W. On the other hand, if Mw MW is an idempotent endomorphism of M and P = MW(c(lW)), then j a' P + MW P for the inclusion morphism j and for': W -~ w(lw) W: w oC(W) W = o(w), is a splitting sequence of P through MW. The relationship between the idempotents of W and of End(MW) was established by the representation theorem for -W (Give'on 1964) since W is isomorphic to End(Mw) 11

3. THE CHARACTERIZATIONS OF MW FOR A FINITE W 3.1 In our first paper in this series (Give'on 1964) we showed that if MW can be identified (up to an isomorphism) by means of categorical predicates then /W is categorically complete. There we succeeded to characterize MW for the case where W is a unit-commutative monoid (i.e., where wlw2 = 1W always implies wlw2 = w2wl). 3.2 Our results in this paper enable us to characterize MW for the case where W is any finite monoid. Thus one can hope to apply the categorical study of AW to the theory of finite monoids. 3.2.1 THEOREM: If W is a finite monoid then an object X of 4W is isomorphic to MW iff X satisfies the following two conditions: (i) X is monogenic; (ii) for any monogenic projective automaton P there exists a monic P + X. Proof: By our previous results we know that MW satisfies these conditions. Assume now that X is an automaton which satisfies them as well. 12

Since X is monogenic there exists an epic MW - X and therefore the cardinality of SX is not larger than that of W. Since MW is projective we have a monic MW j X and therefore j is surjective and it determines an isomorphism of MW and X. 3.2.2 COROLLARY: If W is finite then AW is categorically complete. 13

BIBLIOGRAPHY Give'on, Y., "Toward a Homological Algebra of Automata, I, II & III," Tech. Reports in process, ORA, The University of Michigan (1964-1965). 14

UNIVERSITY OF MICHIGAN i 3 9015 02826 0845