Stuart W. Margolis, Jean-Éric Pin et Mishal V. Volkov
Résumé : Etant donné un entier n et un
alphabet fini A, on dit qu'un mot w sur Agarantit
une image minimale si, pour tout morphisme f du monoïde
libre A* sur A vers le monoïde de toutes les
transformations sur un ensemble à n éléments, le rang
des transformations wf est de cardinalité minimale parmi les
rangs de toutes les transformations de la forme vf où v
varie dans A*. Bien que l'existence de mots garantissant
l'image minimale soit évidente, le problème de leur
description explicite est loin d'être trivial. Sauer et Stone ont
donné en 1991 une construction récursive pour un tel mot
w mais la longueur du mot obtenu à partir de cette
construction était doublement exponentiel en n. Nous montrons
d'abord que des résultats connus de théorie des automates
fournissent immédiatement un mot plus court qui garantit l'image
minimale: ce mot est de longueur simplement exponentielle, et plus
précisément, sa longueur est en
O(|A|(n3-n)). En utilisant une
approche différente, nous donnons un mot d'image minimale similaire
à celui de Sauer et Stone mais de longueur en
O(|A|(n2-n)). Nous observons par
ailleurs que la longueur d'un mot qui garantit l'image minimale est au moins
|A|(n-1).
Abstract : Given a positive integer n and a finite alphabet
A, a word w over A is said to guarantee minimal
image if, for every homomorphism f from the free monoid
A* over A into the monoid of all transformations
of an n-element set, the range of the transformation wf has the
minimum cardinality among the ranges of all transformations of the form
vf where v runs over A*. Although the
existence of words guaranteeing minimal image is pretty obvious, the
problem of their explicit description is very far from being trivial. Sauer
and Stone in 1991 gave a recursive construction for such a word w
but the length of the word resulting from that construction was doubly
exponential (as a function of n). We first show that some known
results of automata theory immediately lead to an alternative construction
which yields a simpler word that guarantees minimal image: it has
exponential length, more precisely, its length is
O(|A|(n3-n)). Then using a different approach,
we find a word guaranteeing minimal image similar to that of Sauer and
Stone but of the length O(|A|(n2-n)). On the
other hand, we observe that the length of any word guaranteeing minimal
image cannot be less than |A|(n-1).