You are here

Dexter Kozen

Joseph Newton Pew, Jr. Professor in Engineering


 Computational theory, computational algebra and logic, logics and semantics of programming languages

Graduate Fields

  • Applied Mathematics
  • Computer Science
  • Mathematics


My research interests include the theory of computational complexity, especially complexity of decision problems in logic and algebra, and program logic and semantics. In the past I have worked on algorithms for type inference in programming languages; static analysis of programs; functional decomposition of polynomials and rational and algebraic functions; and algorithms for resolution of singularities. My most recent interests include the theory and applications of Kleene algebra and Kleene algebra with tests (Kleene/Boolean algebra) in programming language semantics and verification.


  • Language constructs for non-well-founded computation (with Jean-Baptiste Jeannin and Alexandra Silva), in Matthias Felleisen and Philippa Gardner, editors, 22nd European Symposium on Programming (ESOP 2013), volume 7792 of Lecture Notes in Computer Science, pages 61-80, Rome, Italy, March 2013. Springer.
  • On Moessner’s theorem (with Alexandra Silva), The American Mathematical Monthly, 120(2):131-139, February 2013.
  • Left-handed completeness (with Alexandra Silva), in Wolfram Kahl and Timothy G. Griffin, editors, Proc. Conf. Relational and Algebraic Methods in Computer Science (RAMiCS 2012), volume 7560 of Lecture Notes in Computer Science, pages 162-178, Cambridge, UK, September 2012. Springer.
  • New; in Proc. 28th Conf. Math. Found. Programming Semantics (MFPS XXVIII), Bath, England, June 2012, Elsevier Electronic Notes in Theoretical Computer Science (Ulrich Berger and Michael Mislove, eds.), 13–38.
  • Realization of coinductive types; in Proc. 27th Conf. Math. Found. Programming Semantics (MFPS XXVII), Pittsburgh, PA, May 2011, Elsevier Electronic Notes in Theoretical Computer Science (Michael Mislove and Joel Ouaknine, eds.), 148–155.