Un Best Theory Paper pour les équipes Mocqua et Carbone

7 juillet 2022

Toutes nos félicitations à Emmanuel Hainry, Romain Péchoux (Mocqua), Jean-Yves Marion (Carbone) et Bruce Kapron (Université de Victoria, Canada), qui ont obtenu le prix EATCS du meilleur article à ETAPS 2022 (European Joint Conférence on Theory and Practice of Software).

Conférence européenne majeure, ETAPS a eu lieu du 2 au 7 avril à Munich et réunissait chercheurs et industriels autour de la science des logiciels en regroupant quatre conférences : ESOP, FoSSaCS, FASE et TACAS.

Les chercheurs ont été récompensés du prix EATCS (European Association for Theoretical Computer Science) du Best Theory Paper pour leur article Complete and tractable machine-independant characterizations of second-ordre polytime.

Ces travaux d’informatique théorique portent sur la complexité implicite, c’est-à-dire la caractérisation des classes de complexité des programmes informatiques pour déterminer leur performance.

Ces recherches s’ancrent dans un partenariat entre les équipes du Loria et un chercheur de l’Université de Victoria : “Il y a cinq ans, Bruce Kapron a trouvé une nouvelle caractérisation de l’équivalent à l’ordre 2 de la classe de complexité en temps polynomial (classe P) : les Basic Feasible Functions (BFF). Nous avons ainsi démarré avec lui une collaboration fructueuse dans ce domaine“, explique Emmanuel Hainry.

Les travaux des quatre chercheurs décrivent un langage de programmation qui caractérise la classe BFF avec une procédure de typage permettant de déterminer si un programme se situe dans cette classe ou non. Ce typage étant décidable en temps polynomial, le résultat a permis à l’équipe d’obtenir la première caractérisation tractable, complète et implicite de BFF.

Bravo à nos quatre lauréats pour ce résultat qui résout un problème ouvert depuis 20 ans !