This work relates classes of finite automata under various feedback products to some well-known pseudovarieties of finite semigroups via a study of their irreducible divisors (in the sense of Krohn-Rhodes). In particular, this serves to relate some classical results of Krohn, Rhodes, Stiffler, Eilenberg, Letichevsky, Gécseg, Ésik, and Horváth.
We show that for a finite automaton satisfaction of
(1) the Letichevsky criterion for non-empty words,
(2) the semi-Letichevsky criterion for non-empty words, or
(3) neither criterion,
corresponds, respectively, to the following properties of the characteristic semigroup of the automaton:
(1) non-constructability as a divisor of
a cascade product of copies of the two-element monoid
with zero U,
(2) such constructability while having U but no other non-trivial irreducible semigroup as a divisor, or
(3) having no non-trivial irreducible semigroup divisors at all.
The latter two cases are exactly the cases in which the characteristic semigroup is R-trivial.
This algebraic characterization supports the transfer of results about finite automata to results about finite semigroups (and vice versa), and yields insight into the lattice of pseudovarieties of finite semigroups --- or, equivalently via the Eilenberg correspondence, the lattice of +-varieties of regular languages --- and the operators on these lattices that are naturally associated to various automata products with bounded feedback. In particular, all operators with non-trivial feedback are shown to be equivalent, and we characterize all pseudovarieties of finite semigroups closed under each type of feedback product either explicitly or by reducing the question to closure under the cascade product.
Sponsored in part by the FCT approved projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with the European Community Fund FEDER and by FCT through Centro de Matemática da Universidade do Porto. Also sponsored in part by FCT, the Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III, and by Caixa Geral de Depósitos.