SYNCHRONIZATION AND DECOMPOSITION OF FINITE AUTOMATA Thesis for the Degree of Ph. D. MICHEGAN STATE UNIVERSITY ’ WILLIAM FREDERICK CUTLIP 19.68 mm- ‘" mama? Ll Michigan bun: University This is to certify that the thesis entitled Synchronization and Decomposition of Finite Automata presented by William Frederick Cutlip has been accepted towards fulfillment of the requirements for Mdegree inMthemaIiCS S is the transition function of A. For each s e S, let M(s, A) = s. Automaton, machine, and device will be used interchangeably with finite automaton. There are several schemes for representing a finite automaton A, each having its particular advantages. These will be introduced by example rather than by formal definition; and the fact that they all represent the same automaton will be asserted without proof. Example 2.2.1: Let S = (so, 51,32}. Let Z = {0,1}. Let F = {52}. (a) M may be specified in a transition table. Table 2. 2.1. Transition table of A = (S, M, 80’ F) M 0 1 SO S]. 82 S1 S1 51 S2. S2 S1 (b) M may be Specified by transition matrices. For each symbol 0‘ in alphabet 2, construct a correspon- ding matrix M(o) of 0's and 1'3, with a l in location (i, j) if and only if M(Si-l’ 0') = Sj- The transition matrix specification 1. of the same function M Specified in tabular form in part (a) is as follows: 0 1 0 0 0 1 M(O): 0 1 0 M(1)= 0 1 0 0 _ 1 (c) M may be specified by state diagram. Construct a directed graph with one vertex corresponding to each state, and a directed line or arrow emanating from each vertex for each alphabet symbol. Let the arrow from vertex s.l correSponding to symbol 0 terminate at vertex sj if and only if M(si, a ) = sj. One says in such a case that 0' takes automaton A from state s.l to state 3., or that 0 takes 3.1 to sj. The state diagram specifying the same function M as in parts (a) and (b) is the following: Figure 2. 2.1. State diagram of A = (S, M, so, F) Note that the start state is distinguished with a single arrow entering it from no preceding state, and each state in F is dis- tinguished with two concentric circles. The function M may be extended in obvious fashion to map S x2>' into S as follows. * Definition 2. 2. 2: For any tape x e E , any symbol (7 in Z, ‘and any state s E S, M(s, x0” ) = M(M(s, x), o ). Example 2. 2. 2: We compute M(sO, 101) using each of the specifica- tion schemes of Example 2.2. 1. (a) Using Definition 2. 2. 2 and the transition table for M, we obtain M(SO,101) = M(M(s0, 10) 1): M(M(M(so,1), 0), l) = M(M(sz, 0), l) = M(sz, 1) : sl. (b) In terms of symbol matrices, if we let M(101)= M(l) M(O) M(l), we obtain 0 1 0 M(lOl) = 0 1 0 1 It is easily shown that the matrix M(x) obtained in this fashion for any x in 2* has a 1 in location (i, j) if and only if M(Si-l’ x) = Sj-l' Thus, the 1 in location (1, 2) cf M(lOl) reveals that M(so,101) : 81' (c) Finally, the path obtained by beginning at vertex s0 in the state diagram of A and following in turn arrows labelled 1, O, and l terminates in vertex 81' Thus, all three representations of A show that M(so, 101) = 31. The state behavior of A (i. e. , the sequence of states through which A passes starting from any particular state and in response to any input sequence x from Z ) is completely Spec1f1ed by each of the three representations. So far, no particular significance has been attached to the sub- set F of the state set S. * Definition 2. 2. 3: For each tape x in Z) , for each finite automaton A = (S, M, so, F), A accepts x if M(SO, x) is in F. T(A) denotes the set of all tapes accepted by automaton A. If U is the set of tapes accepted by automaton A, we write A = A(U) to denote that A is an automaton whose set of accepted tapes is U. It is apparent from the state diagram that a tape x is accepted by the automaton of Example 2.2.1 if and only if x consists of a single one or a single one followed by finitely ‘many 0's. Symbolically, x 6 T(A) if and only if x e 10*. Thus, T(A) is described by the regu- lar expression 10*. This is no mere happenstance, for Kleene [6] established that an event U is regular if and only if it is precisely T(A) for some finite automaton A. Thus, there is a one-to-one correspondence between the set of distinct events accepted by finite automata and the set of non-equiva- lent regular expressions. McNaughton and Yamada [12] contributed a procedure for obtaining a state diagram for an automaton which accepts the event defined by a given regular expression, and for writing down a regular expression corresponding to a given state diagram. In neither direction is this correSpondence unique. Once an automaton corresponding to a given regular expression has been obtained, a unique reduced automaton, described in Definitiors 2. 2. 4 7 through 2.2.6, can be obtained. However, there is at present no technique for transforming a regular expression corresponding to a given automaton into some unique canonical form. The regular ex- pression notation adapted in McNaughton and Yamada[12] is used frequently in the present work. One additional notion regarding arbitrary finite automata will be useful. Unless we Specify otherwise, we consider only automata with no superfluous states, i. e. , with no states which are never entered under any input sequence, or which duplicate exactly the behavior of other states. More precisely: Definition 2.2.4: Given the finite automaton A = (S, M, 80’ F), the state s e S is said to be accessible if there is a tape x such that M(so, x) = s. Definition 2. 2. 5: States s.l and Sj of finite automaton A = (S, M, SO F) are equivalent if, for any tape x, M(Si’ x) e F if and only if M(sj, x) 6 F. The motivation for this last definition becomes clearer if we think of A as being able to tell an observer only whether or not it is in a final state, and not what particular state is occupied. For ex— ample, the automaton may emit a "1" if in a final state, a "0" if in a non-final state. If 3.1 and s. are to be distinguishable to an observer under this restriction, then there must be some tape x which takes s.l to a state in F and s. to a state not in F, or vice-versa. Such a tape x, if it exists, is said to distinguish between 3.1 and s.; and if no such tape exists, then 3.1 and Sj are indistinguishable or equivalent. There is a straightforward method for merging a set of equiva- lent states of a finite automaton into one state; and one may simply delete all inaccesssible states from the automaton. The net result is an automaton which accepts the same set of tapes as the original machine and uses a minimal number of states in order to perform this tape-sorting function. Definition 2. 2. 6: The finite automaton A = (S, M, 50’ F) is said to be reduced or minimum-state if all states of A are accessible and no two states of A are equivalent. 2.3. Some Elements of the Algebraic Theory of Automata * With each tape x e 2 we may associate a mapping XA of the state set S of automaton A = (S, M, 80’ F) back into S, according to the rule xA(s) = M(s, x) for each s E S. Since S is finite, there are finitely many such mappings for a given automaton; and we view as equivalent those tapes which induce the same mapping of S into 8. Definition 2. 3.1: If x and y are tapes, then we say that x and y are quivalent and we write x E y if for each s 6 S, M(s, x) = M(s, y). It is clear that E is an equivalence relation. Let [x]: denote the equivalence class containing x e 23*. — N. B. The relation E is due to J. R. Myhill. (See [16] Theorem 1 and related discussion.) We shall occasionally refer to it as "Myhill equivalence. " _ >1< The relation : on E is always defined with reference to a par- ticular automaton, and varies from one automaton to another. For a given automaton, the Myhill classes have the following well-known property. Lemma 2. 3.1: Given A = (S, M, 30, F), the equivalence classes [x] form a monoid under the Operation [x]: [y]: = [xy] :. Proof: If x1 E x and y1 E y, then for each s 6 S, M(s, xy) = M(M(S, X), Y) = M(M(s, x1), yl) = M(s, x1 Y1 ). Hence xy E x1 y1; so the Operation is well-defined. Closure and associativity are Obvious, and [A]: is the identity element. Definition 2. 3. 2: Given A = (S, M so, F), let ”(A) denote the momid of A, generated in accordance with the preceding definition and lemma, i.e., 797m): ({ [at]E },-). We shall occasionally write "[x]" instead of "[x]:" where no misunderstanding is likely. 2. 4. Definite Events and Definite Automata The definitions and notation of this section follow Perles, Rabin and Shamir [14] with a few modifications. 9 Definition 2.4.1: For any tape x, the length of x, denoted by f(x), is the number of symbols from 23 which were concatenated in forming x. Put another way, f(x) = n if and only if x 6 Zn (n a non-negative integer). A tape of length n is an n-tape. Definition 2. 4. 2: If x and y are tapes, x is a subtape of y if there exist tapes u and v such that y = uxv. Tapes u and v are not neces- sarily nonempty. The tape x is a suffix Of the tape y if there is a tape u such that y = ux, and is a proper suffix of y if u f A. If k is a non-negative integer, x is a k-suffix of y if x is a suffix of y and 1(x) = k. The conditions under which x is a prefix, proper prefix, and k-prefix Of y are analogous to the corresponding suffix concepts. Definition 2.4. 3: For any event U and for each non-negative integer k, U is weakly k-definite if for each tape x such that [(x) Z k, x is in U if and only if the k-suffix of x is in U. That is, if f(x) 2 k, it can be decided whether or not x is in U by examining the last k symbols Of x. Note that U being weakly k-definite does not preclude the possibility of U containing tapes of length less than k. Definition 2. 4. 4: For each non-negative integer k, for each event U, U is k-definite if U is weakly k-definite but not weakly (k-l)-definite. Example 2.4.1: If z = {0,1} and if U is the set of all tapes which end * in 01, 101, or 001 (i.e., U = 2 {101, 01,001}), then U is weakly 3-definite, since examination of the last 3 symbols Of any tape x whose length exceeds 3 will reveal whether or not x belongs to U. Indeed, x of length exceeding 2 is in U if x ends in 01, whatever the symbol preceding the final 2-suffix might be. Therefore, U is weakly 2-definite. However, U is not weakly 1-definite, for the tape 0101 is in U but its 1-suffix is not in U. Since U is weakly 2-definite but not weakly 1-definite, U is a 2-definite event. kfinition 2.4. 5: For each event U, U is definite if U is k-definite for some non-negative integer k. 10 We Observe that if U is weakly k-definite, then U is weakly m-definite for any integer m > k, and U is j—definite for some non- negative integerj S k. A k-definite event U may be described by listing both the "Short" tapes of length less than k which are in U and the tapes of length k which are in U; for, any tape x whose length exceeds k is in U if and only if its k-suffix is in U. Thus 11v = U (UflZi) and w = Unz", then U = VUF:::W. i=0 U is evidently regular since V and W are finite. Indeed,if V and W are finite, U is definite, independent of whether W 92" for some positive integer k. One well- known procedure for constructing an automaton A such that T(A)— - U: VUZa W involves constructing two automata, one accepting V and the other accepting Z W. The former construc- tion is straightforward but varied, dependent for its particular form on V. The latter construction may be described in quite general terms, and leads to several results of the next chapter. We there- fore center our attention for the time being on events of the form 2:. W, where Wezk. Definition 2. 4. 6: The event U is purely k-definite if U = 23:5W for some WE 2k Note that if U is purely k-definite, then U is k-definite. Definition 2.4. 7: A finite automaton A is weakly k-definite (k-defi- nite) [purely k-definite] if T(A) is weakly k-definite (k-definite) [purely k-definite]. Perles, Rabin and Shamir [14] showed that the state of a re- duced k-definite automaton is uniquely determined by the k most recent input symbols received, and that an automaton whose state is uniquely specified by the last k inputs is m-definite for sOme positive integer m S k. 11 2. 5. Prefix Automata Perles, Rabin and Shamir [14] detailed the construction, used in Obtaining one of our results, of an automaton which accepts an :1: event Of the form 2 W (WEZk). The resulting prefix automaton (so called because of the method of construction, not because it accepts tapes on the basis of their prefixes, which is not the case) will be denoted by P(E*W). The construction is as follows. Given WSZk, let S = [[A]}L ][[s] : s is a prefix of some y 6 W} be the set of states of P, where A is the null tape and [A] denotes so. Let M : S x 23*» S be defined by M([ s], x) = [u] if and only if u is the longest suffix of sx such that [u] 6 S. Let F = {[w] 6 S : w 6 W} be the set of designated final states of P, i. e. , 3:: given x 6 23 , x 6 T(A) if and only if M([A],x) 6 F. * Example 2. 5. 1: Let U = 2 W, where w = {100, 010}. Then S=={[A],[0],[1],[Ol],[10],[010],[100]}, F ={[010],[100]}, and the mapping M is described in tabular form by * Table 2. 5.1. Next-state function of A(Zl W) M 0 1 so: [A] 101 [1] s1: [01 101 1011 s2: [11 1101 111 s3: 1011 10101 111 s4: [10] [100] [01] 35: [010] [100] [01] 36-.- [100] [0] [01] The state diagram of P is shown in Figure 2.5.1. 12 Figure 2.5.1. State diagram of P(Z*W) 2.6. Output Behavior and State Behavior There are two common formulations which associate an output symbol with each input symbol received by an automaton A. The Mealy model of a finite automaton associates, with each state and in- put symbol, one Of a finite collection of output symbols. One may think of the output symbol as being emitted by A during the transition from a given state to the next state. Such a device is depicted in Figure 2. 6.1. (a). Each transition arrow is labelled with an ordered pair (i, j), where i denotes the input causing the transition andj is the emitted output symbol. The Moore model Of a finite automaton A associates an output 3 ymbol with each state of A, the output symbol correSponding to state 8 being emitted whenever A goes into state 3. Such an automaton is depicted in Figure 2. 6.1. (b). Each state is labelled with an ordered pair (s,j), where 3 names the state and j the output symbol. It is readily seen that, by associating an output symbol 1 with each state in F and a O with each state in S-F, the machine A = (S, M, so, F) is a Moore machine and tape x is accepted by A if and only if, when A is started in s0 and receives x, the final output symbol is a 1. l3 (a) (b) Figure 2.6.1. (a) A Mealy machine, and (b) a Moore machine In either case, the output behavior Of A may be described by listing, for each state and input symbol, the correSponding output symbol. We may, however, be interested only in the way S is mapped into S under various inputs, without regard to tape-acceptance or out- put behavior of A. In particular the next chapter concentrates on state transitions (state behavior), ignoring outputs. 14 3. THE SYNCHRONIZATION PROBLEM: GENERAL RESULTS 3.1. Background and Related Problems Our use of the terms finite automaton, automaton and machine as synonyms beSpeaks the physical world origins which automata theory Shares with much of classical mathematics. The tone of the preceding chapter was mathematical, notwithstanding the occasional use of “machine, " for we spoke there in terms of tables, graphs, functions, sequences and the like. If, for a moment we sharpen our focus on the machine-like aspects of automata, we must admit the possibility of error or mal- function Of the devices with which we are dealing. If our principle concern is with state transition behavior, we see that errors may occur either due to a faulty state transition following correct recep- tion of an input symbol, or to incorrect reception of the input symbol. Continuing the machine analogy, the latter may occur when a burst of noise on the input line causes signal 0.1 to be interpreted as signal .3. (1% 1). Whatever the cause of our ignorance of the state of the automa- ton, an obvious task confronts us: to identify the present state or some future state of the automaton. The former is called the distin- guishing problem, the latter the homing problem. The solutions of the distinguishing and homing problems might be described as follows. Given a finite automaton of known structure but in an unknown state, the observer supplies an input sequence. This procedure is called an experiment. At the conclusion of the ex- periment, the Observer may be able to announce either the state of the automaton at the beginning of the experiment, solving thereby the distinguishing problem, or the state of the automaton at the conclusion of the experiment, solving the homing problem. If the input sequence supplied by the Observer is completely determined before the experiment begins, the experiment is said to be preset; if at some time during the experiment the inputs and cor- reSponding outputs which occurred earlier in the experiment are ex- amined in order to determine the next input symbol, the experiment is said to be adaptive. The experiment is further described as being 15 simple or multiple according to whether it is carried out using one or more than one COpy of the automaton in question. Gill [ 2 ] discusses the solution Of the distinguishing and homing problems by means of preset or adaptive, Simple or multiple experi- ments. Ginsburg [3 ] and Even [ l ] also attack the homing problem. All three authors deal with experiments in which, following each input symbol, the correSponding output symbol is observed, with all or part Of the input sequence and the corresponding output sequence being used to identify the state Of the automaton at the start or conclusion of the experiment. 3. 2. The Synchronization Problem; Algebraic PrOperties of Synchronizing Sequences Our attention shall be confined to automata which undergo cor- rect state transitions. We shall be dealing with a restricted version of the homing problem, in which it is our task to identify the state of the automaton at the end of a preset, simple experiment without either prior information or consideration Of the corresponding output sequence. In effect, we suppress outputs and deal only with Eli—3'3 machines. Throughout the following, let A = (S, M, s , F) be a finite automa- 0 ton over the input alphabet 2. Definition 3. 2.1: The sequence (tape) x is a spnchronizing sequence (tape) for A if M(S, x) is a singleton subset Of S. Such a tape x is said to synchronize A. A is synchronizable if there is a tape x which syn- chronizes A. Put another way, a synchronizing tape x will drive A from an arbitrary unknown state to a unique known state. Several equivalent formulations are immediate and are stated without proof in the fol- lowing result. Lemma 3. 2.1: For any finite automaton A = (S, M, so, F) and any tape x 6 23*, the following statements are equivalent: (1) x synchronizes A. (2) M(s, x) = M(so, x) for all s 6 S. (3) M(s, x) = M(t, x) for all s and t in S. 16 (4) M(T. x) is a singleton for any T; S. The automata represented in Figure 3. 2.1 show that some, but not all, finite automata are synchronizable. A synchronizable automaton has infinitely many synchronizing sequences; for, if x syn- chronizes A, so does wxy for any tapes w and y in 23*. Several questions are thus suggested: What are the properties of the set of all synchronizing tapes for agiven automaton? How can one tell whether or not a given automaton is synchronizable? We first deal with the former question. ca (b) ca Figure 3. 2.1. Automaton (a) is synchronizable, e. g. by 00. Automaton (b) is not synchronizable, since both 0 and 1 permute the state set. Two proofs are supplied for the following result because each introduces notions which will be useful in subsequent work. The first is analytic, the second is constructive. Theorem 3. 2. 2: The set of all synchronizing sequences for A: (S,M,s 0’ F) is a regular set. Proof 1: Let R denote the set of all tapes which synchronize A. For each 5.1 and s. in S = {s . , Sn 1} we define a new automaton All 0’ ° = (S, M, Si, {Sj}) having the same transitions but perhaps not the same start and final state as A. Then T(A..) = [x 6 23*: M(s., x) = 3.] is [J 1 J the event accepted by Aij' l7 n-l For fixed j, Rj : n T(Aij) is the set of all tapes which take i=0 _ every 5 6 S to Sj’ i. e. , is the set of all tapes which synchronize A to Sj' Since Pj is a finite intersection of regular sets, Rj is regular. n-l . Thus R = U Rj’ showing that the set of all tapes which synchro- i=0 nize A is the union Of finitely many regular sets. This completes the proof that R is regular. We could also Show R to be regular by constructing a finite automaton whose set of accepted tapes is R. The construction of one such automaton is straightforward, emulating techniques used by Hartmanis and Stearns [19] and may be considered an alternate proof of the preceding theorem. . Proof 2 (of Theorem 3. 2.2): Given A = (S M, SO, F), let S' = [5.1 : SE? S], Sb 2 S, M'(S.l, x) = M(Si’ x) for each tape x and each 8.16 s', and F = {{s} :s e 5}. Let A' = (S', M', Sb, F'). The following statements are then equivalent. (1) The tape x synchronizes A. (2) For some t 6 S, M(S, x) = [t]. (3) The tape x is accepted by A'. Hence the tapes accepted by A' are precisely the synchronizing tapes of A. By a previously cited result of Kleene l6], T(A') is regular and therefore R is regular. For future use, we formalize the notation introduced in Proof 1. Definition 3. 2. 2: MA = (S, M, so, F) and S = {30’ . . . , Sn-l}’ let 9,; >i< _R_= {x 6 E : x synchronizes A} = {x 6 Z : M(S, x) is a singleton}. For each i (O S i Sn-l) let R.l = {x 6 27*: M(S, x) = Si}. That is, Bi is the set of all tapes which synchronize A to state Si. The synchronizing sequences for a particular automaton A are reflected in the monoid ”(A), as is brought out in the next two theorems. 2: Theorem 3. 2. 3: R.l = {x 6 Z :M(S, x) = $1} is a Myhill equivalence class (see Definition 2. 3.1) Of tapes. 18 Proof: For each s 6 S and any tapes x and y in Ri, M(s,x) = Si = M(s, y). By Definition 2. 3. l, x E y. Furthermore, if z 6 27* and z E x, then for every 3 6 S, M(s, z) = M(s,x) = si; hence z 6 Ri' Corollary to Theorem 3. 2. 3:] R.l 6 W(A). Definition 3. 2. 3: The element b of monoid W is a right zero of if, for each m 6%, mb 2 b. Theorem 3. 2. 4: The tape x synchronizes automaton A if and only if [x]: = [x] is a right zero OfWM). Proof: If x synchronizes A then there is a state 5.16 S such that M(s, x) = si for any 5 6 S. Hence for any y 6 23* and each s 6 S, M(s, yx) = M(M(s, y), x) = Si; so yx 6 [x] = R1. Thus for any [y] 6W(A). [y]] x] = [yx] = [x], and [x] is a right zero of 77(A). Conversely, let [x] be a right zero of WM). Let si 6 S be an arbitrary state Of A. Since A is reduced, there is a tape xi such that M(so, xi) = 51. Because [x] is a right zero of 27(A), [xi][x]: [x]. Hence M(Si’ x) = M(M(so, xi), x) = M(so, xix) = M(so, x). Since 8.1 was arbitrary, x synchronizes A. 3. 3. A Test for Synchronizability; Bounds on the Legth of a Shortest Synchronizing Tape Liu [10] also considered the synchronization problem and pre- sented the next three results with proofs resembling those shown here. Definition 3. 3.1: For any finite set B, let [B] denote the cardinal number of, or number of elements in, B. Definition 3. 3. 2: If TES, the tape x synchronizes T if M(T. x) is a singleton. If s and t are states, x merges s and t if x synchronizes [3, t}. Lemma 3. 3.1: The finite automaton A is synchronizable if and only if for each pair Of distinct states 3 and t in S there is a tape x such that M(s, x) = M(t, x). Proof: If A is synchronizable, there is a tape x such that M(S, x) M(so, x). For any pair of states 3 and t, then, M(s, x) = M(so, x) M(t, x). 19 Conversely, if for each pair of distinct states 8 and t there is a tape x such that M(s, x) = M(t, x), one may proceed as follows. (Recall S: [50,..., SH _1}.) Select xi so that M(sl,1x )2 M(tl, x1) for distinct states 51 and t1 in S. Let M(S, x1) = 52' [SIZI< — n-l, since IS] = n and x1 merges s1 and t1. If I52] > 1, select x2 to merge distinct states 52 and t2 of 82. Let M(Sz, x2) = S3. [S3] 5 n-2, since x2 merged 82 and t2. Proceeding in this fashion, since IS] = n there is an integer k s n-l such that M(Sk, xk) = Sk,r1 and IskHI: Thus M(S, xlXZ' . . xk) is a singleton, and x1. . . xk synchronizes A. Lemma 3.3.2: IfA = (S, M, so, F) and Isl = n, and if the distinct states 31 ani t1 can be merged, they can be merged by some tape x n n 1 such that f(x) 3 [2 . (’ 2 I denotes ''the number of combinations of n things taken two at a time. ") Proof: Let y = 01172. . .crr merge SI and t1. Since 31% t1 and M(sl, y) = M(tl, y), there is a least integer j, 0 < j S r, such that M(sl,crl...0j) = M(tl,01...0'j). Let y' = 01. . .Uj. The symbol-by-symbol effect of y' on states 51 and t1 may be depicted as follows: 0'1 2 (7.]. {81:t1} —> {52:t2} T°°' —> {Sj’tj} 9 {sj+1}: where sif- t.l for 1 Si Sj. If any pair {Sp , tp} is identical to another (unordered) pair (sq, t q} for 15 p < q Sj, then the segment of tape up” crq_1 may be removed from x, since M([sp, t } Up" . U-q 1) = {sq, t } {sp,t tp}. One may Obtain, by performing all such deletions of segments of y' , a tape x which sends {31,1 t } through a sequence of state pairs to {Sj+l} without repetition of a pair. Since there are 3 - 1 pairs Of distinct states different from the pair {81, t1}, f(x) 5 [2 . The desired bound is thus established. A more elegant, though less instructive, proof could be con- structed using the automaton A' of Proof 2, Theorem 3.2. 2. Note 20 that A' has (r21) states corresponding to two—element subsets of S, and that, for each input symbol a and state Si of A', [M(S-l, 0‘ )I S ISiI- Thus state {81, t1} of A' can pass through at most I?) -1 other states without repetition before reaching a state of A' corresponding to a Singleton subset Of S. The next theorem, also due to Liu, is the first of several results which bound the length of a shortest synchronizing sequence for a given synchronizable automaton. Theorem 3. 3.3: IfA (S, M, so, F) is synchronizable and Isl = n, then n A has a synchronizing tape whose length does not exceed (n-l) I2] . Proof: By Theorem 3. 3.2, the tapes x1, x2, . , xk Of the proof of Theorem 3. 3.1 can be chosen so that 1(x-l) S (3] , 1 Si 5k. Since k S n-l, x can be chosen so that 1(x) = 1(xlx2. . .xk) : £(x1)+... + 1(xk) 5(1‘1-1) (3). n Definition 3. 3. 3: Let Liu's bound = L(n) : (n-l) I2] . In the establishment of this and other bounds on the length of the shortest synchronizing sequence of A, several notions recur. We might view the synchronization Of an automaton A as starting with total ignorance of the present state of A, presenting to A a preset sequence, and then being able to announce the exact state of A. Thus we pass from a situation where the state Of A may be any element Of S to one in which the state of A is isolated in a singleton subset of S, by successively reducing the size Of the subsets Of S which might con- tain the present state of A. Since A proceeds from state to state in discrete time steps, we can at any time tduring the presentation Of such an input sequence decide for each state s 6 S, on the basis of input symbols received up to time 1;, whether or not 5 may be the state of A at time t. This partitions S into two subsets; the set of all states which A may be in at time t, and the set of states A cannot be in at time t. We refer to the former subset Of S as the occupied set at time t; the elements thereof are occupied states. Note that at any time the occupied set is the smallest subset of S known to contain the state of A at that time. 21 For the sake of brevity, let ”0" be an abbreviation for the phrase “the occupied set. " Note that 0 does not denote a fixed subset of S, but rather a set which may change as A receives inputs. The following example illustrates the concepts just described. Example 3. 3. 1: If an observer is presented with the automaton A of Figure 3. 3.1 and has no information concerning its present state, then O = S = [80, SI, 32’ s3}. Figure 3. 3.1. State diagram Of A If an input 0 is supplied, M(S, O) = {$1, 52, 33}. That is, O becomes {81, s2, s3}. A 1 input then changes O to {32, 33}. Since 0 and 1 permute [32, $3}, the occupied set remains [52, 83} under all subsequent inputs. Definition 3. 3. 4: If Pgs and the tape x has the prOperty that IM(P. XII < lP P does not necessarily contain M(P, x).) , x is said to produce a contraction in P. (Note that Thus Lemma 3. 3. 2 established that, if Isl = n and lol > 1, lOI can be reduced by some tape Of length not exceeding Igl . The application of this result at most (n-l) times will reduce lOI from n to 1, as in Theorem 3. 3. 3. We now establish a second bound on the length of a shortest syn- chronizing sequence of A. Theorem 3. 3.4: If A is synchronizable and lSI = n, then A has a syn- chronizing sequence whose length does not exceed 2r1 - n-l. 22 Proof: Recall the automaton A' of Proof 2, Theorem 3. 2. 2. Synchro- nizing A is equivalent to driving A' from s'0 to one of the states {SJ}. corresponding to a singleton subset of S. A' has 2n states, n of which are of the form {Sj}. Without entering the same state twice, A' can undergo at most 2r1 - n-l state transitions before entering one of the states {Sj}’ since A' initially occupies the state Sb = S. Definition 3. 3. 5: Let B(n) = 2n -n-l for integers n ->— 1. Theorem 3. 3.4 could also have been proved noting the following. NO portion of a Shortest synchronizing sequence x = 0 0' maps an occupied set onto itself. Therefore 0 takes S prOperlylintor S, so that following the application of 0’ l’ IOI S n-l. If IOl = n-l, there are (xi-l] subsets of S which may be occupied before an input symbol again reduces the size of the occupied set; hence at most Infill) input symbols are required to make lOl S n-2. In general, if lOl = k, n a k > 1, then no more than [12] symbols are required to make lOl Sk-l. A szhortest synchronizing sequence, then, has a length not exceeding .2 [3;]: 2n - n-l. J:n The point cf this discussion is not to verify the bound established in Theorem 3. 3. 4, but rather to point out the bound on the number of symbols required to reduce IOI from k (n E’— k > 1) to something not exceeding k-l. These step-by-step reductions of lOl are different from those Of Liu's bound (Results 3.3.1 through 3. 3. 3), which guar- antee that lOl can be reduced by merging two occupied states, using at most (21] symbols. The bound B(n) can be realized for n = l, 2, and 3 as is shown in the following example. Thus B(n) is the best possible bound for n = l, 2, 3. Example 3. 3. 2: (a) n = l. B(l) = 21 -1-1 = O. Trivially a one-state automaton is synchronizable by any sequence x such that [(x) Z O. (b) n = 2. 13(2) = 22 - 2-1 = 1. If a two-state automaton is syn- chronizable, the minimum length of a synchronizing sequence is one. The state diagram Of Figure 3. 3. 2 depicts such an automaton. 23 Figure 3. 3. 2. A two-state, synchronizable automaton (c) n = 3. B(n) = Z3 - 3-1 = 4. 0110 is a shortest synchronizing sequence for the automaton of Figure 3. 3. 3. Figure 3. 3. 3. A three-state automaton requiring four symbols for synchronization The action of 0110 on the state set (a, b, c} is shown in Figure .3. 3. 4. a b c a O l 1 O b...___>. c _———)- a ———>- b ——-—>vb c Figure 3. 3. 4. Action of the sequence 0110 on the state set of the automaton of Figure 3. 3. 3. 24 The bound B(n) : 2n - n-l is better than Liu's bound L(n) : (n-l) I21] for n S 7, while Liu's bound is lower for n > 7, with the difference between bounds increasing rapidly as n increases. Table 3. 3.1 on page 27 lists values Of B(n) and L(n) for l S n 510. We now make one more approach to bounding the length of a shortest tape which synchronizes an n-state automaton. Following two preliminary results (Lemmas 3. 3. 5 and 3. 3. 6), we establish a new bound on the length of tape necessary to reduce lOl (Lemma 3. 3.7). The results of these three theorems are incorporated into the bound of Theorem 3. 3. 8. Lemma 3. 3. 5: If A is synchronizable with n states and lOl = n, there is an input symbol which reduces lOl. Proof: If A is synchronizable, every pair of states 5.1% t1 in S can be merged by some sequence x = (r . . . 0‘ r’ with no proper prefix of 1 l xl merging s1 and t1. Thus if M(sl,crl...crr_l) = 82 and M(t1,01...0'r_1) = t2, then 82 7-1 t‘2 and M(sl,0'r) = M(sz,or). If lOl = n, then lM(S,Ur)l < n; i.e., or reduces lOl. Theorem 3. 3. 6: In a synchronizable n-state automaton A, if IOI = n-l, three symbols are sufficient to produce a contraction in O. Proof: There is a pair [51, 32} Of states which will merge under one (prOperly chosen) symbol. If O contains such a pair, then one sym- bol will yield a contraction. If O contains no such pair, then either 31 )t’ O or 52 f 0. Since A is synchronizable, there is an input sequence which will bring {31, 52} into 0. There are only two choices of O for which [31, 82} 6 O; and since one of them is currently O, at most two sym- bols are required to (perhaps) first change O to the other configura- tion and then to a configuration which contains [51, 32}, upon which a third symbol merges s1 and 32, producing a contraction in O. Pursuing the ideas of the preceding proof we obtain the following. Lemma 3. 3. 7: In a synchronizable n-state automaton A, if 2 S lOI = p Sn-Z, then [B] - [3:2] + 1 symbols (prOperly chosen) are suf- ficient to produce a contraction. 25 Proof: There is a pair [81, $2} of states which merge under one pro- perly chosen input symbol. If this is the only such pair in the state set cf A, there are 3:2 ways for this pair to lie in O, with the remaining (p-Z) states in O being chosen from among the n-2 states different from $1 and 32. There are [3] choices of O for which lOI = p. Thus there are n-2 [B] - [p-Z choicps of O for which IOI = p and {$1, 82} $0; hence n— at most [8] - p-Z + 1 symbols are required to bring O to a con- figuration containing {31’ 32} and then merge SI and 32. The proof is now complete . In the preceding proof, if [31, 32} is not the only pair of states which merge under one symbol, a contraction may be produced using fewer than [B] - [3:2] +1 symbols. Using “the preceding results, we construct a new bound on the length of the shortest synchronizing sequence for a synchronizable n-state automaton. Theorem 3. 3. 8: If A is an n-state synchronizable automaton (n ->— 4), a shortest synchronizing sequence for A has length not exceeding n-2 C(n) = 1 + 3 + .22 Engjl - Int-115122I + l] J: - Proof: The first two terms are consequences of Lemmas 3. 3. 5 and 3. 3. 6, respectively. The summation over 2 Sj S n-2 yields tie terms corresponding to IO] = n-2, n-3, n-4, . . . , 2, in that order, as derived in Lemma 3. 3. 7. These observations comprise the proof. A form of C(n) more suited to computation is C(n)=3n-2+3 z ’j§-, n24. Values of C(n) for l S n S 10 are listed in Table 3. 3.1 on page 27. Examination Of Table 3. 3. 1 reveals that no one of the three bounds L(n), B(n), C(n) is least for all values of n, 1 S n S 10. Each bound was arrived at by examining in a particular way the reduction of lOI from p to some value not exceedinga p-l (n 2 p > 1). These ex- . . . n n) (n n- . am1nations y1elded [pl , I2 and [pl - [p-Zl + 1, respectively. 26 In Table 3. 3. 2 on page 28, we make a term-by-term compariscn of the bounds L(n), B(n) and C(n), each term being the number of symbols sufficient to reduce lOl . Since a best bound has been achieved for n < 4, by L(n) and C(n), we concern ourselves in Table 3. 3. 2 only with n 2 4. Table 3. 3.1. A comparison Of bounds on the length of a shortest synchronizing sequence for an n-state (synchronizable) automaton n B(n) L(n) C(n) .Minsum(n) D(n) DIIn) l O O O - .. .. 2 l l l l l l 3 4 o 4 4 4 4 ll 18 10 10 ll 10 5 26 40 22 22 24 22 6 57 75 46 44 45 42 120 126 94 79 76 72 247 196 184 130 119 114 502 288 382 200 176 170 10 1013 405 748 292 249 242 27 Table 3. 3. 2. A term-by-term comparison of L(n), B(n). C(n), and D(n). Each column heading L, B, C, and D identifies source of all terms in that column. No. symbols to No. symbols to reduce IO reduce IO I n kol B 1. c D kfl B 1. . C D 4 4 1 6 1* 1 5 56 28* 37 19** 3 4 6 3* 4 4 70 28* 56 23*xi 2 6 6 6* 6 3 56 28* 51 26**‘ 5 5 1 10 1* 1 2 28 28* 28 .28 4 5 10 3* 5 9 1 36 1* 1 3 10 10 8* 8 8 9 36 3* 9 2 10 10* 10 10 7 36 36 16* 16 6 6 1 15 1* 1 6 84 36* 50 22** 5 6 15 3* 6 5 126 36* 92 27** 4 15 15 10* 10 4 126 36* 106 31** 3 20 15* 17 13* 3 84 36* 78 34** 3 15 15* 15 15 g_ 36 36* 36 36 7 7 1 21 1* 1 10 1 45 1* 1 6 7 21 3* 7 9 10 45 31* 10 5 21 21 12* 12 8 45 45 18*. 18 4 35 21* 26 16*‘ 7 120 45* 65 25** 3 35 21* 31 19** 6 210 45* 141 31** 2 21 21* 21 21 5 252 45* 197 36** 8 8 1 28 1* 1 4 210 45* 183 40*’ 7 8 28 1* 1 3 120 45* 113 43** 6 28 28 14* 14 2 45 45* 45 45 A single asterisk is used in Table 3.3.2 to indicate, in each row, a minimal entry among columns B, L, and C. Each entry in these columns is valid for an arbitrary synchronizable automaton. We may therefore select the least entry in each row for a given value of n and sum these least entries to Obtain a new bound, Minsum(n), on the length Of a shortest synchronizing sequence. Minsum(n), 1 S n $10, is entered in Table 3.3.1 for ease of comparison with other bounds. 28 We note that, at least within the SCOpe of Table 3.3.2, Minsum(n) may be obtained by using the last (n-4) terms of L(n) and the first three terms Of C(n). This observation holds for all n 2 4, as we shall now ve rify. Theorem 3. 3. 9: For all n 2 4, each of the first three terms of C(n) is less than or equal to the correSponding term Of B(n) or L(n). n Proof: The first terms Of B(n), L(n), and C(n) respectively are 1, I2] and 1. The theorem thus holds for the first terms Of the three series. n n The second terms of B(n), L(n) and C(n) are In-lI . 12] and 3, -1 respectively. For n 24, (11131) = n >3 and I2] = 2921—) 2 6 > 3. n The third terms of B(n), L(n) and C(n) respectively are In—ZI, I21) and In- 2]- In- 4) + 1. For all integers n > n1, In-ZI— - I2 r1I. For all (I (n 2 )2 2) (n- 2)(n- 3) - 2 n>4, 2-[Inn:=ZI-n4+l] n-n4-lz2 l: 2 .2;le = 0. Hence I2I>Inn21 111:2 4 + 1 for n >4. This czoncludes the proof. Theorem 3. 3.10: For n 2 5 and for all integers j such that 4 Sj S n-l, the jth term Of L(n) does not exceed the corresponding term Of B(n) or C(n). Proof: For 4 Sj S n-l, the j th terms of B(n), L(n) and C(n) are res- pectively In -,!:i+1I IE] and Ij-l] -Ilj:2 For the values ij being considered, 3 Sj- -1 Sn- 2; and so Inr1 2+]: I121] SIjElI = In-S'IHI for all such j. That is, the jth term of L(n) does not exceed the jth term of B(n). Still bearing in mind 3< _j- -1 S n- 2, we have the following: 29 jth term of C(n) : (fill) -G1:12) + 1 .(j-l) factors; largest is (n-Z). : n(n-l). . . (nj+2) _ (n-2)(n—3)...(n-fi (j-l)! (j-l)! (j-Z) factors; largest Sn-Z. K’— j-l factors; smallest 2 3. Z nLn-lzj;[)('n-L-Z_L _ 1 + l k _ (j-Z) factors; smallest : 2. The proof is now concluded. One might wonder at this point what the lower limit of such bounds for arbitrary synchronizable automata might be. The question is partially resolved by the existence Of a class of automata in which an n-state machine requires (n-1)Z steps for synchronization. The construction is as follows. Let E = [0,1] and S = [$1, . . . , Sn}. Let the input 0 take 81 and 52 to 82, fixing S3, . . . , Sn; let 1 permute the state set cyclically, sending s-l to si+1(l Si 5 n-1) and sn to 51' The shortest synchronizing sequence for such an automaton is (Oln'l) “'20; and 1[ (01n'1)n'20] = (n-2)(n) + 1 = n2 - 2n +1 -_- (n-l)2. The assertions of the preceding paragraph are made without proof. The two automata of the following example are Offered as supportive evidence. A useful notion, that of the synchronization tree of a synchronizable automaton, is also introduced in Example 3. 3. 2. The tree is read from top to bottom; the path labelled with 0' and emanating from vertex Sig-:8 leads to M(Si, o ). Other features Of the tree are pointed out within the example. Example 3. 3. 2: Let An be the n-state automaton described above, with next state function Mn. 30 (a) n=3 Table 3. 3. 3. Transition table for A 3 M3 0 1 31 82 s2 82 82 83 83 83 s1 TO avoid crowding, the subscripts of the 8.1, with the letter s omitted, are shown at each vertex. 123 I I 0 l 2 3 (l 2 3) I Z Closed curve indicates 0 1 I “this set Of states 3 l appeared higher in the I tree.” 0 1 I 1 2 R ectangle indicate 8 ”synchronization I has occurred. " b 1.2] ® Figure 3. 3. 5. Synchronization tree for A3 Inspection of the tree shows that, for n = 3, earliest synchroni- zation occurs under 0110 = (012)10 = (013'1)3'20. 31 (b) n=4 Table 3. 3. 4. Transition table for A 4 LA4 0 1 s1 82 S2 52 S2 S3 S3 S3 S4 S4 S4 s1 1 2:54 1 | 0 1 274 m 0 1) 2 3:1 1 3 4 I IO 1| @ 174 I 0 1 l 2 4 1 2 3 I I _ I o 1] l0 1 «‘ilfl» 1 3 2 3 (ilila 1 ' 1 (2 i)0 li‘illl -’2 3 O 1 314 I 0 1 I 1 4 ® I I 0 1 I 12 IO 1 I E? Figure 3. 3. 6. Synchronization tree for A4 Thus for n = 4, synchronization occurs first under 011101110 = ((0114‘114‘20. 32 The preceding example Shows that, for a given n21, the best bound on the length of shortest synchronizing sequences for n-state synchronizable automata cannot be less than (n-l)2. It should be noted in connection with Example 3. 3. 2 that construction of a synchroniza- tion tree for an arbitrary automaton, with each path leading to a vertex which appears earlier in the tree being terminated, constitutes a bounded experiment to determine whether that automaton is synchro- nizable. The functions L(n), B(n), C(n) and Minsum (n), for example, bound the number of steps from the tOp Of the tree within which syn- chronization will occur if at all possible. 3. 4. Synchronization Bounds for Several Classes of Automata The bounds which were established in the preceding section for the length Of a shortest synchronizing sequence are valid if no infor- mation is available concerning the automaton in question, save that it is synchronizable. Placing conditions on the automaton yields tighter bounds, as one would expect. We examine two restricted classes of automata in the present section. Liu's bound L(n) was predicated on the fact that any two states which can be synchronized can be merged by some tape of length not exceeding [[21 (see Lemma 3. 3. 2). If an automaton has a pair of states requiring exactly I?) symbols for synchronization, additional information emerges concerning synchronization of the automaton and is set forth in the following results. Theorem 3.4.1: If the n-state automaton A has a pair of states which n require I2] symbols for synchronization, then (1) A is synchronizable, and n (2) for each integerj such that 1 Sj S (2) there is a unique pair Pj = I: s-lj, Sk-} of states of A which requires j symbols J for synchronization. n Proof: (1) Let plgl denote a pair of states requiring I2] symbols for synchronization. Then p n is carried through all remaining state pairs {3, t}, S 7! t, before a singleton set of states is reached. If n x = 010' 2' . .0 (n is a sequence of length I2) which synchronizes p63) to s, and if we let M(p .0)=p :M(p .U)=p . (‘2‘1-1 1 (3)-1 (31-1 2 (31-2 33 n then the set of all I2] pairs of distinct states is enumerated in the list (8 -,-' PP): [3(3) 1. . . . p2, p1. Every pair is synchronizable, since M(p 2 - Uj+10j+2' . . 0' ) = sj; therefore A is synchronizable. (2) In the listing p . , p 22, 2, p1, the pair pj requires j or fewer symbols for synchr nization. Thatj symbols (prOperly chosen) are sufficient was shown in Part (1) of this proof. If h symbols, h Sj, will synchronize pj, then ([21) -j + h symbols will synchronize p n , contrary to hypothesis; therefore j symbols are required to synzchro- nize pj. The proof is now complete. n In the event that some pair Of states Of A requires I2) symbols for synchronization, the preceding result yields a bound on the mini- mum number Of symbols which will synchronize A. Theorem 3. 4. 2: If the n-state automaton A has two synchronizable n states which require I2] symbols for synchronization, then the shortest sequence which will synchronize A has a length not exceeding j;%2[ Isl-1%) +1] = D(n). Proof: If IO] = k, where O is the occupiked set of states and 2 S k Sn, then there are represented in O exactly (2) pairs of states from the exhaustive list p(n), . . . , pl Of the proof of Theorem 3. 4.1. Among the 2 n k pairs of states in 0, there is a pair requiring no more than \2 - I2I+ 1 symbols for synchronization, since in the most extreme instance the pairs of states in O are exactly the first I2 pairs in the list p n . . . p1 of all pairs Of states. Thus to change lOl successively from n to 1, assuming the worst case where IOI decreases by one at each contrac- . n : tion, requires at most _2 2 [ I21)-IJZI + 1] symbols. This is the desired . J = conclus ion. For the sake Of comparison, terms Of D(n) (n 54 S 10) are entered in Table 3. 3. 2 on page 28. A double asterisk ("**") indicates those terms Of D(n) which are less than the corresponding terms (marked with "*" in Table 3. 3. 2) of Minsum(n). The terms of D(n) 34 are valid only under the hypothesis "some pair of states of A requires 12] symbols to merge, " while the terms of Minsum(n) are valid for any synchronizable automaton. For each n, we ‘may thus obtain a new bound D1(n) for this restricted class Of automata by selecting, for each value of IOI, either the correSponding Minsum(n) or D(n) term, whichever is less. Values Of D(n) and the improved bound D1(n), 1 Sn :10, are entered in Table 3.3.1. Lest it be thought we Operate in a vacuum when we speak of n-state automata having a pair Of states requiring I21] steps for their synchronization, we Observe that the machines of Example 3. 3. 2 are such devices. More formally, keeping in mind that each integer n > 1 has a representation of the form 2k or 2k + l, where k is a positive integer, we have the following result. Theorem 3. 4. 3: Let A be an automaton with state set S = [sl,sz,..., Sn}, lSl = n > 1, over the alphabet Z = {0,1} such that M(sl, 0) = $2, M(sj, 0) = sj for 2 Sj Sn, and M(Sj, l) = s for 1 Sj Sn-l with j+1 M(sn,j) = 81. If n = 2k or n = 2k+l, then [32, Sk+2} is a pair of states ' 1'1 requiring I2] steps for synchronization. Proof: The state diagram of such an n-state automaton is supplied (Figure 3. 4.1) in order that the proof may be carried on in visual, rather than symbol-manipulative, terms. In the diagram, @corres- ponds to sj. Figure 3. 4. l._ State diagram of n-state automaton requiring (n-l)2 symbols for syn- chronization 35 Examining the state diagram, we see that the only instance in which an input will alter the relative positions of two states on the circle occurs when one Of those states is 51 = 1 and a O is received. In such an instance, the counterclockwise “distance" between the two states, starting with s2 = 2 = M(Sl, O), is one less than the corres- ponding distance before the input 0. For n = 2k+1, Figure 3. 4. 2 depicts the synchronization Of the pair {2, 2k+2} : {$2, Sk+2}' k+2 [Starting pair y 2 2 1 3 l 1 k+1 1 k+2 1 k+3—‘2 Total input in this line k+2 k+3 n 1 2 ‘S 1’ k+3 1 k+4 1 1 n 1 1 0 2 Total input in this line 2 “" 3 -_" ‘_" k—”k+1 ITZI > andf(w.)< 0 and ITkI = 0; hence wle' . .Wk = w synchronizes A; and 1(w) : k-l k-l k-l n-l . n z l(w.)S z (lSI-lT.l)= z (n.-IT.l)s:: [=(2). The jzl J jzl J J21 J [:1 desired bound is thus established. The bound established in Theorem 3. 5.4 can be realized for arbitrary n by allowing IE] = n-l. This will not be proved here, but the following instances for n = 5 and n = 6 suggest a scheme for generating an example for arbitrary n. Example 3.51 (a) n=5. (2]:1. z:{0,1,2,3}. Figure 3. 5.1. A 5-state automaton requiring : 10 symbols for synchroniza- tion A shortest synchronizing tape for the automaton of Figure 3. 5.1 is 0102103210, with length 10. (b), n=6. 61:15. >:={0,1,2,3,4}. 39 Figure 3. 5. 2. I?) 6-State automaton requiring 2 = 15 symbols for synchroni- zation. A shortest synchronizing tape for the automaton of Figure 3. 5. 2 is 010210321043210, with length 15. 40 4. SYNCHRONIZABILITY OF PARTICULAR CLASSES OF AUTOMATA, WITH CHARACTERIZATIONS OF THEIR SYNCHRONIZING TAPES In the present chapter we examine several classes of automata, establishing conditions under which an automaton in a given class is synchronizable and characterizing, for such a machine, the set Of all sequences which synchronize it. We begin with definite automata as treated by Perles, Rabin and Shamir [14] and then take up in turn the ultimate-definite and reverse ultimate-definite automata of Paz and Peleg [ l3]. Lastly, a new form of regular event emerges quite naturally. It turns out to be a specialization Of events of Paz and Peleg; we close the chapter with a treatment of some Of its properties. Although several early results in the chapter are later lumped into one, and a theorem occuring within the chapter subsumes some earlier results, the presentation here is meant to preserve a spirit of discovery which is among the earliest casualties of a more terse style. 4.1. Synchronization of Definite Automata Perles, Rabin and Shamir (I 14], Theorem 2) showed that the state of a reduced k-definite automaton depends only on the past k input symbols. Thus such a machine A = (S, M, so, F) is trivially synchronizable; for, any sequence x such that f(x) 2 k has the property that, for any 5 6 S. M(so, x) = M(S, x). We have shown the following. Lemma 4. 1.1: If A is any reduced k-definite automaton and x is a tape such that 1(x) 2 k, x synchronizes A. The preceding result Of course applies to the smaller class of purely k-definite automata A(ZI*W), where WEEk. We narrow our attention to the latter class for the time being. The next example reveals that such automata may have synchronizing sequences Of length less than k. Example 4.1.1: Let w1={ 100,101,001}§—:23, where 2: = {0,1}. The prefix automaton P(2*W1) (see Chapter 2, section 2. 5) is depicted in Figure 4.1.1. 41 0 I l / 0 1 O" O 1 O. @D" ®-@ \ 0 g 1 0 o o :5: Figure 4.1.1. State diagram Of A(Z W1) The synchronizing tapes for P are 10, 11 and any tape whose length exceeds 2. Note that, by its very construction, the prefix automaton Of a purely k-definite event is synchronized by any tape Of length not less than 4k. In addition to such tapes, the automaton of Example 4. 1. 1 has the shorter synchronizing tapes 10 and 11, and neither Of these is a 2-suffix of a 3-tape in WI. Theorem 4.1. 2: If f(x) = k-l, x is a synchronizing sequence for 315 P(2 W) (w sz) if and only if x is not a (k-l)-suffix of any k-tape in W. Proof: (Necessity, by contraposition) If 1(x) = k-l and x is a suffix of some y = 010' 2. . .O'k 6 W, then [0'1] is a state Of the corresponding prefix automaton P (see Chapter 2, section 2. 5), as is [A]; hence M([O‘l],x) = [y] with 1(y) = k, and M([A],x) = [t] with f(t)Sk-1. Therefore x is not a synchronizing sequence for the prefix automaton P(2‘.*W). Since [A] and [01] are distinguishable states (by the tape 0' 2. . . 0k), both are also states of the reduced version Of P(23 W). The same may be said for states M([ A], x) and M([o l], x). Therefore a]: x fails to synchronize the reduced automaton A(E W). 42 (Sufficiency) If f(x) = k-l and x iS not a (k-1)-suffix of any y 6 W, consider any [w] 6 S such that w ;L’ A. Now M([w], x) = [u] if and only if u is the longest suffix of wx such that [u] 6 S. The length of u does not exceed k-l; for, if [(u) = k then x is a (k-l)-suffix of the tape u 6 W, contrary to hypothesis. Since f(u)Sk-1, u is a suffix Of x and is the longest suffix of x such that [u] 6 S. Since [w] was arbitrary except for the restriction w 7.1 A, M([w], x) = [u] for any [w] 6 S such that w 7! A. Finally, M([ A], x) = [v] if and only if v is the longest suffix of Ax = x such that [v] 6 S; hence v = u and for any [w] 6 S, M([w], x) = [u]. That is, x synchronizes P(Z*W). CorollarLto Theorem 4.1. 2: If 1(y) S k-l and y is a synchronizing * sequence for P(Z W), then y is not a subtape of a (k-l)—suffix of any tape in W. Proof: (By contraposition) If y is a subtape of a (k-l)-Suffix of some tape in W, then there exist tapes t and u such that tyu is a (k-1)-Suffix * Of a tape in W. By Theorem 4.1.2, tyu does not synchronize P(23 W); hence y does not synchronize P. The proof is complete. One might conjecture that, if 1(y) Sk-l and y is not a suffix of any tape in W, then y synchronizes P(E*W). This is not the case; for, if W = {000, 100, 010], investigation of P(Z‘.*W) reveals the "short" synchronizing sequences tObe 01, 11 and no others. Although 1 is not a suffix Of any tape in W, 1 fails to synchronize P. The precise con- ditions under which a tape Of length Sk-l is a synchronizing tape for P(E*W) are suggested by the above corollary and verified in the next result. Theorem 4.1. 3: If 1(y) Sk-l and y is not a subtape of any (k-l)-suffix a): of a tape in W, then y is a synchronizing sequence for P(Z W) = (S, M, so, F). Proof: (Notation: If 0. is a description of a prefix of a tape in W, let [0.] denote the corresponding state in S.) Recall that, for any tape y, M([A], y) = [longest suffix Of y which is also a prefix of some w 6 W], and, if [x] 74 [A], M([x], y) = [longest suffix of xy which is also a prefix of some w 6 W]. Now suppose y 43 meets the hypothesis of the present theorem. If M([ x], y) = [vy] for some v 75 A, then [(vy) S k and y is a subtape of the (k-l)-Suffix of some tape ryz 6 W, since vy must be a prefix of a tape in W. This is contrary to hypothesis. Therefore v = A, and M([x], y) : [longest suffix of y which is a prefix of some w 6 W] = M([A], y), for any [x] 7! [A]. Hence y syn- chronizes P(Z*W). The preceding theorems and corollary are summarized in the following statement. Theorem 4.1.4: If W Ezk and only if y is not a subtape of any (k-l)—suffix of a tape in W. 3:: , then the tape y synchronizes P(Z W) if An alternate form, based on previously defined terms, is the following. Theorem 4.1. 4-a: If WEEk, then y is a synchronizing sequence for A(Z¥W) if and only if y is not a prefix of any prOper suffix Of a tape w 6 W. This formulation, which matches nicely the statement of a later result, was not used in the preceding develOpment due to a feeling that ”subtape of a (k-l)-suffix" conveys a more vivid mental picture than "prefix of a prOper suffix. " The two notions are equivalent. Save for Lem'ma 4. l. 1, the results of this chapter have been stated and proved in terms of prefix automata. Not every prefix automaton is reduced; for instance, states [001] amd [101] Of Example 4. 11 are equivalent. Certainly each tape which synchronizes a given prefix automaton P also sychronizes the reduced version, P', thereof. The question is: Are there sequences which synchronize the reduced machine P' but which fail to synchronize the k-definite prefix automaton P because of its extra, redundant states? 3:: Theorem 4. 1. 5: Let A(E W), WEZk, be the reduced automaton :1: whose set of accepted tapes is Z W. The tape x synchronizes A if and only if x is not a prefix of a prOper suffix of a tape in W. Proof: We establish the contrapositive of the theorem. If x fails to synchronize A, there are states 51’ 82 6 S such that; M(Sl= x) ,4. M(sz, x). Since A is reduced, there are tapes v1 and v2 44 such that M(SO, v1) = 31 and M(So, v2) = $2; hence M(SO, le) )5 M(so,v2x). Again because A is reduced, there is a tape 2 which distinguishes between M(SO, le) and M(SO, vzx). Without loss of generality, suppose M(SO, lez) 6 F and M(SO, vzxz) f F. Since A is k-definite, the proceeding statement implies f(xz)Sk-1; so the k-suffix of lez is a tape in W in which x is a pre- fix Of a prOper suffix. The contrapositive d the reverse implication in the theorem is now established. Conversely, if x is a prefix of a prOper suffix of a tape w 6 W, suppose w : zxy (z ;5 A). Then M(SO, xy) 6’ F, Since every tape accepted by A must be at least k symbols in length;and M(SO,zxy) 6 F. Thus xy fails to merge s0 and M(so, z), as does x; therefore x fails to synchronize A. The contrapositive of the forward implication in the theorem is now established, and the proof is complete. We have shown that the set of sequences which synchronize the =I< reduced automaton A(ZI W) is precisely the set of synchronizing >I< sequences of the prefix automaton P(Z W), where W Ezk. 4. 2. Ultimate Definite, Reverse Ultimate-Definite and Symmetric- Definite Automata Paz and Peleg [13] generalized the notion of a purely k-definite event and considered several closely related forms of events as follows. Definition 4.2.1: The event PET-2" is ultimate-definite if and only at: 31‘ if there is an event Q Q23 such that P = 23 Q. * The event PEZ is reverse ultimate-definite if and only if Pr is ultimate-definite. (The set of tapes obtained by reversing all tapes in P is denoted by Pr.) The event FEE):< is gymmetric-definite if and only if there are events O, R§Z* such that P = QZ*R. [Note that P, Q and R need not be finite or even regular. ] The authors define a representation 2*0 of the ultimate-definite event U to be canonical if and only if no tape in Q is a prOper suffix of another tape in Q. A constructive procedure for Obtaining such a representation is used to prove the following theorem. 45 Theorem 4. 2.1: (Paz and Peleg) If P is ultimate-definite, then P has a unique canonical representation. We omit the proof of the theorem, but Show the construction of the canonical form. Let P0 = P020, and for each non-negative . J . integer j, let pj+1 = PnZJ'H - kLJO EJ+1"k Pk. That is, PO is the set of all tapes in P of length zero, P1 is the set of all tapes in P of length l which do not have as suffixes any tape in P0, pj+l is the set of all tapes in P of length j+1 which do not have Suffixes oo in Pj, Pj_1, . . . , PO. Finally let Pt = L0) Pj. Thus Pt is a listing of all tapes in P which do not have as proper suffixes other tapes in P. In the case of a purely k-definite event P = 23*Q(Q‘:-_-_Zk), it is evident that Pk = Q and, for jck, Pi = (I) . Thus 2*0 is the canonical form Of the purely k-definite event P. Definition 4. 2. 2: Let ZIPt denote the canonical representation of the ultimate-definite event P. It was noted earlier that P = 2*0 being ultimate-definite does not require Q to be finite or even regular. For example, if Ql = [10p: p is a pos*itive prime integer}, 0] is a well- known non- regular set, and P1: 2*01 is not recognizable by any finite automaton, hence is allso non- regular. (The truth of the latter assertion is evident if one observes that such an automaton would be able to recog- nize the set Of positive prime integers, a task beyond the capabilities of a finite- state device.) In contrast, if Pz- — 2* 02 where OZ: [in: p is a positive prime integer]; 02 is not regular but P2 cortains 00 and any tape in 2* Q2 is in Z 00:2 Therefore P2: 2 00 and is regular. Thus Q non- regular and P: 2* Q may yield either a regular or non-regular P. . However, Paz and Peleg [13] showed that the regularity or non- regularity Of an ultimate-definite event P is reflected in the canonical :1: representation 2 Pt. Theorem 4. 2. 2: (Paz and Peleg) If P is a regular ultimate-definite event with canonical representation ZIPt, then P1: is regular. 46 This result, coupled with the Observation that Pt being regular >:< implies 23 Pt is regular, establishes regularity Of Pt as necessary and sufficient for regularity of P : 2*Pt. A canonical form for reverse ultimate-definite events is now stated in terms of that of ultimate-definite events. Definition 4. 2. 3: The canonical representation of a reverse ultimate- definite event P = 02* is denoted Qt2* and is defined to be the reverse of the canonical representation of Pr. Thus if P = 02*, the canonical form of P is Obtained as follows: Pr = (02*)r = 2*Er = 23* (Or)t, the last expression being the unique canonical representation for the ultimate-definite event Pr. The canonical representation of P, then, is (2*(Qr)t)r = ((Qr)t)r2*. It is readily seen that uniqueness of the canonical representation Pr = E.‘.*(Qr)t of the ultimate-definite event Pr renders ((Qr)t)r2* the unique canonical representation of P, and also that 02* is the canonical representation of P if and only if no tape in O is a prOper prefix of another tape in Q. We now consider finite automata corresponding to regular events of the formsjust discussed. Definition 4. 2. 5: The finite automaton A = (S, M, so, definite (reverse ultimate-definite) if and only if T(A) is ultimate- F) is ultimate- definite (reverse ultimate-definite). 4. 3. Synchronization of Ultimate-Definite Automata We have shown (Lemma 4.1.1 -- Theorem 4. 1. 5) the existence and characterization of synchronizing sequences for purely k-definite automata A(Z*W), ng. Recognizing that such automata are a special class of ultimate-definite automata, we turn now to an investi- gation of the latter class. The proof of the theorem characterizing synchronizing sequences for purely k-definite automata made extensive use of the k-definite properties, i. e. , of the facts that tapes were accepted or rejected on the basis of their last k symbols, and that the state Of the corresponding automaton was determined by the last k inputs. The general proof, below, makes use of the canonical form for ultimate-definite events 47 >'.< p, and is valid whether the event 1=>t such that p = 2 pt is finite or infinite. >,'< Theorem 4. 3.1: If 2 Pt is regular, then the tape x synchronizes A(E*Pt) if and only if x is not a prefix of a prOper suffix of any tape y in pt. Proof: We first prove the forward implication, by contraposition. Suppose x is a prefix of a proper suffix Of tape in Pt. Then there are tapes u and w (u 7! A) such that uxw 6 Pt, whence M(SO, uxw) 6 F. If M(SO, x)- — M(SO, ux), then M(SO, txw) z M(SO, uxw) 6 F. This implies that some suffix v of xw is in Pt and, since u 7! A, v 6 Pt is a prOper suffix of uxw 6 Pt , contrary to the definition of Pt . This contra- diction stems from taking M(SO, x) = M(SO, ux); hence M(SO,X)}(M(SO,UX) = M(M(SO, u), x), and x fails to synchronize .A. The reverse implication is again proved by contraposition. If x fails to synchronize A, then for some 8.1 6 S, M(so,x) 75 M(Si’ x). Since A is reduced, there is a tape w.l such that M(SO, wi) = Si, and there is a tape u (possibly empty) such that u distinguishes between M(SO, x) and M(Si’ x). Thus one and only one of M(SO, xu) and M(si,xu) is in F. If M(SO, xu) 6 F, thent some suffix of xu is in P. Therefore the same suffix of wlxu is in P, and M(Si’ xu)- — M(SO, wixu) 6 F. Hence u fails to distinguish between M(so, x) and M(Si’ x), contrary to the selection of u. This rules out the case M(SO, xu) 6 F. We are forced to conclude M(SO, xu) g’ F and M(sO ,w.xu) = M(S, , xu) 6 F. Hence some Suffix v Of wixu is in Pt, tbut no suffix of xu is in Pt. Therefore xu is a prOper tsuffix Of v 6 P, and x is a prefix of a prOper suffix Of a tape in Pt . The proof is now complete. Theorem 4. 3.1 characterizes those sequences which will syn- chronize an ultimate-definite automaton. Is it possible for the set of synchronizing sequences so neatly described to be empty? That is, >1< need A(Z Pt) be synchronizable? If Pt is finite, with a longest tape in Pt having length k, then any tape whose length exceeds k-l will do and there may be other, . . t . . . . ’1‘ t . . shorter synchronizing tapes. If P is 1nf1n1te, A(E P ) ex1sts and 18 3k ': not synchronizable if and only if 2 Pt is regular and every tape in 23" 48 is contained in a prOper Suffix of a tape in Pt. This latter condition can indeed occur as is shown in the next example. Example 4. 3.1: Let t1 t2 t3 110, 11110 0100, 1111110101100 011010 001000, tj = l- 3., where .s. is a tape Of length 2j - j obtained by concatenating all tapes in 23-], the only stipulation being that the concatenation end in 10j. Let Q = '[ti : i: 1, 2, 3. . .], and let U = 23*0. The representa- tion 2*0 is seen to be canonical and everyrtape in 2* is contained in many proper suffixes of tapes in Q. >I< It remains for us to Show whether or not 2 Q is regular or if a regular set exists having the property we built into Q. These question are resolved by the following theorem and corollary. Theorem 4. 3. 2: All ultimate-definite automata are synchronizable. Proof: We show that any two states of an ultimate-definite automaton can be merged and apply Lemma 3. 3.1. Consider any two states 31 and s2 of A(Z*Pt) = (S, M, so, F). Since A is reduced, there are tapes x1 and x2 such that M(so,xl): s1 and M(so, x2) = 82. Furthermore, there is a tape 21 of length 5 n-l such that M(Sl’ 21): M(so, xlzl) 6 F or M(SZ, z1)= M(SO’XZZl) 6 F but not both. That is M(sil, zl) 6 F for i1 = 1 or 2 but not both. 1 Then for some non-null suffix x-l , XII 21 6 Pt. (x.l = A. 11 0f xi 1 implies some suffix of 21 is in Pt, whence M(Sl, zl) 6 F and M(SZ, Z1) 6 F, contrary to selection of zl.) If M(Sl, x]1)# M(SZ, XII) then, proceeding as above, there is a tape 22(1(z2)Sn-1) such that M(sl,xllz2) s F or M(SZ, xllzz) e F but not both. Denote the one in F by M(Slz’ xillzz). AS before, for some non-null suffix x12 of x- , x12 x[ z 6 Pt. 2 ‘2 l 2 1 2 Proceeding in this fashion, for each positive integerj such that M(sl, X‘Ij . . . x-lz2 xIl) 74 M(SZ, X'Ij . . . Xizlel) we obtain a corresponding 49 ta j+1xj xlez pe xifi1 .lj... .12 i1 j+1 list of such tapes. 6 Pt, with 1(zj+l)Sn-l. Consider the 1 x11 z1 2 X1 Z ”‘12 i1 2 XJ 00 X.2 X.1 Z 1J 12 11 j ' 1 "1J4r1 XiJ x1 x1 zj+1 3+1 j 2 1 This process cannot continue indefinitely for there are finitely many tapes 2]. Since 1(2).) 5 n-l;and no tape zj can be used twice to generate tapes in the above list. (Otherwise for somej < k, zj = z k, J. . . x. z: is a proper suffix of x-lk. . .-xJ_ . . . x1 zk, which cannot j 11 J k j 1l and x. 1 1 . t occur in P .) The above process terminates only when, for some integer r, M(s , xr . . .x.l) = M(s , x.r...x-1). Such termination is assured. l 11. 11 2 ‘r ‘1 We have shown that for any states S and s2 6 S, S1 and s2 can be merged. Thus by Lemma 3.3.1, A(F,‘ Pt) is synchronizable. CorollarLto Theorem 4. 3.2: There is no regular set Q such that (1) no tape in Q is a suffix of another tape in Q, and x: (2) every tape x 6 F is a prefix of a prOper suffix of a tape in Q. Proof: We Show that a regular set Q satisfying 1 violates 2. If O is regular and satisfies condition 1, then P = 2*Q is regular, ultimate- definite and in canonical form. The reduced automaton M(;'*Q) is synchronizable by Theorem 4. 3. 2. There is therefore a tape x which synchronizes A, and by Theorem 4. 3.1 x is not a prefix of a proper suffix of a tape in Q. Hence Q fails to satisfy condition 2. 50 N. B. The set Q Of Example 4. 3.1 is thus revealed to be not regular. 4. 4. Synchronization of Reverse Ultimate-Definite Automata Given a reverse ultimate-definite event P = Qt2* in canonical form, the set Qt may or may not be finite. In the former case it is clear that P is regular, while in the latter instance there is no such assurance. However, regularity Of P is equivalent to regularity of Qt. That is, * Lemma 4. 4.1: The event P = QtZ in canonical form is regular if and only if Qt is regular. Proof: The reverse implication is immediate. The forward implica- tion follows easily from Definition 4. 2.1 and Theorem 4. 2.1; verifica- tion is left to the reader. 3): Theorem 4. 4. 2: If P = QtZ is regular, then A(P) = (S, M, so, F) has exactly one final state 3 Furthermore S is a dead state. F' F Proof: Let sF be a final state of A. There is a tape x such that M(so,tx )= S ; hence there are tapes w and y such that x = wy and w 6 P . F >I< For any tape 2, xz = wyz 6 PtE ; hence M(SF, z) = M(so, xz)6 F. That is, any state reachable from SF is also a final state. Since sF was an arbitrary final state of A, no two final states of A are distinguishable by any tape 2. Since A is reduced, there is but one final state 8F. Furthermore, Since M(SF, z) 6 F for all tapes 2, M(SF,Z)= SF * for all z 6 Z . This shows SF to be a dead state. The next result characterizes synchronizable reverse ultimate- a): definite automata A(QtE ) in terms Of their state sets. 31‘ * Theorem 4.4. 3: If Qt}: is regular, A(QtZ ) is synchronizable if and only if A has no non-final dead state. Proof: The forward implication is immediate, since no two dead states can be merged and A has a final dead state. The reverse implication is established by Showing that the (dead) final state s is F reachable from every state in S - {SF}. 51 For any state t 6 S - {SF}, if SF )6 r(t) then r(t) consists entirely of states from which SF is inaccessible. Therefore no two states in r(t) are distinguishable, Since no final state is in r(t) or accessible from a state in r(t). Thus r(t) is a singleton, i. e., r(t) = t. However this implies t is a non-final dead state, contrary to hypothesis; so 5 6 r(t) for anyt6S-{3F}. F The proof is completed with the Observation that A can be syn- chronized by mapping occupied states in S - [SF] to SF, until the occupied set if reduced to [SF]. We note in passing that Theorem 3. 5. 4 established the bound ([2) on the length of a Shortest synchronizing sequence for A(Qt2::<), if A is synchronizable and has n states. Furthermore, Example 3.5.1 shows that this bound is minimal for reverse ultimate-definite automata; one need only construct an n-state machine in the manner suggested by the example, taking 50 as the start state and SD as the final state. The next theorem establishes a criterion fOr synchronizability of A(Q">:*), where ot is finite, in terms of tapes in Qt. If A is syn- chronizable in such a case, the event P = QtZ* is shown to be m-definite for some positive integer m (see Definition 2.4. 4), and the synchronizing tapes of length less than k are characterized in a sub- sequent re sult. * Theorem 4. 4. 4: If P = 0‘2 and a longest tape in Qt has length k, then A(P) is synchronizable if and only if every tape in 2k has a prefix in Pt. Proof: The reverse implication is proved directly. If every tape in E has a prefix in Qt, then every tape in ER (and hence each tape of length exceeding k) is accepted by A. For any state S Of A there is a tape x such that M(SO, x) = S. For any tape 2 of length k, 1(xz) 2 k; hence xz 6 P. Therefore M(S, z) = M(SO, xz) :1 S the lone final state Of A. Since 8 was arbitrarily chosen, 2 synchrfnizes A to SF. The forward implication is established by contraposition. If not every tape in 2k has a prefix in Qt, there is a tape y of length k which has no prefix in Qt. There is a tape x Of length k in Qt by hypothesis. Thus for any tape 2, M(MISO, x),z)=M(sO,xz)6 F, since 52 x 6 Qt, ' and M(M(SO, y),z) = M(SO, yz) 6' F, Since no prefix Of tyz is in Qt. (This is assured, Since 1(y) = k, no prefix of y is in Qt and no ’1‘ tape longer than y is in k.) That is, for arbitrary z 6 Z] M(M(SO, xlz) 7? M(M(SO, y), z), and z thus fails to synchronize A. Corollary to Theorem 4. 4. 4: If Qt is finite and a longest tape in Qt 5:: has length k, and if A(QtZ ) is synchronizable, then A is m-definite for some positive integer m. Proof: Since any tape of length k synchronizes A to SF, the state Of A is uniquely determined by any tape x such that f(x) 2 k. By the remark following Definition 2. 4.. 7, A is m-definite for some positive integer m, and the desired conclusion is obtained. :3 >:< Thus if Qt is finite and A(QtE ) is synchronizable, QtZ is in reality a definite event. The following result is of course an immediate consequence of the preceding corollary. The proof supplied, 3): however, illuminates the structure of P = QtE as a definite event. * Theorem 4. 4. 5: If Qt is finite, then A(QtZ ) is synchronizable if >1< >1: and only if there exist finite events U and V such that 0%: = UUZ V. Proof: The reverse implication is an immediate consequence of the discussion following Definition 2. 4. 5. The forward implication will be proved constructively. It was observed in the proofs of Theorem 4. 4. 4 and its corollary that A(Qt2*) is synchronizable if and only if A accepts all tapes of length exceeding k-l, where k is the length of a longest tape in Qt. Thus, *Engt2*. The tapes of length less than k accepted by A are Of the form 00(20U 21L} .Uzk'1)UQI(zOU Uzk'2)U m-j-l UQk—11301=JK.,I [le H 21)]. where Qj = Qtflzj. Taking U = U Qj ( U 21)] and V = 2k yields the desired result. We have seen that, for finite Qt_C_ZD>I< such that k is the length >1: of a longest tape in Qt, if A(QtZ‘. ) is synchronizable then any tape Of length exceeding k-l synchronizes A. The following example reveals 53 that shorter synchronizing tapes may exist, and the next result char- acterizes such short synchronizing tapes. >I< Example 4.4.1: Consider A1(Qt2 ), where Qt: {00,01,11,100,101}. A longest tape in Qt has length 3. Since every tape in 233 has a prefix in Qt, Al Examination of the state diagram Of Al (Figure 4. 4. 1) reveals is synchronizable. the “short" synchronizing sequences 00, 01, and 11. Figure 4. 4.1. State diagram of A1 It might seem on examining Example 4. 4. 1 that short synchro- nizing sequences must also be elements of Qt. This is not the case, as is shown by the following example. Example 4. 4. 2: Examination of AZ(P"2"‘) where pt: {0,100,101,11} discloses the short synchronizing tapes 00, 01 and 11. Figure 4. 4. 2. State diagram of A2 54 We now describe the Short Synchronizing tapes of A(Qth‘) for . . t f1n1te Q . Theorem 4.4. 6: If Qt is finite, A(QtE*) is synchronizable, and a longest tape in Qt has length k, then the tape 2 of length m < k is a a): synchronizing tape for A if and only if z 6 01:23 and for any tape y such >I< that 1(y) < k-m, yz 6 Qt): . Proof: The forward implication is established by the following Obser- vations. If z synchronizes A, then for each state S Of A, M(s,z) = SF. For any tape y (hence in particular for y such that 1(y) < k-m), M(SO, yz) = M(M(SO, y))= SF. Thus 2 6 QtZ‘.* and yz 6 Qt2*. To establish the converse, it is useful to recall that A accepts all tapes of length exceeding k-l. Thus for each 8.1 6 S - {SF} there is a tape y.l of length less than k such that M(SO, Yi) = Si. By hypothesis, if 1(yi) < k-m, then M(S .1, z) = M(SO, yiz) 2 SF, since yiz 6 Qt2*. If 1(y.l) 2 k-m, then M(Si, z) = M(SO, yiz) = SF and the proof is complete. Since 1(yiz) Z k. Thus in any case, M(Si’ z) = SF, ‘< Acknowledgedly, since allsynchronizing sequences for A(QtZ>i ) send A into its final state s from which it cannot escape, such tapes F) are Of little worth in the practical sense. For finite Qt we have, however, achieved a clear mathematical solution to questions of their existence and characterization. 4. 5. Central-Definite Events and Automata In this section we define a form of event which springs naturally from our consideration of synchronizing sequences, relate the new form to the ultimate-definite and reverse ultimate-definite events of Paz and Peleg [13] , and Obtain a canonical form for the event. Finally we give a procedure for constructing automata for a particular class of central-definite events. Recall that, for any automaton A and any tape x, x synchronizes A if and only if the Myhill equivalence class [x]: is a right zero of 992(A), the monoid Of A. (See section 3. 2. ) A Eonsideration of the algebraic prOpertieS of right zeros leads to a new form Of event. Lemma 4. 5.1: The set Of right zeros of a semigroup S is a two-sided ideal in S. 55 Proof: Let RES be the set of right zeros of S. Then for each r 6 R and S, t 6 S, s(rt) = (sr)t = rt; hence rt 6 R. Trivially, tr 6 R. Thus for any t 6 S, tRER and RtER. The preceding result prompts a further observation. Lemma 4. 5.2: If A = (S. M, s F) and r is a synchronizing sequence 0’ for A, then for any tapes x and y, xry is a synchronizing sequence for A. Proof: For any state s 6 S, M(S, xry) = M(M(M(s, x), r), y) = M(M(SO, r), y) = M(so, ry). The first and third equalities follow from definitions; the second, from the fact that M(t, r) = M(so, r) for all t 6 S, hence in particular for t = M(s, x). Thus xry takes all states of A to M(SO, ry) which, by Definition 3. 2.1, completes the proof. CorollarLto Lemma 4. 5. 2: If R is the set of all synchronizing 31¢ >l< sequences for A, then R = 2‘. R27 . 31‘ >1< Proof: The inclusion 2'? R27 EER is immediate from Theorem 4. 5. 2. * 3k 3:: The observation that A 623, hence R = ARAQZ RF. , completes the proofl 31‘ :1: :1: Definition 4. 5.1: For any event PQZ‘. , the event U = 27 P? is a central-definite event. If U is regular, A(U) is a central-definite automaton. Thus by the preceding corollary, the set of all synchronizing sequences of a finite automaton is a central-definite event. The next result relates central-definite events to events previously considered. Theorem 4. 5. 3: The event U is central-definite if and only if U is both ultimate-definite and reverse ultimate-definite. Proof: If U is central-definite, there is an event PQEII such that U a 2:31:79"; hence U = 2*(pz*) = (2*p)z*, the first equality showing U to be ultimate-definite, the second Showing U to be reverse ultimate- definite. . Conversely, if U is ultimate-definite and reverse ultimate- definite, there are events P and Q such that U = 2*P = 02*. Then 2*U = 2*(oz*) = 2*(z*p) = 2*13 = U. The proof is completed by noting that 23*QZS* : U. 56 >t< >1< We now Show that U = 2 P23 has a canonical form analogous to those constructed for ultimate-definite and reverse ultimate- definite automata. Definition 4. 5. 2: If U is central-definite, a representation of the >1< >5 form U = 2 02) is canonical if no tape in Q is a prOper subtape of another tape in Q. A canonical representation of U will be denoted :1: >1: by Z QtZ . Theorem 4. 5. 4: If U is central-definite, then U has a unique canoni- cal representation. =I< _ . t , we first Show the eXlstence of an event O >I< Proof: If U = 2 OZ * =I< such that U = E QtZ‘. is a canonical representation of U. We then Show that the set Qt is unique. Let 00 = QnZO. For any integer j Z 1, . -l j-l .1 . let QJ. = 002:3 - L] (IJ Epin' "). i: :0 That is, Qj is the set of all tapes in Q Of lengthj which do not have proper subtapes in Q. CD . t Flnall , let Q = 0.. Y H) J The construction Of Qt assures that no tape in (I)t is a prOper subtape of another tape in Qt. It must still be shown that U: 2*Qt2*. If x 6 U, then there are tapes u and w in 2* and v in Q such that x = uvw. Since v 6 Q, either v 6 Qt or some prOper subtape of v is in Qt. In either case, v 6 23*Qt23*, hence uvw 6 2*Qt2*. Thus 2*QE*§E*QtE*. The reverse inclusion is immediate, since otgo. To see that Qt is a unique set, suppose ZI>I:< is another canonical representation of U. Without loss Of generality, suppose the tape x is in Pt and not in Qt. Then x 6 }:.:I‘Pt2".‘.>:< = 23 Q 2*, and there are tapes u and w in 2*, not both empty, and a tape v 6 Qt such that x = uvw. Since no tape in Pt is a subtape of another tape in Pt, v 6 Pt. Since v 6 Qt, v 6 2*Qt2* : 2*Pt2*; so there are tapes t and z in 23* and y 6 Pt such that v = tyz. 57 Thus x 6 Pt, y 6 Pt, and x = uvw = utyzw. Since not both u and w are empty, y is a proper subtape of x, contrary to the supposition * * that Z PtE is canonical. The supposition is thus false and the uniqueness of the set Qt is established. The unique canonical representations of U = 2*QZ*, viewed as an ultimate-definite, reverse ultimate-definite and central-definite event, may be quite different from one another. For example, U = 2*(10U011)Z* is a central-definite event in canonical form. Its canonical representations as an ultimate-definite and a reverse ultimate-definite event are 2* [100*(0*U1)U0111*] and [ (0*U1*)10U0*011]z*, respectively. (Lest this example be misleading, we observe that in the canoni- cal form U = 2*Pt2*, Pt need not be finite. Consider Pt = 1 0*11.) The three possible canonical representations of U = 2*QZ*a1—e not totally unrelated, however. Their relationship is brought out in the next two results. * * Theorem 4. 5. 5: Given the event U = 2 OZ , the tape x is in Q and has no prOper subtape in Q if and only if x 6 U and has no prOper Sub- tape in U. Proof: If x 6 Q and has no prOper subtape in Q, it is clear that x 6 U. If x has a prOper subtape u 6 U, then there are tapes w and v, not both empty, such that x = wuv. Since u 6 U, there is a tape q 6 O such that q is a subtape Of u. Since w and v are not both empty, q is a prOper subtape of x, contrary to hypothesis. Thus x has no proper subtape in U, and the desired forward implication is Obtained. Conversely, if x 6 U and has no prOper subtape in U, then in par- ticular x has no prOper subtape in Q. Furthermore, x 6 Q; for if not, there are tapes w and y, not both empty, and a tape q 6 Q such that x = wqy. The tape q 6 U is then a proper subtape of x, contrary to hypothesis. =1< 31‘ Theorem 4. 5. 6: If the canonical representations of U = 2 02“. as a reverse ultimate-definite, central-definite, and ultimate-definite a): :1: :1: :1: event, respectively, are PtE , 23 QtZ , and Z Rt, then Qt = PtnRt. 58 Proof: AS a consequence of Theorem 4. 5. 5, x is an element of Qt if and only if x 6 U and x has no prOper subtape in U. Results analogous to Theorem 4. 5. 5 for ultimate-definite events yield the following. The tape x is in Pt if and only if x 6 U and x has no prOper prefix in U, and x 6 Rt if and only if x 6 U and x has no prOper suffix in U. It is thus apparent that thptflRt. The reverse inclusion is established by contraposition. Consider any tape y 6 U. If y 6 Qt, then y has a proper subtape in U, and there exist tapes u, v and w such that v 6 U, not both u and w are empty, and y = uvw. Also,both uv 6 U and vw 6 U. If w f A, then y has a proper prefix in U; if v f A, then y has a proper suffix in U. Thus either y 6 Pt or yf Rt; hence y g‘ Ptn Rt. That is, y/ Qt implies y f PtnRt. The proof is now complete. Theorem 4. 5. 6 shows that, of the possible canonical repre- sentations ofU = for“, the central-definite one is most compact in terms of tapes which must be specified. Since U = 2*QZ* is ultimate-definite, the synchronizing tapes for A(U) have been given one characterization in Theorem 4.3.1. There is a Simpler description if U is viewed as central-definite. * t ’1‘ . Theorem 4. 5. 7: If U = E Q Z 13 regular, then the tape xsynchro- nizes A(U) = (S, M, so, F) if and only if x has a subtape in Qt. Proof: Since U is ultimate-definite, A(U) is synchronizable. Since U is reverse ultimate-definite, A(U) has a single, dead final state SF; and for any tape x which synchronizes A(U), M(S, x) = SF. Thus if x synchronizes A(U), then M(so, x) = S and x 6 U. F Therefore x has a subtape in Qt. Conversely, if x has a subtape in Qt, and s 6 S, then there is a tape y such that M(SO, y) = S; hence yx has a subtape in Qt, yx 6 U, and M(s, x) = M(SO, yx) = 3 Since 3 is F" arbitrary, M(S. x) = S The proof is now complete. F' at: '< Of special interest are events of the form U = Z‘. 05:" where Qt is finite. Such events are regular; and if a longest tape in Qt has * 31! length k, then the membership or non-membership in 2 Qt}: of a tape can be ascertained by examining all subtapes having length k. 59 For example, if Qt = [1111], if is only necessary to scan y taking in four (or more) symbols at a time to see if y belongs to U. * >1: Definition 4. 5. 3: If U = Z QtZ and a longest tape in Qt has length k, U is a central_k-definite event. If th 2k, U is a central purely k-definite event. A(U) is correspondingly said to be a central k-definite or central purely k-definite automaton. We close the present section with a procedure for constructing a central k-definite automaton A(Z*Qt2*) = (S, M, so, F). The scheme is an adaptation of the prefix automaton construction of Perles, Rabin and Shamir [14] . Given U = 2*Pt2*, let S = {[A]]U[[x] :x is a proper prefix of a tape in Pt}U{SF}' Take s0 = [A] and F = {SF}. Let the next- state function M be defined as follows: for each state [x] ,4 SF and each symbol a 6 )3, [y] if SF if and only if y is the longest prefix of M([x],,r ) = :oénlgta 6 pt which is a suffix of x0', and SF if and only if x0” 6 Pt. and let M(SF, 0') = SF. * Example 4.5.1: If U = E (10U011)E*, then S = {[A],[0],[l],[01],sF}, and M is Specified in Table 4. 5.1. The state diagram of A(U) is given in Figure 4. 5.1. * >l< Table 4. 5.1. Transition function of A(E (10U011)Z ) M l 0 1 [A] [0] [1] [0] [0] [01] [1] SF [1] [01] SF SF sF sF sF 60 * * Figure 4. 5.1. State diagram of A(Z) (10U011)E ) 61 5. TOPICS IN AU TOMATON DECOMPOSITION 5.1. Introduction Several authors have attacked the problems of expressing the structure and function of a finite automaton in terms of component devices which are in some way less complicated than the original machine. One such measure of a machine's complexity is its number of states. Instead of concentrating wholly on fragmenting or decomposing automata into devices each of which has fewer states than the original, some writers have placed constraints on the kinds of component machines to be allowed, or on the ways in which they may be inter- connected. For example, Krohn and Rhodes [7 Jand Zeiger [20] described techniques for decomposing an automaton A into a set of automata K1, K2, . . . , Kr wherein each machine Ki is one of several canonical types (to be further discussed in Section 5. 3) and such that the output of K1 is allowed to act as part of the input to Kj if and only if i< j. There is thus a one-way flow of information from machines with lower to machines with higher indices. Such an arrangement is called a cascade of automata. Hartmanis and Stearns [5] , on the other hand, described a decomposition procedure in which any component machine may send its output to any other component machine, resulting in a network of automata. (A cascade is thus a special network.) The procedure yields component machines each having strictly fewer states than the original machine. Figure 5.1.1 Shows a cascade and a network which is not a cascade. AS suggested in the drawings, the input to the net may be supplied to any or all of the component machines. 62 In out I r J Y r (a) K 4 K2 ‘ K3 K4 ———>— Input (b) L1 - L2. L3 L4 -———~— Figure 5.1.1. A cascade of automata (a) and a network which is not a cascade (b) The results Of the present chapter were obtained while in- vestigating cascade decompositions of the classes of automata treated in Chapter 4. Some pertain directly to definite automata, while others are of a more general nature. Zeiger's procedure, correct in concept, has undergone several modifications to remedy errors in the rather intricate details. Some faults persist in that author's most recent exposition [21] . Before exhibiting our original results we review that exposition, point out the errors, and suggest corrections. The balance of the chapter is devoted to general results concerning the ways in which permutations of states in a given automaton are reflected in its Zeiger decomposi- tion and to results on the decomposition of definite automata. 63 5. 2. State Behavior Simulation and Decomposition Before discussing the decomposition procedure we formalize several ideas introduced in Section 5.1 and establish the notation to be used in the remainder of the present chapter. Conforming to Zeiger [21] , the notation is somewhat different from that of preceding chapters, and is used because it was designed to efficiently display the necessary details. The material of the present section is for the most part due to Zeiger [20] , [21] . We review the essentials and elaborate where needed in order to provide the background for sub- sequent results and to correct several errors. Definition 5. 2.1: Given a finite automaton M, let QM denote denote the input alphabet Of M, and SM denote induced by nonempty its set of states, I M the semigroup of all transformations of QM sequences of symbols from I Let SM = TNl‘JSM’ where T M. M consists of the identity transformation on QM and all transformations which map QM to a single state. If x is an input sequence, let xM be the transformation induced by x on Q Note that, if x and y are M. tapes, then (xy) That is, for each s 6 QM, (xy)M (s) = = x . M YM M Since the concern of the present chapter is with state behavior, no reference need be made to a starting state or a set of final states of M. Example 5. 2.1: If M is the automaton whose state diagram appears in Figure 5. 2.1, then QM = {a, b, c] and IM = [1, 2 }. S M contains, among others, the function f = (12)M, with (12)M (a) = c, (12)M (c) = a, and (12)M(b) = b. 64 Figure 5. 2.1. State diagram of M The concept of an automaton N being able to Simulate an automaton M is essential to any decomposition theory. In non- technical terms, we say that N simulates the state behavior of M if there is a way to view the states of N as if they were states of M and if, on so doing, we see that the transitions of N under all inputs are the same as those of M. Definition 5. 2. 2': ‘ The finite automaton N simulates the state behavior of the finite automaton M under the correspondence Z N mapping QN onto QM 1f IN = I and, for each s 6 ON andx GIN = I M M' ZN(xN(s)) = XMIZNISII- Example 5. 2. 2: The automaton N of Figure 5. 2. 2 simulates the state behavior of automaton M, Figure 5. 2.2 under the correspondence ZN shown in Table 5. 2.1. Figure 5. 2. 2. Automata M and N such that N simulates the state behavior of M 65 Table 5. 2. l The function ZN mapping QN onto QM so that N simulates the state behavior of M ti 6 ON ZN (ti) to 80 t1 s1 1:2 S2 t3 s2 The essential features of the decomposition procedure will now be discussed. A fundamental notion is that of a cover of the state set of an automaton. Definition 5. 2. 3: Given a finite automaton M, a collection C = [b , b , b ]of subsets of Q is a cover of Q if 1 r M -—-- M and bi E C there is a bjE C such 2" Ir [J b.=Q andforeachx eS . 11 M m 1: . C = - that xM(b1)___bj. A cover C of QM Isl, . . . , Sn} W111. be M denoted by listing the states in the cover elements in groups separat- 3, 525384}. ed by commas; e. g. , C =[sls That is, C is a collection of "blocks" of states of M which exhaust QM, such that each input sequence takes elements of C into elements of C. Thus C mirrors, in a coarse manner, the actual state behavior Of M. If an element of C is known to contain the present state of M, then it is possible to specify an element of C containing the next state of M following any input x. Indeed, it is possible to construct an automaton N which, for each cover element in C and input symbol x, specifies a next cover element in C. Definition 5. 2.4: Given a finite automaton M and a cover C of QM, the automaton N tells where M is in C if IN = I and there is a M of QN onto C such that, for every x E I and S 6 ON, mapping Z N M xM(ZN(s) 1 c_:_ ZN(XN(S))- 66 Example 5. 2. 3: Let M be the automaton whose state diagram is given in Figure 5. 2. 3. C1 =[ac,bd] is a cover of QM, as is CZ : [ abc,bd] . Trivial covers are I :2 QM and the discrete cover O 2 {a,b, c,d] , which are respectively the coarsest and finest covers of QM . A collection of subsets which exhausts. QM but fails to be a cover is fab, cd] , for 1M(ab) = bd is not contained in either [ab] or{ cd] . It is not necessary for all elements of a cover to be of the same size. A cover element may map onto or properly into another cover element. Table 5. 2. 2 specifies a two-state machine N which tells where M is in C . The correspondence Z 1 mapping QN onto Cl N is also shown. Figure 5. 2. 3. State diagram of M Table 5. 2. 2. Transition table for N, which tells where M is in C1 86 ON ZN(S) ONIS) 1N(s) 31 ac s2 sz 3 I bd s1 52 n . . If the automaton M has n states, there are n ways 1n Wthh a given input symbol x can map QM into QM. The mappings allowed in the machines of a cascade decomposition are sharply restricted in the following sections, to types defined below. Definition 5. 2. 5: The input symbol x E I is a permutation input to M machine M if KM permutes OM, and a. resetting input or a reset if 67 xM(QM) is a singleton. M is a pgrmutation-reset machine if every input to M is either a permutation input or a reset, and is a permut- ation machine if every input is a permutation input. 5. 3. Zeiger's Decomppsition Procedure Examination of Definitions 5. 2. 2 and 5. 2. 4 reveals that, if C is the discrete cover of Q and N tells where M is in C, then N M simulates the state behavior of M. Briefly stated, given machine M which is not a permutation-reset machine, Zeiger's procedure [21] generates a sequence of successively finer covers C1’ C2, . . . , Cr and a corresponding sequence of permutatiOn-reset machines L1, L2, . . . , Lr such that (a) Each machine Li has strictly fewer states than M has . (b) A cascade Nj (specified by the decomposition procedure) of L1, . . . , Lj tells where M is in Cj' by means of the . _ ____._ mapping ZN . QN Cj. (c) The group of perrflutations in S is a homomorphic image of the group of permutatiI-Oins induced on some subset of QM by elements of SM. (d) Cr is the discrete cover of QM. Thus Nr simulates the state behavior of M. The decomposition procedure owes much of its intricacy to the constraints on the Li and the requirements (a) -- (d) above. The proof of Proposition 1 in Zeiger [21] describes the first step in the decomposition process, whereby one generates a cover C of the state set QM and obtains a permutation-reset machine N that tells where M is in C. The construction is as follows: (1) Let C = max [{w (QM): w 6 SM} - QM] . (If B is a collec- tion of sets, max (B) is the set of elements of B which are maximal with respect to set inclusion.) (2) Let QN = C. 68 (3) Let ZN, the correspondence between states of N and elements of C, be the identity mapping. ' E ': I I (4) For any input x IN IM, let xN be defined by a. If W(QM)$QM’ then select any R' E C = QN such that xM(QM)§R', and let xN(b) = R' for each b 6 ON. b. If xM(QM) = QM, then xM permutes the blocks of C; let xN(b) i: xMIb) for each bEQN. It is thus seen that (4)-a produces reset mappings on ON, while (4) -b produces permutations on QN. Furthermore, the group of permutations on QN is a homomorphic image of a subgroup of SM; and N does tell where M is in C. The proof of Proposition 2 tells how this process may be continued. Step 1 of the proof tells how, given a cover C of QM and a machine K which tells where M is in C, a finer cover C' of QM is obtained. Step 2 details the construction of a corresponding permuta- tion-reset machine L and a cascade N of K and L such that N tells where M is in C', via mapping ZN: QN pn_tp- C'. (See figure 5.3. 1.) Steps 1 and 2 are shown following the figure. In t - le__,_ Where M is in C' Figure 5. 3.1. Ilagram of the inductive step in Zeiger's decomposition process Step 1: Given a cover C of QM, two elements of C are similar if each is the image of the other under appropriate transform- ations from SM. (Similarity is an equivalence relation on the elements of C, and partitions C into similarity classes, each of which contains 69 cover elements of a single cardinality. There may be several sim- ilarity classes whose cover elements have the same cardinality.) An element b 6 C is initial in C if b is similar to every element of C N which maps onto b under some transformation from SM. A refined cover C' is obtained by replacing each b in one initial similarity class D C C with Rb = max[[w(R) :w(R) is a proper subset of b, w 6 SM , and R E C I]. Step 2: Pick one q E D. For any p E D, there are transforma- q p in S such that vc1 maps p onto q, v: maps q onto p, M and the composition of VC1 p tions v and v and v is the identity transformation on q. We indicate this by VP vq qisp—Lq (id)- Let the state set of L be Rq, the set of elements which replaced ' ' l .. q in pasmng from C to C . Let IL — OK x IK. which 18 a cascade of K and L, 18 ON = OK x QL; and I The state set of N, N = IK = IM. The function ZN, mapping QN onto C', is defined by: For each (p, r) e QN’ (1) If p E D, then ZN(p, r) (2) If p E D, then ZN(p, r) p. P v (r . q ) The state transitions Of N, and hence of L, are defined as follows: For each x 6 IN and (p, r) 6 ON, define xN(p, r) = (s, t) by: (I) 8 : xu))- (2) If s 6 CflC', let t = r. m ' = q (3) If p E C C , and s E D, 1e; t ;Sm(p). (4) If p E D and S E D, let t = vaNquh). Iteration of Steps 1 and 2 yields the aforementioned sequence of successively finer covers C1, C2, . . . and corresponding permuta- tion-reset machines L1, L2, . . . such that the cascade Nj of L1, , Lj tells where M is in Cj . Finally the discrete cover Cr is obtained, with a cascade Nr of N and Lr telling where M is in Cr. r - 1 Machine Nr is a decomposition of M into a cascade of permutation- 7O (‘5‘ reset machines. These machines may be further decomposed into the canonical machines of Krohn and Rhodes [7], each of which is either a two-state permutation-re set machine with no non-identity permutations or a permutation machine whOse group is simple and is a composition factor of a subgroup of SM. 5. 4. Flaws in the Decomposition Procedure To show that the specification of state transitions of L (items (1)-(4), Step 2, Section 5.3) makes L a permutation-reset machine, Zeiger [21] notes that (2) produces the identity permutation on the states of L. He claims that (3) produces resets. It should be observ- ed, however, that vgxM(p) may be a proper subset of one of the blocks of states with which q was replaced in Obtaining C'. This is illustrated in Example 5. 5. 1. Also, it is claimed that (4) always produces permutations on the state set of L "since vqx vp permutes q. " The mappings vq s M q s P are indeed one-to-one transformations from 3 onto q and q onto p, and v respectively, but xM may or may not be a one-tO-one mapping Of p = vZ(q) onto 8. This is also shown in example 5. 5. 1. Consequently, in a situation where (4) applies, a permutation of states of L is not forced. AS in (3), such exceptions occur only when xM(p) is properly contained in 3. Both of the situations just described may be resolved by applying the following lemma. Lemma 5.4. 1: If p 6 C and xM(p) is properly contained in s, then q . SlepI ls there is a state 11 E QL (not necessarily unique) such that v contained in 11. Proof: If M(p) is properly contained in s, then vgxM(p) is properly q contained in q, since vS maps 8 one-to-one onto q. Therefore vgxM(p) E [w(R) : R 6 C, w 6 SM pleted by recalling that the maximal elements of this last set are taken , and w(R)$q} . The proof is com- to be the states of L. 71 Thus if XMIP) is properly contained in S. in (3) we may always I q . . c . 4 , I SXMII‘I 11 In I I If XM,p) 15 properly 1 contained in s, then for any state 1‘ € QL we may let t = 11, since select t : u E QL, Since v vgva:(r)Ev:xM(p)Eu. Note that in the latter case, (4) produces I a reset of L to state t rather that a permutation on QL. Finally, we note that in (l), (2) and (1)--(4) of Step 2, the states of K are also treated as elements of C, being interpreted in the latter sense in the construction of N and L. Steps (1)--(4), as given above, imply that the next-state assignment of L may be made using only the present input to K and the information "where M is in C" supplied by K. In applying (2)--(4), this state assignment is dependent upon know- ing the next cover element, S, to be specified by K, and no problem arises so long as S is uniquely specified by the present cover element p and transformation xK. However, in following the above procedure ‘for the automaton M' of Example 5. 5. 2 we encounter a situation where K specifies at time t that M' is in element Bi of cover C, receives an input x, and may then specify at time t + 1 that M' is in element Bk or B1 of C (Bk # B1), depending on the exact state of K at time t. This is not totally unex- pected if we note that in general many states of K may correspond to a Single element Bi of C. Among these, some may map under input x to states corresponding to B , others to states corresponding to B k 1; and input x to the original machine M' may indeed map B, into Bkfl B1. 1 Thus, either Bk or B1 is an accurate description of ”where M' is in C". In such a case, the next-state assignment in L requires state of K information rather than element of C information from K. 5. 5. Examples IllustratirgFlaws in the Decomgsition Procedure Our general scheme in the examples is as follows: 1. Obtain a cover C1 of QM and a permutation-reset machine K which tells where M is in C1. Let K = N1, and define ZK : ZN to be the identity map from QK to Cl. 1 72 2. Having cover Ci not consisting entirely of singletons and a machine Ni telling where M is in Ci’ obtain a refined cover C1 + 1’ , and a machine N. + l as a cas- 1 + l , so that N, tells where M is in C, . Let 1 1 + 1 1 + 1 Di denote the initial similarity class of elements of C1 replaced in a permutation-reset machine L, 1 cade of N, and L, 1 1 + obtainin C, . g 1 + 1 We leave it to the reader to verify that the constructions in the examples are carried out according to the procedures of Section 5. 3. In both examples, the decomposition is incomplete, being carried only far enough to illustrate the observations made in Section 5. 4. Example 5. 5. 1: Let M be the automaton whose transition table is shown in Table 5. 5. 1. Then c1 ={abc, bcde]. Table 5. 5. 2 shows the transitions of K = N1 which tells where M is in C . 1 Table 5. 5. 1. State transitions Table 5. 5.2. Transitions of M of K = N1 M 0 l 2 K L O l 2 a b c abc abc bcde bcde c d bcde abc bcde bcde c c d d d c e d e c e d To obtain C2, take D1 = [bcde]. Replace D1 withlbcd, cde}. Th = b d, , = . en QL I: c cde} and QNZ QK x QLZ To Obtain the transition table of N2 we Show the states of N2 as ordered pairs (p, r) where p 6 OK and r E QLZ. If N2 is in state (p, r) and input x is received, the first component of the next state of N2 is xK(p). This accounts for all first components in the body of Table 5. 5. 3. TO obtain second components, we follow parts (2), (3) and (4) of Step 2 of Zeiger's construction. Noting that A A bcde—M+-bcde Abcde (id) where A 73 M is the identity mapping produced by the null input sequence, we obtain the second components in the table body in the manner described following Table 5. 5. 3. Table 5. 5. 3. State transition table for N2. Starred 1 entries required modification of Zeiger's procedure. NZ 0 1 2 1 (abc,bcd) (abc,bcd) (bcde,bcd) (bcde,bcd’k) l (abc,cde) (abc,cde) (bcde,bcd) (bcde,bcd*) ' (bcde, bcd) (abc, bcd) (bcde , cde) (bcde , bcd*) (bcde, cde) (abc, cde) (bcde, cde*) (bcde, bcd*) By (2), the second components in the 0 column are unchanged from the corresponding entries in the present state column. By (3), 1N2(abc, bcd) = (bcde, t1) where t1 = AMlM(abc) = bcd. Similarly, 1N (abc, cde) = (bcde, bcd). In the same manner, 2 = = A : 2N2(abc, bcd) (bcde, t2) where t2 M2M(abc) cd. But ch QLZ. This illustrates the first difficulty discussed in Section 5. 4. Observ- ing that [Cd] Efbcd} ( [cde] would do as well), we let t2 = bcd. In like fashion, we arrive at 2N2(abc, cde) = (bcde, bcd). = = A By (4), 1N2(bcde, bcd) bcde, t3) where t3 AMIM M(bcd) cde. Also, 1N2(bcde, cde) = (bcde, t4) where t4 = AMlM M(cde) = de. However, de é QLZ, illustrating the second difficulty discussed in Section 5. 4. Noting that 1M(bcde) = cde, we select t4 = cde. The entries 2N2(bcde, bcd) = (bcde, bed) and 2N2(bcde, cde) = (bcde, bcd) are similarly arrived at. The table for L2 can be Obtained from the table for N2 and is shown in Table 5. 5. 4. Table 5. 5. 4. State transition table of L2 L2 ] (abc, 0) (abc, 1) (abc, 2) (bcde, 0) (bcde, 1) (bcde, 2) bcd bcd bcd bcd bcd cde bcd cde cde bcd bcd cde cde bcd 74 Example 5. 5. 2: Let M' be the automaton depicted in Table 5. 5. 5. Cover C1 = [abc, abd, acd, bcd]. Table 5. 5. 6 shows the state transitions of K' = N'l which tells where M' is in C1. 1 Table 5. 5. 5. State transition Table 5. 5. 6. State transition table of M' table of K' = N'1 M' 0 1 K' I 0 1 a b b abc I bcd bcd b c c abd I bcd abc c c d acd I bcd abd d d a bcd I bcd acd Since all elements of C1 are Similar, Dl =[abc, abd, acd, bcd]. Note that: A A 111 l abc———r'abc——-,-M' abc (id), abc—WM. abd——-,-M' abc (id), 11 11 l 111 abc—Mlacd—wabc (id), and abc-.M..'.bcd Misabc (id). Replace [abc] with (ab, ac, bc ], [abd] with [ab, ad, bd ], [acd] with [ac, ad, Cd], and {bcd} witthc, bd, Cd}, Obtaining C = {ab, ac, 2 ad, bc, bd, cd}. Take QLiz = (ab, ac, bc 1; and then QN.Z = 0N1 x QL" 2 2 Table 5. 5. 7. Sample computations in Obtaining ZN2 are the following: AM' AM' Since abc —-u—abc ——»—abc (id). ZNgIIabC. adll = AM.I 111 1 since abc ——-M-"-abd—MLabc (id), Z Part of the correspondence ZN,2 mapping QN2 onto C is Shown in ab) = ab; and ((abd, ab)) = 111 ab) = ad. M'( N2 Table 5. 5. 8 depicts some of the state transitions of N2. A sample computation is: ON' ((abd, ab)) :2 (bcd, ac). The first com- 2 ponent results from 010(3de = bcd. The second follows from the fact 111 1 1 111 that abc-_M.'..abd_M..'-abc (id), abc —1ViL—bcd——M-;-abc (id), and lllMIOMtlllMJab) = ad. 75 Table 5. 5.7. Partial list of values of function ZN' 2 State of Ni: Corresponding (K' state, Listate) element of C2 (abc,ab) ab (abd,ab) ad (bcd,ab) bc (bcd,ac) bd (abc,bc) bc (abd,bc) ab Table 5. 5.8. Partial table of state transitions of N' 2 M2 0 1 [ab] (abc,ab) Tbc] (bcd,ab) lbc] (bcd,ab) [ad] (abd, ab) [bd] (bcd,ac) [ab] (abc,ab) [ab] (abd,bc) [bd] (bcd,ac) [bc] (abc,bc) Elements of C2 corresponding to states of N'Z are shown in brackets inTable 5. 5. 8. Note that N'2 may say ”M' is in [ab]". receive an input 0, and then say "M' is in [be] " or "M' is in[bd] ", depending on the exact state of N2 before receiving the O. This illustrates the third difficulty described in Section 5. 4. 5.6. Suggested Remedies In the light of the observations of Section 5. 4, we suggest that Step 2 of Section 5.3 be modified to read as follows: I e . . . . Let ZN map QN onto C so that, for each (pl, r) ON. (1") If zK(p,) (2") Ir ZK(P1’ p 4 D, then ZN(pl' r) = ZK(pl). p 6 D, then ZN(pl, r) vr(r), where... q 76 ...For each x E IN and (p1' r) 6 QN, define xN(pl, r) : (51, t) by: (1') S1: xK(p1)- (2') If ZK(sl) = s 6 GAO, let t = r. (3') If ZK(p1) = p E CflC' and Z (s ) = s 6 D, choose anyt K 1 such that vcslxM(p) Et. (4') If ZK(pl) = p E D and ZK(SI) = s E D, choose t so that vgvag (r) Et. These suggestions subsume some of those contained in an erratum note [22] published after the completion of the present work. In that same note, and to correct still another subtle failing of the Zeiger procedure, it was suggested that the initial similarity class D consist of elements of C which are of maximal size among the ele- ments of C. It is easily shown that such a choice of D is always possible. Lemma 5. 6. 1: If C is a cover of Q and a largest element of C con- M tains k states, then there is an initial similarity class D of cover elements each of which contains k states. Proof: Let D D , . . . , Dn be the distinct similarity classes of 1' 2 elements of C such that each element of Di (ls‘i S n) contains k states. Since similarity is an equivalence relation, each element of Di (1S i ,4 SM for i ;é j, if any element of Di maps onto an element of Dj' then Sn) is mapped by elements of onto every element of Di. Thus, a. every element of Di maps onto every element of Dj under N SM b. no element of Dj maps onto any element of Di. (Otherwise, appropriate transformations from , and an element of Di and an element of Dj would be similar, making Di : Dj.) The relation # defined by Di # Dj if and only if some element of Di maps onto an element of D, is a partial ordering on the set { D1, D2. . . . , Dn l. Since the latter collection is finite, it contains a 77 maximal element D with respect to #. The similarity class D is an initial similarity class, since no element not in D maps onto any ele— A/ S . M ment in D under any transformation in 5. 7. Decomposition of Definite Automata In the present section we characterize definite automata as those in which no non-singleton subset of the state set is permuted by any nonempty input sequence. Using this result and examining the de- composition procedure of preceding sections, we show that a Zeiger decomposition of a definite automaton is essentially a cascade of re— set machines--"essentia11y" because some of the component machines may receive permutation inputs, but only of a trivial sort. A result concerning the way in which permutations of any non-singleton subset of a machine's state set are manifested in decompositions of that machine yields the converse result: an automaton whose decomposi- tion consists essentially of resets is a definite automaton. Lemma 5. 7. l: The finite automaton M is definite if and only if no non-singleton subset of Q is permuted by any nonempty input se- M quence. Proof: Suppose M is k-definite for some positive integer k. Then M is synchronized by any sequence whose length exceeds k. If k k c: A = = ' 2 P . QM, x # , and xM(P) P, then (x )M(P) P. Since 1(x ) k, P is a singleton. Thus no non- singleton subset of Q is permuted by M any input sequence x ;E A . Conversely, if IQ = n, P s Q and IPI =j > 1 implies P is ml M not permuted by any input sequence x ;é A , then for any sequence x n such that L(x) 2(j), it follows that IxM(P)I< IPI. (Otherwise, some subset R of QM with cardinalityj appears twice in the sequence of subsets through which P is mapped as the input sequence x is received by M. Such a set R is therefore permuted by a nonempty subtape of x, contrary to hypothesis.) Therefore if x is any tape of length not 78 n I I T1 . . less than c : szZ I1) , then xM(QM) is a Singleton. The automaton M is hence k-definite for some integer k 5 c, and the proof is complete. It would seem to follow immediately from Lemma 5. 7. 1. that no machine L, in a cascade decomposition of M receives permutation 1 inputs, since the group of permutations on QLi is a homomorphic image of the group of permutations on some subset of Q However, I M' singleton subsets of QM may be permuted (that is, fixed) by nonempty input sequences x; so machine Li may receive an input which induces the identity mapping on QLi' Consider now the induction step in the decomposition of an auto- maton M. Given a cover C of Q and a machine K which tells where M M is in C, one obtains a finer cover C' of Q and a machine L such M that a cascade, N, of K and L tells where M is in C'. A close examination of statements (l')--(4') of section 5. 6 re- veals that, for any p E QK and x G I , (p, x) is a permutation in- put to L if and only if (2') holds, or (4')1\I101ds and xM(p) = s. (In this case, p and 5 correspond to elements of the initial similarity class D of elements of C replaced in forming C'.) The next results and the related discussion rule out the latter possibility for definite automata. In case (2') applies, the resulting identity mapping on QL is trivial in the sense that it represents the arbitrary filling of a ”don't care” entry in the transition table for L. We shall refer to this as the trivial identity and to any other permutations induced on machines in the cascade (when (4') applies) as nontrivial permutations. The trivi- al identity permutations assigned under (2') could as easily have been resets. We therefore shall refer to a permutation-reset machine whose only permutations are trivial identities as a reset machine. The next three results show that a decomposition of a definite automa- ton is a cascade of such reset machines. Lemma 5. 7. 2: The first permutation-reset machine K1 in a decom- position of the k-definite automaton M has no permutation inputs. 79 Proof: Since M is k-definite, no non-singleton subset B of Q is per- M muted by any function KM 6 SM' Therefore no input symbol permutes QM. Proposition 1 construction as described in Section 5. 3), every input According to the procedure for constructing K1 (see Zeiger's to K1 is a resetting input. Lemma 5. 7. 3; If M is a k-definite automaton, C is a cover of Q M, Bi 6 C and IBiI > 1, then {Bi} is a similarity class of elements of C. Proof: Since M is k-definite, any tape x whose length exceeds k-l synchronizes M. If Bi and Bj are distinct elements of the same sim- ilarity class of elements of C, then there are nonempty tapes u and v such that Bi—E-v-Bj—X-rBi (id), and hence (uv)M permutes Bi’ contrary to Lemma 5. 7. 1. This contradiction completes the proof. In connection with the preceding lemma, note in particular that if C is a cover of QM not consisting entirely of singletons, then an initial similarity class D of elements of C contains but one cover ele- ment q. This observation simplifies the proof of the following result. Lemma 5.7.1; If M is a definite automaton, C1' C2, . . . , C1. = O (the discrete cover) is the sequence of covers associated with a Zeiger decomposition of M, and L , L , . . . , Lr is the corresponding se- 1 2 quence of permutation-reset machines, then no machine Li (2 s i s r) receives a nontrivial permutation input. Proof: For 2 S i S r a cascade K of L1, . . . , Li-l tells where M is in Ci-l' Let Di-l = {q} be the initial similarity class of elements of Ci-l replaced in obtaining Ci' In the discussion preceding Lemma 5. 7. 2 it was observed that a nontrivial permutation occurs for the machine Li under the cascade input symbol x if and only if x maps an M element p of Di onto another element 5 of Di' In the present instance this means M(q) = q, which would be contrary to Lemma 5. 7. l. The next result is of sufficient intrinsic interest to be called a 80 theorem, and is not restricted to definite automata. It is also used in I establishing the main result of the present section, Theorem 5. 7. 6. Theorem 5. 7.5: If x 6 IM and )LM permutes a non-singleton subset SX of QM, then in any cascade decomposition of M there is a machine L. which receives a nontrivial permutation input. 1 Proof: Since Sx is split into singletons by C1. = O, and SX is contained in sOme element of C1, there is a greatest integer j < r such that SX is contained in an element of Cj. Then for some element p of Dj, ' ' ' t f . S' - SX Ep and Sx is not contained in any elemen o Rp ince KM per : C . o = o a - mutes Sx’ xM(SX) SX _p, thus either Sx p or Sx is not maXimal in M ty is ruled out by the fact that maximality of Sx would cause Sx to be {w(R) : w is in’sv , R is in cj, and w(R) Ep}. The latter possibili- an element of Cj+1' contrary to the selection of j; therefore Sx = p. Thus KM fixes p 6 Dj' hence permutes the elements of Rp. Moreover, since p is maximal in Cj, if machine Nj is started in a state s corres- ponding to p and receives input symbol x, the next state of Nj also corresponds to p. By step (4') of Section 5.6., (s, x) is a permutation input to Lj+l' We are now in a position to state and prove the main result of this section. Theorem 5. 7. 6.’ The machine M is a definite automaton if and only if any Zeiger decomposition of M is a cascade of reset machines. Proof: The forward implication follows immediately from Lemmas 5. 7. 2. and 5. 7. 4. To establish the reverse implication, we apply the contrapositive of the preceding result and the characterization of def- inite automata of Lemma 5. 7. l. The proof is as follows. If any Zeiger decomposition of M is a cascade of reset machines, then there is a cascade decomposition of M in which no component machine Li receives a nontrivial permutation input. By the contra- positive of Theorem 5. 7. 5. , no non-singleton subset of Q 81 M is permuted by any input symbol x 6 IM. By Lemma 5. 7. l , M is a definite auto- maton. 5. 8. Decomposition Effects of Permutations of Q M In this section we consider automata having permutation inputs, and examine some of the ways in which such inputs are manifested in cascade decompositions. We continue to let Cl, C Cr = 0 Z, O O I , denote the sequence of covers associated with a particular but arbit- rary decomposition. The following lemma is due to Zeiger [21] . Lemma 5. 8. 1: If x E IM and xM permutes QM then xM permutes C That is to say, KM maps each element of C 1. 1 onto (not into) an element of C1, the result being a one-to-one mapping of C1 onto C1. That this result may be extended to any of the covers Ci (1 S i S r) may be intuitively appealing but is not immediate. The extended re- sult depends on the particular way in which cover C1 is generated +1 from cover Ci (1 S i< r) and not just on the fact that C1+1 is a cover of QM. This is shown in Example 5. 8. 1. Example 5. 8. 1: Let M be the machine represented in Figure 5. 8. 1. ____- ...L... 1 9 (bf—IQ) 9 1 1 Figure 5. 8. 1. State Diagram of M Let C = {ab, c, Cd}. Then C is a cover of QM, and IM permutes O M” but IM does not permute C. It may appear that we have somehow cheated by allowing one ele- ment of C to be properly contained in another element of C. However, the procedure by which the sequence C Cr is obtained does 1,..., not preclude such inclusions, for in obtaining Ci each element q in +1 82 ’s’ M C: ' : - z , t C = w(R) +q }), letting C1+1 Ci Di L) {Rq q E Di} no 1+1 max(Ci - DiU{Rq : q E Dil). Di is replaced with Rq = max({w(R) : R 6 Ci’ w E , and Lemma 5. 8.2: If xM permutes QM and KM permutes C, then for each b E C, w(b) E C (and not just contained in an element of C). Proof: Place the elements of C into sets according to their cardinal- ities. Let A1 be the set of elements of C of maximal cardinality, A the set of elements of next smaller cardinality, and so on. 2 Since KM permutes QM, IxM(b)I = IbI for any b E C. Accord- ingly, no element of Ai is mapped by x into an element of Aj for j > i. M Hence xM maps each element of A1 onto an element of A1 and, since XM permutes C, this mapping of A1 into A1 is one-to-one and onto. The mapping KM takes each element of A2 either onto another element of A2 or into an element of Al" Since each element of Al has a pre-image in A under x the latter possibility is ruled out, and l M' x maps A one-to-one onto A2. Proceeding in this fashion, XM M 2 maps Ai on-to-one onto Ai for each class Ai' Corollary 5. 8. 3: If xM permutes QM and permutes C, then the orbit of each element b of C under repeated applications of xM consists of cover elements having the same cardinality as b. Corollagy 5. 8. 4: If XM permutes QM and cover C, if D is any similar- ity class of elements of C, and if b E D, then xM(b) E D. Thus, xM permutes D and permutes C - D. Proof: For some positive integer j, ()LIVI)J is the identity mapping on j-l . . . QM. Then (xM) maps w(b) onto b. Therefore xM(b) 18 Similar to b. Lemma 5. 8. 5: For any integer i (1 S i S r), if yM permutes QM and yM permutes Ci then yM permutes CH1. 83 Proof. If yM permutes QM then for some pOSitive integer J, (yM) is the identity mapping on QM. By the preceding corollary, yM permutes D,. i Let p be any element of Di, and let yM(p) = s E Di. For any cover element b E R (b) is contained in some element c 6 RS. 13' YM C : j'1 C: j'1 j-1 = If YMIb) +C, then I) (YM) (YMIbII +(YM) (C)$(YM) (S) P. - J-l . E c . Since c 6 RS, (YM). (c) E {xM(R) . x SM, R 6 C and xNI(R) +p}, and since b $(yM)J'1(c), b E RP; but this is contrary to the selection of b. Therefore yM(b) = c 6 RS. That is, if yM(p) = s then y maps each element of R onto an element of RS; hence yM maps Rp into pKEJDi Rp' Furthermore, D. i this mapping is one-to-one, since yM is one-to-one on QM. There- fore yM permutes Ci - Di’ permutes q 'D. Rq’ and hence permutes 1 :C-D R. Ci+1 i iq Di ‘1 Lemmas 5. 8. l and 5. 8. 5 are sufficient to establish the follow- ing major result. Theorem 5.8. 6: If x permutes QM and if C1, . . . , Cr = O is the sequence of covers associated with a particular decomposition of M, then x ermutes Ci(15iS r), M P The remaining results of this section deal with ways in which permutations of QM show up in the machines of cascade decompositions of M. Recall that to each Ci (lS i Sr) there corresponds a permuta- tion-reset machine Li and a cascade Ni of L1, . . . , Li such that Ni tells where M is in Ci. Lemma 5. 8. 7: If XM permutes QM and Ni tells where M is in Ci’ and if t is a state of Ni corresponding to p 6 Di’ then xN (t) corresponds i E . to "M(p) Di Proof: It has been shown (Corollary 5. 8. 4) that x permutes Di; M hence w(p) 6 Di. Since Ni tells where M is in Ci' ZNi(xNi(t)) 84 2x (ZNi(t)) : xM(p), where ZNi is the function mapping QNi onto Ci. M The containment shown is actually equality, due to the maximal size of xM(p) in Ci. Lemma 5. 8. 7 facilitates the proof of the following theorem. which characterizes decompositions of automata having permutation inputs. Theorem 5. 8. 8: The automaton M has a permutation input if and only if every permutation-reset machine in any decomposition of M receives a pe rmutation input. Proof: The reverse implication is immediate, for if every machine L. (1:: it’. r) receives a permutation input, then in particular Ll does. 1 By the construction of L1, 0L1 is permuted by xLl only if QM is permuted by XM' The forward implication follows from Lemma 5. 8. 7. If xM permutes Q then XLl permutes QLI = QNl. For any integer i M, (l s is r) there is a state ti 6 ON. corresponding to cover element 1 pi C Di; hence x (ti) corresponds to another element vi 6 Di by N 1 Lemma 5. 8. 7. Therefore (pi, x) is a permutation input to Li+l' Thus for all i (1 '-’-i S- r), Li receives a permutation input, and the proof is complete. In Theorem 5. 8. 8 it is possible for any or all of the permuta- tions in question to be identity mappings. The next result establishes that a non-identity permutation on the state set of an automaton M is reflected in a non-identity permutation on the state set of some machine in any decomposition of M. Theorem 5. 8. 9: If x is a non-identity permutation on Q then at M M’ least one machine L, in any cascade decomposition of M receives a i non-identity permutation input. Proof: Since Cr consists of singletons, x induces a non-identity 85 M permutation on Cr' There is a least indexj (lS j Sr) such that xM induces a non-identity permutation on C,. Ifj = 1, then x is a non-identity permutation on the state L1 set of L1, the first machine in the cascade. Ifj>1, thean 1, acascade of L1, . . . , Lj 1, Let q E Dj 1 be the initial element such that Rq = QL.' ' J 1, the elements of C, which are moved by xM are Let p1 be a moved element of Cj, w1th p2 = xM(p1) # pl. tells where M is in C, . j—l Since fixes C, lei 3- not in C, . J—l Since XM fixes p, XM(pl) = pZ Ep; hence pZ E Rp. The elements of Rp correspond one—to-one to those of R under the mapping q q p . . . p___,.q, and, Since pl if p2, ql - v (p1) # v (p2) q2 The machine Nj 1 tells where M is in C, 1. There is a state a- J— S of Nj 1 corresponding to cover element p E Dj 1; and, since xM fixes Cj 1, XN (s) = t also corresponds to cover element p. Start- -1 ing machine N,J in state s and machine Lj in state q1 and applying input x to the cascade sends N, 1 to state t. Since both 8 and t corres- 1. is in state q1 and receives input (3, x) the next state of Lj is, by step pond to p E D, the input (5, x) to Lj is a permutation input. If Lj J— 4. . . Cl P = q = q = ' ( ) of Section 5 6, vpovq(ql) vprI(pl) vp(p2) qZ :9 q1 That is, (s, x) is a non—identity permutation input to Lj. Corollary 5. 8.10: If x permutes Q andj is the least integer such M M that KM induces a non-identity permutation on Cj, then Lj is the first machine in the cascade such that the input x is part of a non-identity permutation input to L,. J Proof: If i j, m fixes the elements of Ci' then by Theorem 5. 8. 11, KM fixes the elements of Cj’ contrary to hypothesis. It should be pointed out that, even though xM moves an element of Ci' x is not necessarily part of a non-identity permutation input to Li' For example, it may be the case that, for each p E Di’ XM fixes the elements of RP. 87 6. SUGGESTIONS FOR FURTHER INVESTIGATION There are several unresolved or untouched issues which might be considered in connection with the present work. Among the former are questions concerning the machine-independent bounds of Chapter 3. Can a sharp bound be obtained for the length of a shortest synchron- izing sequence of an arbitrary n-state automaton? What sort of bounds can be established in terms of both the number of states and the num- ber of symbols in the input alphabet? It would also be logical to investigate cascade decompositions of arbitrary ultimate-definite automata in an effort to characterize such decompositions. It is evident that, if a cascade decomposition of M is synchron- izable, then M is synchronizable. In the examples constructed by the author, synchronizable automata yielded synchronizable decompositions. Is this always the case? Much work is now appearing concerning cellular arrays of automata. What can be said concerning arrays of synchronizable automata? What sorts of arrays are also synchronizable ? Little mention has been made of the kinds of events accepted by synchronizable machines. The author has examined some aspects of such events, and there seems to be enough structure to warrant further investigation. The decomposition procedure described and modified herein has an ad hoc flavor, its features arising from particular constraints which might also be satisfied by other constructions. A modification which shortened the sequence Cl, C , Cr' perhaps by discard- 2, ing more elements of Ci in obtaining C, , would be of interest. 1 +1 88 REFERENCES l. 10. ll. 12. EVEN, S. Test for synchronizability of finite automata and , variable length codes. IEEE Trans. Inf. Theory IT-lO (1964), I 185-189. GILL, A. State-identification experiments in finite automata. Inf. Contr. 4 (1961), 132-154. GINSBURG, S. An Introduction to Mathematical Machine Theory, Addison Wesley, Inc., Reading, Mass., 1962. HARTMANIS, J. and Stearns, R. E. Algebraic Structure Theory of Sequential Machines, Prentice-Hall, Englewood Cliffs, New Jersey, 1966. . .. Sets of numbers defined by finite automata. Am. Math. Monthly 74 (1967), 539-542. KLEENE, S. C. Representation of events in nerve-nets and finite automata. Automata Studies, Ann. Math. Studies No. 34. C. E. Shannon and J. McCarthy (Eds. ), Princeton University Press, Princeton, New Jersey (1956), 3-41. KROHN, K. and Rhodes, J. Algebraic theory of machines: I. Prime decomposition theorem for finite semigroups and machines. Trans. Am. Math. Soc. 116 (1965), 450-464. . Results on finite semigroups derived from the algebraic theory of machines. Proc. Nat. Acad. Sci. U. S.A. 53 (1965). 499—501. KROHN, K. , Mateosian, R. and Rhodes, J. Complexity of ideals in finite semigroups and finite state machines. Math. Systems Theory 1 (1967), 59-66. LIU, C. L. Some memory aspects of finite automata. Tech. Rept. No. 411, M. I.T. Research Lab. of Electronics, Cambridge, Mass., May 31, 1963. MCCULLOCH, W. S. and Pitts, W. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophysics 5 (1943), 115-133. MCNAUGHTON, R. E. and Yamada, H. Regular expressions and state graphs for automata. Trans. IRE EC EC-9 (1960), 39—47. 89 l3. 14. 15. 16. 17. 18. 19. 20. 21. 22. PAZ, A. and Peleg, B. Ultimate—definite and symmetric- definite events and automata. J. ACM 12 (1965), 399-410. PERLES, M. , Rabin. M. O. and Shamir, E. The theory of definite automata. Trans. IRE EC-12 (1963), 233-243. RABIN, M. O. Probabilistic automata. Inf. Contr. 6 (1963), 230-245. RABIN, M. O.. and Scott, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125. RHODES, J. Complexity and characters of finite semigroups. Submitted to J. Algebra. A homomorphism theorem for finite semigroups. Math. Systems Theory 1 (1967), 289-304. STEARNS, R. E. and Hartmanis, J. Regularity preserving modifications of regular expressions. Inf. Contr. 6 (1963), 55-69. ZEIGER H. P. Cascade synthesis of finite-state machines. In Proc. of the Sixth Annual Conf. on Switching Theory and Automata, Institute of Electrical and Electronics Engineers, New York, 1965. Cascade synthesis of finite-state machines Inf. Contr. 10 (1967), 419-433. ERRATUM, Inf. Contr. 11(1967), 471. 90