EATCS-IPEC Nerode Prize 2022The 2022 EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics is awarded to the following papers by Bruno Courcelle:
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. |
