Calculs avec des grammaires de graphes

Un graphe est un ensemble dénombrable d’arcs étiquetés. Dans ce chapitre, les étiquettes des arcs sont des éléments d’un demi-anneau idempotent et continu. La valeur d’un chemin est le produit de ses étiquettes successives. La valeur d’un graphe (à partir des sommets initiaux aux sommets finaux) est la somme des valeurs de ses chemins d’un sommet initial à un sommet final. Nous voulons calculer les valeurs des graphes engendrés par une grammaire déter- ministe de graphes. On rappelle que nous nous sommes limités à des grammaires pour lesquelles chaque membre gauche est un arc étiqueté du sommet 1 au sommet 2, et il n’y a pas dans les membres droits d’arc sortant de 2, ni d’arc entrant en 1. La valeur de tout arc non-terminal du membre gauche est la valeur de 1 à 2 de son graphe engendré. La valeur d’une grammaire est le vecteur des valeurs de ses membres gauches.En considérant une grammaire comme une fonction de et vers des demi-anneaux (à la puissance du nombre des règles), son application itérée à partir du plus petit élément donne par borne supérieure la valeur de la grammaire (théorème 5).Soit L un ensemble quelconque. Rappellons qu’un L-graphe est un ensemble d’arcs étiquetés dans L.

Plus précisément, un L-graphe G est un sous-ensemble de V ×L×V où V est un ensemble quelconque tel que l’ensemble des sommets de G défini par Rappelons qu’un isomorphisme h d’un graphe G sur un graphe H est une bijection de VG sur VH telle que h(G) = H. De plus, le langage reconnu par G à partir d’un ensemble I de sommets à un ensemble F de sommets est l’ensemble des étiquettes des chemins de I à F : Comme Kp est un ensemble complet pour l’ordre produit dont le plus petit élément est 0 = (0, · · · , 0), nous pouvons appliquer le théorème de Knaster-Tarski [Kn 28, Ta 55] : la borne supérieure de l’application itérée de [Dans le théorème 5, la continuité du demi-anneau est nécessaire pour des gram- maires ayant un circuit. Par exemple, nous considérons le demi-anneau idempotent et complet (IN ∪ {ω, ω}, M ax, ×, 0, 1) dont les opérations M ax et × sont respec- tivement les opérations maximum et multiplication habituelles sur les entiers, et que nous étendons comme suit :]n(0) = ω (la suite croissante est 0 , 1 , ω , ω , . . .). Il est à noter que la première égalité du théorème 5 peut ne pas être vérifiée si l’on permet d’avoir un arc de but 1 ou de source 2 dans un membre droit de la grammaire. Par exemple, en prenant le demi-anneau (2{a,b,c} Nous présentons deux algorithmes généraux pour calculer la valeur d’une gram- maire R pour des demi-anneaux idempotents, continus et commutatifs. Sachant que |R| désigne le nombre de règles, le premier algorithme compare les différences entre le |R|-ième approximant [[ R ] ]|R|(0) avec le suivant pour détecter des aug- mentations (strictement supérieures à 1) dans la valeur des graphes engendrés (cf. théorème 1). Le deuxième algorithme est une simple généralisation de la méthode de Hopkins-Kozen [HK 99] qui a été développée pour les grammaires algébriques (cf. corollaire 7). Bien que le premier algorithme soit plus efficace que le second, il travaille avec des demi-anneaux dont l’ordre est total et il admet un plus grand élément.

Le théorème 5 nécessite des demi-anneaux idempotents et continus. Nos algo- rithmes exigent que ces demi-anneaux soient commutatifs : la multiplication · est commutative. Un cci-demi-anneau est une abréviation pour un demi-anneau idem- potent, continu et commutatif. Cela nous permet de résoudre le problème du plus court chemin sur tout graphe engendré par une grammaire. Nous appliquons l’algorithme de Floyd (sans circuit de coût négatif) sur les graphes finis. Pour toutegrammaire R, nous avons CR en O(ℓ 3 Notons que grâce aux deux transformations de la proposition 2, nous pouvons transformer en temps linéaire toute grammaire de graphes en une grammaire équiv- alente sans circuit. Ensuite, nous pouvons appliquer le théorème 1 avec l’algorithme de Bellman pour le problème du plus court chemin.A partir de tout automate à pile R et en ajoutant des ε-transitions, il est facilede transformer R en un automate à pile R′ reconnaissant le même langage (par états finaux et/ou pile vide) tel que chaque membre droit est un état suivi par au plus deux lettres de pile ; le nombre de règles |R′| et donc sa longueur de description ′ sont en O(ℓR). Puis, nous appliquons à R′ la transformation habituelle pour obtenir une grammaire algébrique équivalent P : |P | et ℓP sont en O(|R′|3). Ainsi, pour tout automate à pile R, le problème du plus court chemin peut être résolu en O(ℓ3).