Ce document est le résumé en français de l’article (Lopez 2024) qui est disponible
sur arXiv, dont le pdf, des slides de présentation, ainsi que le fichier
bibtex associé sont disponibles sur ma page web.
Résumé
Cet article étudie quelles fonctions calculées par des automates pondérés à poids dans \(\mathbb{Z}\) peuvent être réalisées par des automates pondérés à poids dans \(\mathbb{N}\), sous deux hypothèses supplémentaires : la commutativité (l’ordre des lettres dans l’entrée n’a pas d’importance) et la croissance polynomiale (la sortie de la fonction est bornée par un polynôme en la taille de l’entrée). J’utilise cette caractérisation effective pour décider si une fonction calculée par un automate pondéré à poids dans \(\mathbb{N}\) commutatif de croissance polynomiale est sans étoile, une notion importée de la théorie des langages réguliers qui a fait l’objet de nombreuses investigations dans le contexte des fonctions mot-vers-mot au cours de la dernière décennie.
Contextualisation
Ce travail s’inscrit à l’intersection de deux domaines de recherche en théorie des automates. D’une part, la généralisation du modèle qualitatif classique des automates finis non-déterministes à un modèle quantitatif où les transitions sont étiquetées par des éléments d’un semi-anneau \(\mathbb{S}\) (automates pondérés), et de l’autre la généralisation des langages rationnels à des fonctions des mots vers les mots (transductions). Ces deux généralisations en général incomparables, sauf dans le cas où le semi-anneau de l’automate pondéré est \(\mathbb{N}\), et où les fonctions calculées ont un alphabet de sortie unaire, auquel cas l’isomorphisme \((\mathbb{N},+) \simeq (\{1\}^*, \cdot)\) permet de faire le lien entre ces deux modèles. Commençons par rappeler quelques définitions pour comprendre le contexte de ce travail.
Les automates pondérés sont une généralisation des automates finis non-déterministes où les transitions sont étiquetées par des éléments d’un semi-anneau \(\mathbb{S}\), par exemple \(\mathbb{N}\) ou \(\mathbb{Z}\). Les fonctions calculées par ces automates sont appelées séries rationnelles et sont une généralisation des langages rationnels (Berstel and Reutenauer 2010). Les séries rationnelles à valeurs dans \(\mathbb{N}\) (\(\mathbb{N}\mathsf{Rat}\)) sont un sous-ensemble des séries rationnelles à valeurs dans \(\mathbb{Z}\) (\(\mathbb{Z}\mathsf{Rat}\)), et un problème ouvert est de décider si une série rationnelle dans \(\mathbb{Z}\mathsf{Rat}\) est dans \(\mathbb{N}\mathsf{Rat}\) (Karhumäki 1977).
Ce problème a fait l’objet de nouvelles investigations dans le contexte des fonctions polyrégulières (\(\mathsf{Poly}\)), un modèle de clacul qui vise à généraliser la théorie des langages réguliers au cadre des fonctions mot-vers-mot (Bojańczyk 2018). Dans le cas des langages réguliers, les langages sans étoile forment une sous-classe robuste des langages réguliers décrits équivalents en termes de logique du premier ordre (McNaughton and Papert 1971), d’automates sans compteurs (McNaughton and Papert 1971), ou de monoïdes apériodiques (Schützenberger 1965). De manière analogique, il existe un fragment sans étoile des fonctions polyrégulières appelé fonctions polyrégulières sans étoile (\(\mathsf{SF}\)) (Bojańczyk 2018). Un problème ouvert dans ce domaine est de décider si une fonction polyrégulière est sans étoile.
Pour aborder les problèmes de décision sur les fonctions polyrégulières, il a été fructueux de restreindre l’alphabet de sortie à une seule lettre Douéneau-Tabot (2022). Parce que les mots sur un alphabet unaire sont canoniquement identifiés avec les nombres naturels, les fonctions polyrégulières à sortie unaire sont souvent appelées fonctions \(\mathbb{N}\)-polyrégulières (\(\mathbb{N}\mathsf{Poly}\)), et leur contrepartie sans étoile \(\mathbb{N}\)-polyrégulière (\(\mathbb{N}\mathsf{SF}\)). Or, il se trouve que les fonctions polyrégulières avec sortie unaire forment une sous-classe des séries \(\mathbb{N}\)-rationnelles, à savoir la classe des séries \(\mathbb{N}\)-rationnelles avec une croissance polynomiale, c’est-à-dire que la sortie de la fonction est bornée par un polynôme en la taille de l’entrée. Dans mes travaux avec Colcombet et Douéneau-Tabot (Colcombet, Douéneau-Tabot, and Lopez 2023), j’ai introduit avec mes co-auteurs la classe des fonctions \(\mathbb{Z}\)-polyrégulières (\(\mathbb{Z}\mathsf{Poly}\)), qui est une généralisation des fonctions \(\mathbb{N}\)-polyrégulières autorisant des sorties négatives, et montré que l’appartenance à la sous-classe sans étoile \(\mathbb{Z}\mathsf{SF}\) de \(\mathbb{Z}\mathsf{Poly}\) est décidable (Colcombet, Douéneau-Tabot, and Lopez 2023, Theorem V.8). Bien que cela ne permettait pas décider \(\mathbb{N}\mathsf{SF}\) au sein de \(\mathbb{N}\mathsf{Poly}\), il a été conjecturé que \(\mathbb{N}\mathsf{Poly}\cap \mathbb{Z}\mathsf{SF}= \mathbb{N}\mathsf{SF}\) (Douéneau-Tabot 2023, Conjecture 7.61). Ainsi, il semblerait que comprendre le problème de l’appartenance de \(\mathbb{N}\mathsf{Poly}\) dans \(\mathbb{Z}\mathsf{Poly}\), c’est-à-dire une version restreinte du problème équivalent pour les séries rationnelles, serait une étape clé pour prouver \(\mathbb{N}\mathsf{Poly}\cap \mathbb{Z}\mathsf{SF}= \mathbb{N}\mathsf{SF}\), ce qui donnerait espoir pour la conception d’un algorithme pour le problème de décision sur les fonctions sans étoile.
Contributions de l’article
Dans cet article, je travaille avec une condition supplémentaire, la commutativité de l’entrée, c’est-à-dire que la fonction est invariante par permutation des lettres du mot en entrée. Sous cette hypothèse, je prouve que \(\mathbb{N}\mathsf{Poly}\cap \mathbb{Z}\mathsf{SF}= \mathbb{N}\mathsf{SF}\), comme conjecturé dans le cas général. J’ai également conçu un algorithme qui décide (sous la même hypothèse de commutativité) si une fonction dans \(\mathbb{Z}\mathsf{Poly}\) est dans \(\mathbb{N}\mathsf{Poly}\), ce qui était un problème ouvert (Douéneau-Tabot 2023, Open question 5.55). Au vu de la correspondance entre les fonctions \(\mathbb{Z}\)-rationnelles de croissance polynomiale et les fonctions \(\mathbb{Z}\)-polyrégulières (Colcombet, Douéneau-Tabot, and Lopez 2023), cela peut être vu comme un algorithme pour le problème de décision de \(\mathbb{N}\mathsf{Rat}\) au sein de \(\mathbb{Z}\mathsf{Rat}\), sous la double hypothèse de commutativité et de croissance polynomiale.
Une première étape de mon travail a été de caractériser complètement les polynômes multivariés à coefficients dans \(\mathbb{Q}\) qui sont calculables par des séries \(\mathbb{N}\)-rationnelles (resp. \(\mathbb{Z}\)-rationnelles). Cette caractérisation a permis de mettre en lumière une erreur dans une caractérisation précédente de ces polynômes (Karhumäki 1977, Théorème 3.3, page 4). J’ai également démontré que ce précédent résultat est correct lorsque les polynômes possèdent deux indéterminées ou moins, expliquant pourquoi cette erreur est passée si longtemps inaperçue. En plus de proposer des caractérisations décidables de ces classes polynômes, cela met en exergue la combinatoire intrinsèque des fonctions dans \(\mathbb{N}\mathsf{Poly}\) (resp. \(\mathbb{Z}\mathsf{Poly}\)) en les décrivant comme des combinaisons de coefficients binomiaux. En particulier, les phénomènes observables de division (comme calculer la fonction \(n \mapsto n(n-1)/2\)) et de soustraction (comme calculer la fonction \(n \mapsto n^2 - n + 1\)) dans certaines fonctions de \(\mathbb{N}\mathsf{Poly}\) n’existent qu’à cause de l’écriture des polynômes dans une base inadaptée (la base naturelle \(X^2\), \(X\), \(1\)) au lieu d’une base utilisant des coefficients binomiaux translatés, de la forme \(\binom{X - k}{i}\). Cela permet par ailleurs de conclure que les polynômes exprimables par des fonctions \(\mathbb{Z}\)-rationelles (resp. \(\mathbb{N}\)-rationnelles) sont exactement ceux exprimables par des fonctions \(\mathbb{Z}\)-polyrégulières (resp. \(\mathbb{N}\)-polyrégulières) sans étoile, confirmant l’intuition selon laquelle les polynômes sont des fonctions intrinsèquement sans étoile.
Au cours de cette étude, j’ai développé les méthodes de Douéneau-Tabot basées sur l’idée de pompage quantitatif de fonctions, qui joue un rôle analogue à celui du lemme classique de pompage pour les langages réguliers et les langages algébriques. Si un lemme de pompage classique s’écrit typiquement comme une équivalence de la forme \(\forall n \in \mathbb{N}. u v^n w \in L \iff u v w \in L\), où \(L\) est un langage, un lemme de pompage quantitatif décrit la régularité d’une fonction \(f \colon \Sigma^* \to \mathbb{Q}\) lorsqu’appliquée à des mots de la forme \(u v^X w\), ainsi, \(f(u v^X w)\) devient une fonction de \(\mathbb{N}\) vers \(\mathbb{Q}\), qu’il est possible d’étudier avec des outils classiques d’analyse fonctionnelle. Ainsi, on pourra dire que \(f(u v^X w)\) est une fonction croissante, est un polynôme en \(X\), ou est bornée par un polynôme en \(X\). Je conjecture que les propriétés d’une fonction polyrégulière \(f\) s’observent directement à travers une légère généralisation de la notion de pompage : au lieu de considérer un motif de la forme \(u v^X w\), on peut considérer une fonction polyrégulière sans étoile et commutative \(p\) et observer \(f \circ p\). Plus précisément je conjecture que :
- Une fonction \(\mathbb{Z}\)-polyrégulière \(f\) est une fonction \(\mathbb{N}\)-polyrégulière si et seulement si pour toute fonction polyrégulière sans étoile et commutative \(p\), \(f \circ p\) est \(\mathbb{N}\)-polyrégulière.
- Une fonction \(\mathbb{N}\)-polyrégulière \(f\) est une fonction \(\mathbb{N}\)-polyrégulière sans étoile, si et seulement si pour toute fonction polyrégulière sans étoile et commutative \(p\), \(f \circ p\) est sans étoile.
Si ces conjectures sont vérifiées, alors le problème de décision d’appartenance à \(\mathbb{N}\mathsf{SF}\) au sein de \(\mathbb{N}\mathsf{Poly}\) et celui de l’appartenance à \(\mathbb{N}\mathsf{Poly}\) au sein de \(\mathbb{Z}\mathsf{Poly}\) sont tous deux décidables. En effet, un semi algorithme consiste à deviner une fonction dans la bonne classe (\(\mathbb{N}\mathsf{SF}\) ou \(\mathbb{N}\mathsf{Poly}\)) puis tester l’équivalence, ce qui est possible pour ces fonctions. Un second semi algorithme consiste à deviner une fonction \(p\) commutative polyrégulière et sans étoile, servant de contre exemple puis de vérifier si \(f \circ p\) appartient à la classe en question. Cette dernière étape de vérification est rendue possible grâce aux résultats obtenus sur les fonctions commutatives, ce qui est le cas de \(f \circ p\), puisque \(p\) est commutative.
Conclusion
Dans ce travail, je corrige une erreur de plus de 40 ans et je propose une approche nouvelle et prometteuse pour répondre à deux questions ouvertes sur les fonctions polyrégulières et les séries rationnelles.