THE UNIVERSI T Y OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Communication Sciences Program Final Report (14 March 1963 - 13 March 1964) LANGUAGE AND AUTOMATA Arthur -W.. Burks under contract with* U. S. ARMY RESEARCH OFFICE (DURHAM) GRANT NO. DA-ARO(D)-31124-G433, PROJECT NO. 4049-M DURHAM, NORTH CAROLINA administered through OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR March 1964

i~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ p 54-to J l ttt Al

The following is a report of research on language and automata conducted at the University of Michigan during the period 14 March 1963 to 13 March 1964 and supported in whole or in part through grant DA-ARO(D)-31-124-G433. Three technical reports have been prepared: (1) Y. Give'on, "Normal Monoids and Factor Monoids of Commutative Monoids," Technical Note 05662, 03105-25-T, The University of Michigan Office of Research Administration, May 1963. (2) J. W. Thatcher, "Notes on Mathematical Automata Theory," Technical Note 05662, 03105-26-T, The University of Michigan Office of Research Administration, December 1963. (3) Y. Give' on, "Theory of Algebraic Automata I: Morphisms and Regular Systems," Technical Note 05662, 03105-27-T, The University of Michigan Office of Research Administration, January 1964. The paper, "Transition Graphs and the Star-Height of Regular Events," by L. C. Eggan has been published in the Michigan Mathematical Journal. Twenty (20) copies of the published version were sent to you in January 1964. This paper was prepared under contract Nonr-1224(21) with the Office of Naval Research and under grant DA-SIG-36-039-61-G4 with the Signal Corps Research and Development Division and was revised and expanded under Nonr-1225(21) and DA-ARO(D)-31-124-G433. The doctoral dissertation of James W. Thatcher on first-order properties of structures over finite alphabets is well advanced. Since the details of all this work are (or will soon be) covered in the technical reports, only abstracts are provided herein. The general emphasis of the work has been on the relation of logical languages to automata and to algebraic structures. Eggan's paper relates a structural property of regular expressions to the structural properties of automata graphs. Thatcher's thesis relates first-1

order logical languages to various algebraic structures whose domain is a set of possible input sequences to an automaton. Thatcher's "Notes on Mathematical Automata Theory" studies monadic algebras as an algebraic framework for the theory of finite automata. The notion of a monoid turns out to be very important here. Results about monoids and automata are obtained in Givevon's "Normal Monoids and Factor Monoids of Commutative Monoidso" Give'on's "The Theory of Algebraic Automata I: Morphisms and Regular Systems" generalizes the algebraic concept of regular events. The scientific personnel supported in whole or in part are: Professor Arthur W. Burks, Professor John H. Holland, Professor L. C. Eggan, J. B. Wright, J. R. BUchi, and R. A. Laing. The following people are conducting research to satisfy requirements for the Ph.D. in Communication Sciences at The University of Michigan: M. R. Finley, Y. Give'on, S. T. Hedetniemi, C. V. Page, and J. W. Thatcher. -2

A B ST R A C T Normal Monoids and Factor Monoids of Commutative Monoids Y Give on A study of abelian monoids is suggested by the study of commutative machines of Laing and Wright.* In this paper the concept of normal submonoids is adoptedfrom group theory and the expected results about factor monoids are derived in a straightforward manner. However, in order to show that any normal submonoid of a finitely generated free abelian monoid is also finitely generated, certain closure operations are introduced following the relationship that free abelian monoids have to linear spaces. * R. Laing and J. B. Wright, "Commutative Machines," Technical Note 04422, 0310525-T, The University of Michigan Office of Research Administration, December 1962. -3

ABSTRACT Notes on Mathematical Automata Theory J. W. Thatcher An algebraic study of monadic algebras is presented as an algebraic framework for the theory of finite automata. The basic concepts of this framework are: monadic algebra, homomorphisms of monadic algebras, congruence relations on monadic algebras and quotient algebras. The relationship between these concepts, and in particular, the structure of the lattice of the congruence relations on a finitely generated free monoid are studied. Monadic algebras are associated with finitely generated monoids and shown to be isomorphic with the transition algebras associated with monadic algebras in the free case. The direct product of monadic algebras is introduced and discussed, and a necessary and sufficient condition for the decomposition of a monadic algebra (into the direct product of two quotients of 9Jis given. At last an interpretation of monadic algebras as systems defining subsets of the free monoid is introduced and discussed in detail. A generalization, which is analogous to the notion of non-deterministic automata, is introduced and studied as well. -4

A B ST RA C T The Theory of Algebraic Automata I: Morphisms & Regular Systems Y. Give'on A generalization of the concept of regular events is suggested by the characterization of regular events by means of homomorphisms of a finite range. A subset E of W is said to be regular in W iff E =,-P-1YP(E) for some homomorphism 90 of W with a finite range. The paper studies certain basic properties of R, the class of the regular events in W. In particular, it is shown that RW can be determined by finite automata with W as their set of input "tapes" in a fashion analogous to that of Rabin-Scott's approach. Furthermore, by means of the direct product construction, it is effectively shown that RW is a Boolean algebra of sets. The effects of homomorphisms of W on RW are studied and a necessary and sufficient condition for regularity-invariance is given. -5

ABSTRACT Transition Graphs and the Star-Height of Regular Events L. C. Eggan Regular events are determined by various means. This paper studies a structural property of regular expressions relative to the events denoted by them, namely the star-height of regular events. It is shown that there exist regular events of arbitrarily large star-height. Certain sufficient conditions for a regular event to have star-height greater than or equal to n are given. Now structural properties of other systems which define regular events are compared with the star-height of the event defined. In particular, it is shown that for any digraph of cycle rank n, the set of paths between any two points is a regular event of star-height no greater than n. A definition of a measure of feedback for a finite automaton is suggested and it is related to the star-height of the event defined by the automaton. -6

A B S T R A C T First-order Properties of Structures Over Finite Alphabets J, W. Thatcher The principal area of study is that of first-order theories of generalized arithmetic (arithmetic with k successor functions) related to the theory of finite automata. The domain of discourse for such a theory is the set of finite strings or words over an alphabet of k symbols. Concentration is on those theories for which definability is at least as weak as regularity (recognizability by finite automata). A natural sequence of theories, analogous to that studied for ordinary arithmetic, includes successively the primitives: (1) the k successor functions, (2) the initial segment or prefix relation and (3) the equality of length relation. This sequence yields a corresponding sequence of definable sets(1) the definite sets, (2) the atomic regular sets and (3) the regular sets~ The second class, consisting of the closure of the finite sets under the boolean operations and complex product, is especially interesting. Because of the close connection between the atomic regular sets and the regular sets (every regular set is a projection of an atomic regular set), it is hoped that a study of this class may yeild insight into the general study of regularity. Relationships between the classes of definable sets, the languages or theories and the corresponding restricted classes of finite automata are studied. Additional results include determining the undecidability of theories involving the occurrence or subword relation and axiomatizing two of the weaker (and decidable) theories. -7

UNIVERSITY OF MICHIGAN 3II I05 IIII I8ii II1111111111111281 3 9015 02082 8128