Le problème de l’inclusion des automates de Parikh faiblement non ambigus

Introduction au problème de l’inclusion

Dans ce chapitre, nous étudions une conséquence algorithmique de la propriété d’holonomie des séries de comptage des automates de Parikh faiblement non ambigus. Le problème de l’inclusion est le problème de décision suivant : entrée : deux automates A et B sortie : est-ce que L(A) ✓ L(B) ? La décidabilité et la complexité de ce problème dépendent des classes d’automates dont sont issus A et B. Si A et B sont des automates « nis, le problème est classiquement décidable, et est PSPACE-complet [MS72]. Si les automates sont non ambigus, le problème est décidable en temps polynomial [SI85], par un argument de comptage que nous allons développer en détail dans cette introduction. Si A et B sont des grammaires hors-contextes, ce problème est indécidable, car l’universalité est déjà indécidable [BHPS61, Theorem 6.2]. Le problème reste indécidable si A et B sont des grammaires déterministes [GG66, Theorem 5.3], et donc a fortiori si les grammaires sont non ambiguës ([AN00] fournit une preuve directe dans le cas non ambigu, par réduction du problème de correspondance de Post). D’autres variantes ont été étudiées, en mélangeant les classes (par exemple si A est une grammaire hors-contexte quelconque, et B un automate « ni, le problème est EXPTIME-complet [KI92]). Une approche simple pour aborder le problème de l’inclusion, d’un point de vue purement automate, consiste à utiliser l’équivalence suivante : L(A) ✓ L(B) , L(A) \ L(B) = ; , où L(B) désigne le complémentaire de L(B). Il su#t pour décider l’inclusion de calculer ce complémentaire, lorsque c’est possible, puis de calculer l’intersection, Le problème de l’inclusion des automates de Parikh faiblement non ambigus 268 8 Le problème de l’inclusion des automates de Parikh faiblement non ambigus et en »n de tester le vide du langage obtenu. Cette approche sou!re du recours à la complémentation : même dans le cas des automates « nis qui sont clos par complémentaire, cette opération a un coût exponentiel ; par ailleurs pour des classes plus compliquées, le calcul du complémentaire n’est pas pas forcément faisable (les langages algébriques (non ambigus) ne sont pas clos par complémentaire [HU66], et nous ne savons pas si les automates de Parikh faiblement non ambigus sont clos par complémentaire). Pour contourner ce problème, dans le cadre des automates « nis non ambigus, Stearns et Hunt [SI85] ont utilisé plutôt l’équivalence suivante : L(A) ✓ L(B) , L(A) \ L(A) \ L(B) = ; . Mathématiquement, il s’agit exactement de la même égalité ; en e!et en utilisant les lois de De Morgan, L(A) \ L(A) \ L(B) = L(A) \ L(B). Cependant, considérer l’intersection L(A) \ L(B) est intéressant car l’inclusion L(A) \ L(B) ✓ L(A) est toujours vraie, avec égalité si et seulement si L(A) ✓ L(B). Par conséquent, pour décider le problème de l’inclusion, il su#t, pour tout n 2 N, de véri »er qu’il y a bien autant de mots de longueur n dans L(A) \ L(B) que de mots de longueur n dans L(A). Comme A et B sont des automates « nis non ambigus, L(A) \ L(B) est reconnu par un automate « ni non ambigu C, obtenu en utilisant la construction produit. Notons A(x) = P n anx n et C(x) = P n cnx n les séries génératrices de L(A) et L(C) = L(A) \ L(B). Le raisonnement par dénombrement de Stearns et Hunt s’écrit sous la forme : L(A) ✓ L(B) , 8n 2 N, an .

 Introduction à l’algorithme de Lipshitz

Comme nous l’avons vu aux chapitres précédents, la propriété principale pour démontrer que la série génératrice d’un automate de Parikh non ambigu est holonome est la stabilité des séries holonomes par diagonale (ou produit d’Hadamard). Il s’agit d’une opération non triviale sur les fonctions holonomes, qui est toujours l’objet de recherche active en calcul formel. La clôture des fonctions holonomes par diagonale a été démontrée par Lipshitz en 1988 [Lip88] ; sa preuve repose sur des séries formelles, et consiste à interpréter la diagonale d’une série comme une extraction de coe#cients. Cette extraction de coe#cients, du point de vue analyse complexe, avec la formule de Cauchy, s’exprime sous la forme d’une intégrale (ou période), ce qui a donné lieu à de nouvelles méthodes de calcul de diagonale, plus récentes et e#caces, fondées sur le télescopage créatif ([Chy14, BCLS18]). Nous nous sommes limités dans cette 270 8 Le problème de l’inclusion des automates de Parikh faiblement non ambigus thèse à l’algorithme historique de Lipshitz [Lip88], qui a l’avantage d’être facile à comprendre et à étudier (mais s’avère peu e#cace en pratique). Pour donner une idée du principe de l’algorithme de Lipshitz, nous illustrons son fonctionnement dans cette introduction, sur un exemple simple. Soit Aex l’automate de Parikh non ambigu suivant : 0 1 C = {(n, n) : n 2 N}.