Algebra automata II: The categorical framework for dynamic analysis

We extend the treatment of algebra automata to automata employing algebras over arbitrary theories. To this end we re-present Eilenberg and Wright's approach to the notion of a theory and its algebras originated by Lawvere. Special attention is given here to the free theories which correspond, in ordinary automata theory, to the free monoids. For example, we prove that the free theories (like the free monoids) are characterized as the projective objects in the category of theories with surjective morphisms of theories only.For a theory T, a T-automation is defined in a straightforward analogy with the notion of an automaton with an arbitrary input monoid. Our definition of a T-automaton becomes obvious once it is recognized that a T-algebra is the appropriate explication for a right-action of T on a set. Consequently, the construction of a minimal realization and of a minimal dynamics of any given response function f on a theory is analogous to the same construction with respect to a mapping f on a monoid. Also the basic division lemmata which underlie Krohn and Rhodes' composition theory of machines are true for response function on free theories