THE UNIVERSITY OF.MICHICAN COLLEGE OF LITERATURE, SCIENCE, AND TIHE ARTS Department of Communication Sciences Final Report (1 June 1964 - 31 May 1965) LANGUAGE AND AUTOMATA Arthur W. Burks ORA Project 06689 under contract with: U.S. ARMIY RESEARCH OFFICE (DURHtAM1) Grant No. DA-ARO(D)-31-124-G558 DURHAM, NORTH CAROLINA administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR June 1965

I -7~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~-e-/f

The following is a report of research on language and automata conducted at The University of Michigan during the period 1 June 1964 to 31 May 1965 and supported in whole or in part through grant ARO(D)-31-124-G558. Seven technical reports have been prepared: (1) J.W. Thatcher, "Decision Problems for Multiple Successor Arithmetics," Technical Report 03105-36-T, The University of Michigan Office of Research Administration, April 1965. (2) J.W. Thatcher, "Universality in the von Neumann Cellular Model," Technical Report 06376, 06689, 03105-30-T, The University of Michigan Office of Research Administration, September 1964. (3) Y. Give'on, "Toward a Homological Algebra of Automata I: 1. The Representation and Completeness Theorem for Categories of Abstract Automata," Technical Report 06689, 03105-32-T, The University of Michigan Office of Research Administration, December 1964. (4) Y. Give'on, "Toward a Homological Algebra of Automata II: 2. A Note on Some Well Known Functors of Automata," Technical Report 06689, 03105-33-T, The University of Michigan Office of Research Administration, January 1965,. (5) Y. Give'on, "Toward a Homological Algebra of Automata III: 3. Composition Series of Automata 4. Extensions of Q-Automata," Technical Report 06689, 03105-31-T, The University of Michigan Office of Research Administration, December 1964. (6) Y. Give'on, "Toward a Ilomological Algebra of Automata IV: 5. The Characterization of Projective Automata," Technical Report 06689, 03105-34-T, The University of Michigan Office of Research Administration, January 1965. -1

(7) C.V. Page, "Equivalences Between Probabilistic and Deterministic Sequential Machines," Technical Report 03105-37-T, The University of Michigan Office of Research Administration, April 1965. Thatcher's paper on "decision problems" has been submitted for publication; his paper on cellular automata may appear in a collection of papers on the general topic of systems of growing cellular automata. The papers of Give'on concern themselves with the problem of unifying the algebraic approaches to the theory of automata, category theory being the principal algebraic tool employed. The work by Page is directed to explaining the relationship between deterministic and probabilistic automata, the primary practical motivation being the appropriateness of probabilistic automata as models for important processes such as the functioning of actual digital computers, and the synthesizing of proteins within a cell. Since the details of this research have already reached you in the form of the complete technical reports, this Final Report confines itself to abstracts of the research accomplishments. The scientific personnel of the Logic of Computers Group who participated in this program of research are: Professor A. W. Burks, Professor John Holland, R. A. Laing, Y. Give'on, S. Htedetniemi, M. Finley, C. V. Page, and J. W. Thatcher (Thatcher is now at the IBM Watson Research Center, Yorktown Heights, New York). Give'on, Hedetniemi, Finley and Page are conducting research to satisfy requirements for the Ph.D. in Communication Sciences at The University of Michigan; Thatcher has been awarded his degree. -2

ABSTRACT Decision Problems for Multiple Successor Arithmetics J.W. Thatcher Let Nk denote the set of words over the alphabet Ek = {l,...,k). Nk contains the null word which is denoted X. We consider decision problems for various first-order interpreted predicate languages in which the variables range over Nk(k > 2). Our main result is that there is no decision procedure for truth in the interpreted language which has the subword relation as its only non-logical primitive. This, together with known results summarized in Section 4, settles the decision problem for any language constructed on the basis of the relations and functions listed below. Concatenation u v = uv Subword u v gxgy [v = xuy] Prefix u v -+ x [ux = v] Suffix v u +- gx [xu = v] Reflection c(ol.. an) = an. l (aiZck) Right Successors ra(u) = ua (ack) Left Successors C(u) = au (CCEk) Equal length L(u,v) *-+ u and v have the same number of symbols. -3

AB STRACT Universality in the von Neumann Cellular Model J.W. Thatcher The von Neumann cellular automaton model is described and designs within this model are presented for objects that behave like tape and constructing units. An algorithm is developed for embedding in the cellular structure any automaton which effectively manipulates the tape and constructing units. The algorithm is based on a very simple language in which the behavior of such machines can be described. Finally, universality of construction and computation as well as automaton self-reproduction are discussed relative to the von Neumann model. -4

ABSTRACT Toward a Homological Algebra of Automata I: 1. The Representation and Completeness Theorem for Categories of Abstract Automata Y. Give'on In this paper the author formulates the categorical theory of abstract automata. Two immediate basic problems are posed. First, one wonders how restricted the study of abstract automata is when one confines himself to those properties which are formulated by means of the notions of category theory only. This is a mathematical question whose answer should be proved. The author proves the completeness of the categorical study of abstract automata for a wide class of input monoids, a class which includes all types of monoids employed in the theory of finite automata. In order to get this result, a general representation theorem for abstract automata is derived. The second question is psychological. How well does the categorical study of automata suit our intuitions and our problem? The answer to such a problem is not a matter of proof. The development presented in this paper has convinced the author of the potentiality of this new approach toward automata. Thus, this paper serves as a prelude to a series of papers which will exploit homological and categorical algebra methods for the sake of a mathematical theory of automata. -5

ABSTRACT Toward a Homological Algebra of Automata II: 2. A Note on Some Well Known Functors of Automata Y. Give'on The provision of a suitable definition of homomorphisms of abstract automata (i.e., of state diagrams with an arbitrary fixed input monoid W) yields of category (denoted by AW). The naturalness of the application of category theory to the study of automata follows from the fact that many, if not most, of the processes employed in automata theory turn out to be functors of or into AW. This observation, which is reviewed in the present paper, has led the author to experiment with a more thorough application of the category theory approach to AW. The results of this application are presented in the series of papers under the common title "Toward a Homological Algebra of Automata." -6

ABSTRACT Toward a Homological Algebra of Automata III: 3. Composition Series of Automata 4. Extensions of Q-Automata Y. Give'on 3. Composition Series of Automata The classical results of commutative algebra on composition series (i.e., the theorems of Jordan, Holder, Zassenhaus, and Schreier) are derived for automata. The relevance of these results to the study of automata is discussed briefly by means of an alternative proof of these results, 4. Extensions of Q-Automata Previous results of the author concerning composition series for automata lead to the introduction of a specific type of quotient operation of an automaton relative to any subautomaton. Naturally, the problem of extensions, relative to this type of quotient, is posed. A complete characterization and a method of construction of all possible extensions o-automata are derived for a broad class of automata. -7

ABSTRACT Toward a Homological Algebra of Automata IV: 5. The Characterization of Projective Automata Y. Give'on The problem of characterizing the projective objects of a studied category is a natural one. In our case of the category theoretic study of automata, the importance of this characterization is derived from the importance of the characterization of Mw, the input monoid regarded as an automaton. The methods of homological algebra appear to be sufficient for a complete characterization of the projective automata. This characterization implies a possible application of automata theory to the theory of monoids (in analogy to the fruitful interaction between ring theory and module theory). It also provides a characterization of Mw for finite input monoids, and thus the categorical-completeness theorem for AW for any finite input monoid W. -8 —

ABSTRACT Equivalences Between Probabilistic and Deterministic Sequential Machines C.V. Page The concept of probabilistic sequential machines (PSM), a generalization of Rabin's concept of probabilistic automata, is defined. Such diverse devices as unreliable digital computers, slot machines, and chemical cells are presented as examples of PSM. Using the examples as motivation, various kinds of equivalences between machines are discussed. The fundamental question of when a PSM is equivalent in some sense to a deterministic machine, perhaps with random devices attached to output states, is considered. Finally, various tests involving finitely many random variables are devised for each of the kinds of equivalences between PSM and for reduction, if possible, to deterministic machines. One of the tests is a further generalization of the Moore bound for deterministic machines than has previously appeared in the literature. -9

I I I I i I I I I i II I I I I I I I I

UNIVERSITY OF MICHIGAN 3 9015 02653 6063