Words guaranteeing minimal image.

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 A garantit 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 vfv 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).

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!