Systems of holonomic functions : application in automata theory

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 ambigusThis thesis is structured around two independent parts, which are dealing with different subjects, but can be unified by the methodology used to study them: in both parts we rely mainly on mathematical tools specialized in the study of generating series systems.In the first part, we are interested in trees with nodes labelled by operators that represent expressions with semantics. For example, regular expressions represent languages, logical expressions represent boolean functions, etc. We assume that there is an operator (*) associated to an absorbing element P, such that any tree having (*) as a root and P as one of its children is equivalent to P (for example, 0 is absorbing for x, (a+b)* is absorbing for + on a two-letter language, etc). From this absorbing pattern, we define a reduction function σ that reduces a random expression with n nodes, by recursively simplifying bottom-up all occurrences of the element P under the operator (*). This reduction preserves the semantics of the tree, by definition of an absorbing element. The first part of this thesis studies the average size of the reduction of a random tree of size n, when n tends to infinity. In the first two chapters, we focus on uniform expression trees described by a combinatorial system, and a one-dimensional recursive equation respectively. We show that the uniform distribution is degenerated for these expression trees when there is an absorbing pattern: the average size after reduction tends to a constant when n tends to infinity. This result questions the usefulness of uniform random expressions in the average complexity analysis of algorithms, as well as their relevance for automated performance tests (such as benchmarks). We then refine the previous result in the case of regular expressions, using more language-specific simplification rules. Finally, we investigate the average behaviour of the reduction over another distribution, the BST-like distribution. We show that the average size after reduction depends on the probability of appearance of the absorbing operator, and we exhibit two different thresholds in the typical average reduction size, when this parameter varies from 0 to 1.The second part studies the link between formal languages and the properties of their generating series. In particular, we are interested in the notion of unambiguity of some classes of counter automata. Intuitively, an automaton is unambiguous if any word is accepted by at most one single accepting run. Unambiguity makes it possible to link by a one-to-one correspondance the runs of the automaton, which follow a combinatorial specification described by the transitions of the automaton, to the words of the language accepted by the automaton. This correspondance can be used then to translate the particular structure of the automaton into a system of equations over the generating series associated to the automaton. In this second part, we study the link between different equivalent classes of unambiguous counter automata, including weakly unambiguous Parikh automata, and the class of holonomic generating series. We start by introducing the notion of unambiguity for these classes of automata, by relating them with several classes of classical automate in the literature. We then use the link with holonomic generating series to develop techniques for proving inherent ambiguity. We also prove by hand the inherent ambiguity of a language for which the previous techniques do not apply. Finally, by analyzing the recurrences satisfied by the coefficients of holonomic series, we give complexity bounds for the inclusion problem for weakly unambiguous Parikh automat