ALGEBRA AUTOMATA I: PARALLEL PROGRAMMING AS A PROLEGOMENA TO THE CATEGORICAL APPROACH.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1967
- Accession Number
- AD0666677
Entities
People
- M. A. Arbib
- Y. Give'on
Organizations
- Stanford University