2020 S. Barry Cooper Prize awarded to Bruno Courcelle

Due to the pandemic in Europe and in the rest of the world, this year the Conference Computability in Europe will take place virtually in Salerno from June 29 to July 3. I wish to thank the Council and the organizers of the CiE conference “Beyond the Horizon of Computability “ for their efforts in managing to run the main events related to Association in these hard times.

The past editions of the CiE conferences have always been characterized for a special atmosphere of interdisciplinary interaction between the different souls of the Association, reflecting the different areas of Computability. This fruitful mix can be felt particularly during the Special sessions, the tutorials and the invited talks for the general audience, while parallel sessions and contributed talks focus on specific interests and expertise.

The 2020 edition of CiE in Salerno will be unique and memorable: not only it will experiment with new modalities of interaction between the attendees, but it will also be the first edition to celebrate the Barry Cooper Prize, an event that will characterize many more CiE Conferences to come. This edition is also special for me personally: after Siena (2007) and Milan (2013), the 2020 edition in Salerno, is the third taking place in one of the most beautiful areas in Italy.

On this occasion, to remember the extraordinary work by Barry in building a community of researchers and people related by their interest on the various areas of computability and motivated by his broad vision of the subject, I wish to spend few words on my personal experience with him.

I have several memories of Barry’s enthusiasm about this community and the creation of this Association. My active role in this project strengthened our friendship and gave me the opportunity to know him better. I still remember vividly his last visit to Milan, on the occasion of a Turing celebration. He gave a very inspired talk, and as usual he included a picture of me and other friends from the Association. I especially recall a meeting in London, where we discussed the Constitution of the Association and the bureaucratic hurdles of its formal registration. His dream was realized few years after, thanks to the support of the ACiE Executive Committee.

Barry was a researcher with many dreams, and the Barry Cooper Prize realizes a dream of many people actively involved in the Association: to celebrate Barry’s original vision of a multidisciplinary, inclusive and open minded community. Let me also add that this vision included a human aspect: a research community should create a bond of friendship that goes behind the collaboration or sharing of common interests.

It is my pleasure to announce that prof. Bruno Courcelle is the first awardee of the Barry Cooper Prize. My sincere thanks go to the Members of the Prize Committe Anuj Dawar, Yuri Gurevitch, Maryia Soskova and Peter Van Emde Boas who worked hard with me to select the winner among several outstanding candidates.

The 2020 S. Barry Cooper Prize is awarded to Bruno Courcelle for his work on the definability of graph properties in Monadic Second Order Logic, through a sequence of seminal papers and a book (joint with Joost Engelfriet).  This forms an outstanding example of theory building, bringing together logic, computability, graph grammars, and various notions of graph width (tree-width, clique-width and rank-width) and opening new avenues in our understanding of graph structure theory and the computability and complexity of graph algorithms.  Besides its foundational character, the work has had great impact on a number of areas of computer science, including in parameterized algorithmics, verification and other areas, and has influenced a generation of researchers in this field.  It has straddled the divide between the logical and algorithmic aspects of theoretical computer science.

The ACiE President
Paola Bonizzoni