Kozen

Dexter Kozen, the Joseph Newton Pew Jr. Professor in Engineering, is the 2016 recipient of the European Association for Theoretical Computer Science (EATSC) Award. The award acknowledges extensive contributions to theoretical computer science over a lifelong scientific career.

The committee acknowledged Kozen as “the theoretical computer scientist with significant contributions to the field, including 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.”

One of Kozen's first contributions to the scientific community was the definition of the notion of the alternating Turing machine, a complexity theory that made it possible to connect time and space complexity. “The results were viewed as so significant that they were made part of the graduate curriculum in complexity theory,” said the awarding committee. (Complexity theory deals with predicting whether a computer program can run in a reasonable amount of time, or even if a problem can be solved at all.)

Besides complexity theory and modal logic, Kozen has produced major research results on the theory of real closed algebraic theories and on computer algebra, such as the Kozen-Landau theorem. He is also a pioneer in probabilistic semantics, working on measure-theoretic semantics from probabilistic programs.

“Dexter is a rock star in so many ways,” said Greg Morrisett, dean of the Faculty of Computing and Information Science. “This award acknowledges his fundamental contributions to theoretical computer science, which he so richly deserves. We are very fortunate to have him.”

The EATSC Award will be presented at the 43rd International Colloquium on Automata, Languages and Programming in Rome July 12-15.