Jeudi 23 octobre 2025, 14:00 à 15:00

salle de séminaire du département d'informatique

Quentin Aristote

(IRIF, Université Paris cité)

On étudie les automates pondérés dans un anneau de nombres, c'est-à-dire un anneau d'entiers dans un corps algébrique.

On montre que les anneaux de nombre sont ce qu'on appelle « presque fortement Fatou » : si un automate à n états pondéré dans un corps algébrique reconnaît une série à valeurs entières, alors il admet un automate équivalent à n+1 états pondéré dans l'anneau d'entiers correspondant.

On donne une procédure en temps polynomial pour calculer un tel automate à n+1 états pondéré par des entiers, et on montre que décider si cet automate est minimal parmi tous les automates équivalents pondérés avec des entiers est aussi difficile que le PIP, un problème sur lequel se basent certains protocoles cryptographiques et pour lequel le meilleur algorithme connu est en temps polynomial quantique.

Cette procédure fournit une réduction entre les problèmes d'apprentissage pour les automates pondérés dans un anneau de nombres et ceux pondérés dans un corps, et on montre qu'il s'agit d'un cas particulier d'une réduction plus générale entre les problèmes d'apprentissage pour les automates dans deux catégories liées par un foncteur avec de bonnes propriétés.