1998 - 1999 CS Annual Report                                                                  Faculty
choices.gif (4488 bytes)

Dexter Kozen

Joseph Newton Pew, Jr. Professor of Engineering

PhD Cornell, 1977

My research interests include the theory of computational complexity, especially complexity of decision problems in logic and algebra, program logic and semantics, and computational algebra. Recent work includes: new polynomial-time algorithms for type inference in type systems with subtypes and recursive types; algorithms solving systems of set constraints as used in program analysis; a unification algorithm for set constraints and a new constraint 

logic programming language based on set constraints; development of the theory of rational spaces and their relationship to set constraints; an algorithm for decomposition of algebraic functions; a new polynomial-time algorithm for resolution of singularities of plane curves; efficient algorithms for optimal transmission of encoded video data; optimality results for digital interleavers; and complexity and completeness results for Kleene algebras with tests. Recently I have begun to investigate the application of Kleene algebra and the modal mu-calculus to problems in software security. 

University Activities 
  • Undergraduate Admissions Committee, College of Engineering 
  • University Arbitration Panel 
  • Faculty Advisor: Cornell Men's Rugby
  • Football Club and Johnson Graduate School of Management Rugby
    Football Club 
Professional Activities 
  • Program Committees: IEEE Symp. Found. Computer Science (FOCS), 1996; Fixpoints in Computer Science, Sept.. 1998 
  • Supervisory Board: Centre for Basic Research in Computer Science (BRICS), Aarhus Univ.
  • Organizing Committee: IEEE Symp. Logic in Computer Science (LICS); Dagstuhl Seminar on Tree Automata, Oct 1997