Un prix à la conférence ICALP pour Charles Paperman et ses travaux sur les problèmes de mots dynamiques
Charles Paperman du Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL - CNRS/Université de Lille/Centrale Lille) et ses deux co-auteurs, Antoine Amarilli et Louis Jachiet de Télécom Paris, ont été primés lors de la conférence ICALP, spécialisée dans l’informatique fondamentale. Leurs travaux, qui ont reçu le Best Paper Award, étudient le problème du mot dynamique, où on analyse le coût de maintenir une contrainte donnée sous la forme d’une expression régulière, lorsqu’un mot est mis à jour dynamiquement.
Grâce à des approches algébriques, Charles Paperman explore la difficulté et la complexité intrinsèques des problèmes algorithmiques. Cet expert en informatique fondamentale, maître de conférences à l’Université de Lille et membre du laboratoire CRIStAL, traite en particulier des problèmes de complexité liés à la théorie des automates. « Ce sont des questions théoriques étudiées depuis longtemps, détaille Charles Paperman, et plusieurs problèmes restent encore ouverts. »
Avec Antoine Amarilli et Louis Jachiet, tous deux maîtres de conférences à Télécom Paris, Charles Paperman a obtenu un des deux Best Paper Awards de la conférence ICALP1 2021 pour l’article Dynamic membership for regular languages. Soutenue par l’EATCS2 , l’ICALP est la principale conférence européenne en informatique fondamentale, et compte parmi les plus visibles du monde.
L’article primé se concentre sur les problèmes de mots dynamiques. On y fixe un espace mémoire de taille finie et on vérifie s’il satisfait une contrainte exprimée par un automate, c’est-à-dire, dans le cadre de l’informatique fondamentale, par une machine abstraite qui traite l’information sous forme de variables discrètes. On modifie ensuite l’espace mémoire et on regarde s’il répond toujours à cette contrainte.
Dans certains cas, par exemple si l’on veut s’assurer qu’un morceau de l’espace mémoire possède bien une certaine valeur, la durée de la manœuvre peut devenir trop importante à cause d’opérations de mise à jour. Les méthodes les plus rapides et efficaces pour y parvenir doivent donc être déterminées à l’avance.
L’article explique comment classifier exactement la complexité de ces problèmes en fonction de la nature algébrique de leurs contraintes, et prouve que sa méthode est très probablement la plus efficace possible. « Pour trouver mieux, il faudrait obtenir un algorithme pour les files de priorités en temps constant, ce que la communauté informatique conjecture comme impossible », souligne Charles Paperman.
Le cas typique où l’on rencontre des problèmes de mots dynamiques concerne les espaces mémoire à accès concurrents, où il faut vérifier que deux processus n’utilisent jamais les mêmes ressources en même temps. Cela sert également à s’assurer de l’état de la mémoire pendant l’exécution d’un programme, sans la gêner.
« En plus d’avoir réussi à mener ces recherches à terme, je suis très content d’avoir été distingué par l’ICALP car c’est la première fois que je reçois un prix, se réjouit Charles Paperman. C’est une vraie victoire pour mon domaine d’études, tout ce travail de simplification et de concision sur des algorithmes n’aurait pas été possible sans l’algèbre. Même les pairs qui ont évalué l’article ont été surpris que tout fonctionne aussi bien ! »
Les trois co-auteurs réfléchissent à présent à étendre ces travaux aux segments de mémoire non contigus, où l’on utilise des pointeurs pour passer d’un espace mémoire à l’autre. Cette structure se retrouve notamment dans les grandes bases de données, habituellement présentées sous forme arborescente. Cela aiderait par exemple à améliorer des algorithmes d’indexation, pour rendre les bases de données plus efficaces.