|Press release for the EATCS Award 2016 to Dexter Kozen|
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; http://www.cs.cornell.edu/~kozen/) 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 http://www.wisdom.weizmann.ac.il/~harel/papers/Kozen.pdf) 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