Le prix EATCS-IPEC Nerode récompense les articles exceptionnels dans le domaine de l’algorithmique multivariée. Cette année le prix est décerné à Bruno Courcelle pour ses articles :
1. Bruno Courcelle. "The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs." Inf. Comput. 85(1): 12-75 (1990)
2. Bruno Courcelle. "The Monadic Second-Order Logic of Graphs III: Tree-Decompositions, Minors and Complexity Issues." RAIRO Theor. Informatics Appl. 26: 257-286 (1992)
Ce prix sera remis lors de la cérémonie à la conférence de l’IPEC (International Symposium on Parameterized and Exact Computation), en septembre prochain.
Ce sont les deux premiers articles d'une séquence qui a développé la théorie de la définissabilité des propriétés des graphes en logique monadique du second ordre. La séquence complète de seize articles intitulée "the Monadic Second-Order Logic of Graphs" a abouti au livre "Graph Structure and Monadic Second-Order Logic" (conjointement avec Joost Engelfriet), publié par
Cambridge University Press en 2012.
Ses travaux rassemblent des méthodes issues de la logique, des grammaires de graphes et des automates pour l'étude de problèmes algorithmiques sur les graphes et les structures similaires. En particulier, les articles primés établissent ce qui est désormais connu sous le nom de "théorème de Courcelle", à savoir que chaque propriété des graphes définissable en logique du second ordre monadique du second ordre est décidable en temps polynomial sur toute classe de graphes de largeur d'arbre bornée. Ce théorème a eu une influence considérable dans le développement du domaine de l'algorithmique multivariée, et est souvent cité comme le paradigme d'un métathème algorithmique.