Some results on the generalized star-height problem

Jean-Éric Pin, Howard Straubing et Denis Thérien



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.

PostScript file compressed with gzip, PDF file


Valid HTML 4.01!