Joseph Newton Pew, Jr. Professor
of Engineering kozen@cs.cornell.edu 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 algorithms for efficient code certification and the application of Kleene algebra with tests to the verification of compiler optimizations.
Class of 1960 Scholar, Williams College.
Member: Undergraduate Admissions Committee, College of Engineering; University Arbitration Panel. Faculty Advisor: Cornell Men’s Rugby Football Club; Johnson Graduate School of Management Rugby Football Club; Cornell Women’s Rugby Football Club.
Program Committee Member: Foundations of Software Science and Computation Structure; Mathematical Foundations of Computer Science. Editorial Board Member: Journal of Relational Methods in Computer Science; Journal of Algorithms (special issue). Supervisory Board: Centre for Basic Research in Computer Science (BRICS), Aarhus University; Goedel Prize Committee.
Parikh’s Theorem in Commutative Kleene Algebra. FLOC ’99, Trento, Italy, July 1999. On Hoare Logic and Kleene Algebra with Tests. FLOC ’99, Trento, Italy, July 1999. On Hoare Logic, Kleene Algebra, and Types. International Congress for Logic, Methodology and Philosophy of Science, Kracow, Poland, August 1999. Language-based Security. 24th Conference on Mathematical Foundations of Computer Science, Wroclaw, Poland, September 1999. —. Department of Computer Science, Dartmouth College, Hanover, NH, March 2000. On the completeness of propositional Hoare logic. RelMiCS 5 Conference, Quebec City, Canada, January 2000. “Parikh’s theorem in commutative
Kleene algebra.” “On Hoare Logic, Kleene Algebra,
and Types.” “Language-based security.” “Certification of Compiler Optimizations
using Kleene Algebra with Tests.” In “On the completeness of propositional
Hoare logic.” “Dynamic Logic.” MIT Press, Cambridge, MA (2000) (with D. Harel and J. Tiuryn). |
||||||