Date Posted: 6/21/2022

By Patricia Waldron

Dexter Kozen, M.S. ’76, Ph.D. ’77, the Joseph Newton Pew, Jr. Professor Of Engineering in the Cornell Ann S. Bowers College of Computing and Information Science, will receive the 2022 Alonzo Church Award for Outstanding Contributions to Logic and Computation. The award recognizes “his fundamental work on developing the theory and applications of Kleene algebra with tests, an equational system for reasoning about iterative programs.”

Kleene algebra with tests is a system of equations useful for program verification and debugging code. It combines two types of algebra, Kleene algebra and Boolean algebra, and has been applied successfully for multiple basic verification tasks. These include communication protocols, which are used when computing systems exchange messages; basic safety analysis for identifying faults in the software; source-to-source program transformation for translating between programming languages; concurrency control, which ensures that software components operating at the same time function correctly; compiler optimization, which can help reduce a program's run time, power consumption, storage size, and memory footprint; and static analysis, a debugging process that doesn’t require running the program.

Established in 2015, the Alonzo Church Award recognizes exceptional research published within the previous 25 years by an individual or group that has proven to have an enduring impact in the field of logic and computation. The ACM Special Interest Group on Logic (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Gödel Society (KGS) jointly sponsor the annual award. 

The prize will be formally presented at the Federated Logic Conference 2022 (FLOC2022), held in August in Haifa, Israel.