Dexter Kozen
Joseph Newton Pew, Jr. Professor of Engineering
kozen@cs.cornell.edu
Ph.D. Cornell University, 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; and complexity and completeness results for Kleene algebras with tests.
University Activities
- College of Engineering Undergraduate Admissions Committee
- University Arbitration Panel
- Faculty Advisor: Cornell Men's Rugby Football Club and Johnson Graduate School of
Management Rugby Football Club
Professional Activities
- Chair, Program Committee: IEEE Symposium on Logic in Computer Science (LICS), 1995
- Program Committee: IEEE Symposium on Foundations of Computer Science (FOCS), 1996
- Supervisory Board: Centre for Basic Research in Computer Science (BRICS), Aarhus
University Organizing Committee, IEEE Symposium on Logic in Computer Science (LICS)
Lectures
- Kleene algebras with tests and commutativity conditions. Invited Lecture. Second
International Workshop Tools and Algorithms for the Construction and Analysis of Systems
(TACAS'96), Passau, Germany, March 1996.
- Trends in computer science research: A U.S. perspective. Keynote address, 25th
anniversary celebration, Computer Science Department, Aarhus University, Aarhus, Denmark,
March 1996.
- On regularity-preserving functions. Computer Science Colloquium, Cornell University,
Ithaca, NY, December 1995.
- Efficient algorithms for optimal transmission of video data. Computer Science
Colloquium, Cornell University, Ithaca, NY, September 1995.
- Rational spaces and set constraints. Invited Lecture. Sixth International Joint
Conference on Theory and Practice of Software Development (TAPSOFT'95), Aarhus, Denmark,
May 1995.
Publications
- Kleene algebra with tests and commutativity conditions. Proceedings of the Second
International Workshop Tools and Algorithms for the Construction and Analysis of Systems
(TACAS'96), Passau, Germany. LNCS 1055, Springer-Verlag, March 1996, 14-33.
- Decidability of systems of set constraints with negative constraints. Information and
Computation 122, 1 (October 1995), 30-44 (with Alexander Aiken and Edward Wimmers).
- Rabin measures. Chicago Journal on Theoretical Computing Science 3 (September 1995)
(with Nils Klarlund).
- Rational spaces and set constraints. Proceedings 6th International Joint Conference on
Theory and Practice of Software Development (TAPSOFT'95). P.D. Mosses, M. Nielsen, and
M.I. Schwartzbach, eds. LNCS 915, Springer-Verlag, May 1995, 42-61.
- Efficient recursive subtyping. Mathematical Structures in Computer Science 5 (1995),
1-13 (with Jens Palsberg and Michael Schwartzbach) .
Return to:
1995-1996
Annual Report Home Page - Departmental Home
Page
If you have questions or comments please contact: www@cs.cornell.edu.
Last modified: 2 November 1996 by Denise Moore (denise@cs.cornell.edu).