The EATCS-IPEC Nerode prize rewards outstanding papers in the field of multivariate algorithms. This year the prize is awarded to Bruno Courcelle for his 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)
This award will be presented at the ceremony at the IPEC (International Symposium on Parameterized and Exact Computation) conference in September.
These are two early papers in a sequence that developed the theory of definability of graph properties in monadic second-order logic. The full sequence of sixteen papers titled "the Monadic Second-Order Logic of Graphs" culminated in the book "Graph Structure and Monadic Second-Order Logic" (joint with Joost Engelfriet), published by Cambridge University Press in 2012. His work brings together methods from logic, graph grammars and automata to the study of algorithmic problems on graphs and similar structures. In particular, the award-winning papers establish what has come to be known as "Courcelle's Theorem": that every property of graphs definable in monadic second-order logic is decidable in polynomial time on any class of graphs of bounded tree-width. This theorem has been enormously influential in the development of the field of multivariate algorithmics and is often cited as the paradigm of an algorithmic metathoerem.