Algebra automata I: Parallel programming as a prolegomena to the categorical approach

Wright, Thatcher and Mezei have built on the observation of B\:uchi that finite automata may be considered to be monadic algebras, to study non-monadic algebras from the viewpoint of automata theory, and have generalized the usual studies of regular sets and context-free languages in this context. We continue this work, but shift the emphasis from the use of algebra automata as acceptors to the dynamics of algebras with outputs. We show that the Nerode and Myhill approaches to state minimization and minimal dynamics can be carried through in the general case.In Part I, we emphasize the interpretation of algebra automata as executing parallel programs. However, Eilenberg and Wright have shown that much of Wright, Thatcher and Mezei's 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. Our results in Part I pave the way for the extension of this categorical framework to the treatment of algebra automata as dynamic systems in Part II [Inform. Control 13, 346\2-370 (1968)]