CHAPTER III

Permutation-Free Events

The class of permutation-free events has been defined by Papert and McNaughton [4] as those regular events that are realized by automata for which there does not exist a subset S_i of states and a word x in A* such that T(S_i,x) is a permutation of s_i. In this chapter the class of permutation-free events is defined in a different manner, but is essentially identical to that of Papert and McNaughton.

3.1 The Ross Tree

To define permutation-free events it is useful first to define a ross and a ross tree.

• Definition 3.1.1 The refined ordered successor set of a set of states of an automaton S_i=(s_i1, s_i2,...s_in) under input a_r is the ordered set s_k=(s_k1, s_k2, ...,s_kn) obtained from the ordered successor set s_j=(s_j1, s_j2,...s_kn) by removing all s_jp such that there exists an s_jq=s_jp with q<p.

For convenience a refined ordered successor set will be called by its initials, that is it will be called a ross. The ross s_k of a set s_i is always of cardinality equal to or less than the cardinality of that set s_i. When the cardinality of a set and its ross are equal, the order of the elements within the set must be maintained. If, however, the ross has fewer distinct elements, these elements may be arranged in any convenient order. Two ross are equal if they are equal in membership but not necessarily in order. Two ross are identical if and only if they are equal in both membership and order. One ross is a permutation of another ross if they are equal but not identical.

• Definition 3.1.2 A ross tree is a tree structure starting with the set S of all states of an automaton as the only node at level zero. Each node at level n branches to one node at level n+1 for each a in A. Each node at level n+1 is the ross of a non-terminal node at level n under some input a_i in A. A set is considered a terminal node if it is equal to a previously encountered node in the same branch or if it is a singleton set containing only one state of the automaton. A branch is the direct path between a node and the zero level node.

Since there are a finite number of states in an automaton and hence a finite number of ross, the tree will terminate in a finite number of levels, that is, when all the branches have been terminated. If all the branches terminate with an identity, that is, there are no branches terminating with a permutation, then the tree is called permutation-free. A singleton set can of course in no way generate a permutation, hence it is terminated early. A leftmost reduced tree may be generated to reduce the size of the tree by following the additional rules: Construct the tree to the left using the first letter of the alphabet through as many levels as possible until a terminal node is reached, then continue on the previous level with the next letter of the alphabet. In this manner nodes may be considered terminal if they appear anywhere else in an already terminated branch, as the subtree generated by that node will be identical to the subtree already generated by the first appearance of that node.

An automaton with a permutation-free ross tree is said to be permutation-free. The event realized by a permutation-free automaton is called a permutation-free event. The class of permutation-free events is denoted by PF.

The construction of the ross tree may be shown by several examples. Consider first the automaton of Figure 2.3.1 realizing the event R=(01)*, The state table is shown again in Figure 3.1.1a for convenience in constructing the ross tree in Figure 3.1.1b.

Figure 3.1.1b
Ross Tree

Under input 0 the set (ABC) goes to ross (BC). Under 0 the ross (BC) goes to ross (C) which is terminal because it is a singleton. Under 1 (BC) goes to (AC), under 0 (AC) goes to (BC) which is terminal because it appears in level one of that branch. Under 1 (AC) goes to (C) which is terminal because it is a singleton. Under 1 (ABC) goes to (AC) which is terminal because it appears in an already terminated branch. This concludes the construction and since none of the terminations were permutations, the ross tree is permutation-free. Hence the event R=(01)* is in PF. Consider next the automaton shown in figure 2.4.2 realizing the event R=(11)* which was not in GF. The construction of the ross tree shown in Figure 3.1.2 shows that (ABC) under input 1 produces the ross (BAC) which is a permutation of (ABC).

Figure 3.1.2b
Ross Tree - Event (11)*

Hence event (11)* is not in PF. Consider finally the automaton depicted by the state table in Figure 3.1.3a which realizes the event R=(I11(I00I)'11I)' which is obviously in SF.

Figure 3.1.3b
Ross Tree

The ross tree shown in Figure 3.1.3b is large but is easily seen to be permutation-free. Hence (I11(I00I)'11I)' is in PF.

In the definition of a ross, if S_i is a ross of S_j, and the cardinality of S_i is less than that of S_j, we have allowed the elements of S_i to be arranged in any convenient order. It may happen that S_i is a ross of two sets S_j and S_k. Because we have allowed some choice in the ordering of the elements of S_i, we must avoid having unnecessary permutations of the elements of S_i resulting from this arbitrary ordering and not from the action of the automaton. If in the leftmost reduced tree, the first appearance of S_i is S'_i, the ross of S_k, then when S_i, the ross of S_j appears in another branch of the tree, we must rearrange S_i to conform to the order of S'_i. For example, notice that in the first example, shown in Figure 3.1.1 the first choice for the ross of (ABC) under input 1 is (CA). But, since this is a case where the cardinality of the ross has been reduced, and we already have (AC) in an already terminated branch, we choose to rearrange the order.

The mapping T may be modified to a mapping T such that T(S_i,a_j) is the ross S_k of S_i under input a_j. T may also be extended, as T was, to include T(S_i,x) under input string x in A*. Again notice that because choice of order is allowed when the cardinality is reduced, the mapping is not uniquely defined in that case. However, this causes no problems.

3.2 Equivalence of Classes of Events

In this section a number of theorems are presented showing that all the classes of regular events described so far are equivalent. That is, the classes of star-free, non-counting, group-free and permutation-free events are all different definitions of the same single class of events. The first two theorems relating to permutation-free events are similar to theorems given by Papert and McNaughton. but first an initial lemma is presented.

• Lemma 3.2.1 If there exists an ordered set S_i=(s_i1, s_i2, ..., s_in) which under some input word w in A* goes to ross S_j=(s_j1, s_j2, ..., s_jn) which is a permutation of the set S_i, then there exists a set S_k=(s_k1, s_k2, ..., s_km) such that 2≤m≤n and such that T(s_kp,w)=s_kp+1 for all p, 1≤p≤m-1, and T(s_km,w)=s_k1.
  
  Proof: Both S_i and S_j are made up of the same n distinct elements but in some different order. Therefore each element has only one successor and is the successor of only one element, under input word w. If there exists an element which is its own successor, it may be cast out of both sets S_i and S_j creating new ordered sets S'_i and S'_j. When all such states have been cast out, both S'_i and S'_j are made up of the same n'≤n distinct elements but in some different order, and again each element has only one successor and is the successor of only one element under input w. If S'_i and S'_j are empty then S_i and S_j must have been identical which was not so. If S'_i contains some element s_i then S'_j must contain s_j=T(s_i,w)≠s_i. Since S'_i and S'_j are equal, S'_i must also contain s_j. Hence n'≥2. Let s_k1 be the first element of S'_i and s_k2 be the first element of S'_j; hence T(s_k1,w)=s_k2. But s_k2 is also en element of S'_i and its corresponding member of S'_j is T(s_k1,w). If T(s_k2,w)=s_k1 then we have the required set S_k=(s_k1, s_k2); else T(s_k2,w)≠s_k2 because we have cast out elements of this type. Hence let s_k3=T(s_k2,w). Now generalizing: If T(s_kp,w)=s_k1 the required set is S_k=(s_k1, s_k2, ..., s_kp); else T(s_kp,w)≠s_kr, 2≤r≤p, because s_kr is already the successor of s_kr-1. Hence it can only be equal to s_k1 or some new element s_kp+1. This must terminate at s_kn', if not sooner, because there are only n' elements, in which case T(s_kn',w)=s_k1 because s_k1 is the only element in S'_j which is not a successor of any previous elements. Hence we obtain the required set S_k=(s_k1, s_k2, ..., s_km) 2≤m≤n'≤n.

• Theorem 3.2.1 The set of non-counting regular events is contained in the set of events realized by automata whose ross trees are permutation-free, that is NC⊆PF.
  
  Proof: Assume R∉PF; then there exists a terminal set in the ross tree which is a permutation of a preceding ross. Let w in A* be the word which is a concatenation of the inputs required to travel from that preceding ross to the terminal ross. Then, by Lemma 3.2.1, there exists a set S_j=(s_j1, s_j2, ..., s_jm), m≥2 such that T(s_ji,w)=s_ji+1 for all i, 1≤i≤m-1, and T(s_jm,w)=s_j1. By definition of a reduced automaton, there is a word x in A* such that one but not both of T(s_j1,x) and T(s_j2,x) is in F. Let v₀ in A* be a word such that T(s₁,v₀)=s_j1. For any value of k≥0 in vw^kx and vw^k+1x there is a v=v₀w^p, where p is the smallest integer such that k+p is a multiple of m, which makes T(s₁,v₀w^pw^k)=s_j1 and T(s₁,v₀w^pw^k+1)=s_j2. Hence one but not both of v₀w^pw^k and v₀w^pw^k+1 is in R. Thus R∉NC and it follows that NC⊆PF.

• Theorem 3.2.2 The class of events realized by automata whose ross trees are permutation-free is contained in the class of events realized by automata with group-free monoids.
  
  Proof: Suppose R∉GF. Then there is an element (congruence class) w in the syntactic monoid of the automaton M such a (w,w²,...,w^q) is a cyclic subgroup around idempotent w^q where q≥2. Let w be a word in the congruence class w, then w^q≡w^2q mod M. But w^q≠w^q+1 mod M and so there must be a state s_i such that s_j=T(s_i,w^q)≠T(s_i,w^q+1). Now T(s_j,w)=T(s_j,w^q+1)≠s_j, but T(s_j,w^q)=T(s_i,w^2q)=T(s_i,w^q)=s_j. Now consider the set of states S_j=(s_j, T(s_j,w), T(s_j,w²), ..., T(s_j,w^q-1)). The number of distinct states in S_j must be a divisor of q, but it cannot be one, since T(s_j,w)≠s_j. Hence w makes a non-trivial permutation on S_j. The set S_j appears as a subset of S in level zero of the ross tree of the automatom M. This subset S_j must appear in all ross of S under input wⁿ. Since the tree is finite, for some power n, the ross T'(S,wⁿ) must be equal (in membership) to the ross T'(S,wⁿ⁺¹). However, they cannot be identical because those elements of T'(S,wⁿ) that are also elements of S_j are permuted. Hence R∉PF. Hence PF⊆GF.

• Theorem 3.2.3 The following classes of events are identical: SF, NC, GF, PF.
  
  Proof: From theorem 3.2.1 we have NC⊆PF. From theorem 3.2.2 we have PF⊆GF. From theorem 2.4.2 we have GF⊆NC. From the above three theorems we can say NC≡PF≡GF. From theorem 2.2.1 we have SF⊆NC. And from theorems from Papert and McNaughton [4] and from Meyer [8] and Cohen and Brzozowski [14], we have SF≡GF≡NC. Hence SF≡NC≡GF≡PF.

3.3 Tests for Star-Free Property

In Chapter II we saw that for some events we could write a regular expression with stars and one without stars representing the same regular event. We said there that a regular event was star-free if and only if a star-free regular expression could be written for it. However, the given regular expression may contain stars and there may not be any simple method of deriving a star-free expression from it, yet we would like to know whether the event is star-free or not. From the equivalences of the last section we see that all we have to do is determine whether the event is group-free or non-counting or permutation-free. In view of this, Papert and McNaughton [4] have presented two possible tests. Both tests require the construction of the syntactic monoid, which can be sumbersome. One test requires a search for permutations between elements of the monoid, but no algorithm is given. The second requires a search for non-trivial groups in the monoid and is a well-defined test, but requires the additional labour of constructing the monoid multiplication table. The permutation-free test using the ross tree is a simple well-defined test:

1. From the expression of the event, or from the automaton, find the reduced automaton [Appendix B].
2. From the reduced automaton, construct the ross tree.
3. If the ross tree is permutation-free, then the event is in PF and hence in SF.

The test is somewhat related to Papert and McNaughton's first test, and, really an extension of Brzozowski's test for definite regular events [11]. Definite events are a small subset of star-free events and may be tested for by requiring the input successor tree to terminate only in singletons. The ross tree introduces ordering and multistate termination to the definite-event test, giving us a test for a much larger class of events. To illustrate the relative simplicity of the ross tree test, the reader is invited to test the example in figure 3.1.3 by the GF method.