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