Bruno Courcelle, premier récipiendaire du prix S. Barry Cooper

Le prix S. Barry Cooper récompense l'ensemble de ses travaux sur la logique du second-ordre monadique appliquée aux graphes structurés de façon arborescente et à la construction d'algorithmes, et notamment, à la synthèse de ces travaux publiée en 2012 dans un livre écrit avec Joost Engelfriet (Université de Leyde) intitulé Graph structure and monadic second-order logic. Dès son arrivée en 1979 à Bordeaux, Bruno Courcelle a collaboré avec J. Engelfriet au sujet des « grammaires d'attributs » qui ont été le point de départ de ses recherches ultérieures sur les graphes, la logique et les algorithmes.

L'un des résultats les plus cités de Bruno Courcelle dans ce domaine est que tout problème sur les graphes qui peut être exprimé dans la logique du second-ordre monadique (un formalisme très puissant, qui capture de nombreux problèmes) peut être résolu de façon efficace (en temps linéaires) sur les graphes qui ont une largeur arborescente bornée. En d'autres termes, la largueur arborescente est un paramètre qui, s'il est fixé, permet d'obtenir des algorithmes rapides sur des problèmes très variés. C'est l'un des résultats d'où est issue la théorie de la complexité paramétrée (Fixed Parameter Tractability Theory) développée par M. Fellows et R. Downey. Bruno Courcelle, en collaboration avec Irène Durand au LaBRI, travaillent actuellement en une implémentation utilisable de ce résultat, ce qui n'est pas une conséquence immédiate de la preuve initiale.

Le prix a été remis lors du colloque de l'association Computability in Europe, prévu initialement à Salerne (Italie) en juin 2020 mais remplacé par une conférence « en ligne ». Bruno Courcelle a réalisé un exposé lors de ce colloque.