Accession Number : AD0666677

Title :   ALGEBRA AUTOMATA I: PARALLEL PROGRAMMING AS A PROLEGOMENA TO THE CATEGORICAL APPROACH.

Descriptive Note : Scientific interim rept.,

Corporate Author : STANFORD UNIV CALIF DEPT OF ELECTRICAL ENGINEERING

Personal Author(s) : Arbib,M. A. ; Give'on,Y.

Report Date : 1967

Pagination or Media Count : 26

Abstract : Wright, Thatcher and Mezei have built on the observation of Buchi that finite automata may be considered to be monadic algebras, to study non-monadic algebras from the viewpoint of automata theory, and have generalised the usual studies of regular sets and context-free languages in this context. This report continues this work, but shifts the emphasis from the use of algebra automata as acceptors to the dynamics of algebras with outputs. It is shown that the Nerode and Myhill approaches to state minimisation and minimal dynamics can be carried through in the general case. In Part I, the interpretation of algebra automata as executing parallel programs is emphasised. However, Eilenberg and Wright have shown that much of the work can be carried through in the context of categorical algebra, using the notion of algebraic theory introduced by Lawvere as a categorical explication of the notion of variety initiated by Birkhoff. The results in Part I pave the way for the extension of this categorical framework to the treatment of algebra automata as dynamic systems in our 'Algebra Automata II.' (Author)

Descriptors :   (*LEARNING MACHINES, AUTOMATA), (*MATHEMATICAL LOGIC, AUTOMATA), SET THEORY, MAPPING(TRANSFORMATIONS), GRAPHICS, ALGEBRA, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE