Systèmes analytiques bien conditionnés, théorème de Drmota
Les systèmes qui nous ont intéressés dans cette thèse ont des propriétés supplémentaires qui assurent entre autres l’unicité de la solution, de la singularité dominante, et un comportement en racine carrée. Le cas analytique est étudié par Drmota dans [Drm97, Drm09] avec des paramètres u que nous n’utiliserons pas, et reformulé (sans paramètre) dans [BBY10] qui précise les conditions du théorème sur les points caractéristiques. Flajolet et Sedgewick donnent une preuve de ce résultat, qu’ils appellent théorème de Drmota-Lalley-Woods, dans le cas polynomial [FS09, p. 489]. Les systèmes étudiés sont appelés bien conditionnés par [BBY10]. Ils véri »ent un ensemble de propriétés que l’on retrouve plus ou moins, sous une forme ou un autre, dans les conditions de [FS09], de [Drm97] ou de [Drm09].
Définition 1.88 ([BBY10]).
I Un système d’équations y = F(z; y) est bien conditionné s’il véri »e les conditions suivantes :
a. chaque Fi est une série entière à coe#cients positifs ;
b. F(z; y) est holomorphe dans un voisinage de l’origine ;
c. F(0; y) = 0;
d. le système n’est pas linéaire ;
e. le graphe de dépendance associé est fortement connexe ;
f. pour tout i, Fi(z, 0) 6= 0.
J La dernière condition est énoncée différemment chez [Drm97, Drm09], qui demandent qu’il existe un i tel que Fi(z, 0) 6= 0. Cette condition est équivalente par forte connexité, dès qu’on peut assurer qu’aucune composante solution ne peut être nulle. Dans plusieurs chapitres nous utiliserons cette version, en remplaçant la condition f. par la condition : f’. il existe i tel que Fi(z, 0) 6= 0, et il existe un vecteur solution y(z) de séries non nulles, dont les coe#cients de Taylor sont positifs. De même, dans [Drm97], la condition de non linéarité semble plus forte, car elle demande l’existence d’un terme au moins carré @2Fi/@y2j6= 0 pour certains indices i et j ; ce n’est pas un problème, car par forte connexité, on peut obtenir un tel terme à partir d’un terme non linéaire, en utilisant les transformations présentées dans [BBY10] (minimal self-substitution). Dans [BBY10], les auteurs ont ajouté une condition (det(I JacyF(0; 0)) 6= 0), qui a été par la suite retirée, dans une version corrigée de l’article sur Arxiv. En »n, dans [Drm97], l’auteur a ajouté la condition Fz(z, y) 6= 0. Ces deux dernières conditions sont en fait impliquées, dans le cas où F n’est pas nul, par la condition F(0; y) = 0 et l’analycité de F en 0 (car F s’écrit alors sous la forme F(z, y) = zK(z, y)). Un travail de nettoyage des conditions des différentes versions du théorème est en cours de réalisation par Carine Pivoteau et Bruno Salvy, que je remercie pour m’avoir éclairé sur le sujet.
Définition des arbres d’expressions sous forme de classe combinatoire et de systèmes
Dans toute cette partie, les arbres considérés sont des arbres planaires étiquetés enracinés, c’est-à-dire qui véri »ent les conditions suivantes :
a. (enracinés) tout nœud possède un unique père, à l’exception d’un seul nœud, appelé racine
b. (planaires) les fils d’un nœud sont ordonnés, si bien que les deux arbres sont distincts
c. (étiquetés) chaque nœud est étiqueté par un symbole.
La taille d’un arbre est son nombre de nœuds. Pour un nœud N d’un arbre planaire enraciné, nous appelons arité de N le nombre de fils du nœud N. Les nœuds d’arité 0 sont classiquement appelés feuilles, les nœuds d’arité 1 sont appelés nœuds unaires, ceux d’arité 2 nœuds binaires. Nous employons le terme arité et non degré comme en théorie des graphes, car pour un arbre, vu comme un graphe, le degré d’un nœud di!érent de la racine est son arité plus un. Nous nous intéressons à des arbres d’expressions qui suivent une syntaxe précise. Les systèmes de séries Les étiquettes des nœuds sont associées à une arité fixe génératrices associées seront donc polynomiaux. Comme nous l’avons expliqué dans l’introduction, nous pourrions vouloir considérer que ^ a une arité non fixée pour modéliser son associativité. Nous sortons du cadre des systèmes polynomiaux dans ce cas, cf le chapitre 3. : par exemple, pour la syntaxe des expressions logiques, l’opérateur ¬ est unaire, tandis que l’opérateur ^ est binaire. Dans la suite de cette section, chaque opérateur aura une seule arité fixée. De façon plus formelle, soit S un ensemble « ni d’éléments appelés opérateurs, et soit a une fonction de S dans N. Pour un symbole d’opérateur s, la valeur a(s) est appelée l’arité de l’opérateur s, et désigne le nombre de « ls qu’un opérateur peut avoir
Conclusion de la partie et discussion sur le cas des expressions régulières
La contribution principale de ce chapitre est de montrer que les arbres d’expressions uniformes décrits par des systèmes manquent d’expressivité, car ils se réduisent considérablement dès qu’un opérateur admet un élément absorbant. Cela remet en question la pertinence de cette distribution pour l’analyse théorique en moyenne et la génération d’arbres d’expressions. Comme nous l’avons déjà mentionné dans le coeur du chapitre, les hypothèses que nous avons données sur les systèmes n’ont pas pour but de caractériser tous les systèmes bien fondés où un tel phénomène de dégénérescence se produit. Nous voulions juste identifier un cadre suffisamment général pour capturer de nombreux exemples, tout en gardant des conditions faciles à vérifier. Discussion sur les hypothèses du chapitre. Nous pouvons ainsi discuter un peu de ce qui se passe si les hypothèses (H) ne sont pas vérifiées. Pour (H1), si le graphe de dépendance n’est pas fortement connexe, nous pouvons considérer le DAG de ses composantes fortement connexes ; s’il n’y a qu’une seule composante fortement connexe finale, ou s’il n’y a qu’une seule composante dominante, qui produit exponentiellement plus d’expressions que les autres composantes, on devrait pouvoir se réduire à notre cadre en analysant ce qui se passe dans cette composante principale. Si G⇤ est cyclique, alors le système soit n’est pas bien fondé, soit il est possible de retirer certains cycles. Pour (H2), nous pouvons essayer de traiter séparément les tailles modulo la période. Cela se produit notamment lorsque tous les opérateurs sont binaires (dans ce cas, la taille des arbres est nécessairement impaire). Pour (H3), on pourrait affaiblir cette condition, mais elle est là essentiellement pour garantir que le système n’est pas capable d’empêcher l’élément absorbant d’apparaître un grand nombre de fois sous son opérateur, ni de limiter la taille des arbres réduits par la règle d’absorbance. Pour (H4), si le système est linéaire, les arbres sont filiformes, et l’analyse est complètement différente, bien que sans doute plus facile. Nous ne nous sommes pas intéressés au cas linéaire car nous n’avions pas d’exemples concrets suffisamment motivés. Si (H5) n’est pas vérifiée, nous avons déjà expliqué en note de marge que le résultat restait valide si la spécification était finiment ambiguë. Si la spécification est infiniment ambiguë, les séries génératrices déduites du système ne représentent pas bien la combinatoire de l’ensemble d’arbres d’expressions étudié, si bien qu’il est nécessaire de chercher une spécification non ambiguë du problème.
Comparaison avec les automates de Parikh non ambigus
La condition de non-ambiguïté que nous avons introduite pour les automates de Parikh est standard : tout mot est accepté par au plus un calcul acceptant. Si tout le monde semble s’accorder sur cette formulation de la non-ambiguïté, il y a une imprécision sur ce qu’on appelle un calcul acceptant pour les automates de Parikh. Dans cette thèse, un calcul acceptant est un calcul qui accepte un mot du langage, autrement dit une preuve de l’appartenance d’un mot au langage de Parikh : il s’agit donc d’un chemin de l’automate, partant d’un état initial jusqu’à un état final, et étiqueté par un vecteur appartenant au semilinéaire C. Il existe dans la littérature une autre notion de non-ambiguïté pour les automates de Parikh, pour laquelle un calcul acceptant est simplement un calcul joignant un état initial à un état final, indépendamment du vecteur qui l’étiquette. Avec cette définition, un calcul acceptant peut donc être étiqueté par un mot qui n’est pas dans le langage accepté par l’automate. Cette classe d’automates est appelée dans la littérature automates de Parikh non ambigus. Un automate de Parikh est non ambigu si pour tout mot w, il existe un seul calcul joignant un état initial à un état final étiqueté par w : autrement dit l’automate fini obtenu en effaçant les vecteurs est non ambigu. Il s’agit d’une contrainte assez forte, et tout automate de Parikh non ambigu est faiblement non ambigu (l’inclusion est stricte, voir Proposition 6.11). Les automates de Parikh non ambigus ont été introduits et étudiés par Cadilhac et al. dans [CFM13]. Pour être exact, il s’agissait d’une variante équivalente aux automates de Parikh, appelée Unambiguous Constrained Automata. Dans les discussions de sa thèse, Cadilhac propose une dé »nition équivalente à cette classe dans le modèle des automates de Parikh, qu’il appelle automates de Parikh non ambigus. Ces restrictions fortes dans la définition des automates de Parikh sont contrebalancées par la stabilité remarquable de la classe sous de nombreuses opérations, dont les opérations booléennes (union, intersection, complémentaire) et les quotients à gauche et à droite. Cette stabilité s’explique par leur équivalence avec des modèles déterministes de machines (dans [CFM13], les auteurs montrent l’équivalence de la classe avec un modèle déterministe d’automate à registre, et plus récemment les auteurs de [FGM19] ont montré l’équivalence avec un modèle d’automates de Parikh déterministe two-way).
|
Table des matières
Introduction générale à la thèse
1 Chapitre préliminaire
1.1 Préliminaires pour les langages formels
1.1.1 Langages réguliers
1.1.2 Langages algébriques
1.1.3 Ensembles semilinéaires
1.2 Préliminaires de combinatoire analytique
1.2.1 Série formelle, série génératrice
1.2.2 Série rationnelle, série algébrique, série holonome
1.2.3 Classes combinatoires
1.2.4 Paramètre combinatoire, moments
1.2.5 Paramètre hérité
1.2.6 Singularités et Théorème de Transfert
1.3 Préliminaires sur les systèmes de séries et le théorème de Drmota
1.3.1 Systèmes polynomiaux
1.3.2 Systèmes analytiques bien conditionnés, théorème de Drmota
I Réductions d’arbres d’expressions en présence d’un élément absorbant
Introduction à la partie
2 Réduction d’expressions spécifiées par un système
2.1 Introduction
2.2 Système combinatoire d’arbres
2.2.1 Définition des arbres d’expressions sous forme de classe combinatoire et de systèmes
2.2.2 Exemples de systèmes
2.2.3 Traduction en système de séries génératrices
2.2.4 Systèmes mal fondés et cas pathologiques
2.3 Formalisme, hypothèses de travail et simplifications
2.3.1 Élément absorbant
2.3.2 Systèmes propres
2.4 Résultat principal
2.4.1 Analyse du dénominateur
2.4.2 Analyse du numérateur
2.4.3 Preuve du théorème principal
2.5 Preuve des propositions techniques
2.5.1 Preuve de la Proposition 2.35
2.5.2 Compléments techniques sur le théorème de Drmota
2.5.3 Preuve de la Proposition 2.36
2.6 Moments d’ordres supérieurs et temps d’exécution moyen des algorithmes polynomiaux
2.7 Conclusion de la partie et discussion sur le cas des expressions régulières
3 Réduction d’expressions spécifiées par une seule équation
3.1 Introduction
3.2 Contexte et restrictions
3.2.1 Arbres d’expressions
3.2.2 Élément absorbant et réduction
3.2.3 Le schéma d’inversion lisse
3.2.4 Comportement asymptotique du nombre d’arbres dans L .
3.3 Étude de la réduction
3.3.1 La classe des entièrement réductibles
3.3.2 Série bivariée et espérance de la taille après réduction
3.3.3 Convergence des moments d’ordre supérieur
3.4 Conclusion et expérimentation sur les langages réguliers
4 Détection heuristique de sous-arbres universels pour les expressions régulières uniformes
4.1 Introduction
4.2 Modèle et définitions
4.2.1 Dé »nitions
4.2.2 Le nouvel algorithme de simplification
4.2.3 Série génératrice associée à la réduction
4.3 Caractérisation analytique de la limite
4.3.1 Système combinatoire induit par la réduction
4.3.2 Séries génératrices et probabilité d’être entièrement réductible
4.3.3 Système bivarié et spécification de la réduction
4.4 Calcul pratique de la limite et analyse numérique
4.4.1 Forme triangulaire du système (calcul de y(⇢))
4.4.2 Vecteur propre associé aux probabilités limites
4.4.3 Réduction de la taille du système et calcul de la taille réduite
4.5 Conclusion
5 Éléments absorbants et expressions suivant la distribution ABR
5.1 Introduction
5.2 Modèle, définitions et probabilité des entièrement réductibles
5.2.1 Le modèle des expressions ABR
5.2.2 Élément absorbant et restriction technique
5.2.3 Récurrences pour l’espérance de la taille après réduction
5.2.4 Feuille de route pour l’étude de la réduction
5.3 Étude des arbres entièrement réductibles
5.3.1 Série génératrice et équation de Riccati
5.3.2 Comportements asymptotiques des probabilités des arbres entièrement réductibles
5.4 Résultat principal : tailles moyennes des arbres après réduction
5.4.1 Forme close pour la série E(z)
5.4.2 Comportement local de E(z) en z = 1 : angle d’attaque et intégration singulière
5.4.3 Étude de K(z)
5.4.4 Étude de J(z)
5.4.5 Preuve du théorème principal
5.5 Le cas binaire pI = 0
5.5.1 Étude rapide de A(z)
5.5.2 Étude rapide de E(z) et asymptotiques des tailles réduites
5.6 Conclusion
II Automates de Parikh faiblement non ambigus
Introduction à la partie
6 Modèles de machines à compteurs non ambiguës
6.1 Introduction
6.2 Automates de Parikh faiblement non ambigus
6.2.1 Automate de Parikh, calcul acceptant, faible non-ambiguïté
6.2.2 Quelques propriétés de clôture
6.2.3 Comparaison avec les automates de Parikh non ambigus
6.3 Modèles non ambigus équivalents aux automates de Parikh faiblement non ambigus
6.3.1 Rappels et notations sur les calculs d’un automate de Parikh
6.3.2 Automates de Parikh généralisés faiblement non ambigus
6.3.3 Automates de Parikh faiblement non ambigus avec « -transitions
6.3.4 RBCM non ambiguës
6.3.5 La classe RCM
6.4 Automates de Parikh à pile faiblement non ambigus et modèles équivalents
6.4.1 Définition, propriétés de clôture
6.4.2 Élimination des « -transitions
6.4.3 Équivalence avec les RBCM à pile unidirectionnelles non ambiguës
6.4.4 Équivalence avec la classe LCM
6.5 Preuve de l’élimination des fi-transitions dans un automate de Parikh à pile faiblement non ambigu
6.5.1 Plan de la preuve
6.5.2 Grammaires hors-contexte contraintes
6.5.3 Élimination des règles déplacement
6.5.4 Élimination des règles unité
6.5.5 Mise sous forme normale de Greibach
6.5.6 Élimination des fi-transitions
6.6 Conclusion et ouverture
7 Intrinsèque ambiguïté et séries génératrices
7.1 Introduction : intrinsèque ambiguïté des langages algébriques
7.1.1 Preuves d’intrinsèque ambiguïté par des arguments d’itération
7.1.2 Preuves d’intrinsèque ambiguïté par argument analytique : la méthode de Flajolet
7.1.3 Deux nouveaux critères d’intrinsèque ambiguïté portant sur des séries génératrices rationnelles
7.1.4 Plan du chapitre
7.2 Langages algébriques de Parikh faiblement non ambigus et séries holonomes
7.2.1 Stabilité des séries holonomes
7.2.2 Analogue du théorème de Chomsky-Schützenberger pour les automates de Parikh (à pile) faiblement non ambigus
7.3 Intrinsèque faible ambiguïté
7.3.1 Premiers exemples de langages intrinsèquement faiblement ambigus
7.3.2 Vers un argument d’itération pour montrer l’intrinsèque faible ambiguïté d’un langage de Parikh
7.3.3 Problèmes de décision liés à l’intrinsèque faible ambiguïté
7.4 Ouvertures
7.4.1 Sur l’intrinsèque ambiguïté des langages algébriques bornés
7.4.2 Séries N-rationnelles, séries N-algébriques, lien avec l’ambiguïté des langages algébriques
7.4.3 Ouverture sur l’in »nie ambiguïté des langages algébriques
7.4.4 Diagonale de série N-rationnelle ou N-algébrique : lien avec les langages (algébriques) de Parikh faiblement non ambigus
7.4.5 Tentatives échouées d’extensions
7.5 Conclusion
8 Le problème de l’inclusion des automates de Parikh faiblement non ambigus
8.1 Introduction
8.1.1 Introduction au problème de l’inclusion
8.1.2 Introduction à l’algorithme de Lipshitz
8.1.3 Cadre de travail, notations, et plan du chapitre
8.2 Séries génératrices rationnelles associées à un automate de Parikh
8.2.1 Notations, bornes sur les déterminants, règle de Cramer
8.2.2 Séries génératrices des calculs de l’automate et du semilinéaire
8.3 Série génératrice d’un automate de Parikh faiblement non ambigu
8.3.1 Préparation de la série génératrice à l’algorithme de Lipshitz
8.3.2 Équation di!érentielle satisfaite par F
8.3.3 Équation di!érentielle satisfaite par un langage de Parikh faiblement non ambigu
8.4 Le problème de l’inclusion des automates de Parikh faiblement non ambigus
8.4.1 Bornes sur les équations di!érentielles
8.4.2 Bornes sur la récurrence et témoin de non inclusion
8.4.3 Borne de complexité du problème de l’inclusion
8.5 Conclusion, et ouverture
Conclusion
Bibliographie
Télécharger le rapport complet
