T HE U N I V E R S I T Y O F M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Conmmunication Sciences Program Technical Note NORMAL MONOIDS AND FACTOR MONOIDS OF COMMUTATIVE MONOIDS Yehoshafat Give' on ORA Projects 03105 and 03662 under contract with-:.'' DEPARTPE-T OF TH ENAVY OFFICE OFV NAVAL RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON, D.C. and U. S. ARMY RESEARCH OFFICE (DURHAM) BOX CM, DUKE STATION CONTRACT NO. DA-31-124-ARO(D) -G433 DURHAM, NORTH CAROLINA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR May 1963

I_ / - ^ I..' J.!?

~1 Introduction The relevance of the theory of monoids to automata theory has recently become more and more apparent. (See, for example, Mezei [2] with respect to finite automata, and Laing and Wright [1] with respect to the theory of commutative machines.) In this paper certain properties of commutative monoids are discussed; some of them are directly relevant to the theory of commutative automata. In particular, we are interested in finitely generated monoids and in finite factor monoids. We begin with a study of three closure operations on submonoids of a commutative monoid which provides us with tools for the study of factor monoids. Next we discuss some properties of factor monoids and give certain conditions for finite factor monoids. We conclude with the proof that those closure operations lead to finitely generated monoids when they are applied on any submonoid of any finitely generated free commutative monoid. In particular this implies that any normal submonoid of any finitely generated free commutative monoid is finitely generated.

The notation used in this paper partially follows the notation used in [1] for employing regular expressions to denote commutative events. The customary notation of abelian algebras is also used. Thus B*, x*, and A* denote the commutative monoids generated by B (any non-empty set of elements of a given commutative monoid,) x (any element of a given commutative monoid) and X (the identity element of the monoid under discussion). But "+" denotes the operation of the monoid and therefore x+B* denotes the coset determined by the monoid generated by B with x as a leader. The problems discussed in this paper were suggested by J. B. Wright; I wish to thank him for prompting this research and for his continuous interest.

3 ~2 The closure operators NF, SF and HF. Let F be a fixed commutative monoid. Definition 1: Let M be a submonoid of F. We denote by NF(Cm) the set of all elements y of F for which x+y MN for some x E M. NF(M) is said to be the normal extension of M in F and NI is said to be a normal submonoid of F (in short normal) iff NF(M) = M. Lemma 1: Let M be a submonoid of F, then: (i) NF(M) is the minimal normal submonoid of F which includes M; (ii) M is normal iff x,x+y E M implies y e M for any x,y e F. Remark: For the proof of (i) we shall prove that NF is a closure operation on the submonoids of F. Proof: (1) M C N (M). Let y e M then y+X e M. Since X c M we get y C NF(M). F

4. (2) NF(M) is a submonoid of F. Let x,x c N (M), then x +y, x+y E M for some 12 F 112 Yl Y c M and therefore (x +x ) + (y + ) c M where y *y c M, which shows 1Y2 12 12 1+2 that x +x c NF(M). Since X E NF(M) we have that N F(M) is a submonoid of F. (3) NF(NF(M)) = NF(M), hence NF(M) is normal. By (1) we have that NF(M) N NF(NF(M)). Let y e NF(NF(M)), then y+x1 c NF(M) for some xl e NF(M). But y+x1 L NF(M) implies y+x +x2 M for some x2 M and x c NF(M) implies x +x3 M for some x c M. 1 2 2 1 13 3 Hence, y+(x +x +x3) c M where x +x +x c M, which shows that y c NF(M). Thus we have NF(M) = NF(N(M)). (4) Let M,M2 be submonoids of F; if MH r M then 12 1 2 NF(M ) S N (M ). Let x c N F(M ) then x+y c H' MN for some y c M G M which shows that x c N (M ). To complete the proof of (i), let M' be any normal submonoid of F which includes M, then NF(M) C N (M') = M'. This shows that NF(M) is the minimal normal submonoid of F which includes M.

The proof of (ii) follows immediately from Df. 1. Corollary: Let MI be any intermediate submonoid of F between M and N (M), (i.e., M fi MI N (M)), then F I F N CM ) = N (M). Proof: Immediate Lemma 2: Let *:F -+ F be a homomorphism of F onto a monoid F If M is a normal submonoid of F then *"'CM ) is a normal submonoid of F. In particular, the kernel of * is a normal submonoid of F. Remark: Note that from the commutativity of F it follows that F is commutative. Proof; Since * is a homomorphism it follows immediately that *1I(M ) is a submonoid of F. Let x,x+y c'1C(M ) where x,y C F, then we have *(x),O(x4y) = +(x)++(y) c M Since M is normal 1 1 we have that ~(y) e M and therefore y C *'1(M ). Hence 1M ) is a normal submonoid of F.

6. Since * s {(} is a normal submonoid of M I we get that ker * = *'1(X) = -1l(X*) is a normal submonoid of F. Lemma 3: Let M be a submonoid of F; then (x+Nb)n (y+N) J 0 iff (x+N (M))r (y+NF (M)) 0 Proof: From M a NF(M) it follows that (x+M) (y+NM) ~ 0 implies (x+NF(M)) n (y+NF(M)) # 0. On the other hand, let (x+NF(M)) (y+NF(M)) i 0 then we have x+xl = y1 yI for some xl, yi c N (M); hence x1+u = u2 and Y +v v2 for some u1,v1, u2, v C M. Therefore, x+x +u +v = x+u +v1 and x+x +u+v = y+y+v1+U == y+v2+u, which imply x+(u2+vl) = Y+(v2+u ) and this shows that (x+M)A (y+M) a 0 since u +v,v +u E NI. 21 2 2 1 2 1 Lemma 4: Let M and N be two submonoids of F. If M G N and N is normal then x c N & (x+M) n(y+M) 0 0 implies y c N. Proof: We have y+m = x+m where m,m c M Q N. Hence 2 1 N and thee2 m,y+m c N and therefore y c N. 2 2

Definition 2: Let M and M be two submonoids of F. We say that M is subtractive onto M iff for any x c M there 1 1 is y X MI such that x~y c M. We denote by SF(M) the set of all elements x c F such that x+y c M for some y c F. Lemma 5: Let M be a submonoid of F, then SF(M) is the maximal submonoid of F which is subtractive onto M. Proof: Clearly X c SF(M). Let x,y c SF(M), then we have x+x,y+y c M for some x,y e F. Hence 1 1 I 1 (x+y)+(x +y ) (x+x )+(y+y ) c M, which shows that x+y c SF(M). Therefore SF(M) is a submonoid of F. By the definition of SF(M) it follows that any subF monoid of F which is subtractive onto M is included in SF(M). Corol lary: M S(M) Proof: M itself is subtractive onto M. Lemma 6: Let M be a submonoid of F then SF(M) satisfies the following condition:

for any x,y c F: x+y C S (M) implies F x c SF(M). (In particular, x+y c M implies x ~ SF(M).) Proof: Let x+y c SF(M) then x+(y+z) c M for some z c F, hence x X SF(M). Corollary: SF(M) is a normal submonoid of F. Hence, x c SF(M) F (x+M)n (y+M) I 0 implies y c SF(M). Proof: Immediate; the result follows from Lemma 4. Lemma 7: S is a closure operation on the submonoids of F; i.e., (i) M g SF(M) and SF(M) is a submonoid of F, (ii) M1 M2 implies SF(M1) G SF(M2), (iii) SF(SF(M)) SF(M). Proof; We had (i) as a corollary to Lemma 5. The proof of (ii) is immediate by Df. 2. From (i) follows that SF(M) G SF(SF(M)); so let x c SF(SF(M)) then we have x+y C SF(M) for some y E F and so we have x+(y+z) ~ M for some y,z e F, thus x e SF(M).

9. Corollary: Let M be an intermediate submonoid of F between M and SF(M) then SF(M ) = SF(M). Proof: Immediate. Lemma 8: Let M be an intermediate submonoid of F between M and S (M). If M is normal then it is subtractive F 1 onto M. Proof: Let x c M S (M), then x+y c M for some y c SF(M). But M n M and so x,x+y c MI which implies that y E M. Hence for any x c M there is y c M such that x+y E M. Lemma 6 implies the following relation between the sets of generators for F and for SF(M) Lemma 9: Let W be a set of generators for F then W' = (w W: (w+F)In M 0) is a set of df generators for SF(M). In particular, if W is a basis of F then W' is a basis of SF(M).

10. Proof: From the definition of II' it is clear that I' c- SF(N1). Let x C SF(M) ~ F then x is a finite sum of elements of W. Let w be any element of W which is a summand of x, then we have x = w+y which implies by Lemma 6 that w c SF(lM) and therefore w c N'. Hence x is a finite sum of elements of IV' which shows that SF(M) is generated by W'. Corollary: (i) If F is free then ST.(M) is free. (ii) If F is finitely generated then SF('M) is finitely generated. Proof: Immediate. The proof of the following lemma is now obvious and so is not given here. Lemma 10: Let M, H and M be submonoids of F. 1 2 (i) M 1 M implies that if M is subtractive onto 1 2 M then it is subtractive onto M 1 2

11. (ii) M G M implies that M is subtractive onto M iff it is subtractive onto N (M). Definition 3: Let M be a submonoid of F, The submonoid spanned by M in F is denoted by tIF(M) and defined by HF(M) =df {x F: x = X V x*n N F(N) f X*) Lemma 11: Let M be a submonoid of F. II (M) is a normal F submonoid of F which includes M and is subtractive onto M and so M - N F(M) s H F(M) c SF(M) c F. Proof: Let x,y e HF (M) then we have k xk y E N (M) for for some positive integers k and k. Therefore, k k 2(x+y) = k (k x)+k(k2 y) c N F(M), hence x+y E HF (M). Since X E H (M) by definition, IHF(M) is a submonoid of F. and from the definition of HF(M) it follows directly that M! HF(M). Let x,x+y E H (M), that is k x,k 2(x+y) E NF(M) for some positive integers k and k. tlence k2(klx),klk2 (x+y) E NF(M), that is, k k x, k k x+k k y c N (M) which implies k k y c NF(M) which shows that 12 12 12 F 12 F

12. y c H (M). Thus H (M) is normal. F F Let x c 1F (M) then kx c N (N) for some positive integer k. Hience x+(k-l1) N F(M) g S SF() which implies by Lemma 6, that x E S F(M). Thus H (M) g SF(M) and so by Lemma 8, li (M) is subtractive onto M. Corollary: x t1i (M) & (x+M) n (y+M) ~ 0 implies y c IiF(M). F Proof: Immediate by Lemma 4. Remark: The relation x*> N (M) f X* can be interpreted as the "linear" dependence of x on M. This interpretation is in particular obvious in the case where F is a finitely generated free commutative monoid. In this case, F can be embedded in a linear space over the rationals, Rn (where n is the number of the free generators of F) and HFI(M) is the intersection of F with the subspace of Rn spanned by NM. Lemma 12: H is a closure operation on the submonoids of F; i.e., F I (i) N c HF(M) and HF(M) is a submonoid of F, (ii) M c M implies HF(M ) ~ HF(M),

13. (iii) HiF(HF(M)) = HF (M) Proof: From Lemma 11 we have (i). (ii) follows directly from the definition of H (M). From (i) we infer that H (M) i H F(HF(M)), so let x e H (H (M)). If x = A then x c H F(M). If x f A then x*n N (HF(M)) Ak*. By Lemma 11 we have that II F(M) is normal and therefore we have for x # A and x H (i F (M)) that x*AnH (M) i A*. This implies k x C HF (M) for some positive integer k; hence k2 k x E NF(M) for some positive integers k and k, which shows that x c HF(M). The algebraic relations among NF, HF and SF are summarized in the following Lemma, some of them are implied directly by our previous discussions. Lemma 13: The three operations NF, H and SF are commutative, F F F idempotent and satisfy the following relations: (i) IF o NF = HF (ii) SF o NF = SF o HF = SF. In other words, the semigroup of operations I generated by NF, HF,SF is a commutative idempotent monoid with a zero, in which NF is the identity element

14. and S is its zero element. Proof: All we need to show is tha, ti'; f olioi t.i.'',:: is the multiplication table for t: N I S. F F F NF N F SF F F F S S S S F F F F By Lemma 1, corollary of Lemima 6 and Lemma I l.,, have the following relations: N NF = N N o = S andt N o= iid,l F F F' F:: From the corollary of Lemmuna 7 and Lenmma 11 we get the relations: SF NF = SF o HF SF From Df. 3 and the relation N o N = N we get the F F e relation: II o N = 1tF. 1F LF F 1 By Lemma 7 and Lemma 12 we have the relations:

15. S o SF = SF and 11F O HF F i. F Hences we need to prove only that ItF, SF = SF holds. By Lemma 12 we know that SF(M) c IIF(SF(M)); so let x c 11F(SF(M)),then we have kx e NF(S (bl)) = S (M) for some positive integer k. But kx - x+(k-l)x and so F F by Lemma 6 we have that x E S (M). Ilence we have I1F oS = S FF F F'

16, ~3 Factor monoids. The method by which factor groups are defined in group theory cannot be applied directly to our context in order to get a definition of factor monoids. This is due to the fact that in our case we do not have the property that two cosets are either disjoint or identical. However, by defining a suitable equivalence relation in F we can define F/M to be the abstraction of F by that equivalence relation and the term "factor monoid" will be appropriate for F/M in the sense that factor groups become special cases of factor monoids and the theory of factor monoids will be similar to theory of factor groups. With this aim in mind we follow the suggestion of Mezei [2] for the equivalence relation pM and introduce the following definition. Definition 4: Let M be a submonoid of F, we define a binary relation P in F by xp y iff (x+M) r (y+M) 0 M Furthermore, we shall use the following notations: (i) for any equivalence relation p which is defined in F: p(x) =df {y c F: xpy }. (ii) for any submonoid H1' of F we define

17. M'/M =d M'/ = {P (x):x e Ml'. df M M Theorem 1: (Mezei) For any submonoid NI of F, pr is the minimal congruence relation p which is defined in F such that p(X) = N (M). F Proof: From the definition of OM it follows immediately that PM is symmetric and reflexive. Let x pbl y and y pM z, then we have x + m = y + m and y + m = z + m for some m, m, m, m C NI. Hence x + m + m = z + m + m and m + m, m + m c Mi which imply x p z 1 3 2 4 1 3 2 4 M Thus pM is an equivalence relation. Let x PM y and z be any element of F, then we have x + m = y + m for some m, m c M. Hience (x+z) + m = (y+z) + m which shows 1 2 1 2 1 2 that (x+z)pM(y+x). Therefore oM is a congruence relation defined in F. By Lemma 3 we have that x c pM(X) iff (x + N (M)) n NF(N) I 0. But since NF(M) is normal we have (x + NF(M))rn NF(M) f 0 iff x E N F(M). ience PM(X) = NF(M). Now let p be any congruence relation which is defined in F such that p(X) = NF(M). By Lemma 3 we have that x PM y implies

18. x + m = y + m for some m, m c N (M) = p(X). Since p is a congruence 1 2 1 2 F relation we have x + m p x and y + m p y, which together with the equality x + m * y + m imply x p y. Hence x PM y implies x p y. 1 2 Another connection among congruence relations which are defined in F, is given in the following lemma. Lemma 14: Let M and M be two submonoids of F such that 1 2 MI M and let x,y c F, then x PM y implies x PM y. 1 2 Proof: Immediate by Df. 4. Definition 5: Let M be a submonoid of F. we define a binary operation * in F/M by: OM(x) 8 PM(y) =df ~M(X+Y) Theorem 2: Let M be a submonoid of F, then: (i) <F/M, @> is a commutative monoid with p (X) as its identity element;

19. (ii) <F/M, *> is the image of <F, +> under the homomorphism r M(x) -df PM(x) whose kernel is N F(M); (iii) the maximal submonoid of <F/M, Q> which is a group is <S (M)/M, *>; F (iv) if F is a cancellative monoid (i.e., if x + z = y + z implies x = y for all x, y, z E F,) then <SF(M)/M, i> is the maximal subsemigroup of <F/M, @> which is a group. Remark: As it is usually done, we shall use the symbols 1 F/M", fSF( M)/M" and "HF(M) /M" to denote the sets of the equivalence classes and the algebraic systems consisting of these sets and the operation (. Proof: Since pM is a congruence relation we get that x PM x and y p y imply (x + ) P) (x+y) and I M M M 1 therefore $ is well defined. (i) Clearly F/M is a commutative semigroup, and PM(X) Q 0M(A) = M(X) holds for any x E F since 0M is a congruence relation. Hence F/MN is a commutative monoid with PM1(A) as its identity element. (ii) Immediate.

20. (iii) pM(x) is a unit in F/M iff there is y C F such that pM(x+y) = PMO(X). Hence, by Lemma 6 and Lemma 11, pM(x) is a unit in F/M iff x c S F(M). Since S (M)/M forms a group we get that it is the F F maximal submonoid of F/M which is a group. (iv) We have to show that in the case where F is cancellative, PM(x) + PM(u) * PM(x) implies p (u) * PM(X). From (x+u) p x follows x + u + ml a x + m (for some m, m E M), hence, by the law of concellation we get u + m = m which shows that pM(u) = pM(X). We can strengthen the result stated in Theorem 2 (iii) as follows: Lemma 15: Let M and M be submonoids of F, then M /M is a submonoid of F/M which is a group iff MI is subtractive onto N F(M). Proof: If M /M is a group then for any x c M there is y C M such that p (x+y) = (PM). Thus, for any x E M1 there is y c Mt such that x + y E PM(C) = N (). ilence is subtractive onto NF(M). If M is subtractive onto NF(M) then for any x E M there is y c M such that x + y c NF(M). Hience for any a c M /FM there is 1 1

21. b e M /M1 such that a W b = pM(A) and since M1 /M! is a commutative monoid, this 1 1 implies that -1 /M is a group. Corollary: If M c NM then M1 /M is a group iff M is substractive 1 1 1 onto M. Proof: Immediate by Lemma 10 (ii) Most of the expected connections between homomorphisms of monoids, factor monoids, congruence relations and normal submonoids can be established similarly to the corresponding results of group theory. Theorem 3: Let F and F be commutative monoids and let 1 f: F be a homomorphism of F onto F (i) Kf, the kernel of f is a normal submonoid of F. (ii) The relation pf determined in F by f: Xpfy > f(x) = f(y) df is a congruence relation and pf(X) = Kf (iii) F is unit-free (i.e., u + v = X implies u = X for all u, v c t-,) iff SF(Kf) = Kf. P'roof: (i) See Lemma 2.

22. (ii) Immediate. (iii) Let x + y e Kf then in F we have f(x) + f(y) = Hlence, if F1 is unit-free then x + y E Kf implies x E Kf which shows that SF (Kf) = Kf. On the other hand if we have in F u + v = X then u = f(x) 1 and v = f(y) for some x, y c F and f(x+y) = f(x) + f(y) = u + v = A; i.e., x + y E Kf. Hence if SF(Kf) = Kf then we have x E Kf and therefore u - f(x) = A and thus F is unit-free. Theorem 4: Let F and F be commutative monoids and let f: F + F 1 1 be a homomorphism of F onto F. There exists a unique homomorphism 4:F/KF + F such that the following diagram is commutative, F F r F/Kf that is, * o rK=f (where rKf(X) = P (x)). Moreover,4 is onto and it has Kf df Kf a trivial kernel, namely K = {Kf }. owever, is an isomorphism of F/f onto F iff p = p 1 Uf Kf

23. l'roof: Clearly, we defille 0 by *(pKf(x)) =df f(x). biy Theorem 1 and according to Tlheorem 3(i), we thave that PK is the minimal congruence relation p which is defined in F such that Kf p(X) = Kf. By Theorem 3(ii) we have thatPf is a congruence relation wlhich is defined in F such that pf(X) = if. ence imlies which shows that is well defined. It is obvious that e is the only mapping from F/Kf to [:1 which satisfies the relation 9orK f. From the fact that rKf and f are both homomorphismls of F f and f is onto, and from the relation Qorh = f it follows that 9 is a humomorphism of F/Kf onto F. Note that PKf(x) c K~ iff f(x) = A in F1, i.e., iff x c Kf, f i.e., iff pKf(x) = Kf ilence, K = {K } Nrow, if pf = K and {(p (x)) = ~(p (y)), then f f Kf f(x) = f(y) and therefore pf(X) = pK (x) = p (y) = pf(Y). ience Pf = p implies that ~ is an isonmorpliism of F/Kf onto F1. On the other hand, if ~ is an

24. isomorphism then f(x) (P= (X)) (pK (y)) = f(y) implies p (x) = p (>) f f ff. that is, that pf implies oK. Since always pK imiplics pf, we get that if Q is an isomorphism then pf = K f We end this section with a discussion on certain conditions for F/M to be finite. Lemmua 16: Let M be a submonoid of F. If F is cancellative and SF(M) $ F then F/Ml is infinite (and so F is infinite too). Proof: Let x c F and let k > k, be two distinct non-negative integers. Assume that p i(ktx) = pN(k2x), then k x + m = k2 x + m2 for sone mI, mi2 e NM. lHence k x + (k -k2)x + m = k2x + m which by cancellation implies (k k2)x + E bl. Since k > k2 we get k -k2 > I and so we have x + ((kl-k2-l)x + ml) E M which shows that x E SF(M). Hlence if x j SF(0I) then p l(klX) Z pN(k2x) for any distinct non-negative integers kl, k2, and tlius F/: is infinite.

25. Lemma 17: Let F be cancellative and 1 be a submonoid of F. If x c F but x j llF(M,) then p0l(klX) = %b(k2x) implies 1kl-k2 x = X. In particular, if kl f k2 and yet Pl(k 1x) = pl(k2x), (where x c F but x lHiFO(M), ) then x is a unit of F (i.e., thlere is y E 1: such that x + y = A ). I'roof: As in the proof of Lemma 16 we get that Ikl-k21x c (!I). Thus x II F(Ml) implies kl-k2Ix = A. Corollary: Let F be cancellative and unit-free and let H! be a submonoid of F. If 11F (.I) ~ F then F/il is infinite. Remark: Note that since fF(MII)' S F(i) - F holds, IiF(NI) = F implies SF(M) = F. Lemma 18: Let F be cancellative and unit-free, HI be a submonoid of F and w c F; then w*n NF(N) is a norrmal subnonoid of F generated by a unique element. Proof: Let x, x + y e w* for x, y E F, then x = kwl and x + y = k2W for some non-negative integers kl, k2.

26. If k2 > k then let k= + k and we have k w + kw = k w + v and so by 2 2 1 1 cancellation we get y = kw c w*. If k2 < kl then let kl = k2 + k and we have x + y + kw = x and so by cancellation we get y + kw = A, I'ut F is unit-free and therefore we have y = XA w*. Thus w* is a normal submonoid of F. Ilence w* n NhF(Ml) as an intersection of normal submonoids of F is a normal submonoid of F too. If w*\ NF:(M) = A* then A is the generator of w*rlJCF(l). If w*r NF(M) $ X* then let k0 be the minimal positive integer k such that kw E (w*INF( M)). Clearly (k w)* c (w*A NF(M)) and we shall show that (kow)* = (w*' NF(M)). Let kw E (w*c NF(MN)) and let k = pk0 + r where p,r are non-negative integers such that 0 - r < kO. Then we have kw = p(kow) + rw and kw, p)(k0w) E (w*n NF(M)). But w*nNF (M) is normal and therefore rw E (w*1 N F(C1)); hence, by the choice of k0 it follows that r = 0 and kw = p(kow) E (k w)* Thus w*rn NF(lM) = (k w)*. As for the uniqueness of the generator of w*c NF(M) we shall show that x* = x implies x =x2. From x =x* follows that x1 k2x2 and x klx f 2 2 1 12 2 1 for some positive integers k,, k2. 1Ience x, = 1kkx and x = x + (k1k -l)x1

27. which by cancellation implies (klk2-l)x1 = X and this by thlc fact that F is unit-free, implies k2 1 and thus x = x Definition 6: Let F be cancellative and unit-free, and MNI be a subnonoid of F. For any set B = {..wi..} of generators for ilF(G1) we associate the set B = {...Ei....}where = kiwi, for any i, is the generator of w n NF (1). lie denote by [B1] the set of all elements of 11F(M1) of the form x = Iaiwi where for any i:0 < a. < k (and a 0 only for a i 1i. (anda finite set of values for i). Lemmla 19: Let M be a submnonoid of F where F is cancellative and unit-free, and let 13 be a set of generators for IlF(M). Then: (i) BM is a set of elements of NF (I), (ii) for any x E HF(M!) there is y E [BAl] such that x + B1 c ) + B*,

28. (iii) (X + i,*) n (X2 + and xl E N(1) imply ~. 2 I) # ~ and 1 ) iF x E N (M1). 2 [F I'roof: From the definition of i1 it follows directly that iB is a set of elements of N F(). Hlence 1'* G N (!) and this implies (iii). Let x c llF(M) then x = aiwi. For any i there are F 1 1 non-negative integers bi and ci such that a. b k + c. and 0 s c. < k i so x = lbi.i + ci.w. Let m = b.c.i and y = ci. then x E i*, E [1] and x = y + m. ilence x + B* c + 13 Corollary: (i) [B3 ] u B1 is a set of,enerators for iIF(M). (iii) F() = { + t y E [B}. iii) ([Bn F()) U BH is a set of generators for NF(ti). (iv) N (H1) = y +L;': ([l!] c r )) In order to apply these results to factor monoids we leed the following lemma.

29. Lemrna 20: Let 11 and M2 be subrnonoids of F such that 21 I2. if F/,I1 is finite then F/,l2 and t 2/\! are finite too (hence, NiF(H12)/All is also finite.) I'roof: Let F/l1 = {PM(X ) P(I (x))}'. Iy Lemma 14 we have that for any x e F: p (x) c Pi (x) ~1 2 iience F = P\1 (xi) and therefore I/''2 contains at i.:ost k clel;:ents. i=l 2 Let pl(x) be an element of H12/11 then P l() c PF (x) E F/M!1. Let p (x) and PI(Y) be any elements of 12/1 which are included in p l (z) for some z e F, then xpM y and therefore p l(x) = P1(y)' Hlence M12/M11 contains at most the same number of elements as F/M 2 By taking M2 = N F(M2) we get that NF(M2)/N1l is finite Theorem 5: Let F be cancellative and unit-free and N1 be a submonoid of F. If Iif (N) is finitely generated then NF(M) is finitely generated and IIF(NI)/M is finite. Proof: Let B be a finite set of generators for HIF(bI), then clearly B1 and [1 ] are finite. From the corollary of Lemma 19 it follows that NF(H) is generated by a subset of [B ] u B and so it is finitely generated. From the same corollary follows MI N

30. that HIF(M)/B* is finite, but B* c N F(M) and so by Lemma 20 we have that F M NI F IHF(M)/NF(N!) is finite but I1F(M1)/NF(M) = HF(M)/NI and so HF(M)/NM is finite. Combining Theorem 5 with the corollary of Lemma 17 we get a necessary and sufficient condition for F/M to be finite in the case where F is finitely generated,cancellative and unit-free, e.g., in the case where F is a finitely generated free commutative monoid. Theorem 6: Let F be a finitely generated cancellative and unit-free commutative monoid and let M be a submonoid of F then F/M is finite iff IHF(M) = F.

31. ~4 Normal submonoids of F n Let F be the free commutative monoid generated by E = (el,..., e }. The special case of the finitely generated submonoids n of Fn is of importance to the study of commutative events since these are the submonoids of Fn which are denoted by regular expressions over E as an alphabet. For a detailed discussion on this connection the reader is referred to [1]. Lemma 21: Let M be a submonoid of F. There is a finitely n n Proof: Let Rn be the n-dimensional vector-space over the rationals; then, as one can easily verify, HF (M) = Fnn V(M) where V(M) is the sub-vector-space spanned by M and clearly n F is the first orthant of Rn. n From linear algebra we know that for any sub-vector-space V of Rn which has a basis in the first orthant of Rn, one can find such a basis {vl,..., vk} with the additional property that v is a vector of V with non-negative components only iff v = Z r.vi where for all 1 - i s k: r. O. i= 1 1

32. Since M c F, V(M) has such a basis in the first orthant of Rn say (vl,...,Vk). For any vi in this basis there is positive integer pi such that pivi c F and therefore pivi E H1F (M). but this implies that piqivi c NF (M) for some positive integer qi. So let wi = kivi be the first non-zero point on the line determined by vi which is an element of NF (M). Since {vi, *.., Vk? n is an independent set of vectors in Rn we get that W = (wl,..., Wk) generates a free submonoid N of NF(M). Let x, x+y e N for some y e Fn then clearly y E V(M) and k k k therefore y c HF (M). So let x = E a.w. y r.v. and x + y = i b.w. n i=li=l i=l then we have ri = (biai)ki 1 O for all 1 < i 6 k which shows that y e N and therefore N is normal. From V((M) = V(N) follows V(M) n Fn = V(N) n Fn that is, IF (mI) = iF (N). n n Following some of the ideas which were discussed in the last part of the previous section we define:

33. Definition 7: Let N be a normal free submonoid of Fn generated by the basis W = {w1,.., wk}. a: We denote by [W]i1 the set of all elements x of k F for which in Rn we have x = Z r.w. where for all 1 - i - k: ri is n i= 1 l rational and 0 -= r. < 1. 1 b: We define a binary operation <+> in the first orthant of V(N) with regard to W: k k k x = C riwi and y = s.iwi imply x <+> y =df (max(r,s ))w. i ~ d i=l df i=l Certain properties of <+> are summarized in the following lemma; the proof is straightforward and will not be given. Lemma 22: (i) <+> is associative, commutative and idempotent. (ii) x,y c [W] iff x <+> y E [W] l Similarly to Lemma 19 we have the following theorem which establishes the relation between N and 1IF (N) in more detail. n

34. Theorem 7: Let N be a normal free submonoid of F generated _ -- n by the basis W and let I1 = HIF (N). n Then: (i) [W] is a finite set of elements of Ht, (ii) for any x e il there is y e [IV] such that x + Nc y + N (iii) (x+N)n (y+N) f 0 (i.e., xpNy,) for x,y ~ ii implies: (1) (x+N) n (y+N) = (x <+> y) + N, (2) x, y, x <+> y E pN(X) (3) if x, y E [W]} then x = y. Proof: (i) From the definition of [W] it follows that if x c [W]H then px e N for a suitable positive integer p and since x E Fn it follows that x E ii. Clearly [li]l is finite. Let W - {wl,..., wi}. From the definition of 1F (see section k 1, Df. 3) it follows that in our case, for x E F, x M1 iff x = ~ r.w where nfr ali=l 1 1 for all 1 - i - k: ri is a non-negative rational.

35. k (ii) Let x E 11 then we have x =- r.w. for i=l 1 1 non-negative rationals ri. For any 1 A i < k let ai be a non-negative integer and si be a non-negative rational such that ri = ai + s. and 0 = s.< 1; and so we have k k x= a.w. + E s w. i=l 1 1 i=l k k Let w = E a.w.and y = gsiwi,then we have w c N and x = w + y. From i=1 i=l x, w c F follows that y c Fn (in other words, Fn is a normal submonoid of the first orthant of Rn which is a commutative monoid) and so y e [W]1I and x + N c y + N. k k k (iii) Let x = E r.w., Y =E siwi and z = Z t w E i=l i=l i=l (x+N) f(y+N) for non-negative rationals ri, si and ti. lience we have k k k k k z = L tiwi = riwi + E aiwi = siw + bi.w. i=l- i=l i=l 1 1i=1 i=l or k k z = E (r +a.)w - (si+bi)w i=l i=l for non-negative integers ai and bi. Since W is a linear basis of V(N) we get ti = ri + ai = Si + bi for all 1 s i 5 k which implies t. = max(ri,s.) + min(abi) 1i i i i and a. -b. = Si-'ifor all 1 - i - k

36. k Let w - ~ (min(ai,bi))wi then clearly w c N and we ir-1 have z = (x <+> y) + w which implies (x + N)n (y + N) Q (x <+> y) + N On the other hand we have: k x <+> y r= r r.w, (si-r)w x + ( (ai -b)w i=l 1 sAr. a.b and k x <+> y = Z s w + 2 (ri-si)wi = y + Z (bia8i)wi i=l i i risi1 bi 1ai Hence x <+> y c (x + N)n (y + N) and this concludes the proof of (iii),(1). Furthermore, the last equalities show that (x <+> y)oN x and (x <+> Y)PN Y and since we assume xPNY we have proved (iii), (2). The same equalities yield x <+> y = x + ~ (si-ri)wi = y + Z (r -s )wi s r. r.s. i and so x,y e [W]H implies 0 = ]ri-siI < 1 for all 1 i i - k and yet Iri-si.wi c N which is possible only ifri-si = and therefore x = y. Corollary: (i) [W]iUo W is a set of generators for tI and therefore H is finitely generated.

37. (ii) 11/N = fy + N: y c [N] } and so 11/N is finite. Now, by Lemma 21 and Theorem 5, Theorem 7 yields the following result: Theorem 8: For any submonoid M of Fn, if M is normal then it is finitely generated. In particular M is a finite union of disjoint cosets of a normal free submonoid of M. Proof: By Lemma 21 there is a normal free submonoid N of M such that HF (M) = HF (N). By Theorem 7 we get that 11F (M) is finitely n n n generated and so by Theorem 5 we get that NF (M) = M is finitely generated. n From the relations N c M I HF (M) = 1iF (N) it follows n n that x E M and xpNY imply y E NF (M) = M. Hence we get MI = U {y + N: y E [IV] AlNi n i and so by Theorem 7 we get that M is a finite union of disjoint cosets of N. Thus Theorem 8, the corollary of Theorem 7 and Lemma 9 show us that the operators NF, HF and SF have in their range only finitely generated n n n submonoids of Fn. This is implied directly from Theorem 8 "alone" since IHF n and S have in their range only normal submonoids of F. F n * * *

38, References [1] R. Laing and J. B. Wright, "Commutative Machines," Technical Note, The University of Michigan (ORA), December 1962. [2] J. Mezei, "Structure of Monoids with Applications to Automata," Technical Report, IBM Corporation

DISTRIBUTION LIST (One copy unless otherwise noted) Assistant Secretary of Defense Bureau of Ships for Research and Engineering 2 Department of the Navy Information Office Library Branch Washington 25, D. C. Pentagon Building Attn: Code 607A, NTDS Washington' 25, D.C. Bureau of Naval Weapons Armed Services Technical Department of the Navy Information Agency 10 Washington 25, D.C. Arlington Hall Station Attn: RAAV, Avionics Division Arlington 12, Virginia Bureau of Ships Chief of Naval Research 2 Department of the Navy Department of the Navy Washington 25, D.C. Washington 25, D.C. Attn: Communications Br., Code 686 Attn: Code 437, Infor. Syst. Br. Naval Ordnance Laboratory National Security Agency White Oaks Fort George G. Meade, Maryland Silver Spring 19, Maryland Attn: R-4, Howard Campaigne Attn: Technical Library Director, Naval Research Labs. 6 Massachusetts Institute of Technology Tech. Infor. Officer, Code 2000 Research Laboratory of Electronics Washington 25, D.C. Cambridge, Massachusetts Attn: Professor W. McCulloch Commanding Officer 10 Office of Naval Research David Taylor Model Basin Navy No. 100, Fleet Post Office Washington 7, D.C. New York, New York Attn: Technical Library Commanding Officer, ONR Br. Office Naval Electronics Laboratory 346 Broadway San Diego 52, California New York 13, New York Attn: Technical Library Commanding Officer, ONR Br. Office University of Illinois 495 Summer Street Control Systems Laboratory Boston 10, Massachusetts Urbana, Illinois Attn: D. Alpert Chief of Naval Operations OP-07T-12 University of Illinois Navy Department Digital Computer Laboratory Washington 25, D.C. Urbana, Illinois Attn: Dr. J. E. Robertson

Technical Information Officer Massachusetts Inst. of Technology U. S. Army Signal R&D Laboratory Cambridge, Massachusetts Fort Monmouth, New Jersey Attn: D. W. Baumann, Dynamic Attn: Data Equipment Branch Analysis and Control Lab. U. S. Naval Weapons Laboratory Burroughs Corporation Dahlgren, Virginia Research Center Attn: Head, Computation Division Paoli, Pennsylvania G. H. Gleissner Attn: R. A. Tracey George Washington University National Bureau of Standards Washington, D.C. Data Processing Systems Division Attn: Prof. N. Grisamore Room 239, Bldg. 10, Attn: A. K. Smilow Washington 25, D. C. Aberdeen Proving Ground, BRL Aberdeen Proving Ground, Maryland Lockheed Missiles and Space Company Attn: J. H. Giese, Chief Comput. Lab. 3251 Hanover Street Palo Alto, California Office of Naval Research Attn: W. F. Main Resident Representative The University of Michigan The University of Michigan Ann Arbor, Michigan Ann Arbor, Michigan Attn: Professor A. W. Burks, Dept. of Philosophy Commanding Officer ONR, Branch Office Census Bureau John Crerar Library Bldg. Washington 25, D.C. 86 East Randolph Street Attn: Office of Assistant Director Chicago 1, Illinois for Statistical Services, Mr. J. L. McPherson Commanding Officer ONR, Branch Office National Science Foundation 1030 E. Green Street Program Dir. for Documentation Res. Pasadena, California Washington 25, D.C. Attn: Helen L. Brownson Commanding Officer ONR, Branch Office University of California 1000 Geary Street Los Angeles 24, California San Francisco 9, California Attn: Department of Engineering, Professor Gerald Estrin National Bureau of Standards Washington 25, D.C. Columbia University Attn: Mr. R. D. Elbourn New York 27, New York Attn: Department of Physics, Naval Ordnance Laboratory Professor L. Brillouin Corona, California Attn: H. H. Weider

University of Illinois The RAND Corp. Champaign Urbana, Illinois 1700 Main St. Attn: John R. Pasta Santa Monica, California Attn: Numerical Analysis Dept. Naval Research Laboratory Willis H. Ware Washington 25, D.C. Attn: Security Systems General Electric Research Laboratory Code 5266, Mr. G. Abraham P. O. Box 1088 Schenectady, New York Diamond Ordnance Fuze Laboratory Attn: Information Studies Section Connecticut Ave. & Van Ness St. R. L. Shuey, Manager Washington 25, D.C. Attn: ORDTL-012, E. W. Channel Mr. Sidney Kaplan 1814 Glen Park Ave. Harvard University Silver Spring, Maryland Cambridge, Massachusetts Attn: School of Applied Science University of Pennsylvania Dean Harvey Brook Institute of Co-operative Research Philadelphia, Pennsylvania The University of Chicago Attn: Dr. John O'Conner Institute for Computer Research Chicago 37, Illinois Stanford Research Institute Attn: Mr. Nicholas C. Metropolis Menlo Park, California Attn: Dr. Charles Rosen Wright Air Development Division Applied Physics Laboratory Electronic Technology Laboratory Wright-Patterson AFB, Ohio Northeastern University Attn: Lt. Col. L.M. Butsch, Jr. 360 Huntington Ave. ASRUEB Boston, Massachusetts Attn: Prof. L. O. Dolansky Laboratory for Electronics, Inc. 1079 Commonwealth Ave. New York University Boston 15, Massachusetts New York, New York Attn: Dr. H. Fuller Attn: Dr. J. H. Mulligan, Jr. Chairman of E. E. Dept. Stanford Research Institute Computer Laboratory Marquardt Aircraft Co. Menlo Park, California 16555 Saticoy St. Attn: H. D. Crane P. 0. Box 2013, South Annex Van Nuys, California General Electric Co. Attn: Dr. Basun Chang Schenectady 5, New York Research Scientist Attn: Library, L.M.E. Dept. Texas Technological College Hunter College Lubbock, Texas New York 21, New York Attn: Paul G. Griffith Attn: Dean Mina Rees Dept. of Elec. Eng.

Dr. Stanley Winkler University of Pennsylvania IBM Corporation Mechanical Languages Projects Federal Systems Division Moore School of Elec. Eng. 326 E. Montgomery Ave. Philadelphia 4, Pennsylvania Rockville, Maryland Attn: Dr. Saul Gorn, Director Post Office Department Applied Physics Laboratory Office of Research and Engineering Johns Hopkins University 12th and Pennsylvania Ave. 8621 Georgia Ave. Washington 25, D.C. Silver Spring, Maryland Attn: Mr. R. Kopp Attn: Document Library Res. & Dev. Division Bureau of Supplies and Accounts, Chief L. G. Hanscom Field Navy Department AF-CRL-CRRB Washington, D.C. Bedford, Massachusetts Attn: Code W3 Attn: Dr. H. H. Zschirnt National Aeronautics & Space Admin. Department of the Army Goddard Space Flight Center Office of the Chief of Res. & Dev. Greenbelt, Maryland Pentagon, Room 3D442 Attn: Chief, Data Systems Div. Washington 25, D.C. Attn: Mr. L. H. Geiger Federal Aviation Agency Bell Telephone Laboratories Bureau of Research & Development Murray Hill Laboratory Washington 25, D.C. Murray Hill, New Jersey Attn: RD-375, Mr. Harry Hayman Attn: Dr. Edward F. Moore Mr. Donald F. Wilson National Biomedical Res. Found., Inc. Naval Research Laboratory 8600 16th St., Suite 310 Washington 25, D.C. Silver Spring, Maryland Attn: Code 5144 Attn: Dr. R. S. Ledley David Taylor Model Basin University of Pennsylvania Washington 7, D.C. Moore School of Elec. Eng. Attn: Aerodynamics Laboratory, Code 628 200 South 33rd St. Miss Cravens Philadelphia 4, Pennsylvania Attn: Miss Anna Louise Campion Lincoln Laboratory Mass. Institute of Technology Division of Automatial Data Lexington 73, Massachusetts Processing /AOP/ Attn: Library Department of State Washington 25, D.C. Dr. C. R. Porter Attn: F. P. Diblasi, 19A16 Psychology Department Howard University Auerbach Electronics Corp. Washington 1, D.C. 1634 Arch St. Philadelphia 3, Pennsylvania

Electronics Research Laboratory Hebrew University University of California Jerusalem, Israel Berkeley 4, California Attn: Prof. Y. Bar-Hillel Attn: Director National Physical Laboratory Institute for Defense Analysis Teddington, Middlesex Communications Research Division England Von Neumann Hall Attn: Dr. A. M. Uttley, Supt. Princeton, New Jersey Autonomics Division 3 9015 02825 9631