Soutenance de thèse de BENALIOUA Yahia Idriss

Résumé de la thèse

La théorie des automates est un domaine fondamental de l'informatique aux applications diverses, allant de la vérification formelle à la recherche de motifs, l'analyse syntaxique, la conception de compilateurs et d'interpréteurs, parmi bien d'autres. Elle étudie les propriétés des modèles de calcul et leurs problèmes associés. Au fil des années, plusieurs variantes de son objet élémentaire, l'automate fini, ont vu le jour, enrichissant ses capacités.
Les automates pondérés (Weighted Automata ou WA) étendent les automates finis en attribuant une valeur à chaque transition prise dans un semi-anneau donné (entiers, rationnels, mots, etc.). Elles peuvent modéliser le coût de la transition, la quantité de ressources utilisées, sa probabilité de succès, etc., selon le semi-anneau. Ils réalisent des fonctions des mots vers le semi-anneau, appelées séries rationnelles, permettant d'étudier des propriétés quantitatives allant au-delà de la simple réponse oui/non des automates finis.
Alors que les WA requièrent du non-déterminisme pour réaliser ces fonctions, un modèle plus récent, l'automate à registres de coût (Cost Register Automata ou CRA), permet de réaliser les séries rationnelles de manière déterministe. Un CRA est un automate déterministe doté d'un nombre fini de registres stockant des valeurs du semi-anneau. Ces registres sont mis à jour à chaque transition à l'aide d'expressions spécifiant comment chaque registre doit être actualisé en fonction de leurs valeurs précédentes et comment les combiner pour produire la sortie finale.
Les problèmes centraux de cette thèse concernent la minimisation des CRA. D'un point de vue pratique, nous cherchons à minimiser la mémoire utilisée par la machine, afin d'obtenir des algorithmes plus efficaces. D'un point de vue théorique, ces questions sont étroitement liées à des problèmes classiques en théorie des automates. Nous abordons ces questions à l'aide de méthodes algébriques dans trois contextes différents.
Premièrement, nous considérons les WA prenant des valeurs dans un corps (tel que les nombres rationnels). Dans ce cas, des résultats classiques montrent l'existence d'un WA minimal réalisant une série donnée. En utilisant les invariants de cet automate minimal, nous caractérisons les conditions sous lesquelles une série rationnelle peut être réalisée par un CRA avec un nombre donné d'états et de registres. Nous déduisons de cette caractérisation des algorithmes pour la minimisation des CRA et analysons leur complexité.
Deuxièmement, nous généralisons le cas précédent aux automates dont les entrées sont spécifiées par des arbres étiquetés au lieu de simples mots (tandis que les valeurs sont toujours prises dans un corps). Malgré cette structure plus riche, plusieurs propriétés des WA ont été généralisées aux automates d'arbres pondérés, et nous pouvons transposer la plupart des résultats obtenus dans le contexte précédent à celui-ci. Nous soulignons également les similitudes et les différences entre les deux contextes et établissons des liens entre les questions non encore résolues et d'autres problèmes ouverts intéressants.
Troisièmement, lorsque les poids des transitions sont des mots, de tels WA sont appelés transducteurs. Ils peuvent être vus comme des “traducteurs” entre langages, les fonctions qu'ils réalisent sont appelées transductions rationnelles, et leur modèle de CRA correspondant, stockant des mots dans ses registres, est appelé transducteur à registres (Streaming String Transducers ou SST). Les transductions rationnelles admettent une caractérisation algébrique fournissant une représentation canonique de la fonction à l'aide d'un modèle appelé bimachine. Nous décrivons une correspondance entre les bimachines et une classe restreinte de SST et utilisons les résultats classiques de minimisation des bimachines pour minimiser ces SST. Nous introduisons également un modèle de bimachine modifié afin d'obtenir une correspondance complète et discutons sa minimisation.