THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Computer and Communication Sciences Department Technical Report A Conjecture on S*-semigroups of Automata Dennis Paul Geller with assistance from: Department of Health, Education, and Welfare National Institutes of Health Grant No. GM-12236 Bethesda, Maryl and and National Science Foundation Grant No. GJ-519 Washington, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR January 1971

X'"- t ^' r - I

Introduction In [2] Hedetniemi and Fleck define the S*-semigroup of an automaton. It was conjectured that if A and A' are any two strong machines with the same number of states then s*(A) is isomorphically embedded in S*(A'), and vice versa. In this note we prove a stronger result which settles the conjecture except in the case where exactly one of the machines is autonomous. s*-semi groups Let A = (S,I) be an automaton with states S and input set I; if scS, iEI then we write si for the successor of s under input i. If s,teS and x is a string of symbols from I(xcI*) such that sx = t then we say that (s,x,t) is a triple of A; if x = iEI then (s,x,t) is an elementary triple. Let U and V be finite sets of triples of A; we define the product UoV by UoV = {(s,x,t)l3(s,y,r)cU,(r,z,t)~V such that x=yz}. Under the operation o the finite sets of triples form a semigroup; we call this semigroup S*(A). Let A be a strong automaton with n states and at least two inputs, n and n. Since A is strong, for any states s and t of A there is a string wst of length at least one such that swst=t. Let A' be any automaton with at most n states, and let q be a 1-1 map from the states of A onto the states of A'; thus, unless IA'J=JAJ the domain of p will be a proper subset S of the states of A. If the input set of A' is I' = {ii,.,' a = I I'\} we define a map h:S x I' + I* in the following manner. Let seS and ijeI' be such that (p(s),ij,t') J J is a triple of A'; choose teS such that p(t) = t' and define h(s,i') = h (ij) = nJRw hJ~i nw~,q

2 where q = s(nJr). Clearly hs is 1-1 for each seS; also for each seS, i EI', the relation ((shs(ij)) = q(s)ij holds. (In fact, the pair (p,h) defines a generalization of the classical automata-theoretic notion of realization; this is dealt with in detail in [1]). We can also extend h to domain S x(I')* inductively by hS(ijx') = hs(ij)ht(x'), where S i S J t x' (I')* and t = sh (ij)ES. i J Lemma. The map h:S x (I')*+I* is 1-1 for each seS. Proof. let jl..jm and kl and k... m, be two strings from (I')* and let hs(j...jm) = h (k...k m,) = w. Then, by definition, there are states r,teS such that w = hs(ji)hr(j2*..jm) = hs(kl)ht(k2." km ). But there is a unique positive integer z such that the prefix of w having length k + 1 is the string n'n. This uniquely determines jl = = i S, so that r=t= si. Then h(j.. jm) = h (k2 kmi), and we can repeat the above process r 2r m r 2 H until we arrive at m=m' and j = k, p = 1, 2,...,m. p p Note that the lemma would not simply follow if hs was 1-1 on symbols for each seS. Using the notation of the lemma, suppose hs(jl) = a, h (k1) = ab, h (j) = bc, ht(k2) = c. Then hs(jlj2) = hs(klk2) = abc, but jlj2 klk2. Theorem: Let A be a strong automaton with n states and at least two inputs, and let A' be an automaton with n' <n states. Then S*(A') is isomorphic to a subsemigroup of s*(A).

3 Proof: We use the maps q and h above to define the isomorphism. Let b' = {(s', x', t')} be a singleton in S*(A') and set g(b') = { S,hS(x'),t)jl(s) = s'}. Note that this implies that p(t) = t'. Also, since hs is 1-1 for each S~S, g(b') = g(bp) if and only if b{ = b2; i.e., g is 1-1. Let bi = {(sj,xj,r')} and b2 = {(r',x~,t; )}. Let b1 = {(sl,xl,r)} = g(bl) b2 = {(rx2,t2)} = g(b)). Then bob2 = {(Slhs (xx'), t )} is a singleton of s*(A) and, as ~(sl) = Si, p(t2) = th, blob2 = g(blobh). Thus g(bp)og(b;) = g(blob'). On the other hand, if bi = {(s,x{,t)}, b = {(s,x,t")}, g(bp) = {(s1,xl,tl)}, g(b)) = {(s2,x2,t2)} and ti s~ then tl f s2, so that bob' = o and g(b:)og(bh) = p. Now let V' be any element of S*(A'); V' is a finite set of triples of A'. Extend g to g* by g*(V') = {g(b')jbsV'}. Let S*A,(A) be {g*(V')IV' S*(A' )}. Now, if VI,V~s*(A'), g*(V *(Vog*(V = [U{g(bl)b V }]o[ L {g(d')d.) V}] = J {g(b')og(d') bEVj,d'eV}b iJ j i' = j g(bod) lbV1,d'V.} = {g(fk){ fqV]~V2,} = g*(V oV). Thus S*A,(A) is a subsemigroup of S*(A), and g* is a homomorphism. We wish to show that g* is 1-1. Suppose g*(V9) = g*(VI). Choose a triple bEcVp, and let {b}= g({bi}). Then there is a triple b2EV' such that {b} = g({b;}). If b = (s,w,t), bi = (d(s),x',~(t)) and

4 b2 = (4(s),x2,(t)), where w = hs(xl) = hS(x'). Then, by the lemma, xl = x2, so b: = b2 and VC1V;. The symmetric argument gives Vi = Vp so that g* is 1-1, and hence g* is an isomorphism between S*(A') and S*A,(A). Q.E.D. In particular, if A and A' are both strong n-state automata, s*(A) s*A(A') < s*(A') *A, (A) < *(A), where sl < S2 indicates that sl is a proper subsemigroup S2. To complete our partial solution to the conjecture, we need only note that any two strong, autonomous, n-state automata are isomorphic, and hence have isomorphic s*-semigroups. To completely settle the conjecture it only remains to decide whether the s*semigroup of the unique autonomous, strong, n-state automaton can isomorphically contain the s*-semigroup of every other strong, n-state automaton. REFERENCES 1. Geller, D.P., to appear. 2. Hedetniemi, S.T. and A.C. Fleck, "s-semigroups of Automata," Technical Report No. 6, THEMIS Project, University of Iowa, 1970.