THE U N I V E R S I T Y OF M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Philosophy Technical Note COMMUTATIVE MACHINES Richard Laing Jesse B. Wright ORA Projects 03105 and 04422 under contract with: DEPARTMENT OF THE NAVY OFFICE OF NAVAL RESEARCH CONTRACT NO. Nonr 1224(21) WASHINGTON, D.C. and OFFICE OF THE CHIEF SIGNAL OFFICER RESEARCH AND DEVELOPMENT DIVISION CONTRACT NO. DA-SIG-36-o39-61-G4 WASHINGTON, D.C. administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR December 1962

COMMUTATIVE MACHINES* Richard Laing and Jesse B. Wright *This research was supported through Contract Nonr-1224(21) of the Office of Naval Research, and through Grant DA-SIG-36-039-61-G4 of the Office of the Chief Signal Officer.

COMMUTAT I VE MACHINES In this paper certain commutative automata and their behavior are discussed. We begin with characterizations of the class of machines under consideration. We then go on to show several associations between this class of machines and a set of words, and a set of points. We then show an association between a language for the set of words and the set of points. Some results about this language are presented, after which we show how machines can be constructed which realize the behavior expressed in this language. We conclude with results and comments on the characteristics of commutative machines and their transition systems. I. BASIC TERMINOLOGY A machine M is a quintuple M = < S, s, fa, fb, T > in which S is a (finite or infinite) set of states of M; s c S is the initial state of 0 M; fa, fb are the (direct) transition functions of M which take elements of S into elements of S; T is a (finite or infinite) subset of S, called the terminal state(s) of M. When for every s C S, sfafb = sfbfa, then M is a commutative machine (c-machline). We associate with each M a set of words. Let W be the set of all words in a and b (and including A, the null word). There is a useful association between the words in W and the states s c S of machines M. For any w E W and any s E S in a machine M, w = s will mean that if the functions fa, fb are applied to M in the sequence indicated by the word w (reading from left to right) and starting in s (and A applied to s results in s ), then the result will be s. 2

The behavior of a machine M is the set of all words w such that w = s for some s c T. W is the free algebra, where W = < W, A, fa, fb > and where (as before) W is the set of all words in a and b, and A is the empty word, and where wfa = wa, wfb = wb, for all w e W. Whenever we have M = < S, s, fa, fb, T > consider a mapping H(w): W -+ S. If 11(w) = s, then s is the state into which M is taken by the input sequence w beginning in state s. H(w) is a homo0 morphism between W and M. We now introduce the c-machine L which plays for commutative machines a role analogous to that of W for the class of all M. L = < L, X, fa, fb > where L is the set of points in the plane with non-negative, integral coordinates (i.e., the lattice-points in the first quadrant) and where X ~ L is the origin. For every p E L, pfa is to mean the point one unit to the right of p, and pfb is to mean the point one unit above p. The functions fa, fb commute so that for every point p E L, pfafb = pfbfa. L may be viewed as a commutative machine (without final states) where the p e L are the states of L. Consider W and an M. If M is a c-machine then we can interpolate L between W and the c-machine M. Consider the mapping P:W + L which for any word w associates a corresponding lattice-point p; P(w) = p, such that starting at X and moving right one unit for each a in w and upward one unit for each b in w, we arrive at p. For any p e L, h(p) = s is to mean that if a c-machine is placed on X c L while in state s, and moves right one unit under fa, and upward one unit under fb, then M will be in state s when resting on p c L. (Alternatively, h(p) = s can be interpreted "s is the state into which M is taken by a word w, where P(w) = p, with M started in s.") Because the 0 machine M is a c-machine, the point p it reaches in L is independent of the path it follows to p. 3

Consequently h is a well-defined, single-valued function. H(w) = h(P(w)). Note that hi is a homomorphism. W, L, and an M, where M is a c-machine, are related in that if we apply the mapping from W - M, it is the same as if we go from W -+ L N+ M. Thus the study of commutative machines is the same as studying all homomorphic images of L II. A LANGUAGE FOR DENOTING POINTS OF L. The behavior of any machine is a set a of words w such that w = s for some s E T. In addition, if M is a c-machine then M has associated with its final states a set of points of L such that h(p) e T. Regular expressions (see [1, 2]) have frequently been used to denote the set of words a which is the behavior of a finite machine. Under a different usage we can employ regular expressions to denote the behavior of a c-machine. If 8 is a regular expression denoting a set of words, then let c(8) be the commutative closure of the words of 8. c(6) is the behavior of a c-machine. If a c-machine M has a behavior c(6) then P(c(f)) is the set of lattice points of L corresponding to the final states of M. Note that P(B) = P(c(U)). Regular expressions can thus be employed to denote the points of L which are associated with the final states of certain c-machines. The use of regular expressions in denoting points of L is shown in the following figures.

aabb aa Figure 1 1 I I I P I 1 X AL< a(bb) abb( 2a) * (aa)* Figure 2 Figure3. Ad(aa) *(bb)*.

Ah ~~~ ~ ~ ~ / fo~ ~, I G\ I 1 IdI I* S> I | I; / 1 FFre Figure / yab(aa) (bb) Figure Figure 6

Figure 7. (aa) *(ab)*. Figure 8. (abb) *(ab) * 0 0 $ 0 0 0 0 0 ~ 0 ~ * 9"~~~~ 0 a-axis Figure 9. Fundamental set (aaabbbbb)'~(aabb)*(aaab)*

If a set of points P contained in L is denoted by a regular expression of the form w w * or w w * w * (where w may be A) then P is a fundamental 0 1 0 1 2 0o set. (Also w is called the origin of the fundamental set, and w *, w * are 0 1 2 called the axes of the fundamental set.) If P is denoted by w w * w *, where the points denoted by w, w along with the point X, are not collinear, then P is a planar fundamental set. If P is denoted by w w * and w f A, then 01 1 P is a linear fundamental set. (Thus the arrays of points shown in figures 3, 4, 7, 8, 9 are planar fundamental sets, and the points of figure 2, 5, 6 are linear fundamental sets.) If the pattern of points of a planar fundamental set is extended beyond its axes over the whole first quadrant, then we will speak of such a set of points as the extended fundamental set of the given fundamental set. When a fundamental set is described by an expression w * w *, where w and w are mixed words (in both a and b) then the lines of points w *, w * 1 2 are oblique, and we will speak of such an expression as w * w * as describing an oblique planar fundamental set (and similarly for linear fundamental sets). When an expression is of the form w * w * where one of the two words w, w is in a's alone and the other in b's alone we will speak of the set as orthogonal. Theorem: Every extended fundamental set derived from an oblique fundamental set is a union of orthogonal fundamental sets. Two fundamental sets, w w * w * and w w * w * are said to be conjugate 0 1 2 3 4 5 if c(w * w *) = c(w * w *). Thus two fundamental sets are conjugate if, when 1 2 4.5 they are given the same origin, they coincide. If two fundamental sets have their respective axes parallel they are called similar. 8

Theorem: If two fundamental sets are similar but not conjugate, they can be made conjugate by use of the Key Identity. Lemma: Key Identity: Where x is a regular expression, x* = (A u x)k-1 (xk)* The Key Identity allows infinite periodic sets of points in a line or in a planar array to be represented as a finite union of conjugate sets of the same kind. This changing of the period of the representation of an infinite set facilitates the comparison of infinite processes. Theorem: Quasi-Normal Form. Where w, w, w are any words of W, then 0 1 2 any regular expression for denoting points of L can be put in the form of a finite union of constituents of the following kinds: w w * w w * w w w * w * 0 0 0 1 0 1 2 The following identities are employed in obtaining this result. Where x, y are regular expressions: Universal Identities 1. (x U y)* = (x* y*)* 2. x* = (A u x)k-l (Xk)* (Key Identity) Commutative Identities 1. xy = yx 2. (x u y)* = x* y* 3. (x* y )* = A U x* y* y This last identity allows the reduction of star-height of commutative regular expressions so that no star operates over a star. 9

Proof: [Note: x* = A u x u x x u...] (x* y )* =A u (x* y) u (x* y)2 u = A u (x* y) u (x* x* y y)... = A u (x* y) u (x*2 y2) u... (x*n yn) [Note: x*2 = x* x* = (x u x)* = x* (and likewise for the nth pcwer)] A u x* (y u y2 u y3. yn...) A u x* y* y Thus, beginning with an arbitrary regular expression, and employing in particular the commutative identities 2 and 3 above, an expression is obtained composed of a union of constituents within which there are no unions and having no stars operating over starred expressions. Some of the resulting constituents may, however, contain long concatenations of starred words. Constituents of this sort may be brought into the proper form by use of the following result: Lemma: Star-length Reduction. Any constituent of the form w * w * w * 0 1 2 can be placed in the form (A u w u w 2... 0 0 " 0 1 2 Thus, beginning with a constituent composed of a concatenation of any length, of starred words, a portion of star-length three of the constituent can be reduced to star-length two. This process can be repeated, and, with law, applications of the distributiveA the whole expression reduced to the desired form. Proof: Case 1: At least two of w *, w *, w * lie on the same line. 0 1 2 Similar linear fundamental sets are thus established, which by the Key Identity can be made conjugate, and the result is obtained 10

Case 2: No two of w *, w, w * lie on the same line. Because 0 1 2 of the commutativity identity we can assume without loss of generality that w * is the line of points lying between w * and 0 1 w *. w * w * can be viewed as determining a planar fundamental 2 1 2 set, and w * can be viewed as providing an infinite set of 0 relative origins for w * w *, i.e., establishing an infinite 1 2 series of conjugate fundamental sets of the form w * w *. 1 2 Of two conjugate fundamental sets, F, F', if the origin of F is contained in F, then F' - F. A linear fundamental set (an infinite linear periodic set of points) within a planar fundamental set, and having a point in common with the planar fundamental set, has an infinite periodic subset (a linear fundamental set) in conmmon with the planar fundamental set (from Chinese Remainder Theorem). Thus since w * and w * w * have the origin in common, an 0 1 2 infinite periodic subset of w * is contained in w * w *. In 0 1 2 particular there exists a number such that w raised to that number is an element of w * w *, Let k be that number. As long as w i, 1 2 0 i < k, then the relative origin chosen from w * does not satisfy the hypothesis that the origin of F' is in F. When i reaches k, at that point and beyond (because of the periodic nature of the process) every element w i for i ~ k is an element of 0 (A u w k) * w * 0 1 2 Given any planar fundamental set F, there can be, in L, only a finite number of zero intersection fundamental sets conjugate to F. Given any linear fundamental set, there can be on a line in L only a finite number of zerointersection fundamental sets conjugate to the given set. The number, ~, of 11

possible conjugate fundamental sets of a given kind F, (including F itself) under the above conditions will be called the index of F. Note that in the Star-length Reduction the index of w * w * is a bound on k. As will be seen in the section on construction, certain classes of commutative machines realizing behaviors expressed as the points of fundamental sets will prove to have minimal numbers of states related to the index of the associated fundamental sets. Lemma: Given two regular expressions E and E' in quasi-normal form, denoting points of L, it can effectively be decided whether E = E', i.e., whether E and E' denote the same points of L. Detailed proof will not be given. Proof is obtained by first applying techniques for determining coincidence in the constituents within E and within E'. After this redundancy in E and E' separately has been eliminated, E and E' are examined together for coincidence and difference. Important tools in facilitating the making of these comparisons are results in elementary number theory such as the Euclidean Algorithm, the Chinese Remainder Theorem, and such intermediate results as the Key Identity and the fact (already mentioned) that if a planar fundamental set and a linear fundamental set lying wholly between the axes of the planar fundamental set have a point in common, then they have a linear fundamental set in common, and a regular expression for this set can be obtained. Note also that if E is any regular expression in quasi-normal form, with constituents e, e, e,... e,then c(E) = c(e ) u c(e)... u c(e). 0 1 2 n 0 1 n Theorem: Given any two regular expressions, E and E' it can be decided whether c(E) = c(Ed). This follows from the last Lemma, and from the earlier result that any regular expression can be put into quasi-normal form. 12

III. CONSTRUCTION OF COMMUTATIVE MACHINES We have shown how regular expressions can be employed to denote points of L, our lattice-point model. These points of L in turn are employed to denote all the legitimate paths to the points. The words which are associated with these paths are the behavior of the commutative machines under consideration. We will consider in some detail the construction of machines which realize the behavior denoted by certain expressions in quasi-normal form, Some of these machines will prove to be finite state devices, and some of them will be infinite state devices. The use of the lattice-point model L as a guide to the constructing of state-diagrams for both finite and infinite machines is central to our discussion. Any commutative event can be represented in a set of lattice points a of L. The process of producing a machine M consists in merging points of L relative to a and a' (complement of a) to form states of M. Consider an operator -p (merge) which is to be applied to sets of points of L Definition: p(a) is a c-machine. Definition: Let x - y mean x and y can be merged; then x ~ y if and only if for all u's,x u e a is equivalent to y u e a, where x, y, u are elements of L. - is thus defined. Definition: ~(a) = L (mod -) (the quotient of the free algebra L where we factor out -) with the X designated an output if and only if x c a (x is the set of all points related to x by -). 15

Lemma: ~ is an equivalence relation on L and is a right congruence. (It is in fact a bi-congruence.) Thus: the two input operations of L induce operations on the equivalence classes by choosing representatives and the result is independent of the choice of these representatives. Every equivalence class is either entirely in or entirely out of a Since we wish to take the equivalence classes as states we must show the transitions between these states. From the Lemma it is apparent that the next state under an a-transition for example, can be obtained by taking a representative of x (x itself perhaps) and finding the point one unit to the right. The — class of this point is the state sought under an a-transition. Similarly for a b-transition. Theorem: The machine p(a) is the minimal machine having behavior a. Certain points cannot be merged. Consider a and any merging relation ~ for which L (mod ~ ) has behavior a. Given a, x - y implies x u ~ a if and only if y u E a. Thus: If a u can be found such that x u E a and y u e a', then x, y cannot be merged. Note that if F is an oblique fundamental set and x, y are two points, then if the line through x, y is not parallel to F, we cannot merge x, y. Regularity Criterion If a set of words is non-regular, the set will not be "acceptable" by the finite machine. All finite sets of words are regular. An infinite set a is non-regular if there is an infinite set a with an infinite sub-set such that if you call find two elements (words) of B such that when you add a word to one of the elements then the resulting word is in a, but when you add it to the second element of the pair then the result is not in a. If such a B cannot be found, then the set a is regular.

Corollary: The set of words associated with any oblique fundamental set is non-regular. Corollary: The set of words associated with any oblique fundamental set is not acceptable by a finite automaton. We now apply these results to construct machines realizing various behaviors. The behaviors first considered satisfy the Regularity Criterion above and thus prove to be realizable by finite machines. Finite state machines. The state diagram for the behavior denoted by c(w) where w is an unstarred word can be easily obtained. The method to be employed will be made apparent by use of example. Let us attempt to realizec(aa) and also c(aabb). (Figure 1 shows the points denoted by these expressions.) ExampZe 1: c(aa): The commutative closure of aa is again aa. A state diagram is to be obtained of a machine which will "detect" or "accept" the word aa and no other words, in the sense that application of the sequence aa will place the machine in an s E T, and no other word will place the machine in an s C T. Using L as a guide, and identifying X of L with the initial s of a a a machine M, then s + s, s + s (read "s by a takes M to s " etc.). This 0 1 1 2 o 1 is the only acceptable path (word), and s e T. "O a jl a1 2 15

No other words are to result in placing M in an s s T. In this particular M, receipt of any b whatsoever, or any number of a's greater than two, will take the machine into a "limbo" state: a state which is not an s C T, and which the machine can never leave. In this case s is a limbo 3 state. "3 B___ Thus all points of L other than s, s, s are limbo states. Since all limbo states have the same behavior, viz, upon receipt of either a or b the machine remains in the limbo state, all limbo states may be merged into a single state. The state diagram for an M realizing c(aa) is: b a a

In order to indicate an s s T we will often mark the state with an x. Also, to secure neatness of state diagrams we will often abbreviate the transitions to limbo by SL. Thus the machine M = < s, S, f fb T > realizing C[(aa)] is: 0 a'' S S, S {s, s, s, s } T = {s }, and the transition functions f fb 0 0 1 2 3 2 a are: or (alternative notation) fa a s fa = s s s 0 1 0 1 fb = s 0 3 0 3 fa a s $ = S S - S 1 2 1 2 sfb s s b 1 3 1 3 fa a = S S ~1-. S 2 3 2 3 fb b s fb s s b s 2 3 2 3 s fa = S a s 3 3 3 3 fb b s - S S S 3 3 3 3 ExamprZe 2: c [(aabb) ]: b b b 8a a a b b b a a a b b b a a a 17

Lattice Model (aabb) b SL SL a a a SL S ( S - _ SL c-machine c (aabb) (s e T) 8 This machine accepts aabb, abab, abba, bbaa, baba, baab, and no other words. ExampZe 3: c(aa u aabb): In realizing the behavior of a finite union of unstarred words, the resulting machines can always be at least partly combined. L sL sL 3<+~~~~~~ ~~~sL b b b a { _ S L By distinguishing both s and s as elements of T we can realize c(aa) and c(aabb) in the "same" machine.

ExampZe 4: c(aa)* (See Figure 2): b sb a 1 a Note: (1) The index of (aa)* is 2. If the points (states) on the a-axis are numbered respectively 0, 1, 2,... etc., then all the even numbered states can be merged into the single state s, while all odd numbered states on the a-axis can be merged into the single state s. (2) As before, the remaining states (points) of L are merged in the single limbo state s. (3) Since A is an element of c(aa)* the machine, in s initially, also is "on", initially, under receipt of A. 19

Example 5: c (abb'(aa)*):....I I b b b b b b bb b "L ad But note that parts of the above machine can be merged reducing the machine from 10 states to a 7 state minimal machine for c(abb%(aa)*). 20

b L BL LB Example 6: c ( (aa) * (bb)*) (See Figure 3): a b b b a 21 b b

There are four fundamental sets conjugate to AC"(aa)*(bb)*: A" (aa)*(bb)* itself, a"-'(aa)*(bb)* Xb(aa)*(bb)*, and (ab)'"(aa)*(bb)*. All the points of L which are "output" points, viz. A"'(aa)*(bb)* are merged into s e T; all the points of L which we denoted by the other three fundamental sets are merged to form states s, s, s respectively. Note that the index, ~, of the fundamental set (aa)*(bb)* is 4, and that this is the minimal number of states for the machine realizing this behavior. This is true in general of planar fundamental sets which denote the behavior of finite machines. For linear fundamental sets, because of the limbo state, the minimal machine realizing finite behavior is t + 1. Example 7: c(ab(aa)*(bb)*): b Eapb b B b a Compare Example 6. By designating a different initial state the behavior is modified without additional states. Note that by thus choosing alternative initial states the behavior denoted by each of the conjugate fundamental sets can be obtained. 22

Example 8: c (aaabbb'(aa) * (bb)*): This additional behavior cannot be directly realized by merely re-labelling the initial state as in Example 7. Additional machine states are required. s15 e T b a a a b b b b c ((aaabbb)^(aa) * (bb) *) adb~ 2 b b Db (S BQ~~' 23

Theorem: If a planar fundamental set is extended over the first quadrant, then the minimal c-machine having the behavior denoted by the set of points has a number of states equal to the index of the extended fundamental set. In some cases the minimal machines associated with extended fundamental sets may be "skewed" as in the following figure. / < a Exampte 9: c((A u aabb u aaaab)v'(aaaaaa)*(bbb)*) This machine realizes the behavior denoted by the oblique fundamental set (aabb)* (aaaab)* extended over the first quadrant. Recall from Section II: Theorem: For every fundamental set with oblique axes, there is a union of fundamental sets with orthogonal axes (axes in a's alone and b's alone) such that this union is just the points of the oblique fundamental set extended over the first quadrant. 24

Corollary: For every minimal machine which is skewed, there is an "orthogonal" machine with the same behavior, (having usually several s e T). Thus the behavior of a minimal skewed machine can be realized by a direct product of counters. The "orthogonal" (18-state) machine realizing the same behavior as the minimal (6-state) "skewed" machine of the last example, is shown below, a a a,a a 2 ) Ha bb b b b 25

Since the machines of Examples 1-9 are all finite, there exist ordinary regular expressions [1] denoting their behavior, thus: Comment: Where 8 is a regular expression in quasi-normal form, and where c(s) denotes the behavior of a finite c-machine, then for every c(s) there is a corresponding Kleene regular expression for the behavior of the machine. For example, Lawrence Eggan has shown that an ordinary regular expression for c((aa)*(bb)*) is (aa u bb u (ab u ba)(aa u bb)*(ab u ba))*. An ordinary regular expression for the behavior of a c-machine can be obtained by the Analysis technique applied by Kleene. This technique, however, does not guarantee any minimality properties of the expression. In particular, the star-height of the resulting ordinary regular expression may not be minimal. Comment: Where the behavior c(a) requires an infinite c-machine there can be no ordinary regular expression for this behavior. Comment: For any regular expression, it can be decided whether it denotes the behavior of a c-machine. (Using the Kleene Synthesis result, construct the machine realizing the behavior denoted by the regular expression. Minimize the resulting machine [3]. Test each of the states of this machine for the commutativity condition, sfafb = sfbfa.) 26

Infinite Commutative Machines Some behaviors describable by employing the c-operator on regular expressions in quasi-normal form cannot be realized by finite machines, This will be indicated by means of the following examples: Consider the following set: c(ab)*fAa*b*. a*b* is regular, and if c(ab)* is regular, then the intersection of the two sets should also be regular. The intersection consists of all sequences in equal numbers of a's and b's intersected with all sequences in which a's precede b's. That is to say, all sequences of the form anbn, (where n ranges over all positive integers and zero). In order to detect the sequences of this set, the machine will be required to register the receipt of an and upon the receipt of bn indicate acceptance of the sequence. But n can be indefinitely large, and indeed an n can always be found which will exceed the registering capacity of any given finite machine. Thus, to realize the behavior c(ab)* a potentially infinite machine is required, and c(ab)* is not regular. Exampne 10: c(ab)*: a b _ 2 27

All of the points which lie on the line (ab)* can be merged into the single origin point (state) s, which is also the output state. In addition, all of the points on lines parallel to (ab)* can be merged with their respective origins on the a and b axes. The state diagram for the infinite machine realizing c(ab)* can be set down in a linear fashion. b b b b b b a a a a a a Example 11: c(aab)*: b b b a a a a 28

Examnpe 12: c (aabb)* a a a a a b b b b In this case alternate points on the main diagonal and on lines parallel to the main diagonal map into upper and lower rows of points (states). The number of rows of points is equal to the index of the linear fundamental set which denotes the behavior of this machine. Exanmpe 13: c(aa'(ab)*): 29

In this case the initial and output states are not identical. The prefixed word aa can readily be accomodated as can any prefix in a's and b's alone by displacing the initial state the requisite number of proper transitions from the output state. ExampZe 14: c(aabb^ (ab)*): In order to realize this behavior, a "feeder" machine system must be employed. (See Example 8 for a feeder system to a finite machine.) b b b b b b b b a a a a a a b /b a ab b a 3o

Exampte 15: c((aa)*(ab)*): This behavior can be realized by distinguishing an infinite number of states as output states: in this case alternate states to the right of s 0 This technique can be applied to all cases where a pure word starred is concatenated with a mixed word starred. Exampte 6:c((aaabbbbb) "(aabb)* (aaab)*) The only "'machine" that realizes this behavior is the machine M whose state diagram is L and whose output set T is those points of L denoted by c((aaabbbbb) (aabb) * (aaab) *), Although points in lines parallel to oblique lines of points in a in L can be merged, since the a of this example is a system formed from two oblique lines of points, there are no lines of points parallel to both of the two nonparallel lines of points. Thus no points can be merged. Comment: For every regular expression a there are machines realizing the behavior c(a). Every regular expression can be put in the quasi-normal form, and in the foregoing examples we have shown how to realize the behavior denoted by any of the constituent types of the quasi-normal form. 31

IV. A CLASS OF TAPE MACHINES WITH INPUT The finite and infinite machines described in the preceding section can be represented in the form of certain tape-machines with input (TM). These machines have two major components: a finite state reading head, and an indefinitely expandible tape upon which are a finite number of "marked" squares. The reading head receives input symbols and upon receipt of such symbols, the reading head will undergo transitions, ancdove a unit distance right (R) or left (L) Dn the tape. These moves can be given by state diagrams or by a finite table (see example below). Whenever the reading head is in an s C T, and is resting on a marked tape square, the machine has an output. In all cases under discussion here, the reading head will be a finite state automaton which is also commutative. Thus the reading heads of these tape machines with input are precisely the finite devices discussed in the preceding section of this paper. For any finite commutative machine there is an associated tape-machine with input realizing the same behavior. This follows trivially by setting any finite commutative machine on the marked square of a tape so that the additional condition "when M is in an s s T and M is on a marked square of tape there is an output" is satisfied. Theorem: For any commutative behavior denoted by an expression of the form w w * (where w may be A) there is a tape-machine which realizes 0 1 0 this behavior. If w is a mixed word, then an infinite machine 1 will be required. There is a close relationship between the reading head required to realize this behavior and a class of finite commutative machines. 32

The transition structure of the reading head for a tape-machine with input which realizes the infinite behavior c(akbZ)* is identical to the transition structure for the finite c-machines realizing c[(ak)*(be)*]. To the transition structure so obtained must be appended moves (R,L) so that whenever an input sequence reaches ak then R, and whenever an input sequence reached b~ then L. If, instead of unit moves of the tape, right or left, we allow moves of any fixed finite number of tape squares, then the minimal reading head will have a number of states equal to the index of the linear fundamental set denoting the behavior. Exampte 17: c(aabb)* (See Example 11 for the realization of the infinite c-machine having this behavior.) (1) The transition structure of the reading head is obtained by constructing a finite c-machine realizing c(aa)*(bb)*. b b b 33

(2) To the above we append tape-move instructions R and L.'.e also add that the finite reading head.is placed on the (single) marked square of a tape and is in s (s E T) and is resting on the x-square, then there is 0 0 an output (s (x) = 1). Thus the TM for c(aabb)* is: a/ sO(X) =1 a The full description of the above tape machine with input may be presented in tabular form.

Present Input Action Next State State s a _ s o 1 s b _ s o 2 s a R s 1 1 1 O0 s b | | s Ou1tput sOIx) 3 1 3 5 a s 2 3 s b L s 2 0 S a R s 3 2 s b L s 3 1 1 Output: s (x) = 1 Start: s (x) 0 Note that if for example the above machine was started on tape square x-1 rather than on x (M(x-1) instead of M(x)) the machine would realize the behavior c(aa' (aabb)*) rather than c(aabb)*. Feeder systems to the reading head may also be employed. If we relax the restriction that only a finite number of squares of tape be marked, but require that the infinite markings be periodic, we can readily realize additional behaviors. If it is desired to realize a behavior such as c((aa)*(aabb)*) then every tape square to the right of the start x square should also be marked x. If it is desired to realize a behavior such as c((aaaa)*(aabb)*), then alternate tape squares to the right of the start should be marked. 35

Example 18: Some behaviors may not be realizable employing minimal state reading heads. Take for example c((aaa)*(aab)*). c((aa)*b*) is the behavior of the reading head, and this behavior can be realized by: so that c(aab)* can be realized by a tape machine with reading head, b/L b/L where the tape start square is x, and where s (x) = 1. 0

c(aa)*(aab)*) for example can be realized by marking all squares to the right of the start-square with x. c(a*(aab)*) can be realized by (1) marking all squares to the right of the stat. square with x, and by making both s (x) = 1 and s (x) = 1. c((aaa)*(aab)*) cannot be realized employing this (2-state) minimal c(aa)*b* reading head however. For this reading head has an insufficient number of internal states to distinguish aaa from a. c((aaa)*(aab)*) can be realized by the following tape machine with an 18-state reading head. The 18-state reading head is employed in order to obtain a common cycle with (aaa)* and is obtained by the technique of the Fundamental Identity Lemma of Section III. a/R 0 11;s s/ ( x)=l 312 a 113 3/R I a a/ 16 a b/ b/L b / b i \ b/L b/L b/L L —--- ~~~~a/R a a/"R a a/R a b/L b/L b/L b/L /L b/L a a/R a/ a s (X) = 1 S (X) - 1 S (X) = 1 s (X) - 1 S (X) = 1 s (X) - 1 37

The above machine is to start on the x square, and all squares to the right of this are also to be marked x. Printing Machines The use of a tape with a potentially infinite number of pre-marked squares may be found objectionable since under relaxed conditions this feature may permit the realizing of non-effective behaviors. Since, however, in the cases under discussion, the squares are to be marked in a periodic fashion, the marking procedures could be expressed as the behaviors of rather simple automata, viz. input-free finite automata. These automata would move the tape, (or move relative to the tape) and periodically print an x. Once the print machine had begun its action the reading head of the commutative tape machine proper could be set on the appropriate square ready to accept inputs. Both the move-print and the move-read actions can be combined in a finite automaton reading head. Exampte 19: cc((a*)(ab)*): Present Head Tape Input Action Action Next Head State State 1 2 State s X a R Px s o 0 s X b L - s o 0 s - a R - s o 0 s - b L - s 0 0 Output: s (x) 1 0 Start: s (x) 0

Upon receipt of a this machine will, when in s and viewing an x, move right one unit and then print on x, (Px). The tape-machine concept can be further modified to produce a "machine" for realizing the behavior expressed by an oblique planar array of points in L, (e.g. (aabb)*(aab)*). The lattice-point model is viewed as an infinite two-dimensional array of tape squares. With each of the points of L denoting the behavior to be realized is associated an x-marked square of the array of tape. Since the behavioral properties of the systems are being carried in the array, the reading head can be of the simplest sort, viz. a one-state device which under receipt of an a moves right, and under receipt of a b moves up, and which is "on" whenever it is resting on a marked square. V. COMMUTATIVE MACHINES AND THEIR TRANSITION ALGEBRAS We now characterize in a more precise fashion the machines under discussion. Lemma: The structure of M = < S, s, fa' fb' T > uniquely determines a semi-group operation (denoted by o ) on S, and such that given w — s, w s (for all w, w e W, s, s e S) then 1 1 2 2 1 2 1 2 s o s W w 1 2 1 2 39

Definition: A machine M is strongly connected if for every pair of states w s, s', there is some word w, such that s ~ s'. Definition: M is homogeneous if every machine obtained by choosing each s e S as initial state instead of s, is isomorphic to M. 0 The isomorphism intended here is structural and does not take final states into account. Definition: A machine M' will be said to be a sub-machine of M, if the states of M' are states of M, and the transitiions of M' are the same for M but the initial state of M is not required to be a state of M' (contrary to conventional usage). Definition: A machine is backwards-deterministic if its transition functions form a group. "The Logic of Automata", A. W. Burks and H. Wang, JACM, 4, 2, p. 286. Lemma: The following conditions (under the commutativity assumption) are equivalent: (1) M is strongly connected. (2) M is homogeneous. (3) The semigroup of M is a group. (4) M is backwards-deterministic.

Lemma: Every (finite) commutative machine M has a unique homogeneous sub-machine. That is, every M consists of a "feeder" system of states (possibly absent) and a system of states which is unique and homogeneous. (For explicit use of feeder systems to homogeneous machines see especially Examples 8 and 14 of Section IV. Note also that the homogeneous sub-machine need not contain a final state; see Example 3, where the "limbo" state forms the homogeneous sub-machine.) Definition: A state s of a machine is a feeder state if there is no mixed word w such that s W- s. Definition: A state s of a machine is a homogeneous state if there is a mixed word w such that s W s It is of course possible that a fixed, finite number of a's alone or b's alone will, for an s, return M to the same s. This is typically the case in the sort of homogeneous finite machine shown below, which (for s c T) 0 realizes the behavior c((aaa)*(bbb)*) In tib bb b b b 41

H!omogeneous Machines A homogeneous machine M is characterized by there being a mixed word w, such that s - s (that is, such that the initial state of M is a 0 0 homogeneous state). When M is finite and homogeneous there are positive integers i and j ta i. such that s a s and s b s. Thus, there is a pure word (other o o o o than A) which is an "identity" word. When M is infinite and homogeneous then there is a mixed word w such that s W s, (that is, there is an identity word which is a mixed word) 0 0 and there is no pure word which is an identity word. The points of L associated with the identity words of an infinite homogeneous machine are collinear. Observations: (1) Every finite homogeneous machine can be embedded in torus. (2) Every infinite homogeneous machine can be embedded in an infinite cylinder. The finite homogeneous machine (realizing c((aaa)*(bbb)*)) of the last figure can be embedded in a torus. Note also the "variants" produced by "'skewing," which, finite and homogeneous, can also be embedded in toruses. For example:

With any one state designated as both initial and final state, this system can realize the behavior c((A u aaabb u aaaaaab) (aaaaaaaaa)*(bbb)*). The infinite homogeneous machines which are embedable in infinite cylinders can conveniently be set down in an array in which a-transitions take the machine to states to the right, and b-transitions take the machine to states vertically above, until the top row is reached, at which point the next b-transition takes the machine to a state in the bottom row of the array. Repeated b-transitions will always take the machine to states in the bottom row which are to the left of previous states in the bottom row of the array. For example, c(aaabbb)* (where because of the homogeneity property any state can be chosen as initial and final state); Thus the machine under repeated a-transition goes to states to the right a I a I aa b b b bm b and under repeated b-transitions spirals "backward" around the cylinder to the left. Note that if the b-returns from the top row of states do not go to the left then the infinite machine ceases to be strongly connected, and becomes instead a species of counter.

APPENDIX Many of the results given in terms of an alphabet of two letters can be extended to expressions on larger alphabets. Lemmna: The star-length of constituents of a quasi-normal form can be made less than or equal to n, where n is the number of letters of the given alphabet. This result was obtained by Y. Give'on. Since the other properties employed in obtaining the quasi-normal form can be extended directly, Theorem: There is a quasi-normal form for expressions on alphabets of n letters. An association can be made between commutative regular expressions and the Presburger number theoretic logical language [4]. Let L, L,... L be 1 2 n the lattice point models for languages of 2 letters, 3 letters, n letters, etc. Theorem: For every regular expression E in n letters, there is a Presburger formula Q, having n free variables, which defines the same points of L n For the case of expressions for the behavior of finite commutative automata, this was conjectured by hI. P. Shutzenberger, z i was later demonstrated by C. C. Elgot and J. D. Rutledge [5].

There is a decision procedure for truth of sentences of the Presburger language. From this fact and the theorem above, the result of Section II that "for every two regular expressions E and E' it can be decided whether c(E) = c(E')" follows directly. Theorem: The set of regular expressions E such that c(E) is regular is effectively decidable. Given a regular expression E on two letters, there is a related Presburger formula Q(x,y). An equivalence relation = on points is introduced: (x,1 y (x2 y2) -,,Vu, v [Q(x + u, y + v) Q(x + u, y + v)] 1 1 2 2 1 1 2 2 The above Presburger formula expresses the fact that x, yl, x, y are 1 1 2 2 related by the induced congruence relation [6]. We now incorporate a finiteness condition for the number of congruence classes. 3z Vx, y 3x., l [(x <z, y <z) & ((x, y) = (x, y )] This expression asserts that there exists a finite automaton having the behavior c(E). By the Presburger decision procedure it can be determined whether such an expression as the above is true or false. Thus we have an effective procedure for deciding whether the event c(E) is regular, for any regular expression E. From the above two theorems it follows that, Corollary: For any regular expression E, for which c(E) is regular, we can effectively construct a finite commutative automaton whose behavior is c(E),. 45

REFERENCES 1. S. C. Kleene, "Representation of Events in Nerve Nets and Finite Automata," Automata Studies, (edited by C. E, Shannon and J. McCarthy), Princeton University Press, Princeton, New Jersey,(1956) 3-41. 2. Irving M. Copi, Calvin Elgot, and Jesse B. Wright, "Realization of Events by Logical Nets," J. Assoc. Comp. Mach., 5, (1958) 181-196. 3. E. F. Moore, "Gedanken-experiments on Sequential Machines," Automata Studies, (edited by C. E. Shannon and J. McCarthy), Princeton University Press, Princeton, New Jersey, (1956) 129-154. 4. M. Presburger, "Uber die Vollstandigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt." Comptes-rendus du I Congres des Mathematiciens des Pays Slaves, Warsaw, (1930) 92-101 and 395. 5. C. C. Elgot and J. D. Rutledge, (Paper to appear on "Generalizations of the finite automaton model," Mathematical Sciences Department, International Business Machines Corporation, Yorktown Heights, New York). 6. J. R. BUchi, "Mathematical Theory of Automata: Notes for a Seminar" given by J., B. Wright and J. R. BUchi, Fall 1960, The University of Michigan

DISTRIBUTION LIST (One copy unless otherwise noted) Assistant Secretary of Defense Bureau of Ships for Research and Engineering 2 Department of the Navy Information Office Library Branch Washington 25, D. C. Pentagon Building Attn: Code 607A, NTDS Washington' 25, D.C. Bureau of Naval Weapons Armed Services Technical Department of the Navy Information Agency 10 Washington 25, D.C. Arlington Hall Station Attn: RAAV, Avionics Division Arlington 12, Virginia Bureau of Ships Chief of Naval Research 2 Department of the Navy Department of the Navy Washington 25, D.C. Washington 25, D.C. Attn: Communications Br., Code 686 Attn: Code 437, Infor. Syst. Br. Naval Ordnance Laboratory National Security Agency White Oaks Fort George G. Meade, Maryland Silver Spring 19, Maryland Attn: R-4, Howard Campaigne Attn: Technical Library Director, Naval Research Labs. 6 Massachusetts Institute of Technology Tech. Infor. Officer, Code 2000 Research Laboratory of Electronics Washington 25, D.C. Cambridge, Massachusetts Attn: Professor W. McCulloch Commanding Officer 10 Office of Naval Research David Taylor Model Basin Navy No. 100, Fleet Post Office Washington 7, D.C. New York, New York Attn: Technical Library Commanding Officer, ONR Br. Office Naval Electronics Laboratory 346 Broadway San Diego 52, California New York 13, New York Attn: Technical Library Commanding Officer, ONR Br. Office University of Illinois 495 Summer Street Control Systems Laboratory Boston 10, Massachusetts Urbana, Illinois Attn: D. Alpert Chief of Naval Operations OP-07T-12 University of Illinois Navy Department Digital Computer Laboratory Washington 25, D.C. Urbana, Illinois Attn: Dr. J. E. Robertson

Technical Information Officer Massachusetts Inst. of Technology U. S. Army Signal R&D Laboratory Cambridge, Massachusetts Fort Monmouth, New Jersey Attn: D. W. Baumann, Dynamic Attn: Data Equipment Branch Analysis and Control Lab. U. S. Naval Weapons Laboratory Burroughs Corporation Dahlgren, Virginia Research Center Attn: Head, Computation Division Paoli, Pennsylvania G. H. Gleissner Attn: R. A. Tracey George Washington University National Bureau of Standards Washington, D.C. Data Processing Systems Division Attn: Prof. N. Grisamore Room 239, Bldg. 10, Attn: A. K. Smilow Washington 25, D. C. Aberdeen Proving Ground, BRL Aberdeen Proving Ground, Maryland Lockheed Missiles and Space Company Attn: J. H. Giese, Chief Comput. Lab. 3251 Hanover Street Palo Alto, California Office of Naval Research Attn: W. F. Main Resident Representative The University of Michigan The University of Michigan 146-B Temporary Classroom Bldg. Ann Arbor, Michigan Ann Arbor, Michigan Attn: Professor A. W. Burks, Dept. of Philosophy Commanding Officer ONR, Branch Office Census Bureau John Crerar Library Bldg. Washington 25, D.C. 86 East Randolph Street Attn: Office of Assistant Director Chicago 1, Illinois for Statistical Services, Mr. J. L. McPherson Commanding Officer ONR, Branch Office National Science Foundation 1030 E. Green Street Program Dir. for Documentation Res. Pasadena, California Washington 25, D.C. Attn: Helen L. Brownson Commanding Officer ONR, Branch Office University of California 1000 Geary Street Los Angeles 24, California San Francisco 9, California Attn: Department of Engineering, Professor Gerald Estrin National Bureau of Standards Washington 25, D.C. Columbia University Attn: Mr. R. D. Elbourn New York 27, New York Attn: Department of Physics, Naval Ordnance Laboratory Professor L. Brillouin Corona, California Attn: H. H. Weider

University of Illinois The RAND Corp. Champaign Urbana, Illinois 1700 Main St. Attn: John R. Pasta Santa Monica, California Attn: Numerical Analysis Dept. Naval Research Laboratory Willis H. Ware Washington 25, D.C. Attn: Security Systems General Electric Research Laboratory Code 5266, Mr. G. Abraham P. O. Box 1088 Schenectady, New York Diamond Ordnance Fuze Laboratory Attn: Information Studies Section Connecticut Ave. & Van Ness St. R. L. Shuey, Manager Washington 25, D.C. Attn: ORDTL-012, E. W. Channel Mr. Sidney Kaplan 1814 Glen Park Ave. Harvard University Silver Spring, Maryland Cambridge, Massachusetts Attn: School of Applied Science University of Pennsylvania Dean Harvey Brook Institute of Co-operative Research Philadelphia, Pennsylvania The University of Chicago Attn: Dr. John O'Conner Institute for Computer Research Chicago 37, Illinois Stanford Research Institute Attn: Mr. Nicholas C. Metropolis Menlo Park, California Attn: Dr. Charles Rosen Wright Air Development Division Applied Physics Laboratory Electronic Technology Laboratory Wright-Patterson AFB, Ohio Northeastern University Attn: Lt. Col. L.M. Butsch, Jr. 360 Huntington Ave. ASRUEB Boston, Massachusetts Attn: Prof. L. 0. Dolansky Laboratory for Electronics, Inc. 1079 Commonwealth Ave. New York University Boston 15, Massachusetts New York, New York Attn: Dr. H. Fuller Attn: Dr. J. H. Mulligan, Jr. Chairman of E. E. Dept. Stanford Research Institute Computer Laboratory Marquardt Aircraft Co. Menlo Park, California 16555 Saticoy St. Attn: H. D. Crane P. O. Box 2013, South Annex Van Nuys, California General Electric Co. Attn: Dr. Basun Chang Schenectady 5, New York Research Scientist Attn: Library, L.M.E. Dept. Texas Technological College Hunter College Lubbock, Texas New York 21, New York Attn: Paul G. Griffith Attn: Dean Mina Rees Dept. of Elec. Eng.

Dr. Stanley Winkler University of Pennsylvania IBM Corporation Mechanical Languages Projects Federal Systems Division Moore School of Elec. Eng. 326 E. Montgomery Ave. Philadelphia 4, Pennsylvania Rockville, Maryland Attn: Dr. Saul Gorn, Director Post Office Department Applied Physics Laboratory Office of Research and Engineering Johns Hopkins University 12th and Pennsylvania Ave. 8621 Georgia Ave. Washington 25, D.C. Silver Spring, Maryland Attn: Mr. R. Kopp Attn: Document Library Res. & Dev. Division Bureau of Supplies and Accounts, Chief L. G. Hanscom Field Navy Department AF-CRL-CRRB Washington, D.C. Bedford, Massachusetts Attn: Code W3 Attn: Dr. H. H. Zschirnt National Aeronautics & Space Admin. Department of the Army Goddard Space Flight Center Office of the Chief of Res. & Dev. Greenbelt, Maryland Pentagon, Room 3D442 Attn: Chief, Data Systems Div. Washington 25, D.C. C.V.L. Smith Attn: Mr. L. H. Geiger Federal Aviation Agency Bell Telephone Laboratories Bureau of Research & Development Murray Hill Laboratory Washington 25, D.C. Murray Hill, New Jersey Attn: RD-375, Mr. Harry Hayman Attn: Dr. Edward F. Moore Mr. Donald F. Wilson National Biomedical Res. Found., Inc. Naval Research Laboratory 86oo00 16th St., Suite 310 Washington 25, D.C. Silver Spring, Maryland Attn: Code 5144 Attn: Dr. R. S. Ledley David Taylor Model Basin University of Pennsylvania Washington 7, D.C. Moore School of Elec. Eng. Attn: Aerodynamics Laboratory, Code 628 200 South 33rd St. Miss Cravens Philadelphia 4, Pennsylvania Attn: Miss Anna Louise Campion Lincoln Laboratory Mass. Institute of Technology Division of Automatial Data Lexington 73, Massachusetts Processing /AOP/ Attn: Library Department of State Washington 25, D.C. Dr. C. R. Porter Attn: F. P. Diblasi, 19A16 Psychology Department Howard University Auerbach Electronics Corp. Washington 1, D.C. 1634 Arch St. Philadelphia 3, Pennsylvania

Electronics Research Laboratory Hebrew University University of California Jerusalem, Israel Berkeley 4, California Attn: Prof. Y. Bar-Hillel Attn: Director National Physical Laboratory Institute for Defense Analysis Teddington, Middlesex Communications Research Division England Von Neumann Hall Attn: Dr. A. M. Uttley, Supt. Princeton, New Jersey Autonomics Division

S~4*0) ~c') C\1OC: i s a, in c "o CO=s 6, LOc -rl~C~