faculty.gif (20410 bytes)
choices.gif (4488 bytes)

Dexter Kozen

Joseph Newton Pew, Jr. Professor of Engineering
kozen@cs.cornell.edu
http://www.cs.cornell.edu/kozen/

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

kozen.tif (275562 bytes)
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)

  • Organizing Committee: Dagstuhl Seminar on Tree Automata, Oct. 1997

Publications

  • On the complexity of reasoning in Kleene algebra. Proc. 12th Symp. Logic in Computer Science (LICS), Los Alamitos, CA. (June 1997), 195-202.

  • Efficient algorithms for optimal video transmission. Proc. IEEE Data Compression Conf. (DCC'98), (J.A. Storer and M. Cohn ed.), (March 1998), 229-238 (with Y. Minsky and B. Smith).

  • Set constraints and logic programming. Information and Computation 141, 1 (April 1998), 2-25.