Structure and Transition-Preserving Functions of Finite Automata
Zamir Bavel · Journal of the ACM · 1968
Arbitrary finite automata are decomposed into their major substructures, the primaries. Several characterizations of homomorphisms, endomorphisms, isomorphisms, and automorphisms of arbitrary finite automata are presented via reduction to the primaries of the automata. Various characterizations of these transition-preserving functions on singly generated automata are presented and are used as a basis for the reduction. Estimates on the number of functions of each type are given.