tfechni e ), c: t'_.... Errors in tFinite Au.tarat a Philip So Dauber Defuinition 4-. 9, line 2 Ic'a in:,' U, a s dl stat'e). e i..'te under a stc rongly con naected Mjlrtsrsduction... t ~I k Id nly I. " I" w.here.s. -Ls the set of r minimum...............?' - { s, )'-,,, si'dm~)ot:nsof' (SW) 2-' Kl.,?,3',tsst~s8,,{ie teff 9,) I.$ 5D

THE U NI V E R S I T Y OF M I C H I G A N SYSTEMS ENGINEERING LABORATORY Department of Electrical Engineering College of Engineering Technical Report SEL-65-1 ERRORS IN FINITE AUTOMATA by Philip S. Dauber October, 1965 This research was supported in part by AF contract AF 30(602)-3546 and in part by the General Electric Research Laboratory, Information Study Section, Schenectady, New York.

"rw~y\:-:-, YV kA NA~CT

Acknowledgments I would like to express my appreciation to Professors Richard F. Arnold, Harvey L. Garner, John H. Holland, and Eugene L. Lawler for serving on my doctoral committee. I would particularly like to thank Professor Arnold for serving as chairman. I would also like to thank Miss Sharon Bauerle for her fine job of typing this report. I would, in particular, like to thank my wife, Elayne, for her constant encouragement throughout this work. This work was supported in part by the Information Systems Laboratory of The University of Michigan through Air Force contract AF 30(602)-3546. Parts of sections four and five were done during the summer of 1964 while the author was associated with the Information Studies Section of the General Electric Research Laboratory, Schenectady, New York. To these two I give my sincere thanks for their financial and intellectual support. ii

Abstract The purpose of this research is to study the correctability properties of errors in a finite automaton driven by a random source. An error is defined to be a pair of states and is corrected by a tape if the tape takes both coordinates of the pair into the same state. Errors are then classified as one of four types: correctable, finite, definite, and non-correctable. A correctable error is an error for which there is a correcting tape. The error is finite if the probability of the set of correcting tapes approaches one as the length of the tapes gets longer. A definite error is an error for which all tapes, of length greater than some fixed length, are correcting tapes. A noncorrectable error is one for which there does not exist a correcting tape. We show that the set of finite errors induces a partition, called the finite error partition, on the set of states. Also, for a restricted class of random sources, this partition can be obtained from the set of correctable errors independent of the statistics of the source The notation of the semigroup of the automaton is then introduced. It is shown that many of the error properties of the automaton can be studied in terms of its semigroups. In particular, necessary and sufficient conditions are given for the automaton to have errors which are correctable but not finite and for the automaton to have only definite or non-correctable errors. Further results are then given on analyzing the error properties of finite automata which have a large number of states but can be decomposed into a series, parallel connection of smaller automata.o 111

Table of Contents Section Page 1 Introduction 1 2 Formalization of the Problem 3 3 Fundamental Results 7 4 Introduction to Semigroups with Applications to Definite Errors 15 5 Automata with Errors Which are Correctable But are Not Finite 28 6 Errors in Series Parallel Connections 39 7 Conclusion 67 Appendix Some Remarks on- the co Case 69 References 72 iv

1. Introduction This problem arose from an attempt to make a general study of reliability in computer like machines. The classic results of von Neumann (ref. 10), deal only with networks which do not have any feedback. Thus a malfunction only causes the network to be in the incorrect state for a fixed length of time. However, a malfunction in the general case with feedback can cause an error which persists forever. Fortunately, not all errors are of this type. Some errors are of the type that can persist only for a bounded time. Some, although they can persist infinitely long, for certain random sources they have a probability of being corrected which approaches one as the tapes get longer. Thus "almost all" of the "long" tapes correct the error. This is the phenomenon which we:will study. We will show that errors of the latter type, which will be called finite errors, induce a partition on the set of states. In section two we will show that in the case where the set of states is a finite set, this partition can be obtained from another relation on the set of states without knowing the statistics of the same. Thus a phenomenon which will start out as probabilistic in nature will turn out to be a deterministic one. We would like to apologize now for the trivial nature of the probabilistic arguments which will be used. This is due to the nature of the problem. In Appendix A we will show that in the case where the set of states is infinite, the phenomenon of an error being corrected by almost all 1

2 the long tapes is indeed a probabilistic one. The infinite case will not be studied any further due to the fundamental difference in the nature of this problem. The finite state problem will be studied within the framework of finite automata theory. Although we have attempted to give the definition of all the terms that we have used, we are still assuming that the reader is familiar with the main results in this area. Thus where the proof involves a construction used in the reference, we will only outline the construction. We also found that the use of semigroups is very helpful. Thus in section four we have given the necessary definitions and fundamental results. We have not assumed that the reader has any previous knowledge of the theory of semigroups. The value of semigroups will become quite evident in the later sections.

2. Formalization of the Problem In order to clarify the notation and to make the problem more formal we will begin by defining a finite automaton and an error in a finite automaton. Definition 2. 1 A finite automaton M is a triple M = (M', z, 6) M'is a finite set with elements m. (set of states); Z is a finite set with elements oa (input alphabet); 6 is a function from M' X Z -- M' (next state function). Later we will use M both to denote the finite automaton and its set of states. We will also extend 5 to M' X Z*, the set of sequences of symbols from Z, in the natural manner with sequences read from left to right. Definition 2.2 a. An error, E, in a finite automaton, M, is a pair of states (mimj) b. An error, (mi.,m), is corrected by a tape t ("tape" is synonymous with "sequence")if and only if 5(mi.t) -= (m,t). We can think of an error (mi.mj) as the situation, when due to a previous malfunction, the automaton is in state m. and should be in state mj, or is in state m. and should be in state m.i. We can see from 3

the definition of an error being corrected that these situations are equivalent. In this work we will consider a random source, which generates sequences and drives the automaton. The next definition will make this clearer. Definition 2.3 A random source S over an alphabet Z is a set (P ), where P is a probability distribution on Z n, satisfying the n requirement: 1) for all integers n and sequences x of length n Pn l(xa) = P(x) C~ If, in addition, the random source satisfies the additional requirement: 2) There is a real number k > 0 such that for all sequences x of length n and letter a n+l (xa) > k Pn(x) then we will say that the source has property P. We will call the ratio Pn+l (XOa)/Pn(x) the probability that the letter a follows the sequence x. Note that this means that if the source has property P. there is a constant, k, associated with the source such that the probability of any a following any sequence x is always greater than kg In addition we will say that a random source S = (P ] n

5 drives an automaton M if the probability distribution on the set of input strings of length n for the automaton M is PnF Definition 2- 4 Let S be a random source with property P and output symbols Z, and let M = (M, Z, 6) be a finite automaton driven by S. For an error E = (mi,mj) we define the following: a. y (mimj) = probability of the set of tapes of length I which correct the error (m.im. ) b. S(mi mj.) = lim y (m ) if the limit exists. The following lemma shows that for any source S and any error (mim) 7 (mmj) exists. Lemma 2.1 lim yS (mi,mj) always exists. S S PROOF: 1 >'Y(S m jm) ~> (mim.). Since the limit of a monotonic, R0r 1 _ + I ( bounded sequence always exists, the lemma is proved. Q.E.Do Now let us consider the following classification of errors in a finite automaton M being driven by a source S as above.

Definition 2.5 An error E = (mi,mj) is a. definite if and only if there is an I such that y7 (E) = 1. b. finite if and only if y S(E) = 1. c. correctable if and only if y (E) > O. d. non-correctable if and only if yS(E) = 0.

3. Fundamental Results In this section we will derive some fundamental properties of errors and will show the connection between the concepts of correctable and finite errors. Theorem 35.1 If, for any'source S, y (ml,m2) gl and S (m2,m3) = g2, then 1- - g > Y (mlms) > (g + g2) PROOF: Let TO be the set of tapes that do not correct (ml,m2) or (m2,m3); Tl be the set that either corrects (m1,m2) or (m2,m3) but not both; T2 be the set that corrects (ml,m2) and (m2,m3); and T3 be the set that corrects (mim3). We know that TO, Tl, and T2 are mutually disjoint and that T2 C T3 C T2 U TO. We will use Pr~(T) to mean the probability that a tape t of length 2 is in T. Therefore, we have gl + g2 = lim (Pr (T1) + 2Pr (T2)) = lim Pr (T1) + 2 lim Pr (T2). 2R- oo 26 00 But we also have for all 1, Pr~(T1) + Pr (T2) < 1. Therefore gl + g2 < 1 + lim Pr~(T2) < 1 + g ~-~ co where g = Y(mlm5). Hence g3 _ gl + g2 - 1. Likewise, letting Tll be the set of tapes which correct (ml,m2) and not (m2,m3), and T12 be the set which corrects (m2m3 ) and not (ml,m2), we have y (mlm2) = Pr2(T2) + Pr~(Tll) and

7y (m2,m3) = Pr,(T2) + Pry (T12). Thus Y I( jmm2) - 7,(m2m3) I = IPr(Tll) - Pr,(T12) But I Pr,(T11) - Pr(T12) < Pr,(T1) < 1 - (Pr2(TO) + Pr2(T2)). Now, taking limits as I goes to infinity, we get g g21 < 1- g3 Therefore g3 <1 - I g1 - g2 Corollary 3.1 The set of finite errors in an automaton M driven by any source S induces a partition on the set of states. That is, there is a partition F on the states of M so that E = ( (mmjm) is finite if and only if mo = mj (iF). PROOF: It is obvious that if y S(mi,m.) = 1, then y S(m. mi) = 1 by the S symmetry inherent in Definition 2.2b. Likewise, y(mimi) = o Now, S by Theorem 3.1, we have that if y (mi,mj) = 1 and 7y(mj,mk) = 1, then y (mi.mk) = 1. Hence, the finiteness relation is an equivalence relation and partitions the set of states. Q.E oD. We will use the abbreviation lg(t) for the length of the tape t.

Theorem 3.2 Let C C M X M be the relation (m. mj) C if and only if i-a (mi m,) is a correctable error. Also, let S be a source with property P. Then 7S( m.,m) = 1 if and only if for all tapes t, (b(mit), 6(mj,t))eC. PROOF: If (mimj) is finite then, obviously, (m.,m ) is correctable. If there is a tape t such that (6(mi,t), 6(m.,t)) is not correctable, then for all t' (6(mi,tt'), 6(m.jtt')) is not correctable. Hence, y(mim.) < 1 - (k) < 1 where k is the constant greater than zero associated with the source. Therefore (m.im.) is not a finite error. Conversely, let us assume that for all t (6(mi,t), b(mjt))eC. Let A = (mk,m) I for some t 6(mit) = mk and 6(m,t) = mi}. Then, for each (mk,mI)cA, pick a t' which corrects (mkum). Let p = k where r = max lg(t'). Then y (mi,mj) > 1 - (l-p)[-/r] where [~/r] is the greatest integer less than I/ro Hence lim y~(mi,m) > 1 - lim (l-p)[2/r] Since p > O we have y(mi.m) = 1 QE oD. Since the concept of an error being correctable is not dependent upon the source, the above theorem tells us that as long as we are dealing only with the class of sources that have property P, the property of an error being finite is also independent of the source. In what follows we will assume that the term'"source" will refer to a source with property P unless we explicitly say otherwise~ Thus we will call an error a

10 finite error if it is finite for some source (hence all sources) with property P, and we will call 7TF the finite error partition. Likewise we will drop the superscript denoting the source. We will call an error a non-trivial error if it is not of the form (mi,mi). Theorem 3.2 gives us some idea of the connection between the relation C and the partition iF' The next theorem is a stronger characterization of this connection. We will use the canonical ordering on partitions (i.e. T1 -'2 (ml - 2 ('2) ml = m2 (T1)) Theorem 3.3 iF is the coarsest partition with the substitution property such that m. - m: (-) (MVM )CC. PROOF: First we must show that if m.- m. (F) then for all tapes, t, 1 jF b(mi,t) - 6(mj,t)(QF) and hence AF has the substitution property. Let us assume that this was not true and there was a t such that b(mi,t) X 5(mj,t)(TF). Then by Theorem 3.2 there would be a t such that the error, (6(o(mi.t),t'), b(b(m,t),t')) = (b(mi,tt'), (m,, tt')), is not a correctable error. Hence all tapes in the set tt'Z* do not correct the error. Hence, for all X > lg tt', (mm) < 1 - km Thus (mi,mj) is not finite which is a contradiction. Now to show that TF is the coarsest such partition, let c be a partition with the substitution property such that mi m (c)=> (mi,mj)cC. Then if mi - mj (it), (mi,mj)eC. Also, since by the hypothesis A has the substitution property, for all tapes t, b(mi,t) - b(mjt)(t) and hence (6(mi,t), 6(mJ,t))cC. But by Theorem 3.2, this means that mN - mE (F). 3 j

l1 Therefore c < F' Q.E.D. We will now give two definitions due to J. Hartmanis and R. Stearns (ref. 4 and 6). Definition 3.1 A finite automaton M1 = (M1, Z, 6) state behavior realizes M2 = (M2, Z, 6') if and only if there is a one to one mapping, h of M2 onto M1 such that for all tapes t and states m.i C M2, h(3'(mit)) = 6(h(mJi)t). Definition 3.2 Let M1 = (M, Z, 6), M2 = (M2, Z', 6') and X:M ~ Z e Z' Then the series connection of M! with M2 with connecting function X is the automaton M = (M X M2, Z, 6") where 6" is defined as follows: b"t((mi mj),) = (6(m.i,), 6'(mj, M(mia))). We will say that a finite automaton M can be state behavior realized by a series connection of finite automata M1 and M2 if there is a connecting function X such that M is state behavior realized by a series connection of M1 and M2 with connecting function o. The following corollary is an immediate consequence of Theorem 3.3 and a well known result of Hartmanis.

12 Corollary 3.2 If M is a finite automaton with a finite partition fF' then F can be state behavior realized by a cascade connection of two automata M/CF and T, where all errors in T are finite, and M/rF has no non-trivial finite errors. PROOF: By Theorem 3.3, F is a partition with the substitution property. Hence, we know (Hartmanis, ref. 4) that we can decompose M into a cascade connection of two automata where the state of the front automaton distinguishes between blocks of the partition and the back automaton distinguishes the elements of a single block. Thus since an error within a single block is a finite error, all errors in the back automaton are finite. Likewise, since an error out of a block is not a finite error, the front automaton has no finite errors. Q.E.D, Let us now look at an example in order to demonstrate these theorems. Example 3.1 Let M = ((a,b,c,d,e), (0,1], 6) where 6 is the mapping shown below. 0 1 a b d b a d c a b d b d e a d It is easy to show that C = {(a,d), (da), (bc), (c,b), (e,a), (a,e), (e,d), (d~e) (be) 9 (enb) (ce) (e,c),(aa) (b9,b), (c,c) (d,d),(ee)} There are four equivalence relations with the substitution property

13 contained in C. I T (a, (a. c, dn:2 c, e} i3 ( {a, bc, d, e) i4 = (and, b,c, e). The greatest one is t4. Thus the only finite errors are t (a,a), (b,b), (cc), (d,d), (e,e), (a,d), (d,a), (b,c), (c,b). Also using Theorem 3.3 we can get a simple proof of a special case of a theorem which was proved by Winograd (ref. 15), and also in another context by Gilbert and Moore (ref. 3). Corollary 3.3 All errors in an automaton M are finite if and only if M has a reset tape. (A tape t is a reset tape if 5(mit) is independent of mi.) PROOF: From Theorem 3.3 we get that all errors in an automaton M are finite if and only if all errors are correctable. Define a tape t = tl t2`9 tk1l (k = number of states of M) as follows: tl corrects (ml m2) ti+l corrects (b(ml, t1... ti), (mi+2 t1 t. )) If it is possible to construct such a t, then t is a reset sequence. It is not possible to construct such a tape if and only if for some i, (6(mi, t1.. ti), 6(mi+2t1 t t)) is not a correctable error. But then, this (6(ml, t1... t) 6(m)2, t1) t,)) is not finite. Hence we can construct t if and only if all the errors are finite. Q.E.D.

14 Let us now look at another example to show the use of this theorem. Example 3.2 Let M = (ta,b,c,d), 0o1,i, 8) where 6 is shown below. 0 1 a b c b c d c d b d d b It is easy to see that all the errors are correctable. Hence nF = Iab,c,d] and all errors are finite. Upon examination it can be seen that the tape 000 is a reset tape since b(mi,000) = d regardless of m..

4. Introduction to Semigroups with Applications to Definite Errors In the course of studying errors in finite automata, it became obvious that many of the error properties (as well as other properties) of finite automata are more easily discussed in terms of the semigroups of the automata (ref. 7 and 9). In this section we will give some results about semigroups. Their usefulness will become more and more apparent in later chapters. (For a greater exposition on semigroups the reader is referred to Clifford and Preston, ref. 2). First let us define what a semigroup is and what we mean by the semigroup of an automaton. Definition 4.1 A mapping y: S X S -4 S is said to be an associative mapping if and only if for all elements sl's2' and s3 all in S, ((Si' s2)y s3) = (si Y(s2 s3)). Thus if a mapping is associative, the order of the elements in a compound mapping determine the result independent of parenthesization. Hence we will omit the parentheses. Definition 4 2 A semigroup is a pair, (S, ) where S is a set of elements, and ~ is an associative mapping of S X S -4 S. A semigroup will be called finite if the set of its elements is finiteo We will call ".' multiplication and will write sls2 rather than sl.S2 as with multiplication of real numbers~ We will also use the 15

same letter to denote the semigroup and its set of elements. It will be clear from the context which one we mean. Definition 4.3 Let M = (M, S, 6) be a finite automaton. SM, the semigroup of the finite automaton M, is the semigroup whose elements are transformations, mapping the set of states M into itself, induced by the next state function 6. That is, SM = [si I si' M- M and there is a nonempty string t over Z such that for all states mi. b(m.,t) is equal to the image of the state mi under the transformation s }]. The multiplication operation s1 S2 is the composition of s2 and s1. It is clear that the multiplication operation in the above operation is associative and that the set of its elements is closed under multiplication. Hence SM is indeed a semigroup, as desired. Definition 4.4 (Ideals) (a) A nonempty subset L of a semigroup S is called a left ideal if and only if SL C L, where SL = (x for some ssS and ~cL s2 = x30 (b) A right ideal, R, is a nonempty subset such that RS C R. (c) A two-sided ideal, T, (or just ideal for short) is a nonempty subset such that STS C To (d) 4 two-sided ideal is called a minimum ideal if it does -not properly contain another two-sided ideal. Similarly, a right (left) ideal is a minimum right (left) ideal if

it does not properly contain any right (left) ideal, (e) The kernel of a semigroup is the minimum two-sided ideal, if it exists. The followring three lemmas are known results about finite semigroups (See Clifford and Preston, ref. 2.) that will be used in this study. Lemma 4.1 Every finite semigroup has a kernel. PROOF: The kernel is just the intersection of all the two-sided ideals. There is always at least one two-sided ideal since S is a two-sided ideal of itself. Likewise, since S is finite, there can be only finitely many ideals. Also, if T1 and T2 are two ideals of S. then T1T2 C T1 and T1T2 C T2o Hence T1T2 C T1 0 T2 and thus the intersection is nonempty. Thus the theorem is proved. Q.E.D. Lemma 4 2 Let S be a finite semigroup with kernel Ko Then K = U R = U L where (R.) is -the set of minimum right ideals and (L.) is the set of minimum left ideals. PROOF: It is clear that if Ri is a minimum right ideal Ri C K since if sicK, Risi C K and Risi C Ri. Hence R. n K is not empty. But R n K is a right ideal, hence, Ri n K = Ri, since Ri is a minimum right ideal. Thus U Ro C K. We will now show that U R. is a left ideal. First we 1

18 claim that for any sicS, s.R. is another minimum right ideal of S. It is clearly a right ideal. Assume V C s iRi is a right ideal. Then let U C Ri, U = triERi I sirieV}. Then, if V is properly contained in siRi, U is properly contained in Ri. But U is a right ideal. Hence V = s.Ri 1 11 and thus siRi = R. a minimum right ideal. Now U Ri is a right and left ideal and, therefore, ideal. But K is contained in every two-sided ideal. Thus K = U R.. Likewise K = U L.. Q.E.D. Lemma 4.3 Let R be a minimum right ideal and L a minimum left ideal of a semigroup S. Then RL = R n L = G is a group. PROOF~: See Clifford and Preston, page 77 (ref. 2). I will now give an example illustrating some of the concepts which were introduced above. Example 4.1 Let M = (ab,c,d)}, (0,1), b) where 6 is given in the following table: 6 0 1 a b c b c d c d b d d b SM, the semigroup of the finite automaton has elements as indicated below.

19 S1 s2 s3 s4 s5 S6 s7 S8 S9 10O Sll S12 s13 a b c c d b d b d b d c d c b c d d b b d b c d d c d c c d b d b d d b c d c d b c d d b d b d d b c d c d b c The kernel K of SM is the set of elements (s6s7,s13 The only minimum right ideal is (s6;s7,s13). The three minimum left ideals are (s6)1,s7), and ts13). Examples of right ideals which are not minimum right ideals are (s3,s6,s7,s8,s13) and (s5,s6s7, s10, s11s 12 13). Definition 4.5 Let S be a semigroup. An element s.cS is idempotent if and only if sis. = si. We will call an element a minimum idempotent if it is an idempotent element and also is contained in some minimum right ideal. Using this definition and the above lemmas we get the following well known corollary first obtained by E. H. Moore (ref. 10). Corollary 4l 1 Let s be an element of a finite semigroup S. Then for k some integer k, s is an idempotent element of S. PROOF: Consider the set of elements [si]. This is a finite semigroup and hence must contain at least one minimum right ideal and one minimum left ideal. But the intersection of a minimum right and minimum left ideal is a group and hence contains an identity. But an identity must be an idempotente Hence the corollary is provedo Q.E.D.

20 So far in this section, we have only been giving results which deal with semigroups in general, The next theorem shows the intimate connection between errors in a finite automaton and the semigroup of the automaton. For convenience we will use hM(x) to denote the element of the semigroup of the finite automaton M which corresponds to the input tape x. Note that hM is a semigroup homomorphism of Z* into SM, Theorem 4.1 Let E be an error in a finite automaton M. Then E is 1. correctable if and only if E is corrected by some minimum idempotent of SMO 2, finite if and only if E is corrected by every minimum idempotent of SM' PROOF: If E is correctable then there is a tape x such that all tapes in the set x Z* correct E. But hM(x Z*) is a right ideal of SM' which must be finite since M is finite, and hence must contain a minimum idempotent. Likewise, if si, a minimum idempotent of SM corrects E, just by the definition of SM' there must be an xcZ* such that hM(x) = si. Hence E is correctable. Thus we have proven part 1. Let us now assume that there is a minimum idempotent which does not correct E. Then there exists a right ideal R C SM; all of whose elements do not correct E. But the set of tapes x I hM(x)ER] is a right ideal of Z* and hence contains a right ideal of form y E* all of whose elements do not correct Eo Hence E is not finite since y(E) < 1 - klg(y) < 1 Now if E is corrected by every minimum idempotent we must show that E is finite. We know for every finite semigroup there

21 is an element si such that for all s. and sk, sksisj is in a minimum 1 j k right ideal. Also, if E is corrected by every minimum idempotent, it is corrected by every element of every minimum right ideal. Now let xcZ* be such that hM(x) = s.. Also, let V = yeZ* I y ~ z X z' for all z and z'I. Then it is obvious that lim P.V = 0; thus lim P i(Z*-V) = 1. 1 i-no i-no But all elements of E*-V correct E. Hence E is finite. We have thus proven part 2. Q. oE.D We will now state an immediate corollary to this theorem. We will use Ts to indicate the partition induced by the mapping associated with the semigroup element s. Corollary 4.2 An error E = (mimj) in a finite automaton M is (1) finite if and only if mi = mj(n s. ) where (si is the set of minimum idempotents of SMO (2) correctable if and only if m = m. (CS ) for some minimum idempotent of SMWsio Thus the above corollary tells us that the partitions associated with the minimum idempotents of SM completely characterize the error properties of the automaton M. Returning again to semigroups, the next theorem will prove to be very useful in studying definite errors.

22 Theorem 4.2 Let S be a finite semigroup and T a two-sided ideal of S. Then there is a constant c such that for all n > c and all sl'S2''...sn 1 sl s2 Sn c T, if and only if there is no idempotent element of S contained in S-T. PROOF: First of all, if there is an idempotent si in S-T, then for 1 all j, sj is in S-T. Thus there is no such constant c. We will prove the converse by contradiction. If there does not exist such a constant c, then there is an infinite set of products sl's2 s2`s3 s3 s3.o8 1 1 2 l 2 3 all in S-T. Now let n be an integer greater than I SI, the cardinality of the set of elements of the semigroup S, and consider the set P = I pi = nl S n Since I P i must be less than IS I, 1n 2 1 there must be an i and j such that pi = pj; that is S S o.o S = S s. S S..o s ~ Now since T is a twon1 n2 no n1 n ni ni+ nj sided ideal and all p. are in S-T, we get that Pi is in S-T and x = sn... sn is in S-T. Hence for any i, pix = Pi is in S-T. ni+1 0 However from Corollary 4&1 we get that some power of x must be an idempotent, and we know it is not in T. Therefore S-T must contain an idempotent. Q.E.D. This theorem will get most of its use in this study in the partic. ular instance when T is the kernel of S.

23 Corollary 4.3 Let S be a finite semigroup and K its kernel, Then there is a constant c such that SC C K if and only if all the idempotents of S are in K. PROOF: This follows immediately from Theorem 4.2 if we let T K. Now let us give two more definitions. Definition 4.6 A right ideal of a semigroup S, is a universal minimum right ideal if it is contained in every other right ideal of S. (Clifford and Miller, ref. 1) Definition 4.7 (Perles, Rabin, and Shamir, ref. 12) A finite automaton M = (M, Z, 5) has a k-definite move function if and only if for all sequences a1 0.. ak of k letters from Z; 6(mi, C1' ) = 6(mj.,a. ) for all mi,,m. 1 k 1 k in Me Note that this implies that 6(m, a. c) = (m s b(M..C e, ( 1' ) =k k+l ~' ~~I1 (Yk) We will informally call a finite automaton k-definite if its move function is k-definite. The tie up of definite errors and definite automata is clearer after the following two lemmas which are due to Hartmanis and Stearns (ref. 5),

24 Lemma 4.4 A finite automaton M = (M, 7, 6) is definite if and only if all its errors are definite. Lemma 4.5 If M is a finite automaton, then M can be decomposed into a series connection of two finite automata M1 and M2 as shown below with all errors in M2 being definite and no nontrivial error in M1 being definite. Hence M2 is a definite automaton This lemma follows from the fact that there is a partition with substitution property cD on the states of M with the property that an error E is definite if and only if E < ~D. The following theorem gives a characterization of the semigroups associated with definite automata. Definition 4.8 Let S = (S,.) be a semigroup. Then, an element z of S is a right zero if and only if for all seS, suz = z. Definition 4.9 We will say that M = (M,., 6) is a union of the finite automata Mi = (min Ti, 5i) i=1l...ok if the following conditions hold: 1. i / j M. N M. empty 28 UM. =M

25 3 = 6 restricted to M.. i 1 Theorem 4.3 Let M = (M, Z, 6) be a finite automaton. Then the following two conditions are equivalent: (1) M is a union of definite automata. (2) SM contains a universal minimum right ideal U such that all elements of U are idempotent and all the idempotents of SM are in U. PROOF: If M is a union of k-definite automata then for all a. a...a. 9 1 m2 k (mi, a2.Ck ) = 6(mi, tai2 a ai. ) for any tape t Hence' 1'12'k 1'2 hM(t ii'..' i ) must equal M(a.l ak) Thus hM(t)hM(ai o cik) hM(al... vi ) since hM is a homomorphism. But since a... ak was an arbitrary type of length k we get that if't' is a tape of length k, hM(t') is a right zero and thus an idempotent. It is also clear that if x is an idempotent, then x k= x, an element of hM(Z). Thus, since every right ideal must contain an idempotent we get that M( k) is a universal minimal right ideal all of whose elements are idempotents and which contains all the idempotents of SM. To prove the converse we must show that there is a k such that all products of k elements are in U and that every element of U is a right zero. Now since U is a universal minimum right ideal, U is the only minimum right ideal and thus by Lemma 4.2, U is the kernel of So But since all the idempotents of SM are in U, we are guaranteed of the existence of such a k by Theorem 4.2, Also, since U is the kernel of SM~ it is equal to the union of the minimum left ideals. But since the

26 intersection of a minimum left ideal and a minimum right ideal is a group (Lemma 4.3), it must contain exactly one idempotent. Hence every element of U must be a one element minimum left ideal. Therefore, for all ucU and scSM, sou = u which means that u is a right zero. QsE oD. From this theorem we get two immediate corollaries. Corollary 4.4 M is a union of definite automata if and only if the set of idempotents of SM is a minimum right ideal~ PROOF: If the set of idempotents is a minimum right ideal, it must be a universal minimum right ideal since every right ideal must be a finite semigroup and hence must contain an idempotent. Corollary 4.5 M is a union of definite automata if and only if every idempotent of SM is a right zero. PROOF: It is clear that for any finite semigroup the set of right zeros, if it is not empty, is a universal minimum right ideal. Conversely, if all the idempotents are in a universal minimum right ideal, they are all right zeros as shown in the proof of Theorem 4.3 Q oE oD e Let us point out here that Theorem 4.2 can be applied to give more results on definite errors. Thus, for instance, a finite automata is such that all its finite errors are definite errors if and only if there

27 are no idempotent elements outside its kernel. As an aside, let us remark that it can be shown that linear automata only have errors which are either non-correctable or definite. Hence the above results tell us something about the structure of semigroups of linear automata.

5. Automata With Errors Which Are Correctable But Are Not Finite In the course of studying errors, an attempt was made to classify the set of finite automata which have errors that are correctable but not finite. One conjecture of the author was that if an automaton was strongly connected [That is, for all pairs of states mi and mi, there is a tape t such that 6(mi,t) = m.] and if it had correctable errors which were not finite, then the automaton could be state-behavior realized by a cascade connection of some automaton M1 and a nontrivial permutation automaton M2 (a permutation automaton is one where every input causes a permutation of the states). Note that this conjecture said that correctable but not finite errors were just errors which arose in M1 and "drifted" into M2o That this conjecture is not true can be seen by the automaton in Example 5.1. Example 5.1 M ((a,b,c,d,e), [0,1), 6) 6 O 1 a d a a b The correctable error relation is C = (a,c), (c,a),(d,e), (e,d),(c,e),(e,c),(ad),(d,a), (a,a),(bb), (cc), (dd) } However, there is no nontrivial partition with the substitution property on the states of M. Hence, there are no nontrivial finite errors, and also M can not be decomposed as in the conjecture, 28

29 It turns out that there is a classification of the class of automata with errors that are correctable but not finite in terms of their semigroups. This classification is very useful in aiding our intuition as to why certain errors are correctable and not finite and also is useful if we want to construct automata in this class. Definition 5.1 If S is a semigroup, then S is equal to S if S has a two-sided identity and is equal to S U (1) where s-l = 1-s = s if S does not have an identity. Definition 5.2 Let S be a semigroup. Define a relation < on the elements of S~ as follows. s. < s. if and only if there is an ele1 - j ment skcS such that si = s.sk. Also, define a relation i jk with si - sj if and only if si < sj and s. < si. The following lemma will tell us something about the relations "<" and "-". We will use [si] for the equivalence class of so. Lemma 5.1 (1) is an equivalence relation on the elements of So (2) < is a partial ordering on S/=, the equivalence classes of S modulo the relation -. (3) If S is a finite semigroup, then sisj > sj implies S.S. - S..

30 PROOF: (1) _ is obviously symmetric. Likewise, since S1 has an element such that s.il = sj, it is reflexive. Also, si sj and sj - sk implies there are elements stand such that ist S sjsu = si, s.sv = Sk and SkSw = S by the definition of To Wherefore, ju i' v wj k = i( v) and s = k(wS Thus s - sk. Since E is symmetric, reflexive and transitive it is an equivalence relation. (2) If [si] < [sj] and [sj] < [Sk], then si < S. and s < Sk. Thus si < sk and hence [si] < [Sk]. Therefore "<" is a transitive relation on S/-. Likewise, it is antisymmetric since x < y and y < x implies x _ y which means that [x] = [y]. A relation which is transitive and antisymmetric is a partial ordering. (3) ssj. > sj. implies there is an skeS such that sisjsk = s. i j - j k jk a Also, since S si C S, we have Ssisjsk C Ssjsko But since s sjsk = sj, we get Ssj C Ssjsk. However, since (Ssj)sk C Ssj we have Ssj = Ss sko Hence, multiplication on the right by sk causes a permutation of the finite set Ss.. Therefore, some power of sk has to be the inverse transformation of sk with respect to the set Sse. Call this element sk o Therefore, since s.isjSsj, we have s.is(sk ) SoS Likewise - ~ ~11 -l -l j (sisjsk)sk = jsk. Hence sos. = S5sk and thus sos. < s.. But, iak k j k'a1j j k'a- a since the hypothesis was that sisj > si, we have proved that ssj _= s.o Q.E oD. Definition 5 3 Let M be a set, and S a semigroup of transformation on So For each element si of S we define an equivalence relation Si on M as follows: m. mS.and onto th me a (" ) if and only if So maps mj and onto the same element Again, we will use the canonical ordering on the set of equivalence relations.

31 Note that we now have two partial orderings. One is on the semigroup and the other on the set of equivalence relations induced by the semigroup elements. We will now tie these two relations together. Lemma 5.2 s. < s. implies Ai > AT PROOF: If si < sj, then there is an sk such that sjsk = si. But if mi- mj ( ), then mi m. (it ). Thus m. m(i ), and therefore it > itss S. - S. Corollary 5.1 If s. s, then tS =it 1.3 S. s. PROOF: If si - s., then both si < sj and s. < si. Hence, by Lemma 5.2 s. < it and tS < T. But since < is a partial ordering on equivalence i j j i relations, we get that it = It Si Sj Q.E. o D. In general the converse to Lemma 5.2 and Corollary 5.1 are not true. This can be seen, for example, in the semigroup shown in Example 4.1. In this case, St = IS a,bc,d}. But, neither is s1 < s2 nor is S1 s2 S2 _< s1 as would be implied by the converse. However, in an important special case the converse holds. Theorem 5.1 Let S be a semigroup of transformations on M and let so be an idempotent element of S. Then, for all s.eS, if i > i.O s5 so then s. < s...3- 1

32 PROOF: Since s. is an idempotent of S, we have sis. = s. Thus, for all mcM, msisi, the image of the point m under the transformation (sisi) is equal to ms.. Hence ms. m(sT ) Therefore, if 1 > e i1 1 S. S - we have ms. - m(s ). However, this implies that ms s. = msjo Hence 5. J J the transformation s.s. is equal to sj, and therefore s. < s., Q oE eDo Corollary 5.2 Let si and s. be two elements of a semigroup S such that for some idempotent skeS, [si] = [sk]o Then.T < s if and only if s i s.. PROOF: If si > sj, then by Lemma 5.2, i < i Conversely, if So. — S. [Si] = [Sk], then by Corollary 5.1, = t o But, by Theorem 5019 1 k if e5 < its then sk > Sjo Hence, since [si] = [Sk], we have i > S.. Q oE oDo Definition 5. 4 An equivalence class [si] of a semigroup S is called a minimal class if and only if for all s-, [s.] < [si] implies that [s.] = Esi]. It is a minimum class if for all sj, [si] < [sj]. Lemma 5.3 Every minimal class of a finite semigroup contains at least one idempotento

33 PROOF: We know by definition of [si] that [s ]S D [s i] Likewise, if Esi] is minimal, [si]S C [si]. Hence [si]S = [si] and thus Isi] is a right ideal of S. But since a right ideal is also a finite sub-semigroup, it must contain an idempotent. Q.E.D We will now apply this to characterize the finite automata which have errors which are correctable but not finite. Theorem 5.2 A finite automaton, M, has errors which are correctable but not finite if and only if SM has two elements si and sj such that [si] / [Esj] and [si] and [sj] are both minimal classes. PROOF: If (m,m') is an error of M which is correctable but not finite, then by Corollary 4.2, there are elements si,sj in SM such that m - m' (Ir ) and for all skm / m'(t ). Thus for all s < si and s < s, ~k sjSk u- i v- j s a it since m - m'(I ) and m/ m'(I ). Therefore Es ] # [s ] V u u v Conversely, assume [si] and [sj] are two minimal classes such that [Si] / [Sj]. Then, since there are idempotents in both [si] and [sj] by Lemma 5.3, we get that eit / it by Theorem 5.1. Hence there are elements m,m'cM such that m _ m'(Q ), and m / m'(s ). Since for all i j Ski, tS = TS because [s ] is minimal, we get that (m,m') is correcsjsk j table but not finite. Q.E.D. There are many interesting corollaries to this theorem.

Corollary 5.3 A finite automaton M has errors that are correctable but not finite if and only if its semigroup, SM, has equivalence classes which are minimal but not minimum. Corollary 5.4 Let M be a finite automaton with correctable, nonfinite errors. If we have two copies of M in the same unknown state, then there are tapes x and y such that if we feed one copy x and the other y, we cannot find tapes xt and y' so that by feeding xt to one and y' to the other copy they will both once again be in the same state. Corollary 5.5 A finite automaton has no errors that are correctable but not finite if and only if for any two elements of its semigroup there is a third element less than botho PROOF: If any two elements have a common element less than both, then there can be only one minimal class. Hence the theorem follows from Theorem 5.3. Q.E oDo There is one case in which the error properties come out exceptionally nice. For interest, this is given below. Definition 5.5 (Laing and Wright, ref. 8) A finite automaton, M, is called a commutative automaton if and only if for all sisj elements of SM ss. = sjsi. 2~~~~~J~ 0J 0J

35 Corollary 5.6 A commutative automaton has no errors which are correctable but not finite. PROOF: For any two elements si,sj of its semigroup s.sj = s si. and thus s.s. < si and ssj < sj.. Hence this follows from Corollary 5.5. Q.ED. Corollary 5,7 A commutative automaton, M, can be state behavior realized by an automaton of the form where P is a permutation automaton and F is a finite automaton all of whose errors are finite. PROOF: We know F' the finite error partition on M, has the substitution property. Since P must distinguish amongst blocks of iFt no error in P can be correctable. Hence P must be a permutation automatono Likewise, since F distinguishes amongst the elements of a single block of M, all errors in F must be finite. Q.E.D. Let us now give one more result concerning errors which are correctable and not finite. Theorem 5.3 Let N be the set of errors which are correctable but are not finite in some finite automaton. Then there does not exist a tape t such that t corrects all the errors in N.

36 PROOF: Let EeN and let t be a tape that corrects E. We can assume without loss of generality that t corrects all finite errors. Since E is correctable but not finite, by Theorem 4.1 there is a minimum idempotent s iSM such that E < Si. But since iCE hM(t)' we get Si h(t) Likewise EC $ 1hM(t) since if it were, then by Theorem 5.1 we would this cannot be true. Hence neither TC < h(t nor g > r hold. s. - i hM(t) Therefore there must be an m and m' such that m f m'(thM(t)) and m -m'(m ). Q oE oD o We will now give two examples to demonstrate the use of these theorems. Example 5.2 Let the automaton and semigroup be as in Example 4.1. Then the 1 ordering on S is as follows:

37 Thus, this automaton has no errors which are finite but not correctable since there is only one minimal class, [s7,s7,s131. Example 5.3 Let M = ((a,b,c,d,e,f,g), (0,1}, 6) 6 0 1 a b c b c d c d b d d b e g f f f f The transformation associated with the elements of the semigroup of M, SM, are shown in the table below. s 1 s 4 S 6 s 7 8 g s1o s S12 s13 14 15 16 a b c c d b d b d b d c d c d b c b c d c b b d b c d c d b c d b c c d b c b d d b c d c d b c d b c d d b c b d d b c d c d b c d b c e g f g g f f f g g f f f f g g g f f f f f f f f f f f f f f f f f g g g g g g g g g g g g g g gg The ordering on S is as follows:

38 S 11 S9 Sl2 14 S7 sl5 s13 5i6 We can see that there are two minimal classes {s6,s7,s13 3 and (s14, s15,164. Thus the automaton must have errors which are correctable but are not finite. In fact N = ((e,g),(f,g))} Notice that every tape which corrects (e,g) does not correct (f,g) and vice-versa as required by Theorem 5.3.

6. Errors in Series-Parallel Connections In this section we will deal with the problem of errors in a seriesparallel connection of' finite-automata. This problem arises in two ways. The first is, if we are given a series-parallel connection finite automata with known error properties, what can be said about the error properties of this compound automata? The second is, if we are given a large complicated automaton, is it easier to find its error properties (or some bounds on it) by splitting the original automaton into smaller automata, find all their individual error properties, and then recombine them as above? The parallel connection, of course, does not introduce any new problems. If we have a parallel connection of n automata, then the composite automaton is just the cartesian product of them and if the finite error partition for the i-th automaton is gM. then the finite error partition for the composite automaton is just TM1 X MM. X.. M a 1 2 n Unfortunately, there is no easy solution for the series connection. We could consider the series connection problem by using the fact that the semigroup of the series connection of two automata is a susbsemigroup of the wreath product of the semigroups of the two automata. In the authorts attempt this led to some very complicated notation but not to any fruitful results. Hence we will go about it in another way. Now let us define a few more terms in order to be able to discuss the problem more readily. 39

40 Definition 6.1 A finite transducer M' is a 4-tuple M' = (M, K, o', nm) where M is a finite automaton Z' in a finite set (output alphabet);: M X Z - Z' (output function); and m e M (initial state). We will extend X in the natural manner to be a mapping from input strings to output strings, k: M X Z*-t~'*. As before, we will be informal and use the same letter to denote the finite transducer, the finite automaton, and the set of states of the automatono m. We will use superscripts, viz. M, in order to differentiate amongst a set of transducers each of which has the same finite automaton and output function but which have different m.'s as their 1 initial states. A transducer M then induces a length preserving mapping from Z* into'e*. If we drive the transducer with a random source with property P, we get a set of probability distributions (Pk(x)) on the output strings. That is, if x is a tape of length k, over ZE, Pk(x) *= zPv where k(m0 v) = x and where P~(v) is the probability of the tape v being the output of the random source driving M, given it has generated k letters~ We will call

41 the output toegether with the induced set of probability distribution, an M-transduction of the source S, or for short, just an M-transduction. Keep in mind that S always has property P. First, let us see what happens if, instead of driving the machine M2 directly with the source, we drive it with an M-transduction of the source. Thus, the situation is as follows: source t E. Later, we will get to the more difficult situation where we consider specific Ml-transductions, but for now let us let M1 range over all finite transducers and see what results we will get. We will always assume the output alphabet of M1 is contained in the input alphabet of M2 Theorem 6.1 Let M2 be a finite automaton. Then, all errors in M2 are finite for any M1-transduction of a source with property P if and only if M2 is a definite automaton. PROOF: If M2 is definite then it is k-definite for some finite k. Hence all tapes of length k correct all errors in M2 and consequently all errors in M2 are finite. On the other hand, assume that M2 is not definite. Then, by Lemma 4.4, there must be an error (mi,mj) in M2 such that (mimi) is not definite. But this means that for all k there must be a tape tk that does not correct (mi,mj)o Now, since M2 is finite, there must be tapes t and t such that all tapes of form ot do not correct (mi,mj). Since the set, T, of prefixes of the set

42 of tapes I(to tn is a regular set, there is a finite transducer M1 all of whose output sequences are in T. Hence (mi,mj) is not correctable under an Ml-transduction. Consequently, all of the errors in M2 are not finite under an Ml-transduction. Q oE oD This theorem has significant computational value. By using the techniques developed by Hartmanis and Stearn (ref. 5) we can pull off the maximal definite back machine. Then, in order to find the partition for the whole machine, we only have to find the partition for the front machine. We will also point out here the obvious result that if an error is non-correctable, it is non-correctable for any Ml-transduction. Hence, if a finite automaton has only non-correctable errors (viz, every input causes a permutation of the states), all its errors are correctable under any Ml-transduction. Thus, as a computational aid, we can also pull off automata of this type. By using the same type of argument as in Theorem 6.1, we can get a slightly stronger result along the same line. Theorem 6.2 Let E be an error in a finite automaton M25 Then E is a correctable error for all ML-transductions of the source if and only if E is a definite error. PROOF: If E is a definite error, there is some k such that all tapes of length k correct E. But since every Ml1-transduction is a length-preserving mapping, E remains definite for all of them. If E is not definite, then by using the same argument as was used in Theorem 6.1, to construct

43 a transducer which does not correct (mimj), we can construct one which does not correct E. Hence E is not correctable under all M -transductions. Q.E.D We will now give two examples to show the usefulness of these theorems. Example 6.1 Let M = ((ge, gf, he, hf, ie, if, je, jf), {0,1), 6) 6 0 1 ge ge gf gf hf he he ie if hf jf je ie ge gf if hf he je ie if jf jf je M can be decomposed into a series connection as follows. M1 = ([e,f] [0.1), 51) [0,1}, k e) 61 0 1 f f e M2 = (1g,h,i,j}, {0,1), 62) 62 0 1 h i g h,~l ~ j

44 Since M2 is a definite automaton we know that for m, TF 1F > (eg,eh,ei,ej, fg,fh,fi,fjl. In fact, since (e,h) is a non-correctable error in M1, we know that the equality holds. Example 6.2 Let M1 be as above and let M2 = ((gh,i), 0,1i, 62)) 6 01 hlC h The error (h,i) is a definite error. Hence if M is the series connection for M, iT > -eh, ei, fh, fi, eg, fg.] Let us now attempt to apply some of the results of the earlier sections to this part. It is easy to see that if [Pn) induced by an Mtransduction is statistically indistinguishable from a set (P' ) induced by some source with property P over an alphabet E' then, for any automaton M2 = (M2, 2Z, 6), an error in M2 is correctable (or finite) under the M-transduction if and only if it is correctable (or finite). The next lemma shows a necessary and sufficient condition for this in each of two special cases. We will use IE I to indicate the cardinality of the set Z.

45 Lemma 6.1 Let M = (M,, E, 9,', mo) and let P' ]P be the set of probability distributions induced by it when driven by a source S' with property P. (1) If I < I Z' I then the M-transduction is distinguishable from every source with property P over Z'o (2) If 1 ~ I = IZ' I then the M-transduction is indistinguishable from some source with property P over the alphabet Z' if and only if for all states m, of M such that for some tape xi.b(mo,xi) = mi for every a'ZE' there exists an input aEz so that (miCT) = a'. PROOF: (1) If | j < | ~' f then {'~E J for-: some 5Ec (mo) = a') < 1 >I < 13' I| Hence there is some output symbol which cannot occur at the beginning of an output string. Hence the M-transduction must be distinguishable from every source with property P over Z'. (2) If >Z 3 = |1' [ then for allk, I3kI = IF'k I Hence, if the output is indistinguishable from a source with property k over 3', M must induce a one to one mapping Zk onto >'k since we know the mapping is length preserving. Therefore, for every output string, a unique input string is determined and thus a unique state of M is determined. But, since every output string can occur, we get that for every state m, reachable from the initial state, and for every output symbol

46 a'dE' there is an input symbol ofE. X(ma) = o'. Conversely, if for every m and a' there is a a such that A(m,a) = a', the output must have property P since the symbol a has a probability of occurring greater than k which is strictly greater than zero. Hence a' has a probability of occurring strictly greater than zero. Thus the output is indistinguishable from a source with property P. Q.E. D. In sections four and five we derived various results pertaining to the connection between the error properties of the automaton and its semigroup. It seems reasonable to expect that we would be able to get analogous results for the error properties of the automaton under an M-transduction. Thus, we would hope to get a result like the following analogous to Theorem 4.1. As before, let hM(x) be the element of the semigroup SM associated with the tape x. Conjecture 6.1 Let (P n be a set of probability distribution induced by an M-transduction over Z and let V = {x lg (x)X > (}x Then an error E in M2 is finite if and only if it is corrected by every minimum idempotent of hM (V). This is not a valid conjecture as can be seen by the following counterexample.

47 Counterexample 6.1 Let M = ((a,bc,d), (0,1), 6, X, (0,1), a) o 1 X O 1 b bb b 0O O c c d c 0 0 d d c d 1 1 Let M = ((f,g), (0,1), 5) M2 [ S-0S'1 Sl s2 23 s3s s1 s1 s2 S3 S4 s s4 S3 S 3 3 s4 S3 s3 s4 S3 S4 The mappings associated with SM are as follows: 2 s1 S2 S3 s4 f f g f g g g f f g And x M (x) ~ S2 1 s3 Now (V) ={sl s2 s3gs4},

but the error (fg) is correctable but not finite under an M-transduction. Hence the conjecture cannot be true. However, if M is strongly connected we can get somewhat similar results. We will call an M-transduction a strongly connected M-transduction whenever M is strongly connected. Theorem 6.3 Let (P ) be the set of probability distributions on {En} n induced by a strongly connected M1-transduction, and let V = I Plg(x)X Then there is a subsemigroup W. of Z* such that W C V and for any finite automaton M2 and error E in M2, the following are true: (1) E is correctable under an M -transduction if and only if E is corrected by a minimum idempotent of hM (W). (2) E is finite under an M -transduction if and only if E is corrected by every minimum idempotent of hM (W). (3) M2 has errors which are correctable but not finite under an Ml-transduction if and only if hM (W) has two minimal classes. PROOF: Before we begin the proof let us just point out that all the above terms are well defined since hM (W) is a semigroup, which is a subsemigroup of SM. This follows from the fact that hM is a homomorphism of Z* onto SM. Also note that parts one and two of the theorem are generalizations of Theorem 4.1 and part three is a generalization of

49 Theorem 5.2. Now, let M1 = (M1, X, Z', mn), and let W' = (X(m0,x) J 6(mo,x) = mo and 6(mO,y + mo for all prefixes y of x}. Thus, W' is the set of output strings which are generated by an input string which takes the state m0 to itself for the first time. Now let W be the free semigroup generated by W'. Thus W is the set of output strings generated by a set of input strings which takes the state m0 to itself. Now, let us prove claim number one. If E is correctable, under an Ml-transduction it is corrected by some tape x. But since M1 is strongly connected there is a y such that xy is in W. Now, the set of strings in the set xyW is a right ideal of W and hence hM (xyW) is a right ideal of 2 hM (W) all of whose members correct E. But since hM (xy W'*) is a right ideal it must contain a minimum idempotent of hM (W). Conversely, since every minimum idempotent of hM (W) corresponds to at least one input tape of M1, if E is corrected by a minimum idempotent of hM (W) it is correctable. Thus we have proved claim one. If E is not corrected by some minimum idempotent of hM (W), it is not corrected by some right ideal hM (x(W')*) C 1L (W). But since Ml is strongly connected, this means that all tapes in the set x*h n V do not correct E. Hence, there is a set of input tapes of form yE* such that the image of any tape in the set under an M -transduction does not correct E. Hence E cannot be finite. Conversely, let us assume that E is corrected by every minimum idempotento Then E is corrected by all elements of minimum right ideals, and thus corrected by the kernel of LW(W). Thus there is an siehMW(W) such that for all s, s jsi corrects E. But corresponding to this there is an element x of W such that

50 hM (x) = s Hence all tapes of form yxz correct E. We will show 2 m that if (P'n is the set of probability distribution associated with a n source with property P and if A is the set of tapes which is not of form yxz and M1 maps a set B into A, then lim PY (B) = 0 n Thus since B', theset of tapes whose transduction does not correct E, is contained in B. E is a finite error under an M -transduction. If j is the number of states in M1, we know for every input tape v in B there is a tape u of length less than j such that vu leaves M1 in state mO. Then there is an input tape x whose output corrects E. Also, if the constant associated with the source is k, then vlg(Vux)vux > (k) ()+j P'lg vV. Hence, if P'n(B) = a, then Pn+j+lg(x) (B) < a(lklg(X)+j) Thus, since k > 0, the lim pI (B) = 0. n -e oo Hence we have proven part two. The proof of part three is much easier. We can just note that hM2(W) is a finite semigroup (contained in SM2 ) and hence all the results of section five hold without modification. Q.E BDo

Corollary 6.1 An error E is finite under a strongly connected M -transduction if and only if <E f n it where si is a minimum idemS. i potent of SM (W). 2 PROOF: This follows immediately from part two of the above theorem. We will call W the output semigroup associated with the strongly connected Ml-transduction. This output semigroup gives us a convenient way of talking about strongly connected transductions. Lemma 6.2 If W0 is the output semigroup associated with a strongly m connected M -transduction and W. is the output semigroup 1 m. associated with the M1 -transduction, then there are tapes x and y such that x WOY C Wi and y W. x CWO. PROOF: Let x be an output string associated with an input string xt such that 6(mi,x') = m0 and y be an output string associated with an input string y' such that (mO,y') = mi.. Since M1 is strongly connected, such an x and y exist. Obviously, x and y have the required properties. Q.E.D. Putting together the results of Theorem 6.3 and Lemma 6.2 we get the following result.

52 Theorem 6.4 Let M2 be a finite automaton all of whose errors are finite m0 under a strongly connected M1 -transduction. Then all errors m. in M2 are finite under an M1 -transduction for all states m. E M mi0 PROOF: Let W0 be the semigroup associated with M1 -transduction and W m. 1 be the semigroup associated with a M1 -transduction. Now, since all errors in M2 are finite under an M1 -transduction, by Theorem 6.3 there must be an si C hM (Wo) which corrects all errors in M2. Hence there must be a tape z in W0 which corrects all errors. By Lemma 6.2 there is an x and y such that x W y C W1. Hence xzy E W1 and 2M (xzy)E hM (W). But, since z corrects all errors, xzy must correct all the errors in M2H Also, there cannot be a minimum idempotent s. hM (W1) which does not correct all errors since if there were then sj.hM (xzy):: would cor2 - 0 rect all errors. Hence t S.hM (xzy) > S and MhM (xzy) > S. This j 2 j 2 contradicts the fact that s. is a minimum idempotent. Q.E.Do Besides its theoretical value, this theorem has some nice computational properties. For instance, if we can factor a finite automaton into a series connection of two simple automata, and if for any state m1 in a strongly connected component of M1, all the errors in M2 are finite, then all errors of form ((mi,mj),(m.,m!)) are finite where mi is in the same strongly connected components of M1 as M2 where mi and mj are any states in M2. 03

53 We can note that the proof of Theorem 6,4 depends mainly on the fact that the set of strings which correct all errors form, a two-sided ideal of Z* and hence the set of semigroup elements which correct all errors form a two-sided ideal of hM (W). Using the same type of argument we can: get a stronger theoretical result albeit one which is not so useful,, Theorem 6. 5 Let ~ be a two-sided ideal of SMM all of whose elements correct a set of errors A in M2. Also, let W0 be the semigroup 2 0 associated with the strongly connected M1 -transduction. Then, if hM (WO) n E is not empty, then all errors in the 2 M set A are finite for an M1 -transduction for all mieM1. PROOF: If hM (W) n. is not empty then clearly all errors are finite under an M -transduction. This is so since if there were a minimum 1 idempotent si of SM which did not correct an error in A, then there would be a right ideal si.S which did not correct A-. But si ~. D sit i 42M2 and s.i c 5 since 5 is an ideal. Hence ~ n s iS is not empty. But this is a contradiction since this intersection must correct all of A since it is contained in sisM. Hence, by Theorem 6.3, all errors in A are finite m0 2 errors under an M1 - transduction. Now let W. be the semigroup associm, ated with an Mi -transduction, and x and y be tapes such that x Wi y C W and y W0 x C Wi The existence of such tapes is guaranteed, by Lemma 6.1. If hM (W0) 0n = e is not empty, then hM2 (Y)2' hM (x) is not emptyo But hM (y)' hM (x) = hM2(y)(HM2(W0) 0n ~)2(x) = /2(y) M1(Wo ) 2(x) n hMA(y) h(x)) = hM(Y Wo x) n I" A. But y Wo x CW1 and ", C ~ since 5 is a two-sided ideal. Hence hM (W1) n e

54 is not empty. Thus by reapplying the first part of the theorem we have mo shown that all errors in A are finite under an M1 -transduction. Q.E.D, Although this theorem may be difficult to use for computational purposes, a corollary of it is well suited for this purpose. Corollary 6.2 Let W0 be the semigroup associated with a strongly connected 0 M1 -transduction and M2 a finite automata. Then, if the intersection of W0 with the kernel of SM is not empty, all 2 m. finite errors of M2 are finite under any M1 -transduction. PROOF: If we let A be the set of finite errors we know from Theorem 4.1 that all the elements of the kernel of SM correct all the elements of A. Hence the corollary follows immediately. Q oE.Do Example 6.3 Let M2 = ((a,b,c), (0,1), 6) 8- O 1 a b a b c b Then the mappings of the elements of SM are as shown below: 0 1 00 01ll 001 011 101 0011 0101 1010 a b a c b b a c b b a c c c a c a b a b b b b c

The ordering is s:-. s.ol..cws: / \, X go 1010 k / s00 s001. 001 1 Now let M1 = ((d,e,f), (0,1), 6, X, (0o,., d) 60 1 x 0 Il-.d e d 1 1 f d -d d f Je( Li W, the -associated semiigroup, -is the free semrtigroup on -he set of generators V:= [100, 10). Hience hMr (W) D (s ], and therefore the intersection of' hM (W) and the kernel of SM is not empty. Thus since all errors in M2 are finite for a source with property P. by Corollary m. 6.2, they are all finite under any M —transduction. On the other hand, assume M =: ((d,e,fJ, {0,1), 6, X, {O,1, d)

5 O 1 X O 1 d d e d l 1 e f f e 1 1 Then W is the free-semigroup on the set of generators V (110, il. Thus the only idempotent in hM (W) is sl. Hence by Theorem 6.3 (a,c) is the only correctable and only finite error in M2 under this M1-transduction. In the third case assume M1 = ((d,e), (0,11, 6, X, (0,1), d). 5 0 101 I I1 d d e]!d 1 1 e d d e d1I 1X1 1t1e Then W is the free semigroup on the set of generators V = (1,01). In this case s1 and sO1O1 are both minimum idempotents of hM (W). Hence by Theorem 6.3 we get that although both the errors (ac) and (b,c) are correctable, the automaton M2 has no errors which are funite under the M -transduction. 1 Thus in the case where we are dealing with strongly connected M-transductions, there are some reasonable tools. Let us now somewhat relax the strongly connected restriction and see what we get. Definition 6.2 An M-transduction, M = (M, Z, 6, X, El, mO), is called a connected M-transduction if and only if there is a state ml M such that for all states m.EM there is a tape x such that 5(mj,xj) = m1. States reachable from all states which they canreach, (as m1 is) will be called stable states. All others will be called transient states.

57 Note that if we let M' be the set of states reachable from ml, and let 6' and Xf be equal to 6 and X when restricted to the set of states, M', respectively, then the M'-transduction (M', ~, 6', X',', ml) is strongly connected, and hence, the M-transduction (M, E, 6, X, E', m1) is indistinguishable from a strongly connected M-transductionO Making use of the results in the preceding part we get the following. Theorem 6.6 Let an M' -transduction be connected and M2 be a finite automaton. Then an error (mi,mj) in M2 is finite under an M transduction if and only if for all strings x, which is the output of M1 induced by an input string which takes M1 from state m0 to a stable state m1 in M2 for the first time, the error (5(mi,x), 6(m.,x)) is finite- under the M -transductiono PROOF: It is clear that if for some string x as above, the error m1 (6(mix), 6(mj,x)) were not finite under the M1 -transduction, then (mimi) would not be finite. To show the converse all we have to show is that if V = z I z=uv b(m~,u)'= m1 vEZ*J and if [Pn} is associated with a source with property P, then lim P (V) = 1. n n -- co But this is clearly so since there is a tape u' such that for all mo there is a prefix of u', u" such that 6(mi,u") = m1. Thus V D Z* u" Z*, and lim P(* u" *) = 1. n n ->

58 Thus, "almost all" the long tapes take m0 to mi from where almost all the long tapes correct the error of the form (b(mi,x), 5(mjx)). Q.E.D. From this we get the following corollary. Corollary 6.3 Let an M1 -transduction be connected, and M2 a finite automaton. Then, if all errors in M2 are finite under an M1 -transduction for some stable state mleM, all m. errors in M2 are finite under all M1 -transductions for any mi.EM1 m PROOF: If all errors are finite under an M1 -transduction then obviously, all errors of the form (5(mi,x), 6(mjx)) are finite for all (mi,mj) errors in M2. Hence the corollary follows immediately from Theorem 6.6. Q.E D. It would appear that all of the above results are only of limited use since they only consider the case of the connected or strongly connected M-transduction. However, as the next theorem will show, they are quite general.

59 Theorem 6.7 Let Mo = (Mo, ~, 6, X, ~', imO) be an arbitrary M-transduction. Then there exists a finite number of connected M-transductions M1,M2V.. oMk with the following property. For any finite automaton Mk+1, an error E in Mk+1 is (1) correctable with respect to an Mo-transduction if and only if it is correctable with respect to some M,-transduction for 1 < i < ko (2) finite with respect to an M -transduction if and only if it is finite with respect to all M.-transductions 1 1 i < k. PROOF: First let us define [m.] = (m. for some xEc 6(mix) = m.) and i mi. = m I for some xCe.* b(m.,x) = m.. Now let 1 3 3 1 mmi.,m.,...mi ) be a maximal set of stable states of M0 such that the set 11 12 mh ([m. ],...,[mi ]) are pair-wise disjoint and if for some mjeMO, m. [m] [mi ], then [mj]D [mi. ] ow let M mi where 6 = 6 restricted to Imi I if 5(m,oj) IE |mi | otherwise 5G(m,oj) = 6(ml,ai) where ai is any element of Z such that for m, 5(m, ai) E mi |, and X(m,aj) = X(moaj) if 5(moaj) M~ and otherwise X (m,caj) = X(m,Ci) where a. is as above. It is easy to see that x is an output tape of some Mi, 1 < i < k, if and only if x is an output tape of M. This follows immediately from the definition of the M.o Hence part one of the theorem is trivially true. Now let us assume that E is not finite with respect to some M - transduction 1 < i < k. Then, by Theorem 6.6, thereis an input tape x

6o to M which takes m0 to a state stable state mi with the property that if x' is the output tape associated with input x and if y is an output tape obtainable starting in state mocM. then xly does not correct E. 1 1 But if this is true then there is an input tape x" which takes M0 to state micM0 and which has x' as an output. But then all outputs which result from the set of inputs x"Z* do not correct E o Hence E is not finite with respect to an M -transduction. Conversely, let us assume E is not finite with respect to the M0-transduction. Then there is an input x" such that all outputs of M0 resulting from the inputs xEZ* do not correct E. Also, let x be the output of M0 resulting from the input x". But from the definition of the set (MiA there must be an Mi-transduction with x" as an output. Hence, E is not finite with respect to that Mo. Thus the theorem is proved, 1 Q oE oDo If we apply this theorem to the automaton in counterexample 601 we see that M decomposes into two transducers as follows. M = ((a,b),, (0,11, 56, X, I(01), a) M = ((ac,d), (0,1), 6, X, (0,1), a) 6a 01 0 1 0X1 x 0 1 a b b aQO O a c c aQO O b b bb 0 0 c c d c 0 0 The error (f,g) in M2 is finite under the M -transduction but not under the MI -transduction. Thus it is correctable but not finite under the M:-transductiono

61 In the preceding part of this section we have only been considering half of the problem. We have been considering automata which decompose as follows: source M and we have just considered errors which occur in M2 (the "back" automaton). Let us now consider errors which occur in M1 (the "front" automaton). Definition 6.3 Let M be a finite automaton which can be decomposed into a series connection of a finite transducer M1 = (mlEzPl,X~' mO)0 and a finite automaton M2 = (M2,',62) Then an error E = (mi,mj) in M1 is mi-correctable, ml1M2 if and only if there is an x such that 61(mi.,x) = b2(mjx) and if y = X(mi,x) and z i X(mj,x), then 52(mly) = 62(ml,z). Likewise, it is ml finite if lim P (V) = 1 n n ->oo00 where V is the set of tapes in Z* which have the same properties as the tape x has above. The next few results will relate this case to the case that was previously studied.

62 Lemma 6.3 Let M1 be a finite transducer, M2 a finite automaton, and ml a state of M22 Then an error E in M1 is ml-finite if and only if (1) E is finite; and (2) if x is such that 61(m.,x) =1(m.,x) = mk and y and z m. m. I i are the respective outputs of the M - and M -trans1 1 ducers then the error (b2(ml,y), b2(ml,z)) is finite underthe M -transduction. The proof of this lemma is obvious and follows directly from the definition. Hence, it will not be given here. Note that, in general, condition two is very difficult to check for. However, in some common cases it is very easy. Thus, for instance, if M2 is a definite automaton, or if M1 is a connected transduction which corrects all errors in M2, then condition two is vacuously satisfied. Let us now give a corollary which will give a necessary and sufficient condition for all errors in the series connection to be finite. Corollary 6.4 Let M be a finite automaton which can be decomposed into a series connection of an M -transduction and a finite automaton M2. Then all the errors in M are finite if and only if all the errors in M1 are finite and there is a stable state m1 of are finite under the M M1 such that all errors in M2 are finite under the M1 -trans duction.

63 PROOF: First, if all the errors in M1 are finite then M1 must be a connected transducer. Hence, by Corollary 6.3, since all the errors in M2 m1 mo are finite under an M1 -transduction, they are finite under all M1 -transductions, m iM1. Thus if we represent the states as pairs (mi,mi) where m.ieM and m.jcM2, we know that all errors of the form ((mi,mj)(m!mj)) are finite and likewise errors of the form ((mi,m.)(m.,m!)) are finite. Hence, since we know the relation of finiteness is transitive, it follows that all errors in M are finite. Conversely, if either M1 has errors which are not finite or if for some state, mi of M1, there is an m. error of MN which is not finite under an M1 -transduction, then it is -bvious that the automaton M has errors which are not finite. Q.E.D. Note that the second part of the condition -can be checked for using the results of Theorems 6.3 and 6.4. Before we close this chapter we will give one more example which will illustrate the use of many of the results in this chapter. Example 6.4 Let M be the finite automaton whose move function 6 is tabulated below.

6 0 1 da ha ea db hb eb dc ha ea ea gb fb eb gc fc ec gc fc fa eb gb fb ec gc fc ec gc ga fa ea gb fb eb gc fa ea ha jb jb hb jc jc hc jc jc ia ja ha ib jb hb ic ja ha ja ia ha jb ib hb jc ia ha - It appears at first that the calculation of the finite error partition for M would be a very difficult task. However, as we will show below, once we notice that M can be decomposed into a series connection of M1 and M2 as below, the calculation will be much easier. M1 = ((d,e,f,g,h,i,j), (0,1), 61, X, (0,1), x) 6 0 1 X O 1 d h e d 1 e g f e 0O f e g f O O g f e g 1 1 hj jj h O O ij h i 1l j i h jl 1 Mo = ((a,b,c), (0,11, 62)

65 62 0 1 a b a b c b c c a First let us note that we can calculate the finite error partitions for M1 and M2 by observation: for MF (ab and for M2 F = {d,e,f,g,h,i,j Hence for M, KF < [(da, db, dc, ea, eb, ec, fa, fb, fc, ga, gb, gc, ha, hb, hc, ia, ib, ic, ja, jb, jc}. Now since 001 is an element of the semigroup associated with the strongly e' connected transduction M1, and M (001) is an element of the kernel of SM (See Example 6.4), by Theorem 6.3 we get 2 cF > 1 = {ea, eb, ec, fa, fb, fc, ga, gb, gc.. Likewise, 1 e W of Mh and no string starting with 0 is in it. Hence tF > T2 = (ha, hc). By similar agreement we get that the errors (hb, ha), (hb, hc), and all errors of the form (jx,jy) and (ix,iy) are not finite errors. Next, as per Theorem 6.7, instead of considering the Ml transduction, we can consider the connected transduction Ma and MB with moves and outputs as below.

66 b O 1 X O 1 0 1 i O 1 d e e d 1 1 d h h d 1 1 e g f eQO O hj j h 0 0O f e g f 0 0 i j h i 1 1 g f e g 1 1 j i h j 1 1 We see that although all errors in M are finite under the M-transduction, only the error (a,c) if finite under the M -transduction. Hence we get itF -> 3 = [da,dc] and that (da,db) and (db,dc) are not finite errors. Now applying the results of Lemma 6.2 we get that iF > 4 = (ia,ja, ib,jb, ic,jc). Likewise, since a 0 input corrects (h,i) and causes errors which are not finite regardless of the state of M2, we get that all errors of form (hx,ix) are not finite. Similarly, 01 corrects (h,j) but causes errors which are not finite, all errors of form (hx,jx) are not finite. Now putting this all together we get 4 F > U It = - = ea,eb,ec, fa,fb,fc, ga,gbgc, ha,hc, i=l da,dc, ia,ja, ibjb, icjc, hb,db}. Using all the errors that we know cannot be finite we find that all the finite error classes of r5 are indeed maximal classes and that hence ITF = 5'

7. Conclusion In the beginning we set out to classify and to study state errors in an automata driven by a random source. We feel that by now the reader should have a reasonable feeling of the types of state errors and their properties in the finite state case. One area for further study is that of state errors in various classes of restricted infinite automata. It is our conjecture that in most of the commonly studied classes of automata, many of the interesting questions will be recursively unvolvable. However, this may not be the situation, and in any event, the area deserves further study. Input errors and output errors are two other types of errors that we might have looked at. Input errors can intuitively be thought of as a state error which arises due to a substitution of one input string for another. Thus they are just special types of state errors. However, they also give rise to certain structures on the set of input strings. This has been studied more extensively by Winograd (ref. 15). We can also rewrite many of the results in the last section so that they tell us about input errors. In order to consider output errors we must consider automata with output functions. An output error is then an incorrect output due to the finite automaton being in the incorrect state. If we are considering reduced finite automata (i.e., any two states are distinguishable) (ref. 11), then for any state error, there is at least one input string which causes an output error. If the state error is not correctable then in an intuitive sense, for most of the infinite tapes, the number of

68 output errors is unbounded. Similarly, if the state error is finite, then for most of the infinite tapes, the number of output errors is finite. If we are dealing with a finite automaton which is not reduced, we can get the same results by consdering the state errors in the derived reduced machineso Thus it can be seen that the study of state errors reported here is a prerequisite to a study of output errorso However, more work along this line can certainly be done.

Appendix Some Remarks on the co Case One obvious way to generalize the previous results is to alter Definition 2.1 so that M, the set of states, need not be finite. We have not looked into this area extensively but will give some examples to indicate that the results do not carry over. In this appendix, "automaton" will indicate a system of the type defined in Definition 2.1 without the requirement that the set of states of M be finite. Definition A.1 An error E = (mlm2) will be called a G-error if E is correctable and, for all tapes t, (l(m1,t), 6(m2,t)) is correctable. We will state without proof that the G-errors partition the set of states and that G is the largest partition with the substitution property continued in C the correctable error relation. The proofs are analogous to the proofs of the corresponding theorems in the finite case (Theorem 3.3 and Corollary 3.1). In the case of finite automatons, an error is finite if and only if it is a G-error. However, as Example A.1 will show, this is not so for arbitrary automata. Example A.1 M = (I X I X I, (0,1,2,0',1',2'),b) where I is the set of integers, and 6 is the move function described below. For all (i,jk) ~ (0,0,0) 69

70 b[(i,j,k), 0] = (i+l,j,k) 5[(i,jk),O'] = (i-l,j,k) 5[(i,j,k), 1] = (i,jl,k) 5[(ij,k),l'] =(ij-l,k) 6[(i,j,k), 2] = (i,j,k+l) 6[(ij,k),'2] = (i,j,k-l) and b[(0,0,0), ul] (o,o,o) where u is any input. It is obvious that any error E = [(i,j,k), (1,m,n)] is correctable since there is a tape that takes it to [(0O0,0),(0,0,0)]. However, if S is a source which generates each symbol independently with probability 1/6, then there is a probability greater than zero that (i,j,k) never goes to (0,0,0). (See Spitzer, ref. 13). Thus in the limit, there is a probability greater than zero that E is not corrected; and hence it is not finite. Thus, in the machine M, all errors are correctable; thus all errors are G-errors. However, there are no finite errors. In this example, it is still true that the finiteness of an error does not depend upon the source, as long as it is the property P. That there are some automata where it does can be seen by the following example.

71 Example A.2 A = (I, (0,1), 6) where I is the set of integers. For i ~ 0 6(i,0) = i+l 6(i,l) = i-l For i=O, 6(0,0) = 6(0,1) = O. Let S be the source that generates x with probability p and x' with probability (l-p) independent of its past history. Then, all errors are G-errors and if p = 1/2 all errors are finite. But, if p > 1/2 only errors of the form (i,j) i < O, j < 0 are finite, and if p < 1/2 only errors of the form (k,l) k > 0, 1 > 0 are finite. This follows from the fact that each state is undergoing a one-dimensional random walk with an absorbing barrier at zero. The one-dimensional symmetric random walk (p=l/2) is recurrent whereas the other ones (p/l/2) are not. Hence we get the above results. Thus we can see that the finiteness of an error depends upon the source.

References 1. A. H. Clifford and D. O. Miller, "Semigroups having zeroid elements,' Amer. J. Math,, 70, 117-125 (1948). 2. A.o H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Vol. 7, American Mathematical Society Survey (192T 3. E. Gilbert and E. Moore, "Variable-length binary encodings," Bell Systems Tech. J., 389 933-967 (1959). 4. J. Hartmanis, "Loop-free structure of sequential machines," Information and Control, 5, 25-43 (March 1962). 5. J. Hartmanis and R. E. Stearns, "A study of feedback and errors in sequential machines," IEEE Trans. on Electr. Computers, EC-12, 223-232 (June 1963). 6. J. Hartmanis and R. E. Stearns, "Pair algebra and its application to automata theory," Information and Control, 7, (December 1964). 7. K. B. Krohn and J. L. Rhodes, "Algebraic theory of machines," Mathematical Theory of Automata, Polytechnic Press, Brobklyn, New York (19637 ) 8. R. Laing and J. Wright, Commutative Machines, Technical Note 04422, 03105-24-T, Department of Philosophy, The University of Michigan, Ann Arbor (1962). 9. Yu. T. Medvedev, "On the class of events representable in a finite automaton," Sequential Machines: Selected Papers (edited by E. F. Moore), Addison-Wesley, Reading, Massachusetts (1964). Originally, in Automaty, Moscow, Izdatel'stva Inostrannoi Literaturg (1956), pp. 385-401. 10. E o H. Moore, "A definition of abstract groups, Trans. Amer. Math. Society, 3, 485-492 (1902). 11. E. F. Moore, "Gedanken-Experiments on sequential machines," Automata Studies (edited by C. Shannon and J. McCarthy) Princeton, New Jersey, 129-153 (1956). 12. M. Perles, M. D. Rabin, and E. Shamir,, "The theory of definite automata," IEEE Trans. on Electr. Computers, EC-12, 233-242 (June 1963). 13. F. Spitzer, Principles of Random Walks, Van Nostrand, Princeton, New Jersey (1964). - 72

73 14. J. von Newmann, "Probabilistic logics and the synthesis of reliable organisms from unreliable components," Automata Studies (edited by C. Shannon and J. McCarthy,) Princeton University Press, Princeton, New Jersey, 43-98 (1956). 15. S. Winograd, "Input error limiting automata," J. Assoc. Computing Mach., 11, 338-351 (July 1964).

UNIVERSITY OF MICHIGAN 3 9011111111111111115 02845 3218 3 9015 02845 3218