Friday, January 29, 2016

EATCS Award 2016 to Dexter Kozen (Cornell University, USA)

The EATCS bestows the EATCS Award 2016 to Dexter Kozen (Cornell University, USA) for fundamental contributions across the whole spectrum of theoretical computer science

The EATCS is proud to announce that the EATCS Award Committee consisting of Fedor Fomin, Kim G. Larsen (chair) and Jean-Eric Pin has selected Dexter Kozen (Cornell University, USA; as the recipient of the EATCS Award 2016.

Dexter Kozen is a theoretical computer scientist, perhaps the  theoretical computer scientist, who has excelled across the entire spectrum of our field and crashed through the so-called Volume A/Volume B barrier. Even within these tracks he has exhibited remarkable diversity and depth. This makes him an exceptional candidate for the EATCS Award and he continues the lineage of stellar scientists who have received the EATCS Career Award so far.

Dexter Kozen is known for his many contributions to theoretical computer science. These include, among many others, the most succinct and beautiful proof imaginable of completeness for PDL, a stunning treatment of the far more challenging mu-calculus and the elegant treatment of logics of programs in the setting of Kleene algebra. He has also made fundamental contributions to complexity theory. In fact, one of the first contributions of Dexter Kozen to the scientific community was the definition of the notion of alternating Turing machine, a deep contribution to complexity theory that made it possible to connect time and space complexity. The results were viewed as so significant that they almost immediately became part of the graduate curriculum in complexity theory. Dexter’s work on alternation appeared initially in his singly-authored FOCS’76 paper, independent of the Chandra-Stockmeyer paper that was published back-to-back with it in the same volume; the two later became the famous combined, very high-cited, triply-authored J.ACM version for which the authors won an IBM Outstanding Innovation Award in 1980.

Dexter Kozen’s work on modal logic and Kleene algebra has undoubtedly had a major impact in the area of programming logics and gathered a huge number of citations as it opened up this field.

Besides complexity theory and modal logic, Dexter Kozen also produced major results on algebra, such as the complexity of the theory of real closed algebraic theories, and on computer algebra, such as the Kozen-Landau theorem.

Dexter Kozen has also been a pioneer in probabilistic semantics. Long before it became fashionable, he worked on a measure-theoretic semantics  for probabilistic programs which remains the inspiration for the intense activity in topics like probabilistic programming languages, probabilistic process algebra and logics.

Dexter Kozen has had many collaborations. His connections to Amsterdam, Aarhus and Warsaw are probably the most well-known. He has spent several one year sabbaticals in Europe with successful collaborations. He is an inspiring person  and his presence in a department is of immeasurable value for young researchers. It is worth mentioning that Dexter Kozen’s support for the contacts with Eastern European colleagues has been admirable, at a time when this was rather difficult and complex to achieve.

David Harel's two-page  laudation that appears in the volume for Dexter's 60th birthday (available at provides a wonderful introduction to Dexter Kozen as a scientist and as a colleague.

The  EATCS Award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life-long scientific career. The list of the previous recipients of the EATCS Award is available at

The EATCS Award carries a prize money of 1000 Euros and will be presented at ICALP 2016, which will take place in Rome (Italy) from the 12th till the 15th of July 2016.

No comments: