Résumé : Nous démontrons une série de
résultats sur le problème de la hauteur d'étoile
généralisée. Dans cette version du problème de
la hauteur d'étoile, contrairement à sa version restreinte,
le complément fait partie des opérateurs de base. On montre
d'abord que la classe des langages de hauteur d'étoile ≤ n
est fermée pour certaines opérations (quotients à
droite et à gauche, inverse de morphismes alphabétiques et
substitutions injectives et sans-étoile). On sait que les langages
reconnus par un groupe commutatif sont de hauteur d'étoile 1.
On étend ce résultat aux groupes nilpotents de classe
2 et aux groupes qui divisent le produit semi-direct d'un groupe
commutatif par (Z/2Z)n. Dans la même direction,
nous montrons que l'un des langages proposé comme candidat à
la hauteur d'étoile 2 depuis une dizaine d'année, est
en fait de hauteur d'étoile 1. Nous montrons ensuite que si
un langage rationnel L est reconnu par un monoïde de la
variété engendrée par les produits en couronne de la
forme M o (G o N), où M et N sont des
monoïdes aperiodiques, et G est un groupe commutatif, alors L
est de hauteur d'étoile ≤ 1. Finalement nous montrons que
tout langage rationnel est l'image inverse par un morphisme entre deux
monoïdes libres d'un langage de hauteur d'étoile (restreinte)
1.
Abstract : We prove some results related to the generalized
star-height problem. In this problem, as opposed to the restricted
star-height problem, complementation is considered as a basic operator. We
first show that the class of languages of star-height ≤ n is closed
under certain operations (left and right quotients, inverse alphabetic
morphisms, injective star-free substitutions). It is known that languages
recognized by a commutative group are of star-height 1. We extend
this result to nilpotent groups of class 2 and to the groups that
divide a semidirect product of a commutative group by
(Z/2Z)n. In the same direction, we show that one of the
languages that was conjectured to be of star height 2 during the
past ten years, is in fact of star height 1. Next we show that if a
rational language L is recognized by a monoid of the variety
generated by wreath products of the form M o (G o N), where M
and N are aperiodic monoids, and G is a commutative group, then
L is of star-height ≤ 1. Finally we show that every rational
language is the inverse image, under some morphism between free monoids, of
a language of (restricted) star-height 1.