Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata
✍ Scribed by Pál Dömösi; Chrystopher L. Nehaniv; John L. Rhodes
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 358 KB
- Volume
- 302
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
This paper relates classes of ÿnite automata under various feedback products to some wellknown pseudovarieties of ÿnite 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, Sti er, Eilenberg, Letichevsky, Gà ecseg, à Esik, and Horvà ath. We show that for a ÿnite 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 ÿnite automata to results about ÿnite semigroups (and vice versa), and yields insight into the lattice of pseudovarieties of ÿnite 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 ÿnite semigroups closed