THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Department Technical Report TOWARD A HOMOLOGICAL ALGEBRA OF AUTOMATA IV 5. The Characterization of Projective Automata Yehoshafat Give'on ORA Projects 03105 and 06689 under contract Vith: U.S. ARMY. RESEARCH OFFICE (DURHAM) GRANT NO. DA-ARO(D) -31-1:24: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 January 1965

ABSTRACT The problem of characterizing the projective objects of a studied category is a natural one. In our case of the category theoretic study of automata, the importance of this characterization is derived from the importance of the characterization of MW, the input monoid regarded as an automaton. The methods of homological algebra appear to be sufficient for a complete characterization of the projective automata. This characterization implies a possible application of automata theory to the theory of monoids (in analogy to the fruitful interaction between ring theory and module theory). It also provides a characterization of MW for finite input monoids, and thus the categorical-completeness theorem for AW for any finite input monoid W. iii

0. INTRODUCTION 0.1 Following the main problem of our first paper in this series, we want to characterize the projective objects of tW,) 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. p A / 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. f 1.4.1 An epic A f B is said to split iff there is a morphism B $ A for which B$A f B ~ A f B = ig. 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 Tnir-phism f that it splits iff it is a unit in the composition algebra of the morphisms of /W. 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 -~ P defined by Tp(s, w) = s.w Assume that P is projective then for P - P there exists a morphism 5

P - Sp.MW for which the following diagram is commutative, P Tp Sp-MW 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.hM is projective, there exists a morphism T.MW — A for which the following diagram is commutative. g f P -- T-MW - P et h e2 + A -- B Hence, for el = egg we have e2e1 = e 2eg = hfg = h which proves that P is projective. 4

1.5.1 REMARK: Our arguments show in fact that P1 is projective iff it has a splitting sequence through some projective automaton P2' 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 jip Tp P Sp.MW P defined in the proof of Lemma 1.5. Jp Since Sp.MW = $[(s).M and P — Sp'MW is monic, we have a des composition of P as a direct sum P = $Ps where S SPs = (seSp:jp(s')Es.W), and a family of monic morphisms Ps 4 (s5~MW defined by jp: Sp - (s) x W s' - jp(s). On the other hand we define a family of morphisms Tp (s.Mw P by Tp: Is) x W + Sp: (s, w) + sw. 5

Obviously, for any seSp we have: s= spjp = pjp S pjp s hence T((s.Mw) = P and therefore P is monogenic. P 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 = UPs a family of splitting sequences gs fs P - T *.Mw- P s s X s and we can assume that all the Ts are disjoint. Hence we have the splitting sequence $g ^Ef ss s s f -- (UT -M -- f fP S s s S S where eg and $f 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 AW 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 4 MW 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 ucW is said to be projective ifi the subautomaton MW(u) of MW 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) = (uw w: eW 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 ueW 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.5 and by 2.1, MW(u) is projective iff there exists a splitting sequence of MW(u) through MW: MeuMWu 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 uwl = 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: u j(u)w 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 > 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 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 > 1. 2.5 From the characterization of the projective elements in W given by Prop. 2.5.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) olW 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 MW)J eu MW(u)' MW MW(u) 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 + MW + P through MW. Hence, if P is monogenic and projective, 10

there exists an endomorphism MW - MW which is an idempotent of End(Mw), 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(lw) i.e., je(lw) is idempotent in W. On the other hand, if MW + MW is an idempotent endomorphism of MW and P = MW(a(lW)), then j & P + MW > P for the inclusion morphism j and for a': W -+ c(lW) W: w -+ (lw) w = (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 -AW (GiveTon 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 AW 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 JAW 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 7qW 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 3 901111111 1126 1442111 3 9015 03126 1442