Préliminaires pour les langages formels

Remarque

I Contrairement au cas des langages rationnels, les automates à pile non ambigus sont strictement moins expressifs que les automates à pile non déterministes. Nous parlerons plus en détail de ces langages, appelés intrinsèquement ambigus, dans le chapitre 7. existe des langages algébriques qui ne sont reconnus par aucun automate à pile non ambigu. J

Ensembles semilinéaires

Un des objectifs de cette thèse est d’étendre certains résultats sur les langages algébriques, à d’autres familles de langages plus larges. Dans notre contexte, pour étendre les langages algébriques, nous aurons besoin de la notion d’ensembles semilinéaires.
Les ensembles semilinéaires sont à N d ce que les langages rationnels sont à Σ ⇤.
Ce sont des ensembles fondamentaux qui apparaissent naturellement en théorie des langages. Dans cette section nous présentons les dé »nitions et propriétés de base des ensembles semilinéaires. Nous renvoyons le lecteur au guide de survie de l’arithmétique de Presburger de [Haa18] pour un excellent survey plus complet sur les ensembles semilinéaires. Dans la suite nous « xons d une dimension, et nous nous plaçons dans l’ensemble N d des vecteurs à coordonnées entières.

Préliminaires de combinatoire analytique

Dans cette section, je présente rapidement quelques outils de combinatoire analytique que j’ai utilisés dans ma thèse. La combinatoire analytique étudie des ensembles combinatoires en s’appuyant sur les propriétés analytiques de leurs séries génératrices, vues comme des fonctions complexes. Ces préliminaires sont largement inspirés de [FS09].

Série formelle, série génératrice

Un objet mathématique central en combinatoire est la série formelle. Nous présentons ici les dé »nitions et résultats fondamentaux sur ces objets qui nous seront utiles dans la suite, avant de les relier aux objects combinatoires dans la section suivante.
Nous notons Q l’ensemble des rationnels, R l’ensemble des réels, et C l’ensemble des nombres complexes. Pour K = Q, R ou C, et d > 1, nous notons K[x1,…,xd] l’ensemble des polynômes à coe#cients dans K, en les indéterminées x1,…,xd. Nous notons K[[x1,…,xd]] l’ensemble des séries formelles à coe#cients dans K en les indéterminées x1,…,xd, c’est-à-dire l’ensemble des polynômes formels in »nis de la forme.
Nous introduisons à présent les séries holonomes. La classe des séries holonomes est une classe plus grande que celle des séries algébriques. Une très bonne introduction aux fonctions holonomes à une variable peut être trouvée dans [Sta80], et pour les fonctions multivariées, dans [Lip88] et [Lip89] ; nous citons aussi le début de [Chy94], qui détaille certaines preuves plus en détail.
L’opérateur di!érentiel @xk dé »nit la dérivée partielle d’une série par rapport à la variable xk. Il s’agit simplement de la généralisation de la dérivation des polynômes aux séries. Elle est dé »nit formellement par.

Remarque 

I Les séries holonomes sont aussi appelées D-« nite. Les deux appellations sont utilisées indi!éremment dans le cas des séries de Q[[x1,…,xd]], cependant leur dé »nition n’est historiquement pas la même. La dé »nition que nous avons donnée est en réalité celle des séries D-« nite, qui est plus simple à comprendre. La dé »nition originale des séries holonomes implique la vitesse de croissance de la dimension d’une famille d’espaces engendrés par des dérivées partielles, mais elle dépasse le cadre de cette thèse et nous n’en aurons pas besoin dans la suite. L’équivalence avec les séries D-« nites provient de résultats profonds de Bernšte˘ın [Ber72] et Kashiwara [Kas78, Tak92].
Déterminer la série génératrice d’une classe combinatoire revient à savoir compter exactement pour toute taille n 2 N le nombre cn d’éléments de C de taille n. Il se trouve que de nombreuses classes combinatoires peuvent se construire à partir de classes combinatoires de base et d’opérations sur ces classes. Dans leur livre [FS09], Flajolet et Sedgewick expliquent comment la description d’une classe combinatoire sous la forme de cet assemblage de briques élémentaires se traduit automatiquement en une équation véri »ée par la série génératrice de la classe combinatoire.

Remarque 

I L’intérêt de rendre les unions disjointes dans la dé »nition de la somme est double : premièrement, s’il existait un élément en commun t dans C1 et C2, mais |t|1 6= |t|2, nous aurions un problème pour dé »nir la taille de t dans la classe somme. Ensuite, « dédoubler » les éléments en commun permet d’exprimer facilement la série génératrice de la somme à partir de celles des classes C1 et C2.
Lors des calculs pratiques de combinatoire analytique, la question ne se pose pas car nous partons généralement d’une classe combinatoire qui existe, et nous construisons rétrospectivement une spéci »cation de cette classe, qui par construction engendre exactement la classe combinatoire que nous étudions.
D’un point de vue théorique, il est cependant nécessaire pour construire une théorie des classes combinatoires et de leur spéci »cation de dé »nir proprement celles qui dé »nissent des classes combinatoires valides. Il ne s’agit d’ailleurs pas que d’une question théorique, puisque les spéci »cations servent aussi à rendre automatique la génération aléatoire : un algorithme automatique de génération aléatoire doit être capable de détecter que la spéci »cation qu’on lui donne en entrée décrit une classe combinatoire invalide.
Ce sont des questions profondes, et qui sortent du cadre de cette thèse. Le but de ces préliminaires n’est pas de dé »nir les propriétés que doit véri »er une spéci- « cation pour dé »nir une classe combinatoire. Nous renvoyons pour cela le lecteur à l’article de [PSS12] qui dé »nit précisément et rigoureusement des conditions sur de tels systèmes qui permettent de garantir l’existence et l’unicité de la solution, en utilisant le formalisme des espèces [BBLL98]. En pratique nous utiliserons dans les prochains chapitres des spéci »cations su#samment simples pour que la question ne se pose pas, qui véri »eront presque toutes les conditions de [PSS12]. Les seules qui pourraient poser des problèmes seront celles issues des automates, car les spéci »cations produisent naturellement des classes neutres isolées, ce qui est interdit dans les conditions de [PSS12]. Cependant ces systèmes ont naturellement une solution, puisqu’ils décrivent exactement les calculs des automates, et ils sont d’autre part très simples (ils sont linéaires).
Nous nous intéressons désormais à la transformation suivante : étant donné un arbre d’expression régulière T 2 LR, nous notons (T) l’arbre obtenu à partir de T en supprimant toutes les étoiles ? qui se trouvent directement au-dessus d’une étoile ; autrement dit (T) est obtenu en remplaçant tous les sous-arbres de T de la forme (T et en recommençant jusqu’à ce qu’il ne soit plus possible de trouver deux étoiles consécutives. Nous nous intéressons à la taille moyenne d’un arbre de taille n après simpli »cation. Nous cherchons donc à marquer dans la spéci »cation les étoiles qui disparaissent après simpli »cation. Actuellement, la spéci »cation de LR ne nous permet pas de distinguer les étoiles qui vont rester de celles qui vont disparaître, nous devons introduire des classes supplémentaires pour le faire : nous notons A l’ensemble des arbres dont la racine n’est pas une étoile, et S l’ensemble des arbres qui commencent par une étoile. Nous avons la dé »nition récursive suivante :