THE U N I VE R S I T Y OF M I C H I G A N COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Technical Report OUTLINE FOR AN A.LGEBRAIC STUDY OF EVENT AUTOMATA Yehoshafat Give'on ORA. Project 03105, 05662, 06689 under contract with: U. S. A.RMY RESEARCH OFFICE (DURHAM) GRANT NO. DA-A.RO(D)-31-124-G433, PROJECT NO. 4049-M and GRANT'NO.' DA-A.RO'(D)-31-124-G558 DURHAM, NORTH CAROLINA...and DEPARTMENT' OF THE NA.VY OFFICE OF NAVAL'RESEARCH CONTRACT NO. Nonr-1224(21) WASHINGTON D. C.: administered through: OFFICE OF RESEA.RCH A.DMINISTRATION ANN ARBOR June 1964 June 1964

/7, t-,. K, - /i

ACKNOWLEDGMENT I wish to thank S. T. Hedetniemi and J. H. Holland of the Logic of Computers Group, J. W. Thatcher of the IBM Research Center in Yorktown Heights, and M. Perles of the Hebrew University of Jerusalem, Israel, for their continuing interest in my research and for their invaluable help.

INTRODUCTION Regular events are characterized by various means: Regular expressions, congruence relations or homomorphisms, deterministic and non-deterministic finite automata, BUchi's monadic algebras, etc. Naturally, each characterization carries with it its specific "intuition-space" of mathematical insight and concepts. In addition to these, each characterization suggests natural generalizations. The Kleenean theory of regular events suggests the definition of a class K which is the smallest class of subsets of a monoid W such that it contains the W finite subsets of W and it is closed under the complex-product of subsets of W and under the submonoid-generating operation in W (McKnight 1960-a, 1960-b). The homomorphic theory of regular events suggests the definition of a class RW of the W-regular events which are the subsets E of W such that E =' (E) for some homomorphism 0 of W with a finite range (Rabin and Scott 1959, Give'on 1963' an' M-]IedIv-vecie',v 1.9c8). Rabin-Scott's theory of finite automata suggests the definition of finitestate automata with W as the set of input-tapes. The internal mechanism of these W-automata follows Ginsburg's studies (Ginsburg 1960) with analogous modifications which modify sequential automata into Rabin-Scott finite automata. Here, of course, -1

it is possible to define both deterministic and non-deterministic W-automata in a natural way. Blichits theory of finite automata within the framework of the theory of monadic algebras (BUchi 1960, Thatcher 1963) suggests the following definition of (pure) W-monadic algebra: a (pure) W-monadic algebra is a system (i.. =~ <A, (!Ac h: w' W i! W) " Ww where (i) A is a set, the carrier of Ct; (ii) w: A -- A for any w E W with the condition that the operation in W will be compatible with the compositions of the Cw, the operators of Q, ioe., that for any wl,w2 t W, using the suffix-notation, we shall have: c'w w' w w,' 1 W2 W1W2 Now, for any a. G A and F C A we define the event,la,, FJ = w a C Ff I choose to base my theory on the homomorphic characterization of regular events. I think that it is still premature to justify this starting point though I have the following arguments to support my choice: -2

(a) It seems to me that the study of automata via the study of monoids and monoid-homomorphisms brings automata closer to the main stream of algebra than any other study. Furthermore, in this way, the basic theorems of the ordinary theory of (Rabin-Scott) finite automatea become immediate results of the basic theorems of algebra. (b) Given the vocabulary and the basic concepts of contemporary mathematics, the definition of R is still the most compact explicit definition of regular events (in the case where W is a free monoid). Furthermore, assuming that one of the current important trends in algebra is that of category theory, the natural way to tie the theory of regular events with it is by means of homomorphisms. (c) Certain classes of event-automata, i.e. systems which define sets of tapes, like finite-state transductions and permutation-closures of regular events, fall directly under RW-theory. Even context-free languages can be introduced in a fruitful manner in R -theory using additional combinations which are still of an algebraic nature (Chomsky and Mil.ler 196.)* These arguments are still open to debate and in the course of the presentation several points of criticism will be discussed. Only a further and successful -3

development of the theory, along the lines suggested here, will be:a possible conclusive justification of the theory in toto. However, in this stage of the research, only a few parts of the theory have been established, while most of it is still open to study and inquiry. Those sections which suggest directions of development, discuss open problems, or state conjectures, will be enclosed by asterisks. 1. FINITE AUTOMATA AS REGULAR SYSTEMS In their well-known paper, Rabin and Scott already notice the relationship between finite-range homomorphisms of the free monoid and the regular events which are defined by finite automata. Following this, we define (Give'on 1963) a W-regular system, where now W is a free monoid generated by a finite alphabet say V, to be a system / = <p, F> where: (i)!. is a homomorphism of W with a finite range, o is said to be the structure of }i; (ii) F is any subset of the range of p, the designated set of cX. T(!), the event defined by?1%N, is p 1(F). -4

The definition of direct-product of structures of W-regular systems follows naturally. Clearly the direct product of any finite number of structures is also a structure, i.e. it is also a homomorphism of W with a finite range. A theorem of Birkhoff (Birkhoff 1935) yields as an immediate result the well-known fact (cf. Rabin and Scott 1959) that R, the class of all events defined by Wregular systems, is a Boolean algebra of sets. This property of RW is achieved by specifying an effective procedure of constructing a system which defines the given Boolean combination of the events generated by the given systems. Furthermore a good estimate for the necessary number of states of the combined system is derived,. - We wish to discuss this estimate together with the problem of minimal W-regular systems following J. Myhill and A. Nerode (as presented in Rabin and Scott 1959). - * Following the study of the application of Boolean matrices to finite automata and of the properties of the algebra of lattice-matrices (Give'on 1960, 1962), we find an isomorphism between the algebra of binary relations generated by the right translations of a finite monoid and the power-algebra (the algebra of subsets) of the monoid. Thus the power-algebra of the range of the structure of a given W-regular system serves effectively for the solution of the basic decision -5

problems concerning the event defined by the given system. *- There are still many directions of development which we wish to follow even in the ordinary case of the theory (i.e., for free monoids). Some of them are problems of translation from available studies of automata theory in other formulations. In particular, concerning the problem of compositions and decompositions of W-regular systems, we wish to follow Hartmanis's work on decomposition of machines (Hartmanis 1960), Krohn and Rhodes's application of Wreath-products (Krohn and Rhodes 1962) and to suggest a general framework based on the study of extensions in group theory. Holland's theory of locally effective embeddings of finite-state sequential machines in embedding spaces (Holland 1964) can serve as a machine-oriented conscience for the applicability of my algebraic approach. -* Additional properties of RW, like the closure under the Kleenean operations, will be discussed in the general study of regular events in monoids, -6

2. ALGEBRAIC INTERMEZZO The basic algebraic theory which underlies our approach is that of monoids (i.e. semigroups with identity element), Most of the algebraic material needed for our study has been developed in one way or another but not always within the context of monoid theory itself. Here I would like to present a special algebraic framework for a theory of automata which will fit my approach. This algebraic presentation will give rise to certain purely algebraic problems as well, 2,1 THE MORPHIC THEORY OF MONOIDS In monoid theory, due to the existence of the identity element, we can take advantage of the strong relationship which exists between congruence relations and homomorphisms. Let (P be a homomorphism of a monoid W onto P(W). Denote by'% the equivalence relation determined by F in W. Since 7( is a congruence relation, an operation can be defined in W/ in such a way that the natural mapping fo of W onto W/ becomes a homomorphism. Furthermore, the equation ipy(W)) = fK(W) defines an isomorphism imp from 1(W) onto W/P and thus we get a commutative -7

diagram of homomorphisms: W f / 9(W) < Wl/ 19 Because of my specific interest in homomorphisms as mappings which define certain subsets of their domain, I can identify homomorphisms which induce the same congruence relation, Furthermore, in most cases I find that I do not have to keep the distinction between P and cT. I shall use the term ambimorphism whenever this intentional ambiguity is used. We can, of course, introduce this notion in a rigorous way. For example, if we denote by [Y] the class of all homomorphisms of W which have the same induced congruence relation (as a subset of W x W) like TC, then [9] U {S is said to be the ambimorphism 9 of W. Since O and X9 are identified, both mapping and relation notations can be used according to the specific context. The right interpretation of my notation will be the only one which will make sense at all. Let us denote by A5S the set of all subsets of S, for any set SO Then, by our convention, if ~ is an ambimorphism of W then, in particular, it can be -8

represented by a mapping (- of W into W with W/S as its range. Thus we have W/?; QW and we use the diagram W - W/3 Furthermore, we define the mapping ~P P W -W by cp(E) =df U {(w) w C E3 ( J is regarded as a mapping from 9(W onto E(W which associates with any collection of subsets of W its union.) For any mapping f: S- T we define 6f:'S — 6)T by CPf(E) =df tf(s) s EE Thus, if 9 is an ambimorphism of W we have S i W + W/CC PgW and GDf.o -w - P(W/9) - 6w The following properties of c 5 and ) are derived in a straight forward manner: (1) c9 = UU9o (2) c, is a closure operation in JPW. (3) $ -. (4) (piq9 preserves the complex-product (which is in fact the "J of" the -9

multiplication of W); ioeo Q)F(E1~E2) = DT(E1)?((E2) Let Cg[W] denote the set of the fixed points of c o (5) C,[W] is a Boolean algebra of sets which is generated by means of unrestricted set-unions from W/ o (6) c1[|CW3: CGp[W] -- (3(W/p) is an isomorphism of Boolean algebras of sets. If we define an operation <> in C{[W] by E1<5>)E2 =df c l(E1 E2) then we have also, for any E1, E2. CcjW] D,(E1 <>E2) = P(E1) ~ 91(E2) Thus J9 restricted to C2[W] is an isomorphism of the Boolean structure and <(P> of CQ[W] onto the Boolean structure and the complex product of ~P(W/g). Consider a (coinitial) pair of ambimorphisms C1 and of W as presented in the diagrams W ~ > W/ w w/ w/pg'L % is said to be a morphism of 9o iff c c 91 (as subsets of W x-W)o -10

Clearly z is a morphism of Y1 iff the diagram can be completed into a commutative diagram. Since this completion is unique and it satisfies the equation ~ p = 1 for,, it is natural to introduce the notation ^ =df (P1/ / f This notation is compatible with our ambimorphic convention which implies that 1 /fm: W/9 2, W/~ W means W/Q =(W/9 )/(P/) In addition to this we keep the form that any -morphism / of a structure c(t determines a quotient-structure 0/U of the same type as 1o On the other hand, consider a (coterminal) pair of ambimorphisms j and C of W1 and W2 respectively, with W = W1/ = W2/P, as presented in the diagram: W 1 > W 1 W & is said to be a comorphism of 1 iff Q y 2 (as set theoretic binary 1, 1 -IIrelations).

into a commutative diagram. In this case we denote the completing ambimorphism by and we have Cp (2\1) ='. Furthermore, if we extend our morphic notation to binary relations we get the equation which makes sense. Our morphic convention is still satisfied. We have for any suitable ambimorphisms o,/and t (w/(W \))/= W/(' ji)) W and in our case we have Vy' (t1= S1, and W1/9= w = W2/v )I W2 = W1/P\) W and thus Wi/Q4 =(Wi/((#\'9 ))/ A Note that the relations morphism-of and comorphism-of, being defined by set-inclusion, are transitive and we get, for suitable ambimorphisms Ct, and ^, the following equations: (1) if,/3 and a are coinitial and LC_ /c then OCC and b(^/)(Pll^) - O/2t - (2) if X,/3and aL are coterminal and - /3 c j-1 c the- -1and "1 -. -

(r^) ~ (P\d. = =\. Note that S9 /9 and P\19 can be both meaningful iff W/5' and W/,' are isomorphic to submonoids of W. That is, in the traditional terminology, iff we deal with endomorphisms. For the introduction of products and sums of ambimorphisms, as well as for the discussion of general algebraic automata we introduce the concept of morphic diagram as follows: A morphic diagram (of monoids) is a system o =<M/~<> where: (i) AV is an ordered collection of monoids Wi with i 6 I and an index set I; (ii) / is a mapping with domain D () I x I which assigns to any (i,j) C D() an ambimorphismij: Wi -- Wi/ij Wj g(3) =df <I, Dyt)) is said to be the graph of. Clearly, /can be extended to be a mapping A of the set of all directed paths D* A) of g(O) which assigns to any path x e D* ) which starts at i and ends at j, a unique ambimorphism/*:Wi 4 Wi/Mx c Wj The definition of/* is given by the -13

following recursion: (i,j) ij /4x(i,j) =ij'=/4 x A morphic diagram i =/,/1) is said to be commutative iff for any x, y E D*(/) if x and y are coinitial and coterminal then/Ax =/^, is said to be strongly commutative iffc is commutative and for any cycle z Dl), z* is the identity of W(z). Let 1D and be two morphic diagrams, the relation 2 of inclusion is naturally defined. 1 is said to be subcommutative iff there is a commutative morphic diagram D 2 which includes ~!' Let j =< <,/4> be a morphic diagram with index set I and let Wi E W. A morphic diagram,) =<)V',<'> is said to be a turn-extension ofo from Wi iff: (i).' has J = I U j, where j I, as an index set, and }' = VU{Wj where W is any monoid. J (ii) D(') = D() S D(O, where Sj D() is derived from DtO by substituting j for i; (iii) /'ID(A) = In particular we say that D' is a turn extension of do from W to W.. Now a diagram 2 = (,v > is said to be universal around W-i (for Wi,f ) -14

iff for any monoid W. and any turn-extension )' of Z from Wi to Wj there is an ambimorphism W. —W./ic W. Tij i iWj which completes k' to be a commutative diagram. 0 is said to be couniversal around W. iff for any monoid Wj and any turn-extension <' ofoD from W to W there is an ambimorphism i j j Wi / Wj w/Oii c W which completesco' to be a commutative diagram. Now we define compositions of ambimorphisms. Consider a coinitial pair of ambimorphisms %^ and 92 of W as presented in the diagram: W /so W S~i WI/> w/q x ^ d We define: (1) the direct product ~W7 x of i and ~ by r x2 df MaX { ~/T~ & I3rP/-t' (2) the direct sum V+_ of Y1 and ~ by -15

+ S df = Minjaf: 7J/P &a-/(} where T' and r vary over the ambimorphisms of W and thus "Max" and "Min" regard them as set-theoretic binary relations; and "30//3" means / is a morphism of OL. As an immediate result we get that the diagram above is universal around W/P + 9, and around W/( x 9. As for the effect of these relations and compositions of ambimorphisms we get the following results: (1) If 2 is a morphism of < then c P1/S W/58 =!1A C w] (2) (Birkhoff 1935) For any two ambimorphisms t and % of W: (i) 9 x 9 = n, and therefore W/(T x ) = ('U){W/, W/. W (ii) 9 + 9 is the transitive-closure of' U 2 and therefore W/( I + >) = (W//) n (W/ ) (iii) For any two ambimorphisms 01 and T and any subset of E of W we have 9T(E) E C( + )/ W iff co (E) C T + * - The characterization of direct products and direct sums of coinitial ambimorphisms by means of universal diagrams suggests a definition of codirect produeit ar'd sums of coterminal ambimorphisms by means of couniversal diagrams. ---- -16

-- I wish to study the formal properties of the algebra of ambimorphisms determined by the operations and relations which were suggested here (ioeo, direct sums and products, morphism, codirect sums and products and comorphism). My attention is drawn to a possible relation between this algebra and other systems which were introduced in different contexts, for example the categorical grammars suggested by Ko Ajdukiewicz (Ajdukiewicz 1935) and studies by Yo Bar-Hillel, Cho Gaifman and Eo Shamir (Bar-Hillel et alo 1960) have similar structure. The same holds for J. Lambek's work on syntactic types (Lambek 1958, 1961). -- 2.2 POWER ALGEBRAS My study of regular systems as applied to finite automata (Give'on 1963) led me to consider the power algebra determined by the subset-construction as applied to finite monoids. At the same time, the morphic theory of monoids, as presented in the previous section, led us to introduce operations and relations in order to study their effect on subsets of monoids. Thus we consider the various power algebras (this term was suggested by J. W. Thatcher) which can be associated with a given monoid. First of all we consider'W the complex power algebra which is defined by -w= dQ>W, >,*, -17

where (i). is the complex-product in f-.W, i.e., o is the J' of the multiplication in W; (ii) * is the submonoid-generating operation in [)W, i.e., E* is the sub-monoid of W generated by E; (iii),j is a class of Boolean operations in JDW. Note that in particular <(OW,.' is a monoid with =,{i as an identity element. The distributivity of o over the set union makes W an interesting structure which deserves special study. Now with any ambimorphism 9 of W we can associate the system (''W, w df'' C C. -) As we shall see later, such systems will play an important role in the discussion of regular events in monoids' i__ Since I am interested first in event-automata, a study of such power-systems is necessary for the algebraic framework of my theory. In particular, I should consider diagrams in which power systems appear as components and also study the effect of the various power-associations on diagrams. - -18

2.3 EXTENSION THEORY AND COMPOSITIONS __ Extension theory is developed especially in group theory and recently it was translated to the general framework of category theory (cfo MacLane 1963). It is still an open problem, how much of it can be maintained in monoid theory. The relevance of extensions to automata theory is implied by the fact that they can be suitably interpreted as compositions. Thus the study of Krohn and Rhodes applies Wreath-products to derive compositions of sequential machines (Krohn and Rhodes 1962). This study suggests the hope that transformation-automata can also be studied under the same algebraic approach as that of event automata. Appropriate notions of homomorphisms of morphic diagrams will lead to a theory of compositions of morphic diagrams as wello The general concept of composition of diagrams seems now to me to be defined as a quotient of a direct product of diagrams determined by an equivalence relation which is defined across the components of the given diagrams. However, in order to get a fruitful and interesting theory of compositions of morphic diagrams, certain restrictions should be imposed on the structure of the diagrams. Here, both category theory and the present studies of compositions of sequential machines seem to be insightful sources for such a development, -- -19

3. REGULAR SYSTEMS OF MONOIDS Let W be any arbitrary monoid. A W-regular system is a system = (,F > where: (i) p is an ambimorphism of W with a finite range (p is said to be the structure of c ); (ii) F is a subset of the range of p (it is said to be the designated set of c ). RW, the class of regular events in W is defined by _ Idf CltClJW: W/p is finite. A subset E of W is said to be generated by the W-regular system (<,F> iff E -= (F), and in this case we write E T(). The direct product construction for arbitrary monoids yields the expected result that R is a Boolean algebra of sets. W The problem of determining minimal W-regular systea (with respect to the size of the range of their structure) is relevant here. * - I plan to discuss it after the study of the relationships between the following systems: -20~

(i) W-regular systems and RW, (ii) right invariant relations in W, (iii) finite-state automata with W as input, (iv) non-deterministic finite-state automata with W as input, (v) monadic algebras and relational systems with operators related to W -- The well-known methods employed in the theory of finite automata can be applied to these general structures with the expected results (Mezei 1962; Give'on 1964). Namely, these systems are weakly equivalent; some of them are equivalent even in certain strong senses which can be specified as certain isomorphisms of structures. I feel that some words should be said concerning the notion of "structure" used in the literature of automata theory. Some formulations of automata yield a transparent distinction between "structure" and "behavior" which agrees with the "machine" oriented intuition, It is obvious that W-regular systems do not have behavior in any dynamic senseo On the other hand, though p is said to be the structure of<;,F~ by definition, it is not a structure in the "machine" sense but in the mathematical sense. To some extent, the notion of structure and behavior are diffused in the W-regular terminology. -21

In spite of the equivalence between these generalizations of (free) finite automata, we find that certain properties of regular events get lost in the generalization. For example, by means of certain constructions of nondeterministic finite automata it is proven that the complex-product of regular events and the submonoid generated by a regular event are regular events. This does not hold in R in general, not even with the help of the equivalence of W-regular systems with non-deterministic W-automata, Except for the free monoids only the finite monoids and the groups are known to be classes of monoids for which the classes of the regular events in them are closed under the operations mentioned above. Let us say that a monoid W is a Kleenean monoid iff R is closed under complex-products and the submonoid-generating operation. (In the terminology introduced in section 2.2 we get that W is Kleenean iff (RW ,o,s a subalgebra of / ) A close study of the proof that free monoids are Kleenean suggests the following approach: (i) In order to define non-deterministic W-automata we have to modify Rabin-Scott's definition (of non-deterministic automata)~ If we adopt their definition as it stands we get: -22

Let B be a minimal set of generators for Wo A system (;~ = Sc> is a basic structure of non-deterministic W-automata iff S is any set, i~: S x B —.F)S is any mappingo We wish now to extend -- to be a mapping r ( Ps) xW->PS by the following recursion: -*(Th ) = T for any T c S (T,W1W2) = jIW({s w2) S e (TW1) Contrary to the case of free monoids, the existence of-* is not always guaranteed, __ Apparently, a certain property of the factorization of the elements of W is necessary for the existence of *e - * If A* exists then of course <S,i*> is a structure of non-deterministic W-automata as defined and discussed in (Give'on 1964). (ii) Following the construction used for defining a(non-deterministic) finite automaton which accepts the complex-product of events accepted by given automata we construct the following system: Let t0 and p be two ambimorphisms of W and let F be a subset of W/Ip o We define the mapping -23

(< 2 F >: W - (W/I ) X T(W/) by \p^F~>(w) =df (w), dp(( F)\w)> where S\w =df 1W2 wlw2 = w for some w1 ( S V Clearly, if p; and p are structures of W-regular systems then pFF has a finite range. Furthermore, if it is also a homomorphism of W then (p.Fp is a structure of non-deterministic W-automata. In this case, for any F2 = W/ we get a W-automaton which defines {w: ~PK Fp>(w))2 F = ( )o( F) I. 1., 2 2 Only in special cases is <p FP a homomorphism of W. * Again a / 1. * ~. certain structure, similar to the one suggested by (i) with regard to the factorization of elements in W, seems to be sufficient for (e1Fz> to be a homomorphism of W. --, (iii) Following these discussions, we are led to introduce the following property of monoids. Let W be a monoid and w e W, then we define: W(w) =df {(wlW 2)' Wl'w2 W & w1w2 = w} that is, Cw(w) is the set of all pair-factorizations of w in Wo If we regard a (w) as a subset of W x W, then for any u,v e W the -24

expressions (u,v) x Pw(w) and (w) x (u,v) are meaningful. A monoid W is said to be sequential iff for any wl,w2 V W we have. w(wl2) = W(Wl) X (,W2) j (WAl) xcW(w2) Thus, sequential monoids are monoids in which the pair-factorization of any element is retrievable from any of its factorizations. Clearly the free monoids are sequential and as one can prove, if W is a group then for any w1,w2 w W: w(WlW2). = (w1, );x C(W2) = W(w1) (,,w2) which shows that groups are sequential monoids, One cannot expect that only sequential monoids will be Kleenean, The finite monoids are Kleenean and yet some of them are not sequential. -- As a conjecture, I would like to suggest that sequential monoids are Kleenean and for sequential monoids 7* and<p Fp >, as defined in (i) and (ii), yield homomorphisms of W. -- The definition of <p Fp > deserves special attention since it determines a certain product of W/p and W/I. * - Our study of the problem of Kleenean monoids is connected therefore with the study of cross-products of monoids - -25

4. HOMOMORPHISMS OF REGULAR SYSTEMS The morphism relation between ambimorphisms was introduced because of the following observations, Let c = <e, F> be a W-regular system and let A be any ambimorphism of W. We want an appropriate definition of /4 as an image of ~ under B It is clear that if the diagram of p and ) can be completed into a commutative diagram, then the structure of 4/) can be defined naturally. Thus W - P' w/.' W/p k if 4 is a morphism of p we define M/- =df <P/l F> As we noticed already in section 2, we get the following equality of relations ~p-l = (p/4)-l and so, for any F c W/P we have T( /q))- _ (T()) where T(cA) denotes the event generated by 4 If, however, I- is not a morphism of P then QTQ(T(A )) is not necessarily a regular event:in W/~i). Obviously, if'.t is any ambimorphism of W and E is any -26

regular event in W/J) then -1 (E) is regular in W. In particular, as the following diagram shows, if E is generated by ( = <p, F> W ~ ^> W/.., P (W/) then ~-i(E) is generated by - (,) =df <K' F>. On the other hand, let c = <p, F> be a W-regular system and let ~ be any ambimorphism of W then for any E c W such that c j(E) is regular in W we get that (JP)(E) is regular in W/l). In order to show this, we notice that c (E) is regular in W iff c (E) ( Cp[W] for some ambimorphism p of W with a finite range. Clearly c p(E) C C [W] and therefore c (E) e Cp[W] n c [W] = cp+o[W] which implies (by our results of section 2) that (J)'(E) E (_ C( + )/, EW/Y I Since ( + P)/1 has a finite range, namely W/( p + 6), 1()(E) is regular in W/'. In particular if c >(E) is generated by = <P, F> then s)(E) is generated by Xh) -df <(p + )/ (( + )/p)()> -27

Combining these results we get the following theorem: Let j be an ambimorphism of W: (i) RWi/, C" 99T W (ii) for any E c W: ~ )-(E) is regular in W/T iff c (E) is regular in W; (iii) RW/t /9PRW iff )C(9(RW) c RW i.eo, 9 preserves regularity (from W to W/*) iff c~ preserves regularity in W. * -- Analogous results should be pursued in the context of comorphisms. * Our method. can be generalized by defining the following relation between ambimorphisms, Let P1 and c2 be ambimorphisms of W1 and W2 (resp). We say that T2 reflects q)1 iff there exist ambimorphisms 1 and ~2 which complete the following diagram into a commutative W i~ ~ —"- W1 / ) \ I, \,-8 81'' "12' 2 2 -----— > W2/ 2 72 diagram; that is, such that {2 ^1 = 2 {P1' Symbolically we shall denote this by -28

and the expression D1 ~> 2 will denote that P2 reflects'1 Note that < 1' 2> 9 ~1 -> C2 holds iff the ambimorphism ~12 =df 2 P1 = T2 41 has the following properties: (i) 12 is a morphism of, (ii) 2 is a comorphism of 12 Thus P1 -- ~ 2 iff there exists an ambimorphism Cp2 of W such that Pl2 is a morphism of CP and (2 is a comorphism: of l12 (hence W1/P12 = W2/P2) Moreover, note that morphisms and comorphisms are special instances of reflection; namely, for which either c1 or 2 is the identity mapping. Another special instance is the case where [~ and T2 are successive ambimorphisms (i.e., such that the range of'1 is the domain of 2: 2 = W1/1). In this case we have < 92>: - 92 i.e., the following diagram 1 Wl >W 2 1 ^ 92 W1 W2 2 -29

is of course commutative. Comparing the diagram < 1' 2>: 1 - 2 with the diagram of the definition of 1 X'1 we find that there exists an ambimorphism ^ ~ W1/( X/ )-1W2/ 2 which completes the following diagram into a W: / W < WS )/' 2 l...o \ N~2 i' <p1 (i1 X 2)/: >2 W2/ 2 In particular) we always have: *-0for any coinitial ambimorphisms,> and... Note that for any appropriate ambimorphisms o{, /3, )Y and ~ ~ -3o

V - ^I-iY______ —~~ O, _....____...~....... ~..e__.^ ^ /~19 * ~ The implications of these discussions which are relevant to the various power algebras induced by the ambimorphisms under consideration, are quite straightforward. In particular, if P1 and 02 are structures of W1 and W2 regular systems (resp.) then <l, >2> 1 P2 may be considered as a general form of homomorphisms of structures of regular systems. -- 51

5 REPRESENTATIONS OF EVENTS BY MEANS OF REGULAR EXPRESSIONS Our results of the previous sections led us to consider various classes of subsets of monoids. Some of these classes have been defined before and the rest are defined in the following complete list: (i) Cp [W] = (c (E): E c W= -c cPW) (ii) RW is the class of regular events in W (iii) 9(RW() = (([O(E): E e Rw), which is usually denoted by T(Rw). Since (p (restricted to Rw) is a homomorphism of the multiplicative (monoid) structure of Rw, we can use the notation of ambimorphisms, that is RW/ = p 2 g(RW (iv) jScp(RW) = (cg(E): E e RW), this is the class of the subsets in C^ [W] which are derived from the regular events in W by means of the closure operation cp (v) R =df (E e RW: 9p(E) E R/ }, this is the'class of those regular events in W which remain regular under j9> Our results can be represented in the following diagram. Note that we labeled certain arrows by 99P and c ~ without designating that we refer to the appropriate restrictions of 5 p and co. The dotted lines appear in those cases -52

where the lower class of events is included in the upper class.'The double arrows show our main results, i.e., they represent the cases in which the appropriate restrictions of 9p yield one-to-one correspondences. Note also that our algebraic results imply that 0 o: C[ W] D O(W/I) and 5:): Rw n c[W]~ R/ yield isomorphisms of the Boolean structures of Cc [W] and of RW n Cc.[W]. W - W/f SW:~- (W/g) c [W Rw ---— ~>C SW] a _~-, -~~~ ~ — -- > @w/ R n cA [w] -35

We proceed now to discuss some interpretations of the language of regular expressions (Kleene 1956) by which certain classes of events can be described. Let V be a finite alphabet and let ( be a set of any four symbols which do not belong to V, say 0, 1, U, and *. We denote by (V the class of finite expressions over V U (9 U ((, )) defined inductively by: O. 1 G ^V V- $V V a V - if C, 3 ~ 6 v then (OC U /), oCP, (0C)* 6 BV Any o( q >;V is said to be a regular expression over the alphabet V. Regular expressions are employed in automata theory to denote certain subsets of V* (the free monoid generated by V). This is defined as an interpretation function e: V Q- V*, which will be referred to as the free interpretation and is defined inductively by the following list of equations: (i) e(O) = ~ (the empty event); (ii) e(l) = I = (24 (the silent event) where XA is the identity element of V*; (iii) for any o- e V: e(rr) = (FT); for any o.L, ) ~ V w. (iv) e(((X. U,D)) = e(o^) U e(f)

(v) e(c(3) = e(Oc) e(^) (vi-) e((O0)* = (e(&O))* (the submonoid of V* generated by e(o)). Kleene's theorem of finite automata states that e is a homomorphism of the syntactical structure of V onto the (power) algebraic structure of RV* In general we can define general free interpretations of <V as homomorphisms of the syntactical structure of (V onto an algebra of subsets of V*. An important class of general free interpretations of V can be associated with the class of all ambimorphisms of V* in the following manner. Let 9 be any ambimorphism of V* we define e5~ WV >~(p(Vx*) by e ((C) =df c (e(OC)) In words we shall say that e g (OC) is the 92-closed event derived from OC Kleene's theorem implies that ep maps 4V onto Qc p(Rv*) while our discussions in section 2 show that e T maps the syntactical structure of 6V onto an algebraic structure of c ((Rv*). Thus ep is a general free interpretation of V. In the next section we shall discuss the permutative events which are described by means ofL.such an interpretation of regular expressions (Laing, Wright 1962). -55

So far we -have been: interested'in interpret;ations of.V into QV*, Given any ambimorphism c of V* with W = V*/Sp, we define e W inductively by: (i) e(0) =; (ii) eT (1) = I (the identity element of W); (iii) for any c- E V: e (F) = ((0-)}; for any doL; E V: (iv) e9((OC U /)) = e'(o) U e() (v) e( T(/3)=e) = ( e((O)) (vi) e'((o()*) = (e9(co))* (the submonoid of W generated by e9(oC)). This definition and Kleene's theorem imply that.e (('V) = RV./v and since (Q~)e = e, ei is a homomorphism of the syntactical structure of StV onto the algebraic structure of Rv*/P9. Hence we can use the language of regular expressions to denote events in homomorphic images of V*; that is, in finitely generated monoids. In the next secti-ons we shall also discuss examples of these types of interpretations. Note that we can associate with any ambimorphism p of V* the following -5^6

commutative diagram. V e/ s ec Rv*./ \ e/ / \ V* i/V.g)* / \SP

6. EXAMPLES AND APPLICATIONS 6.1 COMMUTATIVE MACHINES (Laing & Wright 1962) Let V be a finite alphabet, V* the free monoid, and AV the abelian free monoid generated by V. Denote by r-: V* ->AV the natural homomorphism of V* onto Av. Clearly cT is the closure operation which extends any subset E of V* by including for any x E E* all the permutations of letter-tokens in x. Our main interest here is to study Qc (Rl*), the class of permutative events which are derived from regular events. First we note that Tr and c do not preserve regularity (provided that the alphabet V contains at least two letters). For, let a, b e V, then the c -closure of (ab)* intersecting with a*b* yields the event (anb: n O0 which is not regular (Rabin & Scott 1959). Applying our results of section 5, we can use the interpretation functions e and e to denote the events of ~c{(Rv*) and of RV./j7 (respectively). Thus, while regular expressions usually refer also to their free interpretations (e.g., (ab)* and a*b* in le previous example) er(O() will refer to the c -closure ^8-~~~~~~~~~~'

of e(oL) (e.g., e7.((ab)*) is the set of all words over (a, b) with an equal number of occurrences of a and b) and e( (o(.) will denote the image of e(OC) under 9 (e.g., eT((ab)*) is (anb: n A O) as a subset of AV) Our proof that a particular event in Gct(RV*) is not regular can be generalized as follows: Let V = (a,..., an); then for any E E Cq[V*] E is regular in V* iff E n (a... a*) is regular in V* (Give'on 1963). Thus we have a canonical form for the permutative events. Namely, if we choose for any E e C [V*] the set E = En (a a), we have the following: (i) E =E' iff E' = E" (ii) E is regular iff Eg is regular (iii) EB, viewed as a subset of A, is in fact )Xt(E) Furthermore, as presented in the work of Laing and Wright (Laing & Wright 1962), a partial characterization of (EB: E e6 ) (Rv.) is achieved by associating sentences in Presburger's language (Presburger 1930) with a class of subsets of a*... * a* ~~1 n In particular, for any regular expression o there is a Presburger formula Q(xl,..., Xn) such that -59

nl m al.. an (e (t))E iff Q(m, *.., m) al' a,~n ~ Laing & Wright 1962). * - It is still unknown whether this characterization is complete. In particular, the problem whether for any OC(, OC2 E V there exists a. e 9 V such that e(O1l) n e.(o(2) = e(I), is still open. * Another problem which is associated with this context is that of the word problem for abelian monoids. M.O. Rabin, by means of combining the methods used to prove the solvability of the word problem for abelian groups with methods taken from automata theory, proved the solvability of the word problem for abelian monoids (Rabin 1964). * -- Since the methods employed in the solution of the general word problem for abelian groups, namely that of the linear algebra over the ring of integers, were found to be useful for.the study of AV and of permutative events derived from regular expressions, they open new directions for the study of permutative events. -- 6.2 DIRECT POWERS OF V* The direct powers of V* (and their submonoids) are in frequent use in automata theory. This is because direct powers algebraically represent the notion of independence of channels. 1^0-d

Note that we have implicitly discussed a certain submonoid of the n-th power of V*, though not as a representation of a channel. Namely, Av, the abelian n free monoid generated by V, is obviously isomorphic to iX a and, of course, to the n-th direct power of a*. Dk- *k We denote by Dk(V*) the k-th direct power of V*. I.e., D (V*) is the monoid whose carrier is the set of all k-tuples over V* and whose operation is the component-wise concatenation. Clearly D (V*) is finitely generated and has a basis consisting of the "unit-vectors" (i.e., those vectors over V* whose entries are all X except for one which contains a letter). Let us denote by Vk) the basis of D (V*) a;nd so we have a natural homomorphism7 d i: V) Dk (V*) of the free monoid Vk) generated by V(k) onto D (V*). -41

A submonoid of D (v*) is said to be rectangular iff all its elements have components with an equal length. A special case of free rectangular submonoids of Dk (V*) is that of the submonoids generated by subsets of V(k) the k-th cartesian power of V. - The complete characterization of the family of submonoids of D (v*) is still open and it deserves a special study. - * As we shall see in the following examples the study of regular systems and their images under homomorphisms from and to submonoids of D (V*), seems to be a fruitful unifying framework for the study of automata which are closely related to finite automata. 6.3 REMARK ON EVENT AND TRANSMISSION AUTOMATA Finite automata, and automata in general, are viewed in the theoretical framework in a twofold manner..As event automata they are regarded as systems which define certain subsets of the input domain (e.g., finite automata as defining regular events). In a different way, automata sometimes are regarded as transmission automata, that is, as systems which define certain functions from an input domain to an output domain (e.g., Turing machines as systems which define computable functions). Finite automata enjoy a particular property, that in a special case these ~:-2

two points of view are equivalent, and. the general situation does not seem to be essentially different from this special case-which will be discussed presently. With any finite automaton c e over the alphabet V, we can associate the following three functions: (i) Event function ~ C V* {* 0,O 1), which is the characteristic function of TA). (ii) Finitary-transmission function ~:~ V* -> O 0, 1)* which is the "right extension" of, determined inductively by: w(xCr) 1= 7*(x)- (cr) for all r V and x V* (iii) 6- -transmission function,x: ~V - (O, 1), (where S) denotes the set of all infinite sequences, over S) which is defined by: ( (C))(iC) = ((i)) (where (1i) is the i-th element in n ). The relationship between these three functions associated with 64 is ^-43

obvious. Any one of them determines the other two effectively. Such a neat situation does not prevail throughout other domains of automata theory. In fact some students of finite automata theory maintain that the study of event finite automata is not sufficient for the study of transmission finite automata if their output alphabet is larger than a binary alphabet. Since we are interested in systems operating on D (V*) we note that such systems can be viewed in the twofold manner (of event-and-transmission automata) k k 2 in a more natural way. Trivially, any binary relation from D (V*) to D (V*) can be defined as a subset of 1 k2 l\2 D (V*) X D (V*) =D (V*) On the other hand, any subset E C Dk(V*) can be interpreted as a binary relation k k from D (V*) to D (V*) for any k and k such' thatk k =k. This double k interpretation will be employed in our study of regular systems related to D (V*). 6.4 SEQUENCE GENERATORS (Burks & Wright 1962) The basic concept of sequence generator is introduced as a suggested generalization of the concepts of digital computers, finite automata and other information-processing systems (Burks & Wright 1962). Here we shall show how certain features of sequence generators, though being transmission automata, can -44

be studied by means of the theory'o' regular systems. An algebraic sequence generator is defined to be any regular system in a rectangular submonoid of D (V*) generated by a subset of [(vl,.., vk): v. e V). Obviously the theory of regular systems in free monoids is applicable here ~k since such submonoids of D (V*) are finitely generated free monoids. Several constructs, as various types of "behavior," are associatedwith sequence generators. However, since they are all determined by the "finitary behavior," we shall discuss mainly this one. The finitary behavior, (r), of an algebraic sequence generator r is a subset of T(P) derived by means of an operation introduced and studied by I. T. Medvedev (the so called "fundamental operation (t)tp" in Medvedev, 1958): Let W be any monoid and let E c W. We define: E -df (w E w,= wlw2 > wl E) That is E is the set of all elements of E for which E contains also all their prefixes. We define now: f(p) =df (T(r)) Since preserves Eeg~larity in free monoids (Medvedev 1958), the finitary behavior of any sequence generator P is a regular event in the rectangular monoid -45

of p. The converse does not hold, since not every regular event is in the range of. There is, however, an effective procedure by which it can be determined whether or not any given regular system generates an event which is the finitary behavior of an algebraic sequence generator. Most of the properties of sequence generators now follow from this: reduction to regular systems in free monoids. Still, the particular structure of the generators of the monoids, in which sequence generators are defined as regular systems, suggests several problems which are related to other classes of events in D (V*) to be introduced in the next subsection. 6.5 FINITE-STATE TRANSDUCTIONS (Elgot and Mezei 1963) A k-transduction system is a regular system in Vk) and the k-transduction defined by the k-transduction system c is'C(jQ) =f (S d)(T()) Any E c D (V*) is a (k-)transduction iff E = rT ) for some (k-)transduction system. Our results of section 5 imply directly the following statements? (i) The class of k-transductions is completely (and effectively) represented by V) through e. (k) (ii) The class of k-transductionSis therefore the minimal class of subsets of D (V*): which contains the finite k-ary relations in V* and is closed under set-..^.6

k union, complex-product, and the submonoid generating operation in D (V*). Another class of events in D (V*) is introduced by the following intuitive description: Imagine a Rabin-Scott automaton over the alphabet Vi = V U ((3} where e9 a V. This automaton is reading a k-multiple input channel, which is loaded with words over the alphabet V, by means of a reading head with the following behavior. This head feeds the main automaton with the letters of the input. First the first letter of each one of the k words is fed into the main automaton and then the second and so on, according to a fixed order of the channels. Whenever the head reads a blank space (after passing through one of the words) it transmits a /3 to the main automaton. The head stops.the operation of the system when it passes the end of the largest word among the k input words without changing the internal state of the main automaton. The k-tuple of the input words is accepted iff the main automaton, starting its operation with the initial state, ends it in a designated final state. Formally, we have the following situation: (k) Let us denote by V ) the cartesian k-th power of Va; i.e., Clearly there exists a natural monomorphism

8: (v^))* -e D (v ) P V* which is similar to d. Both Dk(V*) and Dk(*) are submonoids of D (V ) but D (V*) - D(/*), their complex-product, is obviously not closed under the multiplication in D (V*). Now, RC Dk(V*) is said to be a fad (for "finite automaton definable") k-ary relation iff there is a regular event E in (V ))* such that: (i) for all ~ E: () E Dk(V*) ~ Dk(*) (ii) R = [( )(E) D (*)] where [S1: S2] =df (x: xy E S! for some y S S2 This definition can be simplified as a result of the following observations: 1. There exists a monomorphism 6' such that the following diagram is commutative. (V ()) - D ( ) d X// Hence for every regular event E in (V))* there is a regular event E' in (V) such that ((P)(E) = (5d)(E'). 2. If E satisfies requirement (i) then we have

[ ( ) (E): Dk (*) ] = ((f )((P )(E) where D (V)t ) D (V*) k is the homomorphism of D (V, ) which amounts to the erasure of/3 3. There exists a homomorphism 6' (which is similar to 8 ) such f3 3/ that the following diagram is commutative. (k))* k (v*) (V ) D (Vi ) ~ ~, D (V*) ~~~~~~~~~/33 6 /d d 6. // / (v~ > 3 )* (k) Vk) Hence, for any fad k-ary relation R there is a regular event E" in Vrk) for which R = (9d)(E"). Therefore, every fad k-ary relation is a k-transduction. Obviously, R (k) /pd is a proper subclass of the class of fad k-ary (v )* relations; namely those which are "length-preserving," that is, rectangular. Thus we have the following decreasing sequence of classes of events in Dk(V*): 1. RV /)d, the class of k-transductions; k) 2. the class of fad k-ary relations; 3. R (k) /Jd, the class of rectangular fad k-ary relations; (v )*49 -49

4. the class of finitary behaviors of sequence generators, * - As for R, I do not know where it is located relative to-this D (v*) sequence. It is quite possible that it is incomparable with any class in this sequence (except for the class of k-transductions. - * 6o6 TRANSDUCTIONS AS GRAMMARS Let us define Ai: Dk(V*) ~ V* by /C (x1', xk) =X1x2'.. Xk This function can be used to interpret systems defining events in D (v*) as grammars for languages over V. In particular we can apply // to R /d and "k) get the class of k-multiple finite-state languages. Note, however, that the k-multiple finite-state languages can be defined by means of a generalization of finite-state grammars (Bar-Hillgl & Shamir 1960) like the following: Let V C V; a k-production rule is an ordered pair (v,,) where v (V - V?)(k) and 4E D (V*)o It is a finite-state k-production rule iff v (v- v- )(k). Dk(V* ) -50

A kmultiple finite-state grammar is a system = v, > where vO 6 (V- V)) and 7 is a finite set of finite-state k-production rules. The definition of k-multiple finite-state languages now follows naturally. - 5l

REFERENCESAjdukiewicz, K., (1935) "Die Syntaktische Konnexitat, Studia Philosophica,!; 1-27. Bar-Hillel, Y., Ch. Gaifman & E. Shamir, (1960) "On Categorical and Phrase Structure Grammars," Bull. Res. Council of Israel, 9F, 1-16.. Bar-Hillel, Y., M Perles & E. Shamir, (1961) "On Formal Properties of Simple Phrase Structure Grammars," Zeitschrift fir Phonetik, Sprachwissenschaft und Kommunikationsforschung, 1 143-172. Bar-Hillel, Y., & E. Shamir, (1960) "Finite State Languages: Formal Representation and Adequacy Problems," Bull. Res. Council of Israel, 8F, 155-166. Birkhoff, G., (1935) "Structure of Abstract Algebras," Proc. Cambridge Philos. Soc. 2 441-464. Blichi, J. R., (1960) "Mathematical Theory of Automata," Notes on material presented by J. B. Wright and J. R. Blichi, Communication Science 403, Fall 1960, The University of Michigan. Burks, A. W., & J. B. Wright (1962) "Sequence Generators and Digital Computers," in Recursive Function Theory, Proc. of Symposia in Pure Math.,, A.M.S., 139-199. Chomsky, N., & G. A. Miller, (1963) "Introduction to Formal Analysis of Natural Languages," in Handbook of Mathematical Psychology, II, John Wiley and Sons Inc., 269-418. Ginsburg, S., (1960) "Some Remarks on Abstract Machines," Trans. of the A.M.S. 96, 3, 400-444. Give'on, Y., (1960) "Boolean Matrices and Their Application to Finite Automata," Tech. Report No. 5, Applied Logic Branch, The Hebrew University of Jerusalem. ---—, (1962) "Lattice Matrices and Finite Automata," Tech. Report No. 8, Applied Logic Branch, The Hebrew University of Jerusalem. (To be published in part ir Information and Control under the title "Lattice Matrices".) —, (1963) "The Application of Algebraic Systems to Finite Automata," Tech. Report 04995-1-T, ORA, The University of Michigan. ----—, (1964) "The Theory of Algebraic Automata I: Morphisms and Regular Systems," Tech. Note o0663 05105-27-T, ORA, The University of Michigan. 52

Hartmanis, J., (1960) "Symbolic Analysis of a Decomposition of Information Processing Machines," Information and Control, 3 2, 154-178. Holland, J. H., (1964) "Universal Embedding Spaces for Automata," Tech. Report 06114-1-T, ORA, The University of Michigan. (To be published in a festschrift for Norbert Wiener, Netherlands Central Institute for Brain Research, Amsterdam. ) Krohn, K. B., & J. L. Rhodes, (1963) "Algebraic Theory of Machines," in Mathematical Theory of Automata, Microwave Research Institute Symposia Series, Volume XII, Polytechnic Press, Brooklyn, N.Y., 341-384. Laing, R., & J. B. Wright, (1962) "Commutative Machines," Tech. Note 04422, 03105-24-T, ORA, The University of Michigan. Lambek, J., (1958) "The Mathematics of Sentence Structure," American Math. Monthly, 65, 154-170. ----—, (1961) "On the Calculus of Syntactic Types," in Structure of Language and its Mathematical Aspects, Proc. 12th Symp. in Appl. Math., Providence, R.I.: American Mathematical Society, 166-178. McKnight, J. D., (1963a) "Fine Quotients of Semigroups," G.E. Computer Lab. Report 63-CDL-8. ----—, (1963b) "Generalized Kleene Quotient Theorems," G.E. Computer Lab. Report 63-CDL-10. Medvedev, I. T., (1958) "Finite Automata and the Representation of Events," (Trans. from Russian by Jacques J. Schorr-Kon) Lincoln Laboratory Group Report 34-73, Lexington, Mass. Mezei, J., (1963) "Structure of Monoids with Applications to Automata," in Mathematical Theory of Automata, Microwave Research Institute Symposia Series, Volume XI, Polytechnic Press, Brooklyn, N.Y., 267-300. ----—, (1964) "Congruence Relations on Abstract Algebras," IBM Research Note NC-352. Rabin, M. 0., (1964) "On the Word Problem for Abelian Monoids," (Private Communication) Rabin, M. O. & D. Scott, (1959) "Finite Automata and Their Decision Problems," - IBM Journal, 5, 2, 14l4125. Thatcher, J. W., (1963) "Notes on Mathematical Automata Theory," Tech. Note 05662, 03105-26-T, ORA, The University of Michigan. -55

UNIVERSITY OF MICHIGAN 11111 i I II IIJIIIMlfil II t 11111ttil I 3 9015 02825 9995