Combinatoire analytique des langages réguliers et algébriques
Institution:
Paris 13Disciplines:
Directors:
Abstract EN:
Analytic combinatorics is concerned with the study of combinatorial structures based on their generating functions, and also the efficient random generation of these structures using the Boltzmann method. The aim of this thesis is to analyze combinatorial structures generated by rational and algebraic grammars through a systematic study of the associated generating functions. The first part is dedicated to the study of the limit distributions of patterns in words generated by automata (rational grammars) and associated generating functions ℕrat: The resulting distribution is Gaussian when the automaton is strongly connected. We illustrate this phenomenon for the model of urban segregation due to the economist Schelling. We then give the first major result of this thesis: when the automaton is not strongly connected, it exhibits a wide variety of possible distributions. Then, we use these distributions for uniform random generation with two parameters (bivariate Boltzmann) and to "reverse engineer" certain empirical distributions arising in biology. The second part is dedicated to the asymptotic behavior generating functions ℕalg defined using algebraic grammars. According to the theorem of Drmota, Lalley, and Woods, these series have a square root behavior in their dominant singularity when the associated grammar is strongly connected. The second major result of this thesis characterizes all possible behaviors when the grammar is not strongly connected (these behaviors are related to dyadic numbers; we illustrate this fact constructively using grammars that generate multicolored trees). Then, we give some closure properties for the radius of convergence of these generating functions. Through these new characterizations, we can establish that various combinatorial objects, such as families of planar maps and random walks, cannot be generated by non-ambiguous algebraic grammars. The last part is dedicated to the random generation of combinatorial objects using an extension of the Boltzmann method in order to generate infinite objects, such as Galton–Watson trees with extinction probability p less than ½.
Abstract FR:
La combinatoire analytique permet l’étude des structures combinatoires via leur séries génératrices, et aussi la génération aléatoire de ces structures de façon efficace via la méthode de Boltzmann. Cette thèse vise à analyser des structures combinatoires engendrées par des grammaires rationnelles et algébriques, via une étude systématique des séries génératrices associées. La première partie est dédiée à l’étude des distributions limites des motifs dans des mots engendrés par des Automates (grammaires rationnelles), et des séries génératrices ℕrat associées. La distribution est gaussienne lorsque l’automate est fortement connexe. Nous illustrons ce phénomène pour le modèle de ségrégation urbaine dû à l’économiste Schelling. Nous donnons, par la suite, le premier résultat majeur de cette thèse : lorsque l’automate est non fortement connexe, nous exhibons la très grande diversité des distributions alors possibles. On utilise, par la suite, ces distributions pour la génération aléatoire uniforme selon deux paramètres (Boltzmann bivariées), ainsi que pour faire de “l’ingénierie inverse” sur des distributions empiriques issues de la biologie. La deuxième partie est dédiée aux comportements asymptotiques des séries génératrices ℕalg définies à partir des grammaires algébriques. D’après le théorème de Drmota, Lalley et Woods, ces séries ont un comportement en racine carrée en leur singularité dominante dès lors que la grammaire associée est fortement connexe et non-linéaire. Le deuxième résultat majeur de cette thèse caractérise l’ensemble des comportements lorsque la grammaire n’est pas fortement connexe (ces comportements sont liés aux nombres dyadiques, nous les illustrons de manière constructive via des grammaires qui engendrent des arbres multicolores). Puis, nous donnons quelques propriétés de clôture concernant les rayons de convergence de telles séries. Grâce à ces nouvelles caractérisations, nous pouvons établir que différents objets combinatoires tels que, des familles de cartes planaires et de marches aléatoires, ne sont pas engendrables par des grammaires non ambigües. La dernière partie est dédiée à la génération aléatoire d’objets combinatoires via la méthode de Boltzmann, en l’étendant pour pouvoir générer des objets infinis comme par exemple les arbres de Galton–Watson lorsque la probabilité d’extinction p est inférieure à ½.