Systèmes de fonctions holonomes : application à la théorie des automates

Cette thèse s'articule autour de deux parties indépendantes, qui s'intéressent à des objets différents, mais qui se rassemblent dans la méthodologie appliquée pour les étudier : nous nous appuyons essentiellement dans les deux parties sur des outils mathématiques spécialisés dans l'étude des systèmes de séries génératrices. Dans la première partie, nous étudions des arbres dont les nœuds sont étiquetés par des opérateurs, qui représentent des expressions avec une sémantique, comme les expressions régulières qui représentent des langages, ou les expressions logiques qui représentent des fonctions booléennes. Nous supposons que pour ces arbres il existe un opérateur (*) qui possède un élément absorbant P, dans le sens où tout arbre de racine (*) et dont l'un des fils est P est équivalent sémantiquement à P (par exemple, 0 est absorbant pour x, (a+b)* est absorbant pour + sur les langages à deux lettres, etc). Nous définissons à partir de cet élément absorbant une fonction de réduction σ qui réduit une expression en simplifiant de bas en haut toutes les occurrences de l'élément P sous l'opérateur (*). Cette réduction préserve la sémantique de l'arbre, par définition d'un élément absorbant. La première partie de cette thèse étudie la taille moyenne après réduction d'un arbre aléatoire de taille n, lorsque n→∞. Dans les deux premiers chapitres, nous nous sommes intéressés à des arbres d'expressions uniformes décrits respectivement par un système combinatoire et une équation récursive unidimensionnelle. Nous avons montré que la distribution uniforme était dégénérée pour ces arbres d'expression en présence d'un élément absorbant : la taille moyenne après réduction tend vers une constante lorsque n→∞. Ce résultat remet en cause l'utilité des expressions aléatoires uniformes pour l'étude de la complexité en moyenne des algorithmes, ainsi que leur pertinence pour les tests de performance automatisés (benchmarks). Nous avons ensuite affiné le résultat précédent dans le cas des expressions régulières, en utilisant plus de règles de simplifications sémantiques propres aux langages. Enfin, nous nous sommes penchés sur le comportement en moyenne de la réduction pour une autre distribution, la distribution ABR. Nous montrons que la taille moyenne après réduction dépend de la probabilité d'apparition de l'opérateur absorbant, avec des changements de phase lorsque ce paramètre varie de 0 à 1.La deuxième partie étudie le lien entre les langages formels et les propriétés de leurs séries génératrices. Nous nous intéressons en particulier à notion de non-ambiguïté de certaines classes d'automates à compteurs. Intuitivement, un automate est non ambigu si tout mot qu'il accepte est accepté par un unique calcul acceptant dans l'automate. La non-ambiguïté permet de relier par une bijection les calculs de l'automate, qui suivent un description combinatoire dictée par les transitions de l'automate, aux mots du langage accepté par l'automate. Cette bijection permet alors de traduire la structure particulière de l'automate en équation sur les séries génératrices associées à l'automate. Dans la deuxième partie, nous étudions le lien entre des classes d'automates à compteur non ambigus, dont font partie les automates de Parikh faiblement non ambigus, et la classe des séries génératrices holonomes. Nous commençons par définir de façon robuste la notion de non-ambiguïté pour ces classes d'automates, en les reliant à plusieurs classes de langages standard de la littérature. Nous utilisons ensuite le lien avec les séries génératrices holonomes pour développer des techniques de preuves d'intrinsèque ambiguïté. Nous proposons par ailleurs une preuve d'intrinsèque ambiguïté à la main d'un langage pour lequel les techniques précédentes ne s'appliquent pas. Enfin en exploitant les récurrences satisfaites par les coefficients des séries holonomes, nous produisons des bornes de complexité pour le problème de l'inclusion des automates de Parikh faiblement non ambigus