Semigroups whith idempotent stabilizers and applications to automata theory

Bertrand Le Saec, Jean-Éric Pin et Pascal Weil



Résumé : Nous prouvons que tout semigroupe fini est quotient d'un semigroupe fini dans lequel les stabilisateurs droits satisfont les identités x = x2 et xy = xyx. Ce résultat a plusieurs conséquences. Nous donnons tout d'abord une application géométrique : tout semigroupe de transformation fini a un revêtement sans point fixe (un semigroupe de transformation est dit sans point fixe si tout élément qui stabilise un point est idempotent). Puis nous utilisons notre résultat, ainsi qu'un résultat de I. Simon sur les congruences de chemins, pour obtenir une preuve purement algébrique d'un théorème profond de McNaughton sur les mots infinis. Enfin, nous donnons une preuve algébrique d'un théorème de Brown sur des conditions de finitude pour les semigroupes.

Abstract : We show that every finite semigroup is a quotient of a finite semigroup in which every right stabilizer satisfies the identities x = x2 and xy = xyx. This result has several consequences. We first give a geometrical application : every finite transformation semigroup has a fixpoint-free covering (a transformation semigroup is fixpoint-free if every element which stabilizes a point is idempotent). Next we use our result and a result of I. Simon on congruences on paths to obtain a purely algebraic proof of a deep theorem of McNaughton on infinite words. Finally, we give an algebraic proof of a theorem of Brown on a finiteness condition for semigroups.

PostScript gzipped file, PDF file


Valid HTML 4.01!