Presburger Award 2011

The Presburger Award Committee, consisting of Monika Henzinger, Stefano Leonardi, and Andrzej Tarlecki (chair) has unanimously decided to propose Patricia Bouyer-Decitre (Cachan) as the recipient of the EATCS Presburger Award in 2011.

Patricia Bouyer, born in 1976, has contributed fundamental results to the theory and applications of timed automata as a fundamental model of real-time systems. Patricia Bouyer has received her PhD in 2002 from the Laboratoire de Specification et Verification, CNRS & ENS de Cachan, for the thesis "Models of Algorithms for the Verification of Timed Systems", and her habilitation in 2009 from the Universite Paris 7, for the thesis "From Qualitative to Quantitative Analysis of Timed Systems". In 2007 she received CNRS Bronze medal, awarded for outstanding achievements by a junior researcher.

Her publication record includes about 70 research papers in leading international journals and conferences. In the following we list perhaps the most important of the many research achievements of her career.

Reachability analysis of timed automata. Patricia Bouyer early research led to a complete characterization of the real-time properties that can be checked by reachability analysis of timed automata in the context of test automaton; this was published in one of her excellent papers with Luca Aceto, Augusto Burgueno and Kim Larsen in TCS in 2003, but the core ideas and results came already in 1997.
One of her best known (and most cited) results concerns the exact delineation of the classes of timed automata for which the emptiness problem is decidable, which came in her joint paper with Catherine Douford, Emmanuel Fleury and Antoine Petit (TCS 2004). This was also related to the algorithmic aspects of the theory of timed automata, so important from the practical perspective. She identified a number of serious, deep and unnoticed problems in the algorithms for the reachability analysis of timed automata based on zone abstraction that were in use at the time.

Timed languages. She participated in the generalization of the fundamentals of formal language theory to take time into account. Her major contributions include extensions of the classical theorems of Kleene and Buchi, published jointly with Antoine Petit and Denis Therien (JALC 2002, I&C 2003).

Temporal logics. She contributed key ideas and results to the study of expressivity, decidability and complexity properties of various fragments and extensions of temporal logics equipped with constructs to deal with time-dependent properties, as summarized in her habilitation thesis. Not only she put forward here a number of novel ideas, she also solved a long-standing open problem concerning relative expressibility of two such standard logics TPLP and MTL, published jointly with Fabrice Chevalier and Nicolas Markey (I&C 2010). Patricia Bouyer's research had a deep impact on the field of timed automata and related topics. She combines excellent technical skills and ability to pursue deep and complex technical results with research stamina and ingenuity that together make the best among scientists. Patricia Baouyer is an extremely active member of a closely collaborating research community, where by now she plays a leading role. This is witnessed by a number of invitations to give plenary talks at workshops and conferences (a dozen or so by now), tutorials and lectures at summer schools (more than a dozen), work on program committees of international events (about 30, including 2 she chaired), participation in a number of national and international projects (more than 10), etc. Truly impressive record of internationally visible and highly appreciated activity of a top class young scientist! She is also a research leader of a group at LSV Cachan (in fact, vice-head of the lab since 2009). Two PhD degrees have been obtained under her supervision, and surely more are to come soon. Patricia Bouyer's scientific talent and skills, and her numerous scientific achievements and results she contributed to a key area of computer science make her one of the most distinguished researchers of her generation. The Presburger Award Committee wholeheartedly recommends Patricia Bouyer for the EATCS Presburger Award in 2011.

European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.