Un prix à la conférence ICALP pour Charles Paperman et ses travaux sur les problèmes de mots dynamiques

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 ICALP 2021 pour l’article Dynamic membership for regular languages. Soutenue par l’EATCS, 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.

Get in Touch

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Articles Connexes

Derniers Messages