THE UNIVERSITY OF MICHIGAN COLLEGE OF LITERATURE, SCIENCE, AND THE ARTS Department of Communication Sciences Final Report (1 June 1965 — 30 September 1966) LANGUAGE AND AUTOMATA Arthur W. Burks ORA Project 07363 under contract with: U.S. ARMY RESEARCH OFFICE (DURHAM) Grant No. DA-ARO(D)-31-124-G665 DURHAM, NORTH CAROLINA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR October 1966

rat.. m s In So * X t.tq, >,; A.,_} WA_>

The following is a report of research on language and automata conducted at The University of Michigan during the period 1 June 1965 to 30 September 1966, and supported in whole or in part through grant ARO(D)31-124-G665. Seven technical reports have been prepared: (1) Y. Give'on, "Transparent Categories and Categories of Transition Systems," Technical Report 03105-38-T, The University of Michigan Office of Research Administration, May 1965. (2) R. Laing, "Tape Machine Realizations of Commutative-Regular Events," Technical Report 07363, 03105-39-T, The University of Michigan Office of Research Administration, September 1965. (3) Y. Give'on, "A Homomorphic Theory of Context-Free Languages and Its Generalizations,' Technical Report 07363, 03105-40-T, The University of Michigan Office of Research Administration, September 1965. (4) C. Page, "Equivalences Between Probabilistic Sequential Machines," Technical Report 03105-41-T, The University of Michigan Office of Research Administration, November 1965. (5) S. Hedetniemi, "Homomorphisms of Graphs," Technical Report 0310542-T, The University of Michigan Office of Research Administration, December, 1965. (6) Y. Giveton, "On Some Categorical Algebra Aspects of Automata Theory: The Categorical Properties of Transition Systems," Technical Report 03105-43-T, The University of Michigan Office of Research Administration, February 1966. (7) S. Hedetniemi, "Homomorphisms of Graphs and Automata," Technical Report 03105-44-T, The University of Michigan Office of Research Administration, July 1966. -1

Since these reports already sent to you present all the technical details of the research, this final report contains the abstracts only of these completed papers. Items (1) and (6) above, by Give'on, present algebraic treatments of automata theory. In this research, various algebraic approaches to automata theory are generalized and the scope of algebraic results applicable to automata theory enlarged. It is hoped that this strengthened association between automata theory and abstract algebra will encourage the participation of more algebraists in automata theory research. Item (2) above, by Laing, shows how counter-tape machines operating in real-time can be constructed so as to realize any of the commutativeregular events on two letters. Item (3), by Give'on, provides, by means of algebraic methods applied to context-free languages, some extensions of the original context-free notion, and simplification of some of the classical results for these languages. Page, in item (4), discusses probabilistic machines, and the problem of deciding when the behavior of such machines is equivalent. These probabilistic machines are of especial importance because they are the theoretical counter-part of important physical systems, such as digital componentry subject to error, and most bio-chemical and biological systems. Items (5) and (7), by Hedetniemi, bring the results and tools of graph theory to bear on automata theory problems. Not only is graph theory shown to be applicable to many automaton problems, but under the influence of the problems and viewpoints of automata theory, many original graph theory notions are defined and results obtained. -2

The scientific personnel of the Logic of Computers Group who participated in this program of research are: Professor A. W. Burks, Professor J. H. Holland, R. Laing, Y. Give'on, S. Hedetniemi, C. Page, and B. Zeigler. Y. Give'on was awarded a Ph.D. in Communication Sciences at The University of Michigan in April 1966; he is now at the Harvard Computation Laboratory, Harvard University. S. Hedetniemi was granted a Ph.D. in Communication Sciences at The University of Michigan in July 1966. C. Page was granted a Ph.D. in Communication Sciences at The University of Michigan in December 1965; he is now at the University of North Carolina. B. Zeigler is conducting research to satisfy requirements for the Ph.D. in Communication Sciences at The University of Michigan -3

A B ST RA CT Transparent Categories and Categories of Transition Systems Y. Give' on Several recent results in automata theory give evidence of the importance of homomorphisms in the study of transition systems and automata. It is natural therefore to inquire how much information can be retrieved from the algebra of homomorphism compositions with respect to transition systems. The natural mathematical framework for the discussion of this problem is categorical algebra. We define a category &W of the transition systems with input W where W is any arbitrary fixed monoid, and with arbitrary sets of states. A preliminary study of SW (Give'on 1964) shows that one can reconstruct the internal structure of any transition system from the way homomorphisms (i.e., the morphisms of A ) behave around it. In this paper we show that AW has a generator, ~M (which is W operating on itself as a transition system) and that there exists a functor Mor: AW - eW naturally equivalent to the identity functor of AW which factors through HomW (~M,-). A general exposition of the nature of properties which are retrievable from the "morphism-behavior" in an arbitrary category is presented so that it provides a rigorous general basis for studying "retrievable" properties and categories in which every structural property of objects and morphisms is "retrievable." Finally, we prove that for a very broad class of input monoids, which -4

includes all the types of input monoids encountered in automata theory, the categories AW are transparent. That is, anything which can be said about the structure of transition systems with input W, can be said by referring to their homomorphisms only. In particular, all the automorphisms of W,' for this type of W, are naturally equivalent to the identity functor of %tw -5

ABSTRACT Tape Machine Realizations of Commutative-Regular Events R. Laing In this paper various infinite tape machine realizations of classes of commutative-regular events are explored. In particular, a class of events which requires for machine realization an infinite-state machine with an infinite number of final states, and a class, somewhat more intractable, which requires an infinite state machine with an infinite number of final states, and which in addition is not strongly connected, are considered. Procedures for constructing deterministic machines with infinite counter tapes, which realize the events under examination, are given.

A B ST RA CT A Homomorphic Theory of Context-Free Languages and Its Generalizations Y. Give'on Usually, and naturally, context-free languages are defined and studied by means of grammars. In the course of study of these languages several algebraic characterizations were found. In this paper we want to regard one of these characterizations (namely, the homomorphic characterization that was established by Chomsky and Schutzenberger) as the definition of this family of languages and to show how one can derive some of their well known properties directly from this "redefinition." In addition to simplification of proofs we find that the arguments involved lead us naturally to some generalizations that have some bearing on mathematical linguistics. The families of languages derived by means of these generalizations exhibit some features which are too complex for the context-free model and yet these features are of the type that one encounters in the study of natural languages. We discuss very briefly some examples of these generalizations. -7

ABSTRACT Equivalences Between Probabilistic Sequential Machines C. Page This report introduces new definitions of behavioral equivalence and shows relationships among the various notions of behavioral equivalence between probabilistic machines. Four basic problems are discussed for several different behavioral equivalences between machines. In what follows we use the symbol "=" as a variable to denote one of the several behavioral equivalences considered in this report. Given an arbitrary probabilistic sequential machine A: (1) Is there an input-state calculable machine A' (a machine with deterministic switching and random outputs) such that A - A'? (2) What are the machines A' with minimal number of states such that A = A'? (3) How does one obtain all stable modifications of A, i.e., all machines A' such that the switching probabilities of A' and A differ but A -- A'? (4) Is there a finite bound on the length of experiments required to establish whether A - A' holds? The four basic problems are solved completely for some equivalences between machines and are left open for other equivalences. Some applications are made to optimal control problems. -8

ABSTRACT Homomorphisms of Graphs S. Hedetniemi The works of Hartmanis and Stearns, Krohn and Rhodes, Yoeli and Ginzburg, and Zeiger amply demonstrate the usefulness of homomorphisms in studying decompositions of finite automata. Yoeli and Ginzburg's approach is slightly different from the others in that it is more concerned with aspects of the state transition graphs of finite automata. In their paper, "On Homomorphic Images of Transition Graphs," they give a complete characterization of the class of homomorphisms of the graphs which correspond to input-free automata. This paper was motivated by an interest in extending these results of Yoeli and Ginzburg in the direction of a characterization of the class of homomorphisms of graphs which correspond to arbitrary finite automata. It is a review and a classification of most of the published definitions and results on mappings of graphs which have been called homomorphisms. The paper contains, in addition, several new results and several new definitions of homomorphisms of graphs. -9

ABSTRACT On Some Categorical Algebra Aspects of Automata Theory: The Categorical Properties of Transition Systems Y. Give' on The ubiquity and usefulness of homomorphisms in various studies of automata lead us to consider the following problem. What can be said on automata by referring only to homomorphisms of automata? In the report, we present a study of this problem with respect to a special type of automaton, namely, with respect to transition systems. Categorical algebra methods are applied to the precise formulation of this problem and to its solution. We find that if W is a monoid belonging to a broad class of monoids, then the categorical abstract properties of transition systems with input W, are determined by the automorphisms of the monoid W. In particular, any property of automata without output is categorical iff it does not depend on the particular labeling of the input alphabet. This study of the categorical properties of automata has two additional outcomes. First, we realize that categorical algebra methods can be applied to automata with arbitrary input monoids, with results pertinent to the theory of monoids. On the other hand, it indicates a possible usefulness in the study of automata, in particular, in getting a better understanding of the mathematical ideas employed in automata theory. In order to support this point of view with respect to automata theory, we show that many actually studied properties of automata are categorical. And we give an example of a categorical examination and formulation of a particular study of perfect automata. -10

A B ST RA CT Homomorphisms of Graphs and Automata S. Hedetniemi A homomorphism of a graph G onto a graph G' is a function j from the set of points of G onto the set of points of G' such that whenever two points a and b are adjacent in G, their images, a~ and b$, are adjacent in G'. The concept of a homomorphism of an algebra or of a relational system has been defined and studied for many years, yet the concept of a homomorphism of a graph has not. Although several definitions of graphical homomorphisms have appeared in the literature, not many results have been obtained. In this paper the concept of a homomorphism of a graph is extensively studied. It is shown that the language of graphical homomorphisms is capable of expressing a variety of previously established results in graph theory in such a light as to enable these results to be generalized, proved as corollaries, or proved more simply. It is shown that the concept of a homomorphism of a graph is related to several other concepts in graph theory on the basis of which a number of altogether new results are established. It is also shown that in some cases the usefulness of homomorphisms in solving problems in graph theory is rather limited. The results that are obtained and the questions that are raised in this paper can be said to be either algebraic or graph theoretic in nature. However, an emphasis is placed upon obtaining graph theoretic results. Consequently, there are very few purely algebraic results in this paper; the portions of this work which are algebraic are almost entirely foundational in nature. -11

I I

UNIVERSITY OF MICHIGAN 3111111III 90 11111111151111111 61 3 9015 02653 6071