CHAPTER IV

It has been shown by Krohn and Rhodes [9] and again by Zeiger [10], that any finite-state automaton can be constructed by a cascade of two-state reset machines and simple group accumulators (permutation machines). It has also been shown by Brzozowski [11] and Perles, Rabin and Shamir [15] that any definite event can be realized by a cascade of unit delays. Mayer [8] and Cohen and Brzozowski [14] have shown that every star-free regular event corresponds to a cascade of two-state reset machines, by invoking the Krohn-Rhodes theory as treated by A. Ginzburg [12], i.e. using a refinement of Zeiger's construction. The construction method presented here is closely related to Ginzburg's. One of the main differences is the use of the ross tree to produce a simpler construction.

4.1 Covers

Throughout this chapter we assume that the given event is in PF. The first step in the construction is to find a nested sequence of preserved covers (which Ginzburg calls "admissable decompositions" and Hartmanis and Stearns [13] call "set systems with S.P.") A cover C_n is any finite set of subsets B_i, called blocks, of S, the set of states of the automaton M, such that the union of all the B_i is the set S. Repeated blocks or blocks that are subsets of other blocks are permitted in a cover, but repeated states within a block are not permitted. A cover C_n is preserved if and only if each successor set of any of the blocks of C_n under any input sequence x in A* is contained in some block of C_n. A cover C_n+1 is finer than a cover C_n if and only if each block of C_n+1 is contained in some block of C_n, and at least one of those containments is proper. A nested sequence of preserved covers of an automaton is then a sequence of covers C₀, C₁, ..., C_p such that C₀={(S)} and C_p={(s₁), (s₂), ..., (s_n)} and each C_r+1 is finer than C_r, 0≤r<p. To find such a nested sequence we need some more definitions.

• Definition 4.1.1 A block B_i of a cover C_n is dominant if and only if no other block in that cover contains more states.

Note that there may be more than one dominant block in a cover.

In the following definition we consider loops in a tree. There are of course no loops in a tree, but when a branch terminates at a set equal to a previously encountered set, that branch is in effect an unfolded loop. This terminating set and those sets intervening between this appearance and the previous appearance of the set could be redrawn as a closed loop.

• Definition 4.1.2 A subset C'_n of blocks of a cover C_n is splittable if and only if C'_n satisfies the following:
  
  
  1. all blocks of C'_n are dominant, and,
  2. either the number of blocks in C'_n is one or all the blocks appear in a single closed loop in the ross tree, and,
  3. No block in C'_n is a successor of a block in C_n-C'_n.

Note that in any cover there always exists at least one splittable set.

• Definition 4.1.3 For every cover C_n, it is useful to choose one of the splittable sets and arbitrarily call it the splitting set C"_n of that cover.

Now we can say that every cover has one and only one splitting set of blocks. Furthermore, we can divide the blocks of a cover into two types.

• Definition 4.1.4 A block is said to be a splitting block if and only if it is a member of the splitting set C"_n of blocks in the cover C_n. All other blocks in the cover C_n are said to be passive blocks.

• Definition 4.1.5 A block B is observable if and only if it appears as a ross in the ross tree.

• Definition 4.1.6 The set D_i of resultant blocks B_ij of a splitting block B_i is the set of blocks maximal under inclusion chosen from among:
  
  
  1. all observable proper subsets of B_i and
  2. all the singleton blocks which are subsets of B_i.

Note that no block of a set of resultant blocks is contained in any other block of that set, and the union of all the blocks of a set D_i of resultant blocks is equal to its splitting block B_i. It is also obvious that the set of resultant blocks of any splitting block is unique.

• Definition 4.1.7 Let B₁={t₁ ... t_m} and B₂={t'₁ ... t'_m} be two blocks of the splitting set of blocks of a cover. Let B_1i={s₁ ... s_n} and B_2j={s'₁ ... s'_n'}, n<m, n'<m be subsets off B₁ and B₂ respectively. Then B_1i and B_2j correspond if and only if n=n' and if p and q are such that s_p=t_q then also s'_p=t'_q.

• Lemma 4.1.1 Let B₁, B₂ and B₃ be blocks of the splitting set of a cover. If B_1i and B_2j are corresponding subsets of B₁ and B₂ respectively and B_2j and B_3k are corresponding subsets of B₂ and B₃ respectively, then B_1i and B_3k are corresponding subsets of B₁ and B₃ respectively. In other words the corresponding property is transitive.
  
  Proof: This follows from the definition of correspondence.

• Lemma 4.1.2 Let B₁ and B₂ be two blocks of a splitting set of blocks, then for every resultant block B_1i of B₁ there exists a resultant block B_2j of B₂ which corresponds to B_1i.
  
  Proof: If B₁ and B₂ are two blocks of a splitting set of blocks then there exists an x in A* such that B₂=T'(B₁,x). From the definition of ross and T' we have that the state t_p in position p of B₁ goes to state t'_p in position p of B₂ under input sequence x. Now consider a set B_2j=T'(B_1i,x). Each state in B_1i goes to a distinct state of B_2j under x. For if this is not true, then two states of B₁ must go to the same state in B₂. This is a contradiction since B₂ and B₂ are assumed to be splitting and hence have the same number of states. Hence B_1i and B_2j have the same number of states. From the ross properties we see that B_1i and B_2j are corresponding. If B_1i is observable (which it must be to be a resultant block) then, after progressing through the ross tree under input sequence x we must arrive at B_2j. Hence B_2j is observable. We now have a B_2j, an observable proper subset of B₂ corresponding to B_1i. To show that B_2j is a resultant block of B₂, we have only to prove that B_2j is maximal among the proper observable subsets of B₂. Assume B_2j is not maximal, then there must exist an observable proper subset B_2k which properly contains B_2j. By the same argument as above we can find B_1m, an observable proper subset of B₁, corresponding to B_2k, which by correspondence must properly contain B_1i. However this is a contradiction, as B_1i is maximal. Hence B_2j is maximal.

• Lemma 4.1.3 Let B₁ and B₂ be two blocks of a splitting set of blocks. Then B₁ and B₂ will have the same number of resultant blocks and each resultant block of B₁ will correspond to some one resultant block of B₂ and vice versa.
  
  Proof: By Lemma 4.1.2, for every resultant block B_1i in B₁ there exists a corresponding resultant block B_2j in B₂. Hence B₂ has at least as many resultant blocks as B₁, all corresponding. But, by the same argument, B₁ has at least as many resultant blocks as B₂, hence B₁ and B₂ have the same number of resultant blocks, each resultant block in B₁ corresponding to a resultant block in B₂ and vice versa.

4.2 The Cover Algorithm

To find the set of preserved covers, an algorithm is presented which obtains the required cover from the previous cover. The covers are presented in matrix form with the blocks of the cover appearing as entries in the matrix. The columns represent the entries of the previous matrix and are labelled by the coordinates of the respective entry in the previous cover matrix. The rows, for cover C_n, are labelled arbitrarily s_n1, s_n2, ..., s_nm.

To obtain the first cover matrix, assume the one row, one column trivial matrix with the single block of the trivial cover as the only entry.

The row and column need not be labelled in this case, as this represents the trivial cover C₀ of one block of all the states and is only used to obtain C₁, the first non-trivial cover by means of the general algorithm. The general algorithm, to obtain cover C_n from the previous cover C_n-1, follows below:

1. For each block of the previous cover C_n-1, create a column of cover matrix C_n and label it with the coordinates of the respective block of C_n-1.
2. Choose a splitting set of blocks C"_n-1 in cover C_n-1.
3. Fill each column belonging to a splitting block of C_n-1 with its set of resultant blocks, one resultant block per row, in such a way that corresponding resultant blocks appear in the same row of C_n. Note that there will be as many rows in this cover matrix as there are resultant blocks per splitting block.
4. Place all the passive blocks of C_n-1 into their respective columns of C_n so that they all appear in the same row, which may be any of the rows already established in step (iii).
5. Label the rows s_n1, s_n2, ... etc. The entries represent the blocks of the new cover C_n, and the remaining locations in the matrix are left blank.

This algorithm is used repeatedly until the trivial cover consisting of all the singletons is reached. At this point an example illustrates the algorithm.

Consider the automaton depicted by the state table in Figure 3.1.3a and construct the ross tree as shown in Figure 3.1.3b. We now start with the trivial cover C₀. The process of finding the covers may be followed in Figure 4.2.1.

To obtain C₁ we notice that the splitting set of blocks of C₀ is the set of one splitting block {(ABCDEF)}. C₁ must contain one column as C₀ has one block. From the ross tree it is seen that the maximal observable subsets of (ABCDEF) are (BCEF) and (ADF). Thus they are the resultant blocks and are placed in two different rows arbitrarily labeled s₁₁ and s₁₂.

To find C₂, (BCEF) is the only dominant block, and we have two columns, one for entry (BCEF) in C₁ and one for (ADF). (BCEF) has two resultant blocks (BEF() and (CEF). (ADF), being passive, is just carried along and may be placed in either row of its own column. Notice the (BEF) (CEF) column has the coordinates of the (BCEF) entry of C₁ and (ADF), of the (ADF) entry. Again the new rows are arbitrarily named s₂₁ and s₂₂.

To find C₃, we have three dominant blocks. Two of them (ADF) and (BEF) are contained in a ross tree loop; hence {(ADF)(BEF)} is a splittable set. {(CEF)} alone is also a splittable set, but we will choose the former as our splitting set and consider the latter passive in this cover. We now have two sets of resultant blocks {(AF)(DF)} and {(BF)(EF)}. Notice that (AF) and (BF) must appear in the same row. (CEF) may be placed in either row. Again notice the labelling of the rows and columns.

To find C₄ we split (CEF) and now (EF)(BF)(DF) and (AF) are considered passive and may be placed in any row as long as they are all in the same row.

To find C₅ we have one large splittable and hence splitting set {(EF)(BF)(CF)(EF)(DF)(AF)} and, checking for corresponding resultant blocks, we obtain all the singletons as shown at the bottom of Figure 4.2.1.

• Lemma 4.2.1 If C_n-1 is a preserved cover, then the cover algorithm yields a cover C_n which is properly finer than C_n-1 and is also a preserved cover.

  Proof: C_n-1 is a cover and all its passive blocks B_i are carried over to C_n. The set D_j of resultant blocks B_jk covers all the states of its splitting block B_j in C_n-1. Hence all the states covered by the splitting blocks B_j in C_n-1 are covered by the resultant blocks B_jk in C_n, thus C_n is a cover. Since each splitting block B_j is replaced by more than one resultant block B_jk (since by definition the resultant block B_jk must be properly contained in B_j) and each cover has at least one splitting block, C_n is properly finer than C_n-1. To see whether C_n is preserved, let us consider first the transitions from one block to another in preserved cover C_n-1 under inputs a in A. They may be divided into five types.

  1. From a passive block B_i to a passive block B_j, that is T'(B_i, a)⊆Bj.
  2. From a splitting block B_k to a passive block B_j.
  3. From a splitting block B_k onto a splitting block B_m.
  4. From a splitting block B_k to a proper subset B_mp of a splitting block B_m.
  5. From a passive block B_i to a proper subset B_mp of a splitting block B_m.

  Note that transitions from a passive block B_i onto a splitting block B_m are not possible due to the definition of splittable. Now let us consider how each case carries over to transitions in C_n:

  1. These transitions carry over directly to C_n, as both B_i and B_j are contained therein.
  2. For each transition T'(B_k, a)⊆B_j in C_n-1 there are transitions T'(B_kr, a)⊆B_j in C_n where all the resultant blocks B_kr of splitting block B_k go to B_j under a.
  3. For each transition T'(B_k, a)=B_m in C_n-1, there must be transitions T'(B_kr, a)=B_mr in C_n, where resultant blocks B_kr of B_k go to corresponding resultant blocks B_mr of B_m.
  4. For transitions T'(B_k, a)=B_mp, a proper subset of B_m in C_n-1, consider the following: B_k is observable, hence B_mp is observable. therefore B_mp must be equal to or contained in B_mq, one of the maximal (under inclusion) proper subsets of B_m, that is one of the resultant blocks of B_m. Hence for all subsets B_kr of B_k, T'(B_kr, a)⊆B_mq, that is all the resultant blocks B_kr (in C_n) of B_k (in C_n-1) go to one resultant block B_mq (in C_n).
  5. For transition T'(B_i,a)=B_mp in C_n-1 there is a transition T'(B_i, a)⊆B_mq as described in case (iv) above.

  This exhausts the possibilities and proves that C_n is preserved. This concludes the proof.

4.3 Reset Machines

Before proceeding to the construction of the automaton it is necessary first to look at the building block. A generalized reset machine M^r, is an automaton with n states s₁, s₂, ..., s_n and n+1 inputs i₀, i₁, i₂, ..., i_n. Its transition function T, is shown in Figure 4.3.1a, where input i₀ leaves the states as they are (that is, i₀ is the identity input) and each of the inputs i_j, j=1 to n, causes all the states to go to the single state s_j.

Figure 4.3.1b
Ross Tree

It may immediately be seen in Figure 4.3.1b that M^r is a permutation-free automaton. Any n-state reset machine, where n is greater than 2, may be decomposed into a number of two-state reset machines connected in parallel. In fact, the number of such machines is log 2_n rounded up to the nearest integer. The procedure may be found in Hartmanis and Stearns [13], although for machines as simple as reset machines, this may be done by inspection. Two-state reset machines are of particular importance because they correspond to a common piece of circuitry, the set-reset flip-flop. In the hardware implementation two inputs called the set and the reset inputs appear as two separate physical inputs. This device corresponds to our two-state reset machine if we let one of our inputs i₂ correspond to a signal on the physical set input, the other input i₁ to the physical reset input and the identity input i₀ to no signal on either physical input. Care must be taken not to allow signal to appear on both physical inputs at the same time, as this would be a fourth, undefined input for our two-state reset machine which would destroy the correspondence between this device and our model of a two-state reset machine. Set-reset flip-flops also have physical outputs corresponding to the set and reset states of the flip-flop. As these outputs indicate the state of the flip-flop we will label the outputs with the states they represent. For the purpose of the next section we will consider the more general n-state reset machines and assume a hardware device with n physical inputs and the same restrictions on multiple signals as the two-state device just considered.

4.4 The Interconnection Algorithm

We are now ready to consider the construction of the cascade of set-reset flip-flops that realize the permutation-free automaton M. With each cover matrix C_n of the automaton M, 1≤n≤p, we associate a reset machine M^r_n with as many states as there are rows in the matrix. Each reset machine M^r_n has as inputs, functions of the inputs to the automaton M and outputs of only the reset machines M^r_m, where m<n. These input functions are arranged in such a manner that reset machine M^r_n contributes information to the cascade, corresponding to the splitting of the blocks in cover C_n-1 to form resultant blocks in cover C_n. In this way, after the final reset machine M^r_p, enough information has been contributed to distinguish between each individual state of the automaton M, since C_p consists of the set of all the singleton blocks.

To find the input functions of M^r_n, we examine the types of transitions found in cover C_n-1 and see how these are carried over to cover C_n, as discussed in Lemma 4.2.1. The input functions are then arranged so that M^r_n performs the appropriate splitting of blocks. We shall consider now the five possible transitions discussed in Lemma 4.2.1 and what is required of reset machine M^r_n for each of them.

1. Passive to passive. Since all the passive blocks of C_n-1 are in the same row of C_n, the required action in M^r_n could be obtained by either an identity input or a reset input to that row; for simplicity, the identity is chosen.
2. Splitting to passive. Since a splitting block in C_n-1 becomes a set of resultant blocks in C_n, (each resultant block in a different row) and since they must all go to one row in C_n, (the row used for the passive blocks) this transition in M^r_n requires a reset to that row.
3. Splitting onto splitting. Since each resultant block goes to one of its corresponding blocks under this type of transition, and corresponding blocks are in the same row, this transition requires an identity input for M^r_n.
4. Splitting to subset of splitting. As in transition type (ii) above, this transition is from many blocks in different rows to one block in one row. Hence this requires a reset input to that row in M^r_n.
5. Passive to subset of splitting. If the passive block and the subset of the splitting block appear in different rows of C_n, a reset input is required. If they appear in the same row then either a reset or an identity will do. For simplicity an identity will be used in this latter case. These two possibilities will be labeled type (v-a) and (v-b) respectively.

Since, in the definition of a cover, duplicate or contained blocks are allowed, care must be taken when they do occur. By looking at the previous cover it can immediately be seen which block is the true successor block of a column when that column initially appears to have more than one. That is if B_i appears to go to either B_jk or B_mp but in the previous cover B_i goes to B_m then we know that B_i goes only to B_mp in this cover.

Now a general algorithm can be given for the interconnections between the reset machines, using the ross tree.

1. For each column in C_n locate the observable block of C_n-1 corresponding to it in the ross tree.
2. For each successor of this block under a in A which is reached by a transition of type (ii), (iv) or (v-a), a factor consisting of the conjunction of all the terms labeling the column in C_n and the input a, is assigned to the input i_nk associated with the row k of C_n which includes that true successor.
3. The input i_nk for each row k of C_n is the disjunction of all the factors assigned to it.

This algorithm is best demonstrated by an example:

Using the ross tree in Figure 3.1.3 and the covers C₁ to C₅ in Figure 4.2.1, the interconnections are obtained one machine at a time. The process may be followed in Figure 4.4.1, where portions of the ross tree have been included for convenience.

Figure 4.4.1
Finding the Interconnections

Consider first the cover C₁ of one column. This column corresponds to the single block of C₀ (ABCDEF). From the ross tree we see that under input 0 it goes to (ADF) via a transition of type (iv), hence contributing a factor of 0 to input i₁₁. Similarly a 1 is contributed to i₁₂. Since this is the only column in this cover we are finished and we have the following:

Consider next cover C₂. The first column represents (BCEF) which from the ross tree can be seen to contribute s₁₂0 to i₂₁ (type ii) and s₁₂1 to i₂₂ (type v-a). Notice that (ADF) to (AF) is a transition of type (i) and hence does not contribute s₁₁0 to i₂₁. Hence for this machine M^r₂ the inputs are:

For cover C₃ we have column (BEF) contributes s₁₂s₂₂1 to i₃₂ (type ii), but not s₁₂s₂₂0 (type iii). Column (CEF) contributes nothing as s₁₂s₂₁0 is type (v-b) and s₁₂s₂₁1 is type (i). Notice in this last case that, in the ross tree, s₁₂s₂₁1 yields (EF) which appears to be in either (EF) or (CEF) of C₃. Looking at C₂, we see that (CEF) under 1 goes to (CEF). Hence s₁₂s₂₁1 goes to (CEF) which is a transition of type (i). In this case it does not matter as the other transition would have been of type (v-b), also a non-contributor. In general it is important to find the correct transition from the previous cover. Column (ADF) contributes s₁₁s₂₁0 to i₃₁ (type iv) but not s₁₁s₂₁1 (type iii). Hence machine M^r₃ has inputs:

For C₄ we have (EF) going to (F) under 1 which could be anywhere. From C₃ we see that (BEF) goes to (CF), hence (EF) goes to (F) in (CF) in C₄, making this a type (v-a) transition which contributes s₁₂s₂₂s₃₂1 to i₄₂ This case shows the importance of using the previous cover's transition to determine the true successor set. The second column (BF) contributes s₁₂s₂₂s₃₁1 to i₄₂ (type v-a). The third column (CEF) contributes s₁₂s₂₁s₃₂0 to i₄₁ (type ii) and s₁₂s₂₁s₃₂1 to i₄₁ (type iv). Note that from C₃ we can see that this last transition is type (iv) not (ii). The fourth column (DF) contributes nothing as both transitions are type (i). The last column also contributes nothing for the same reason. Hence machine M^r₄ has inputs:

In cover C₅ we have the two (EF) columns contributing s₁₂s₂₂s₃₂s₄₁1 and s₁₂s₂₁s₃₂s₄₁1 to i₅₂ (type iv), all the other transitions are of type (iii). Hence the last machine M^r₅ has only one input:

This completes the construction of a machine M to realize the event R=(I11(I00I)'11I)'. The machine consists of the five reset machines M^r₁ to M^r₅ interconnected as shown above and in Figure 4.4.2.

Figure 4.4.2
Interconnections

To prove the algorithm we borrow the following proofs from Mayer [8].

• Lemma 4.4.1 If automaton M_n-1 with states corresponding to the blocks of C_n-1 describes where in C_n-1 the automaton M is, then the automaton M_n, a serial composition of M_n-1 and the reset machine M^r_n, describes where in C_n the automaton M is.
  
  Proof: Consider the six possible transitions given by the interconnection algorithm. Transitions (i), (iii) and (v-b) are performed by M_n-1 and M^r_n remains unchanged. In transitions (ii), (iv) and (v-a), in addition to going to the columns indicated by M_n-1, M^r_n is set to the proper state; hence the proper block of C_n isidentified. This exhausts the possible transitions and concludes the proof.

• Theorem 4.4.1 The serial composition of all the reset machines M^r_n corresponding to the preserved set of covers C_n of an automaton M, using the interconnection algorithm, realizes that automaton.
  
  Proof: A one state trivial automaton M₀ corresponding to the trivial cover C₀ describes where in C₀ the automaton M is, because M can only be in one of the states S of M which comprise the only block of C₀. By Lemma 4.4.1 each M_n tells where in C_n M is for n=1 to k, where k is the number of preserved covers of M. Consider now cover C_k. C_k consists of all the singleton blocks and M_k describes where in C_k M is, hence M_k describes in which state of M, M is. Therefore M_k realizes M.

4.5 Hardware Implementation

To obtain the hardware configuration corresponding to the automaton constructed in the previous section, the physical inputs to each set-reset flip-flop must be driven by the appropriate disjunction of factors assigned by the interconnection algorithm. The disjunction may be realized by a logical OR gate. Each of the factors is a conjunction of the coordinates of the entries of the previous cover, that is, a conjunction of the appropriate states of the previous flip-flops and the original inputs. The conjunction may be realized by a logical AND gate. The state of the previous flip-flops may be obtained from their physical outputs. Note that the circuit considered is a clocked synchronous circuit. Again this hardware implementation is best shown by an example. Using the automaton constructed in the example of the previous section, we obtain the physical implementation shown in Figure 4.5.1.

Figure 4.5.1
Hardware Implementation

Notice that the interconnection algorithm, by its nature, ensures that signal will not appear on more than one of the physical inputs to any one flip-flop, hence ensuring the validity of our model.

Figure 4.5.2a
Three-State Reset Machine

Figure 4.5.2b
Three-State Reset Machine

In Figures 4.5.2a and 4.5.2b we show how a three-state set-reset flip-flop may be constructed from two two-state flip-flops by a simple partitioning of states. Returning to the implementation of Figure 4.5.1, it is a simple matter to write the state table for it, as shown in Figure 4.5.3.

Comparing this state table with the original one in Figure 3.1.3 we see immediately that if we let state A correspond to the state (00000), we may quickly obtain the other correspondences. They are listed here:

We have so far neglected the output of the automaton. In the automaton of Figure 3.1.3, to realize the event

the set (A) of final states defines the output required. In the feedback-free cascade of set-reset flip-flop realization shown in Figure 4.5.1 the output is obtained by the conjunction of the states that correspond to the original state A, that is s₁₁s₂₁s₃₁s₄₁s₅₁. This output may be realized by an AND gate having those five inputs.